The Center for Education and Research in Information Assurance and Security (CERIAS)

The Center for Education and Research in
Information Assurance and Security (CERIAS)

Follow-up on the CA Hack


Yesterday, I posted a long entry on the recent news about how some researchers obtained a “rogue” certificate from one of the Internet Certificate Authorities. There are some points I missed in the original post that should be noted.

  • The authors of the exploit have a very readable, interesting description of what they did and why it worked. I should have included a link to it in the original posting, but forgot to edit it in. The interested reader should definitely see that article online, include the animations.
  • There are other ways this attack can be defeated, certainly, but they are stop-gap measures. I didn’t explain them because I don’t view them as other than quick patches. However, if you are forced to continue to use MD5 and you issue certificates, then it is important to randomize the certificate serial number that is issued, and to insert a random delay interval in the validity time field. Both will introduce enough random bits so as to make this particular attack against the CA infeasible given current technology.
  • I suggested that vendors use another hash algorithm, and have SHA-1 as an example. SHA-2 would be better, as SHA-1 has been shown to have a theoretical weakness similar to MD5, although it has proven more resistant to attack to date. Use of SHA-1 could possible result in a similar problem within a few years (or, as suggested in the final part of my post, within a few weeks if a breakthrough occurs). However, use of SHA-1 would be preferable to MD5!
  • MD5 is not “broken” in a complete way. There are several properties of a message digest that are valuable, including collision resistance: that it is infeasible to end up with two inputs giving the same hash value. To the best of my knowledge, MD5 has only been shown to be susceptible to “weak collisions”—instances where the attacker can pick one or both inputs so as to produce identical hash values. The stronger form of preimage resistance, where there is an arbitrary hash output H and an attacker cannot form an input that also produces H, still holds for MD5. Thus, applications that depend on this property (including many signing applications and integrity tools) are apparently still okay.
  • One of our recent PhD grads, William Speirs, worked on defining hash functions for his PhD dissertation. His dissertation, Dynamic Cryptographic Hash Functions, is available online for those interested in seeing it.

I want to reiterate that there are more fundamental issues of trust involved than what hash function is used. The whole nature of certificates is based around how much we trust the certificate authorities that issue the certificates, and the correctness of the software that verifies those certificates then shows us the results. If an authority is careless or rogue, then the certificates may be technically valid but not match our expectations for validity. If our local software (such as a WWW browser) incorrectly validates a certificate, or presents the results incorrectly, we may trust a certificate we shouldn’t. Even such mundane issues as having one’s system at the correct time/date can be important: the authors of this particular hack demonstrated that by backdating their rogue certificate.

My continuing message to the community is to not lose sight of those things we assume. Sometimes, changes in the world around us render those assumptions invalid, and everything built on them becomes open to question. If we forget those assumptions—and our chains of trust built on them—we will continue to be surprised by the outcomes.

That is perhaps fitting to state (again) on the last day of the year. Let me observe that as human beings we sometimes take things for granted in our lives. Spend a few moments today (and frequently, thereafter) to pause and think about the things in your life that you may be taking for granted: family, friends, love, health, and the wonder of the world around you. Then as is your wont, celebrate what you have.

Best wishes for a happy, prosperous, safe—and secure—2009.

[12/31/08 Addition]: Steve Bellovin has noted that transition to the SHA-2 hash algorithm in certificates (and other uses) would not be simple or quick. He has written a paper describing the difficulties and that paper is online.



Posted by tiny voice
on Friday, January 2, 2009 at 01:16 AM

“There are other ways this attack can be defeated, certainly, but they are stop-gap measures. I didn’t explain them because I don’t view them as other than quick patches.”


You’re missing something important here:  Sure, serial number randomization can be seen as just a quick hack.  But that quick hack addresses a deep issue.


Sotirov et al discuss this problem with respect to X.509 certificates.  In their references, they point to:

Shai Halevi and Hugo Krawczyk, “Strengthening Digital Signatures via Randomized Hashing”, January, 2007.

That paper is worth reading, and discusses things in more detail.

But as a engineering heuristic:  Signing a potential attacker’s chosen text considered harmful.


Spaf replies:

Good point, but it would be more correct to say to never sign an unmodified item provide by someone else.  Signing things provided by others is necessary as part of a digital notary service.  But your basic point is a good one—provide some randomness to disrupt chosen plaintext attacks against your signing key.

Posted by Эротическое белье
on Tuesday, February 24, 2009 at 05:14 AM

I know it may sound stupid and I am sorry for that,
but what is the importance of the certificate? what is it for?
Thank you


Spaf replies:

Digital certificates are used to authenticate (verify) identity of the party holding them.  The hold a public key and identify information that is digitally signed by a key authority.  When you connect, you send a secret and the holder of the certificate signs it using the private key corresponding to the public key in the certificate.  That provides you assurance that the one responding is who he/she/it claims to be.

Posted by grang
on Thursday, March 12, 2009 at 01:07 PM

Signing things provided by others is necessary as part of a digital notary service.  smirk

Posted by Эдуард
on Sunday, March 29, 2009 at 08:57 PM


Leave a comment

Commenting is not available in this section entry.