The following is a long ramble on how to make PKIX certificates more resistant to the recently-announced attacks on hash collisions. If that lead sentence does not interest you, I can assure you the rest of this posting will not either.

Some of what I say below may be wrong and/or incomplete. I fully intend to update this entry over time. Feel free to write me if you find something that needs to be changed.

Potential collision-reduction attacks on PKIX certificates

Some parts of the cryptography community have started to think about what it might mean if someone devises an effective collision attack on PKIX certificates where you can have two certificates with different identities that have the same hash value. In RFC 4270, which I blogged about the other day, Bruce Schneier and I describe a nice construction by Arjen Lenstra and Benne de Weger which allows an attacker to create two certificates that have the same hash; the certificates have the same identity but different public keys, starting with a Wang-style collision reduction. Lenstra and de Weger call this a "construction" instead of an "attack" because no one has come up with a believable attack scenario for it.

Many folks have told me that they are worried that this construction might be able to be extended to allow two certificates with different identities (and, of course, the same public key) to have the same hash value. This would clearly be a valuable, and therefore devastating, attack: the attacker could fool a CA into issuing a certificate for a "good" identity, and that certificate could be used with a "bad" identity as well.

At this point, I am skeptical that such an attack can be created because of the internal structure of PKIX certificates. The logical way to extend the construction is to create a pair of identities that are 1024 bits long that have the same hash. However, I believe this is inherently going to be essentially impossible because the chance that the two identities are valid for PKIX is vanishingly small. For example, if the identities are ASN.1 type "teletexString" or "printableString", then the high bit of every octet must be 0; the chance that that will be true for all 128 octets is 2^128, which is outside the range of feasibility. For "utf8String", the chance is even lower that the random octets will be a valid UTF-8 string. Of course, there is no chance that a randomly-generated string, when shown to the user, would be recognizable.

Having said that, there may be ways for an attacker to use a Wang-style collision reduction to create certificates with different identities that I cannot yet imagine. Thus, it is prudent to think about how to defend against such attacks.

Three ways to prevent the attack

So far, there have been three proposals of how to prevent such attacks, should they ever become feasible. The three have different strengths and weaknesses. Because the strengths and weaknesses are not parallel, it is impossible to pick which proposal is "best". Hopefully, enough discussion will happen on the three proposals that, if an attack can be devised, the PKIX community will have already picked a direction in which to move.

The three can be summarized as:

• Add unpredictability to the certificate serial number
• Use a stronger hash function in the signature
• Allow for a parallel signature with with a stronger hash function

Note: I may have devised the last one myself, or at least I have not read any concrete proposals for how to do it. That is not to say I invented it; in fact, it is somewhat obvious given that it has been possible to have parallel signatures in S/MIME for many years. I easily could have missed the conversation or presentation where someone suggested the same thing. (If you did, please let me know so I can reference it here!)

Adding lots of unpredictability to the serial number ruins the attack because the attacker doesn't know the initialization vector to use for creating the two values. Using a stronger hash makes the attack that much harder; even if the better hash function doesn't eliminate the attack, it hopefully forces the attacker to need to perform too many attempts to be feasible. Allowing a parallel signature is similar to using a stronger hash function, but may make the transition to the new hash function easier.

Adding unpredictability to the serial number

This is quite easy for a CA, and it causes no interoperability issues. In fact, parts of VeriSign has been doing it for years. Some CAs issue certificates with serial numbers that are monotonically increasing, and therefore predictable to an attacker. Others make the serial number a very large, unpredictable integer. The only requirements in PKIX are that it be a positive integer and that no two certificates from a single CA have the same serial number.

Every bit of unpredictability makes the attacker's job twice as hard. Thus, making a serial number be 64 bits long, all of which are unpredictable, would wipe out any advantage an attacker gains from a Wang-style attack.

CAs that do not use this technique can easily start doing so by changing their serial numbers to a MAC with a long output; the key would be a large secret value and the message would be whatever serial number they were going to issue, or vice versa. The CA should change the secret value as often as the issuing process has enough entropy available.

The downside of this solution is that a party relying on the certificate cannot verify that the CA used it correctly. The "large secret number" could be a predictable number like 0xAB0FF0DEADFACE, entered by a bored programmer and never changed. The CA could have gotten "creative" and XORed two values together in a way that makes the serial number predictable to a determined attacker but not to a typical relying party. Thus, the proposed solution works but cannot be proven to work in CA implementations.

On the other hand, relying parties cannot currently prove that the CA is not making some other bad mistake, such as having the CA's private key readable by attackers or not fully verifying the identities in the certificates they issue. It is probably easier to correctly implement "MAC some inputs with a large unpredictable number" than either of those tasks.

Using a stronger hash function

