Should I customize my Root CA's thumbprint/fingerprint? (SHA1 or MD5)

Question

My goal is to make a certificate's thumbprint "easier" to verify, and not reduce security in doing so.

Given that the RSA-based Bitcoin technology has a concept called a "Vanity address" where the random keys are regenerated over and over again until the hash has user-defined leading bits (the content and length of bits are arbitrary), and it doesn't reduce security, I think it's possible to apply this concept to a CA and its Thumbprint/Fingerprint and make manual validation easier.

Of course the computational power needed to customise the leading bits of this hash gets longer (exponentially longer??) for each bit we want to customize, does this activity reduce security in any way?

Question

• Would this increase security for non-trusted root certificates that need manual verification? What about other certificate types?

• Since SHA1 is secure against second preimage attacks, is there any risk in having a CA continually regenerate keys so that the above thumbprint would read 01:23:45:67:89:01:23:45:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx (variable number of bits set, fewer unique bits to verify)

• If this is a good idea, how many bits should be set for a root CA with a long expiration, versus a intermediate, vs a user or web server CA with a consecutively shorter expiration? (in year 2013)

• What server software would support this customization, or scripting of this regeneration until the criteria is set?

• What value is appropriate to make validation easier? Setting to all zeros may make it harder to verify, and since people think in Base10 sequential numbering for humans may be easy 01:02:03:04:05:06:07:08:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx

Answer 1

Forcing "vanity bits" to assume a specific value does not diminish security (second preimage resistance is second preimage resistance) but it is expensive. Namely, to get n "vanity bits" to a specific value, you need to try (on average) 2ⁿ certificates until a match is found. Each try entails making some minute variation in the certificate contents (e.g. in the Subject Key Identifier extension, which contains opaque bytes), then signing the certificate, then hashing it. The signature part cannot be avoided (but see below), because the thumbprint is computed over it as well.

This signing operation will be the most expensive part, by far. You can hope, realistically, for two thousand tries per second or so (with a few PC, depending on key type and size). This means that it will take a fortnight of computation to get 30 "vanity bits", and each additional bit doubles the cost. You will not get eight bytes; at most four. The benefits are thus slight: a SHA-1 hash is 20 bytes, so that's at most 20% of the effort which is saved.

Also, even if set to a specific value, these bits must still be checked.

---

The process can be substantially improved by making the certificate not self-signed. Since a "self-issued" certificate is trusted a priori (i.e. by magic, not by being issued by an über-CA), there is no real point in verifying the self-signature. So that signature needs not be actually correct; it just needs, for decoding purposes, to be a sequence of bytes of roughly the right size.

Thus, you can create your "trial certificates" by simply altering the last bytes of the signature. Since the signature field comes last, this process can become as fast as one elementary hash invocation per try. Throw in a GPU and some programming, and you could try billions per second.

One billion looks great from afar, but that's really only 30 bits. With a good GPU cluster and some patience, you can hope for, say, 52 vanity bits or so. This translates to 13 hexadecimal characters out of the 40 of a SHA-1 hash. In my opinion, this is still not worth the effort, but hey, that's your CPU.

On the technical part, if you want to do that, I suggest implementing your own SHA-1-on-GPU. You will need to become proficient in GPU programming anyway, even if you try to reuse an existing implementation; and the SHA-1 part itself is not hard.

Answer 2

This is comparable to ssh's VisualHostKey option for displaying graphical representations of certificate fingerprints.

Would this increase security for non-trusted root certificates that need manual verification?

There is a risk of creating a false sense of security. If your browser / ssh client / etc pops up saying "Danger danger, untrusted certificate!" but then your only confirmation is to check the first few bytes, rather than the whole fingerprint, you are making your attacker's job a lot easier. All they have to do is generate a self signed cert that starts with those bits.

On the other hand, if the attacker doesn't notice your scheme then you can easily see that it is not your cert.

For a client that displays the fingerprint this is very similar to the situation with VisualHostKeys, but it's easier for an attacker to generate a compliant fake cert.

So: against an attacker who notices this it is going to hurt you more than them; against an attacker who doesn't notice, it's helpful for you.

What about [certificates that chain back to a trusted root]?

If your client connects with no further user intervention when the cert is validated (e.g. a web browser), I'd say it's not useful. The only way you could tell if you were being MITM'ed would be if you went to look at the certificate info after you'd connected. At this point the attacker already has your secure session cookie, but the odds are you won't carry out this check.

Furthermore, an attacker who has gone to the lengths to get a validly signed cert for your address is highly likely to have looked at the original cert in detail, noticed the scheme and copied it.