How to Factor a 4096-bit Certificate
The RSA cipher is the basis of today’s web security. Its strength relies on an attacker’s inability to factor a number into the underlying primes that were multiplied together to create that number.
If you were to search the web about the difficulty of factoring integers used for RSA, you run into these intricate formulas that only an intrepid mathematician could understand. You don’t even get a time estimate, but just an order of magnitude. Then you find references to the RSA challenge numbers1 and discover that many are still not factored. It’s believed that a 1024-bit number could be factorable in the near future, but when you get to a 2048-bit number, terms like “heat death of the universe” start showing up. Also, a 4096-bit number is the gold standard used by signing authorities (those who sign certificates for other entities). This can never be factored without a quantum computer (and we seem to be some time away from that event).
There have been ongoing efforts2 in collecting and analyzing web certificates. An eye-opening 1.4% of 1024-bit certificates are relatively easy to factor, since primes end up being reused between certificates. This seems to be from the random number generation used in creating the primes in the first place.
https://scans.io has a live ongoing project to collect certificates used all over the web. One entry I found had a malformed certificate. Comparing it to the officially published certificate, there is, in fact, a single bit difference in the base-64 encoding of the certificate. It turns out that this change is enough to turn a very strong product into a number that’s relatively easy to factor.
Here’s the certificate as found by scans.io in their 20131030-20150518_certs.gz file (which has the hash of a18db9687dcf975fd74b80b3fbfaf494bd92f9a0)
And here’s the official certificate as published by https://support.comodo.com/index.php?/Default/Knowledgebase/Article/View/966/108/intermediate-1-sha-2-comodo-rsa-certification-authority
Notice the difference? Even the “diff” utility doesn't make it easy:
So I’ve highlighted it here:
This is a change from 0x4f to 0x6f, a one-bit difference. That change is in the middle of the public modulus, which changes the number into:
On the surface, this seems daunting, but quickly breaks down into these primes (and the Miller-Rabin test easily confirms that these are prime):
Don’t worry. This certificate is no longer in use by that site, nor would it have actually been usable, so there is no danger in exposing these details.
How do we get a one-bit error like this? It can happen from memory corruption when a computer doesn’t use ECC memory3, or even when old hard drives are used. A humorous example of the one-bit-error issue is the registration of “micrmsoft.com”4, which changes the ‘o’ (0x6f) to an ‘m’ (0x6d), which is a one-bit difference and received many hits.
It’s a reminder that in all things dealing with encryption, the devil is always in the details, and the slightest mistake may be enough for an attacker to break in. The difference is that an attacker won’t tell you when something is broken. Although I’ve “factored” a 4096-bit certificate and can cross that off my bucket list, we are still some time away before we can declare the RSA algorithm broken.
2 “Mining Your Ps and Qs Detection of Widespread Weak Keys" (https://www.rsaconference.com/writable/presentations/file_upload/cryp-t17.pdf) by Nadia Heninger