[cabfpub] SHA1 options for payment processors

Peter Bowen pzb at amzn.com
Thu Apr 7 16:39:59 UTC 2016


I don't represent a browser, so I may not be the most useful commenter. That being said, I think it is important to understand the risk from weak hashes so proposed mitigations can be accurately evaluated.

Given that digital certificates share a lot of similarities with physical identity documents (passports, driver's licenses, and such), looking at how fake IDs get created is very useful.

There are several kinds of fake IDs that are commonly found in the US: valid IDs issued by untrusted issuers, forged IDs, and tampered IDs are three of the most common.

The first group, valid IDs from untrusted issuers is quite simple: someone comes up with a name, such as "Northampshire University", and creates IDs issued by this non-entity.  The IDs themselves are not forged or tampered, but the process used to validate the data included in the ID is frequently sub-par.  For example, it may be up to the applicant for the ID to provide a picture and details for the ID and there no validation done of the information. The only standard is "nil certificate sine lucre".  For digital certificates this is equivalent of self-signed certificates or certificates issued by an untrusted authority.

The second group, forged IDs, are documents where the creator managed to figure out how to make brand new documents that are identical to valid ones.  This is also frequently referred to as counterfeiting.  This usually happens when the security elements included in the real ID become easy to duplicate.  For example, it used to be that color pictures were considered a good security measure as were embossed seals.  However over time technology got better and it was not nearly so hard to replicate embossed seals and newer technology made getting color photos easy.  This meant that someone could create a brand new ID from scratch that was difficult to impossible to tell from an authentic ID.  For digital certificates this is the equivalent of recovering or calculating the private key of the CA.  Today this is trivial for RSA public keys that are 512-bits long and considered to be within the real of possibility for RSA public keys that are 1024-bits long.

The third group are tampered IDs.  These are documents which started as authentic documents but have been modified after issuance to contain different information.  The classic example is slicing open an ID, removing the original photograph and inserting a new one.  Related attacks are bleaching low value currency (printed on hard to duplicate paper) and using the resulting paper to print higher value notes and removing a holographic seal from one document and attaching it to a new document.  In all these cases the fraudster does not have to forge the security element, she just uses an authentic one.  For digital certificates this is a hash collision.  One gets a valid certificate or other signed document, cuts the signature off, and attaches it to their own certificate with different information.

In late 2008, a team of mathematicians and security researchers executed the third type of attack (http://www.win.tue.nl/hashclash/rogue-ca/).  They took a valid RapidSSL certificate from VeriSign (now Symantec), removed the signature, and attached it to their own certificate.  By formatting their certificate just right they were able to allow the signature to be valid for both the original certificate and the fake certificate.  You can see the details of both certificates in the diagram they posted: http://www.win.tue.nl/hashclash/rogue-ca/downloads/alignment.pdf.  Two details are very important in that diagram: 1) The serial numbers of the two certificates are different and 2) the basic constraints CA field is set differently.  The first variation means that revoking the original certificate has no impact on the fake certificate, as the fake certificate serial number will not be on the revoked list.  The second variation means that the risk does not stop at the faked certificate but cascades, as the fake certificate can be used to issue unlimited new certificates.

Given that anything in the certificate can be faked if you can move a signature from one certificate to another, we need to look at what makes it possible to have a single signature valid for multiple certificates or signed documents.  The signed document case is important as signature for an OCSP response, CRL, CSR, or completely different type of certificate (e.g. S/MIME) from the same issuing CA can be cut off and attached to a  server certificate and used with SSL/TLS.  There is currently no known way to take an arbitrary signature and create a new certificate that matches the signature. This is true for MD5, SHA1, SHA2 and SHA3 based signatures.  What is known is that one can create two certificates which both match a given signature if you have full control over both certificates.  The amount of data needed to do this varies; see http://www.mscs.dal.ca/~selinger/md5collision/ for some examples of short data sequences which both have the same signature.  

So the best solution, other than not using MD5 and SHA1, is to deny the attacker control over the certificate.  In both the MD5 Collisions Inc attack and the Flame attack (https://www.trailofbits.com/resources/flame-md5.pdf) the attacker appears to have created specially generated public keys to submit to the CA to be signed.  These keys were not random but contained sequences of bytes designed to create the desired collision.  These sequences were generated by guessing the bytes leading up to their control point (the prefix) and then ensuring that there were sufficient bytes under the attackers control to change the state of the hash to one of their choosing.  This presents two options for mitigations: make it impossible to guess the prefix and deny them the bytes to set to their chosen values.  

Making the prefix unpredictable can be done by introducing random values into the prefix, for example including them in the certificate serial number.  According to RFC 5280, serial numbers can be up to 20 octets and the top octet must not have a leading 1. This means the serial number can contain up to 159 random bits.  This is a good mitigation, but can still be made worthless if the attacker can predict the "random" values used, either due to poor random value generation by the CA or by secret knowledge of the random value generator.  This mitigation is also useless if the CA is a silent partner in the attack -- that is if the CA is willing to accept a chosen value from the attacker as the serial number.

The other option is denying the attacker sufficient bytes to change the hash state to a collusion state.  The can be done by not allowing the attacker to choose the public key in the certificate and ensuring the subject information does not contain random bytes.  There are two paths available here.  The first would be for the CA to generate the key pair and provide it to the certificate applicant, thus denying them control of the contents.  This is an option, but does not work in most cases, as legitimate certificate requesters have a reasonable request that their private key be under their control at all times.  Alternatively one could require the generation of the key using a trusted algorithm and only sign keys that were generated using such an algorithm.  This is not practical as it requires a level of audit that is unaffordable to most applicants.  The other path would be restricting the key to one that was known to exist prior to any known attack on the hash algorithm.  This works under the assumption that a specially constructed key is required to carry out the attack.  In this model a CA would only certify keys that existing prior to a date considered "safe".

To implement this last option, we can take advantage of Certificate Transparency and the internal audit systems maintained by CAs.  The requirement becomes quite simple -- the only SHA-1 certificates allowed to be issued are those that are simply time extensions of existing SHA-1 certificates.  This can be technically implemented by requiring that the Subject, Subject Public Key Information, and Subject Alternative Name of the new certificate exactly match that of a certificate issued prior to a given date.  The changes then become primarily the notAfter date.  The downside here is that customers cannot rotate their keys used with SHA-1 certificates, but this seems like a small tradeoff compared to the risk of allowing a new key.  This will make the work of an attacker massively harder; they have to not only find an existing key that works for a collision, they also must prove control of the subject and SANs already associated with that key.  Some details would need to be worked out, such as what other extensions must exist in a new SHA-1 certificate, must the CA also issue a "paired" SHA-26 certificate, when must CAs stop issuing the extension certificates, etc, but I think this is a good start.


> On Mar 6, 2016, at 12:51 PM, Dean Coclin <Dean_Coclin at symantec.com> wrote:
> I’ve been asked by the payment processor ecosystem to explore some options for assisting with the SHA-1 issue. The scope of this problem is quite large but there may be a few options for dealing with it which need vetting by this community. I’ll outline them below and would appreciate some constructive feedback:
> 1. Issue and then immediately revoke a new SHA-1 certificate. 
> >>It turns out some payment terminals don’t check for revocation and this would fix a large percentage of them for one North American company.
> 2. Issue a cert with a poison critical extension
> >>Some terminals may work with this but we won’t know until it can be tested. This requires issuing a new SHA-1 cert with this extension. Browsers would see the extension and not allow this certificate to be used. 
> 3. Issue a cert from a new, name constrained intermediate
> >> Same as #2 from a testing perspective. Browsers could blacklist this intermediate.
> It would be interesting to get feedback from not only the community at large but specifically browsers to know what to expect from a proposed ballot.
> Thanks,
> Dean
> _______________________________________________
> Public mailing list
> Public at cabforum.org <mailto:Public at cabforum.org>
> https://cabforum.org/mailman/listinfo/public <https://cabforum.org/mailman/listinfo/public>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cabforum.org/pipermail/public/attachments/20160407/842f6039/attachment-0002.html>

More information about the Public mailing list