Sunday, May 17. 2015
tl;dr News about a broken 4096 bit RSA key are not true. It is just a faulty copy of a valid key.
Earlier today a blog post claiming the factoring of a 4096 bit RSA key was published and quickly made it to the top of Hacker News. The key in question was the PGP key of a well-known Linux kernel developer. I already commented on Hacker News why this is most likely wrong, but I thought I'd write up some more details. To understand what is going on I have to explain some background both on RSA and on PGP keyservers. This by itself is pretty interesting.
RSA public keys consist of two values called N and e. The N value, called the modulus, is the interesting one here. It is the product of two very large prime numbers. The security of RSA relies on the fact that these two numbers are secret. If an attacker would be able to gain knowledge of these numbers he could use them to calculate the private key. That's the reason why RSA depends on the hardness of the factoring problem. If someone can factor N he can break RSA. For all we know today factoring is hard enough to make RSA secure (at least as long as there are no large quantum computers).
Now imagine you have two RSA keys, but they have been generated with bad random numbers. They are different, but one of their primes is the same. That means we have N1=p*q1 and N2=p*q2. In this case RSA is no longer secure, because calculating the greatest common divisor (GCD) of two large numbers can be done very fast with the euclidean algorithm, therefore one can calculate the shared prime value.
It is not only possible to break RSA keys if you have two keys with one shared factors, it is also possible to take a large set of keys and find shared factors between them. In 2012 Arjen Lenstra and his team published a paper using this attack on large scale key sets and at the same time Nadia Heninger and a team at the University of Michigan independently also performed this attack. This uncovered a lot of vulnerable keys on embedded devices, but these were mostly SSH and TLS keys. Lenstra's team however also found two vulnerable PGP keys. For more background you can watch this 29C3 talk by Nadia Heninger, Dan Bernstein and Tanja Lange.
PGP keyservers have been around since quite some time and they have a property that makes them especially interesting for this kind of research: They usually never delete anything. You can add a key to a keyserver, but you cannot remove it, you can only mark it as invalid by revoking it. Therefore using the data from the keyservers gives you a large set of cryptographic keys.
Okay, so back to the news about the supposedly broken 4096 bit key: There is a service called Phuctor where you can upload a key and it'll check it against a set of known vulnerable moduli. This service identified the supposedly vulnerable key.
The key in question has the key id e99ef4b451221121 and belongs to the master key bda06085493bace4. Here is the vulnerable modulus:
c844a98e3372d67f 562bd881da8ea66c a71df16deab1541c e7d68f2243a37665 c3f07d3dd6e651cc d17a822db5794c54 ef31305699a6c77c 043ac87cafc022a3 0a2a717a4aa6b026 b0c1c818cfc16adb aae33c47b0803152 f7e424b784df2861 6d828561a41bdd66 bd220cb46cd288ce 65ccaf9682b20c62 5a84ef28c63e38e9 630daa872270fa15 80cb170bfc492b80 6c017661dab0e0c9 0a12f68a98a98271 82913ff626efddfb f8ae8f1d40da8d13 a90138686884bad1 9db776bb4812f7e3 b288b47114e486fa 2de43011e1d5d7ca 8daf474cb210ce96 2aafee552f192ca0 32ba2b51cfe18322 6eb21ced3b4b3c09 362b61f152d7c7e6 51e12651e915fc9f 67f39338d6d21f55 fb4e79f0b2be4d49 00d442d567bacf7b 6defcd5818b050a4 0db6eab9ad76a7f3 49196dcc5d15cc33 69e1181e03d3b24d a9cf120aa7403f40 0e7e4eca532eac24 49ea7fecc41979d0 35a8e4accea38e1b 9a33d733bea2f430 362bd36f68440ccc 4dc3a7f07b7a7c8f cdd02231f69ce357 4568f303d6eb2916 874d09f2d69e15e6 33c80b8ff4e9baa5 6ed3ace0f65afb43 60c372a6fd0d5629 fdb6e3d832ad3d33 d610b243ea22fe66 f21941071a83b252 201705ebc8e8f2a5 cc01112ac8e43428 50a637bb03e511b2 06599b9d4e8e1ebc eb1e820d569e31c5 0d9fccb16c41315f 652615a02603c69f e9ba03e78c64fecc 034aa783adea213b
In fact this modulus is easily factorable, because it can be divided by 3. However if you look at the master key bda06085493bace4 you'll find another subkey with this modulus:
c844a98e3372d67f 562bd881da8ea66c a71df16deab1541c e7d68f2243a37665 c3f07d3dd6e651cc d17a822db5794c54 ef31305699a6c77c 043ac87cafc022a3 0a2a717a4aa6b026 b0c1c818cfc16adb aae33c47b0803152 f7e424b784df2861 6d828561a41bdd66 bd220cb46cd288ce 65ccaf9682b20c62 5a84ef28c63e38e9 630daa872270fa15 80cb170bfc492b80 6c017661dab0e0c9 0a12f68a98a98271 82c37b8cca2eb4ac 1e889d1027bc1ed6 664f3877cd7052c6 db5567a3365cf7e2 c688b47114e486fa 2de43011e1d5d7ca 8daf474cb210ce96 2aafee552f192ca0 32ba2b51cfe18322 6eb21ced3b4b3c09 362b61f152d7c7e6 51e12651e915fc9f 67f39338d6d21f55 fb4e79f0b2be4d49 00d442d567bacf7b 6defcd5818b050a4 0db6eab9ad76a7f3 49196dcc5d15cc33 69e1181e03d3b24d a9cf120aa7403f40 0e7e4eca532eac24 49ea7fecc41979d0 35a8e4accea38e1b 9a33d733bea2f430 362bd36f68440ccc 4dc3a7f07b7a7c8f cdd02231f69ce357 4568f303d6eb2916 874d09f2d69e15e6 33c80b8ff4e9baa5 6ed3ace0f65afb43 60c372a6fd0d5629 fdb6e3d832ad3d33 d610b243ea22fe66 f21941071a83b252 201705ebc8e8f2a5 cc01112ac8e43428 50a637bb03e511b2 06599b9d4e8e1ebc eb1e820d569e31c5 0d9fccb16c41315f 652615a02603c69f e9ba03e78c64fecc 034aa783adea213b
You may notice that these look pretty similar. But they are not the same. The second one is the real subkey, the first one is just a copy of it with errors.
If you run a batch GCD analysis on the full PGP key server data you will find a number of such keys (Nadia Heninger has published code to do a batch GCD attack). I don't know how they appear on the key servers, I assume they are produced by network errors, harddisk failures or software bugs. It may also be that someone just created them in some experiment.
The important thing is: Everyone can generate a subkey to any PGP key and upload it to a key server. That's just the way the key servers work. They don't check keys in any way. However these keys should pose no threat to anyone. The only case where this could matter would be a broken implementation of the OpenPGP key protocol that does not check if subkeys really belong to a master key.
However you won't be able to easily import such a key into your local GnuPG installation. If you try to fetch this faulty sub key from a key server GnuPG will just refuse to import it. The reason is that every sub key has a signature that proves that it belongs to a certain master key. For those faulty keys this signature is obviously wrong.
Now here's my personal tie in to this story: Last year I started a project to analyze the data on the PGP key servers. And at some point I thought I had found a large number of vulnerable PGP keys – including the key in question here. In a rush I wrote a mail to all people affected. Only later I found out that something was not right and I wrote to all affected people again apologizing. Most of the keys I thought I had found were just faulty keys on the key servers.
The code I used to parse the PGP key server data is public, I also wrote a background paper and did a talk at the BsidesHN conference.
Posted by Hanno Böck in Code, Cryptography, English, Linux at 22:46 | Comments (13) | Trackbacks (4)
Related entries by tags:
Tracked: May 18, 06:10
Tracked: May 18, 07:50
Tracked: May 18, 15:10
Tracked: May 20, 09:31
Display comments as (Linear | Threaded)
Even though your own research didn't end up where you first thought it might, it still clearly paid off by providing the evidence to debunk this latest self-promoting FUD-propagation. So thanks for that; I'll be sure to direct those in a panic on freenode here instead of Mircea's blog.
So in your paper you write "It is unknown to me what the origin of the other two keys is and why they were broken in such a way." Your post seems to imply you are more certain now. What changed?
I don't really know, but I talked to Nadia Heninger about it and she mentioned that they were probably created by some email software only used in Germany. She also mentions something in a talk she gave lately:
The process for hacking a key and finding the factors of a PGP or RSA type key is really no where near as hard as is believed. I will give a few hints
(1) The sum of any two prime numbers can be defined as
Sum = Center^2 - Difference^2 where the high prime is Center + Difference and the lower prime is Center - Difference.
(2) Center can be guessed approximately as SqrRoot(Sum)+1.
(3) Validity checks can validate based on last digits of potential sums
(4) A proposed square produces
Sum - Center(guess)^2 = Difference(guess)^2. If Difference(guess) square root as integer produces a remainder then the guess is invalid.
(5) Using ending digit validation for sums most guesses can be tossed out.
(6) Factors are automatically derived as a pair by this means.
The number of factors to process is reduced by the following means
(a) the process is linear not geometric
(b) the math only uses multiplication and shift right
(c) The process reduces necessary processor time by a factor of several trillion times compared with the successive factors and such methods.
I know people may not realize this but RSA process is easily cracked using this method. Instead of taking years it takes an hour or two and is easily handed to parallel processing.
Cryptographic success with any known RSA Sum should be within reasonable times for any modest computer this way.
The problem is guys you are shooting at the wrong end of the problem. Any time math problems become geometrically more complex your solution method is wrong.
If the high prime is (Center + Difference) and the lower prime is (Center - Difference), then surely, Center² - Difference² is the product of the two prime numbers and not the sum?
The sum of your two primes, (Center + Difference) + (Center - Difference), is just 2Center.
Also, guessing Center "approximately" as SqrRoot(Sum)+1 is a very bad guess. The two factors of a 4096-bit key are likely both 2048 bits long, meaning that guess is possibly off by up to 2^2047, which is an absolutely huge space to search.
> For all we know today factoring is hard enough to make RSA secure (at least as long as there are no large quantum computers)
I find the mention of quantum computers here a bit misleading. In practice the factorisation problem (and the discrete logarithm problem which is also involved in the security of RSA) has proven that it's pretty hard, having hundreds of mathematicians working on it for decades without breaking. But it's not theoretically hard (not NP-complete) and the huge amount of work on it have given significant results (see https://en.wikipedia.org/wiki/General_number_field_sieve for instance) and that's why you need to use huge keys to get a correct security level (2048 bits is the bare minimum if you want to be safe). The work is still in progress (see Antoine Joux's latest work on the discrete logarithm problem http://eprint.iacr.org/2013/400) and I think that RSA is more likely to be abandoned due to this kind of works than by an hypothetical «large quantum computer».
My two cents.
While large quantum computers aren't the only thing that could reasonably play a role in deprecating RSA, I think it's unfair not to mention them given that we already have an algorithm ready that would work if we managed to build one. Since the physics around it is unchallenged so far, it's an engineering problem and it's rarely wise betting on the impossibility of solving an engineering problem.
I'm no mathematician or cryptographer, but all people I asked think that there is no way the results of Joux can be generalized. They only apply to a very specific variant of the discrete log problem (in finite fields of small characteristics). This is interesting research, but irrelevant for any crypto in use.
I don't know what you mean by theoretically hard. There is no way with current knowledge to produce any proovably secure public key algorithms, even if you could base them on an NP-complete problem. That's a given in today's crypto, we always have to rely on plausible assumptions. But to the best of my knowledge there is nothing that even remotely comes close to endangering RSA with reasonable keys (2048 or bigger) - except quantum computers.
You seem to be describing Fermat's method of factorisation, which is well known and RSA keys are usually chosen to be resistant to factorisation using this method.
It's not just an engineering problem - the author of one of the most popular quantum factoring algorithms presented it as a interesting find, but not necessary applicable. There are two issues with quantum factoring:
- it starts with a superposition of all the numbers of the n-bit length - we don't know how to do it, is it even possible and given we can do it how to do it efficiently
- quantum algorithm works with some probability and while it's ok for optimization problems - you get the best solution or a one really close to it, it's not that good in factoring - a bit off is as bad as 2047/2048 bits off. So while the quantum algo will give you almost perfect answer, still getting the single, correct one can take some time.
You can find my web page with links to my work as a journalist at https://hboeck.de/.
You may also find my newsletter about climate change and decarbonization technologies interesting.
Hanno on Mastodon
Show tagged entries