Regardless of that, the authors of the MD5 paper are correct: trust
anchors signed with MD5 are highly questionable as of today (well,
actually, since they published their last paper). Hopefully, the
maintainers of the popular trust anchor repositories (Microsoft,
Mozilla, etc.) will yank out the trust anchors signed with MD5 (and
MD2!) as soon as possible.
This is a different claim than "CAs should stop issuing certs with
MD5 signatures", which is what I as an amateur take away from a
quick scan of the material. Obviously MD5 is suspect in various
ways, but does this new work lead to the conclusion that MD5-signed
roots are untrustworthy today?
We recommended a migration (walk, don't run) away from MD2, MD4, and
SHA-1 toward SHA-256 a few years ago. MD2 and MD4 generate 128 bit
hash values; even without the attacks, these are getting to be too
small. SHA-1 has been shown to be weaker than its design goal, and
the 160 bit hash value will be getting too short in a couple of
years. We recommended SHA-256 while fully recognizing that NIST was
starting a hash competition, and that we might recommend the winner
of that competition as the successor to SHA-256.
I still strongly encourage the migration to SHA-256.
The use of the random bits in the serial number are insurance against
similar problems being found in other hash functions. This insurance
will hopefully provide time to migrate to another hash function when
cryptanalysis begins to show flaws in any future hash function.
Russ