[cryptography] Math corrections [was: Let's go back to the beginning on this]

Arshad Noor arshad.noor at strongauth.com
Sat Sep 17 23:54:05 EDT 2011


Note: I've had to paraphrase some of the content from the archives,
so please excuse me if this does not appear in the context of the
original thread.
----

I remember enough of my Advanced Statistics from school to know that
the following line of reasoning is fallacious, and can leads to
erroneous conclusions:

<ParaphrasedText>

On 09/15/2011 12:15 PM, Ian G wrote:
 >>
 >> Trust in a CA might be more like 99%.
 >
 > Now, if we have a 1% untrustworthy rating for a CA, what happens when
 > we have 100 CAs?
 >
 > Well, untrust is additive (at least). We require to trust all the
 > CAs. So we have a 100% untrustworthy rating for any system of 100 CAs
 > or more.

On Thu, Sep 15, 2011 at 7:16 PM, Marsh Ray <marsh at extendedsubset.com> 
writes:

 > The CAs can each fail on you independently. Each one is a potential
 > weakest link in the chain that the Relying Party's security hangs
 > from. So their reliability statistics multiply:
 >
 > one CA:   0.99      = 99% reliability
 > two CAs:  0.99*0.99 = 98% reliability
 > 100 CAs:  0.99**100 = 37% reliability

 > I don't know many people who would consider a critical system that is
 > only 37% reliable to be meaningfully better than "100% untrustworthy"
 > though.

</ParaphrasedText>

When you say a widget is 99% reliable, this is another way of saying
that there is a 0.01 probability of the widget failing.

If you have a 100 widgets and you use them individually, then the
probability does not change - there is still a 0.01 probability of
any given widget failing.  It is not, as IanG writes, additive so
that if you have 100+ widgets, they will all fail.  (Bear with me,
I'm getting to the CA's).

When you use two widgets combined together, the probability of *either*
of the two widgets failing is *still* 0.01.  However, the probability
of *both* widgets failing - i.e. its conditional probability - is 0.01
of a certain event (which already had a 0.01 probability).  This means
it has a probability of 0.01 * 0.01 failure rate, which equates to
0.0001, a 1 in 10,000 occurrence (not a 2% failure rate as Marsh Ray
writes).

What does all this have to do with trust in CAs?

When you establish a session with a given web-server, you're trusting
ONE issuer of the SSL certificate.  If we assume that one in 100 CA's
in your browser is incompetent and has been compromised, then the
probability of connecting to a web-site whose SSL cert was issued by
the compromised CA is 0.01.

If the Incompetent-CA's certificate was issued by some self-signed
Root CA, and if we assume the same probabilities apply to the Root CA,
then the conditional probabilities of the cert-chain being compromised
at both levels is, at best 0.0001 and at worst, 0.01.  (If there were
three CA's in the chain, then the conditional probabilities are, at
best 0.000001 - one in a million that all three CAs are compromised in
the chain - and at worst, 0.01).

When one connects to a web-site, one does not trust all 500 CA's in
one's browser simultaneously; one only trusts the CA's in that specific
cert-chain.  The probability of any specific CA from your trust-store
being compromised does not change just because the number of CA's in the 
trust-store increase (unless the rate of failure incidents across
all CA's do go up).

For the Dutch people, the probabilities were, unfortunately, skewed
by their own government restrictions on which CA's could be used. If
DigiNotar was the only approved CA, then they changed the original
(assumed) probability of failure from 0.01 to a 1 - a certainty.

Arshad Noor
StrongAuth, Inc.



More information about the cryptography mailing list