Variations on the "just use SHA-256" chant are getting louder in the cryptographic community. The fact that SHA-256's output size and the block size are both bigger than SHA-1 could make SHA-256 safe from practical Wang-style attacks for a very long time. No one has found any noticeable holes in SHA-256 yet.

However, changing algorithms used by PKIX CAs is very different than changing them in, say, S/MIME or IPsec. There is a massive chicken-and-egg problem with CAs using new hash functions. No CA wants to issue certificates that cannot be used by nearly everyone. Individuals certainly don't want to buy a certificate and find out that most of their users get errors when you present it. In fact, they don't want to buy a certificate where even 5% of their potential users get errors.

So, when do CAs start issuing certificates using SHA-256? When has 95% (or, more likely, 99%) of the web browsers been updated to use SHA-256? What if CAs start to move to SHA-256 and then the cryptographic community decides that a different hash function would actually be better? In the "it is more secure" vs. "some users get errors" debate, the latter probably wins every time.

Note that SHA-256 is not the only possible alternative here. There is good evidence that randomized hash functions (standard hash functions that add in a random value that is then exposed as part of the function's identifier) are safer than plain hash functions. These may catch on in the future. But, because the identifier for the hash function changes, these cause the same chicken-and-egg problem as any new hash function.

Allow for a parallel signature with with a stronger hash function

The way that S/MIME gets around the chicken-and-egg problem is to allow parallel signatures on signed messages. Unfortunately, the PKIX format doesn't allow that. Short of redesigning PKIX (something that many of us would love to do, while knowing that the new version would not get implemented in our lifetimes), adding an extension for a parallel signature would allow signers to start using a stronger hash functions like SHA-256 without causing backward compatibility issues.

The structure of the extension might be:

ParallelSignature ::= SEQUENCE {
    parallelID           AuthorityKeyIdentifier,
    signatureAlgorithm   AlgorithmIdentifier,
    signatureValue       BIT STRING  }

One tricky part of the design is choosing what the parallel signature would cover. A first guess might be "everything in the TBSCertificate except the ParallelSignature object itself". However, for this to be successful, you would need to know the eventual length of the ParallelSignature object. Another guess might be "everything in the TBSCertificate including the ParallelSignature object itself, but with a bogus signatureValue". The latter would probably be hard for a typical implementation to handle due to problems with marshaling the certificate contents in order to calculate the signature.

For either proposal, it is likely that the signatureValue would need to have a pre-ordained constant length. For this to work, you need to know the length of the asymmetric signing key. For example, the definition of RSA2048withSHA256 might say "the signatureValue will always be 2150 bits, with left padding of zeros if needed".

This also explains why the definition for the parallel signatures extension only allow one parallel signature in a certificate. Making the rules for including more than one parallel signature would get even more complicated as one specifies what is and is not included in each parallel signature.

I fully admit that that is a lot of complicated hand-waving, but so is a lot of the PKIX specification. If parallel signatures can be specified correctly (and I am confident they can be), they would have the huge advantage of allowing CAs to use new, stronger hash functions before most relying software can handle them, without causing errors in user programs that don't know about the new signature functions. (There are probably some programs that will object to extensions that they don't understand, but such behavior is clearly prohibited by the PKIX specification.)

The biggest downside to this proposal is explaining to users what the heck the two signatures means. We will see dialog boxes that say "The known-weak certificate signature based on SHA-1 is valid, but the parallel signature uses an algorithm I don't understand; would you like to trust this certificate?" or, worse, "The known-weak certificate signature based on SHA-1 chains correctly to a trusted anchor, but I could not find a valid chain for the signature based on the known-strong SHA-256 algorithm; would you like to trust this certificate?". The buttons at the bottom of those dialogs might as well be labeled "Um, yeah, whatever" and "No because this makes no sense and now I'm angry".

Conclusion

Sorry, I don't have one. Weighing the three choices of "simple to implement but hard for relying parties to be sure of" against "simple to implement and easy for relying parties to be sure of, but probably will never happen" against "probably reasonable to implement but certainly very difficult to explain" is incredibly difficult.

I predict that, when the PKIX community looks at this, there will either be a collective shrug of denial, or a lot of very opinionated individuals trying to explain why people who disagree with them are just wrong. If someone comes up with a fourth or fifth option that has merits, it will make the discussion all the more difficult. I would love to be wrong about this prediction.

If we are given lots of time before there is a useful Wang-style attack against PKIX, the topic of choosing a way forward will just be another rat-hole on the PKIX landscape, sharing space with the meaning of non-repudiation and the correct way to do online certificate validation. On the other hand, if a useful attack is described in the next few years, before the PKIX community has a somewhat-unified proposed solution, it will be very destabilizing for the entire notion of third-party trust in Internet protocols.