On 17/04/12 08:54 AM, Peter Kurrasch wrote:
> I don't have much of a problem with added randomness--one may think of it
> as extra fat that makes the whole system work better. However, since I'm
> not most familiar with the mechanics of signing/issuing certs (more
> experienced with the receiving end of certificate clutter) I feel like I'm
> still missing something.
All [0] digital signatures are first done by hashing the message
(certificate body) with a message digest like MD5, SHA1 and increasingly
SHA2.
Then, the public key signature is done by RSA (or variants) over the
hash. So each digsig is a two-phase operation.
More importantly, for this discussion, the signature can be attacked at
two points - the hash *or* the RSA operation. Double trouble! Either
one can cause chaos if weak.
The hash attack works by (a) knowing what the cert looks like up-front,
(b) crunching that to find two matching certs, and (b) asking for a
signature on hash of cert1 when it also matches cert2.
In this case, a hash like SHA1 has 80 bits [1] of strength, or a little
less coz the academic attacks have lopped a few off. We expect academic
attacks to crack through that in due course and reduce it to say 60 ...
at which point it becomes achievable to crunch the whole thing.
So, by adding in 20 bits of randomness into the packet, we make it 2^20
times harder to attack. Think of this as adding 10-20 years crunching
strength. By which time, SHA2 and SHA3 will roll out.
> For the attack you describe, I'm assuming it would be most effective with
> an end certificate (non-CA). For a root or intermediate cert I would hope
> that the authority doing the signing could detect and thus not allow the
> attack scenario...?
Oh. No, far worse. If an intermediate can be forged by the attack on
the hash, then the attacker has a valid intermediate. Which he can use
to create as many certs as he likes, hand them out willy nilly and the
CA need never know until some accident of security happens and the cert
is forwarded for manual validation.
(This is indeed what happened in the original Rabbit attack. The team
of academics used an end-entity user cert to forge an intermediate cert
against an MD5 hash. MD5 hashes are 64 bits in strength, and there was
no randomness in the cert body.)
For a root cert, it doesn't matter, because a root cert gets its value
from being in a root list. Logically it isn't signed at all, as
self-signatures are security-wise of little meaning. Practically it is
self-signed because PKI has to distro the public key somehow, and the
method available is self-signed certs.
> Is it fair to say that there are 2 varieties of attacks at play here: 1)
> tampering with a cert so you can insert your own key; and 2) fraudulently
> obtaining a valid cert...?
Many variants, yes. A recent attack in Asia was purported to be (full
disclosure still lacking) a complete creation of 9 fresh certs by
crunching new RSA signatures without any communication with the CA.
This was for 512bit RSA sigs, now thought to be weak.
Crypto is very complicated. public key crypto is even more complicated.
PKI is horrendously more complicated...
iang
> On Fri, Apr 13, 2012 at 9:03 AM, Phillip Hallam-Baker<
hal...@gmail.com>wrote:
>
>> The requirement for randomness comes from a particular attack on a
>> particular digest function.
>>
>> If the digest function is sound there is no or rather little need for
>> the randomness.
>>
>>
>> The idea of the attack was that the attacker constructs a certificate
>> request in such a way that when the certificate is issued for signed
>> data X it is also valid for signed data X' where the difference
>> between X and X' is ideally just the requisite bits to permit certs to
>> be signed.
>>
>> For the attack to work at all the attacker has to be confident that
>> they can predict X from the data sent in their CSR. The randomness has
>> to be introduced before the data that is sent by the user which
>> includes the subject name and the public key, both are chosen by the
>> user.
>>
>> [NB: Even though the modulus n is traditionally calculated from p and
>> q, this is not the only way you can do it. It is equally possible to
>> chose candidates for n and p and then work out q. This allows the MSB
>> of n to be chosen,]
>>
[0] or nearly all, certainly these ones.
[1] I'm deliberately fudging topics like birthday attacks here for
explanatory purposes.