Rob Stradling wrote on 10/05/2006 11:24:43 AM:

> Most currently valid X.509 certificates rely on the SHA-1 algorithm. 
If/when 
> SHA-1 gets sufficiently "broken", the signatures on those certificates 
will 
> become worthless.  Some experts believe that SHA-1 might get broken 
really 
> quite soon.
> X.509 allows us to stop using SHA-1 and start using SHA-256 (or SHA-384, 
or 
> SHA-512, etc) instead.  However, if we were to do this today, most 
existing 
> software (including all versions of Windows prior to Vista...which isn't 
even 
> launched yet) would not be able to verify the signatures on the 
certificates 
> at all.
> 
> I want to be able to do *all* of the following (in no particular 
order)...
>   1. Start using SHA-256/384/512/etc in X.509 certificates ASAP, so that 
the 
> latest software can take advantage of these (hopefully) more secure hash 

> algorithms.
>   2. Avoid keeping SHA-1 as a single point of failure until such 
> time as there 
> is widespread support for SHA-256/384/512/etc.
>   3. Stop having to rely on any single hash algorithm when verifying the 

> signature of an X.509 Certificate.
> 
> I hope this explains my aims more clearly.

As I understand your proposal (please correct me as necessary), if M is 
the ToBeSigned - before your new SHA256 extension - a CA with RSA private 
key (n,d) would generate a signature essentially like

S = PKCS1(SHA1(M | SHA256(M)))^d mod n

That's a clever idea if it stops the known SHA1 attacks, but has it been 
carefully scrutinized against other attacks?  In particular, is some of 
the benefit of using SHA256 lost once it has gone through the SHA1 output 
(since 256 bits has been crunched to 160 bits).  For example, birthday 
attacks on SHA256 should take about 2^128 hashes, but with your 
construction birthday attacks should take about 2^81 hashes, which is 
certainly better than the 2^63 (the current SHA1 strength), but much worse 
than 2^128 (the current SHA256 strength).  Admittedly, these are rather 
theoretically high levels of security, which the very pragmatic PKIX group 
may not be terribly concerned about, but it leads me to question whether 
your objective 2 will be fully met.

Aside: Does the PKIX group feel that the paper "Colliding X.509 
Certificates" http://eprint.iacr.org/2005/067 is of no concern (assuming 
that it can eventually be extended to SHA1)?  (I've been getting that 
impression from various comments.)  If so, why?  Some possible reasons 
are: (1) pre-existing certs (issued before collision attack) are not 
affected and are still verifiable and usable, (2) when a collision attack 
is discovered, CAs can halt issuing certs and upgrade to a better hash. In 
particular, these reasons make it seems that PKIX can afford to wait until 
the very last minute, i.e. when SHA1 is actually broken, rather than to 
upgrade to some fix like SHA256 before SHA1 is broken.  If new hashes such 
as SHA256 are ready to go, then that should be enough preparation for the 
least amount of downtime during the upgrade.  Older implementations will 
not be able to process the new certs, though.   My concern with a 
last-minute approach is that perhaps somebody will use the collision 
attacks before a CA becomes aware of it?  Is there some other good reason 
that I should not have this concern?  For example, is there something else 
about the "Colliding X.509 Certs" paper that means it will not be useful 
for a realistic attack.

Thanks,

Dan Brown
(905) 501-3857
http://www.certicom.com