It's no disaster, RSA cryptosystem is still strong

May 18, 2015 09:07 GMT  ·  By

Relying on an online tool of their own creation called Phuctor, two security researchers managed to break three pairs of the strongest type of RSA keys (4096-bit).

The RSA cryptosystem relies on a public key for data encryption, from which a private one (which should not be shared) is generated for decryption purposes.

The public key is composed of two values, one of them (modulus) being the product of two large prime numbers. Finding this value can lead to determining the private key corresponding to the public one.

The RSA key super-collider finds Peter Anvin's private key

The underlying principle making the RSA encryption strong is the difficulty of factoring the product of two large prime numbers.

Phuctor is the result of a collaboration between Stanislav Datskovskiy and Mircea Popescu, and represents an RSA key factorization service that determines if there is a common factor in the moduli of two different public keys.

The tool employs the euclidean algorithm to calculate the greatest common divisor of two large numbers, thus finding a shared prime number and calculating the private key.

To paint the strength of RSA encryption, Popescu said in a blog post on Sunday that one would “expect a key to be factored just a little before Elvis comes back as the Queen of England.”

One of the keys factored belongs to H. Peter Anvin (known online as “hpa”), a highly respected contributor to the open-source community, who is also a Linux kernel developer.

The creation date is September 22, 2011, a date considered relatively recent by Popescu, although there is a good chance it is no longer used by its owner.

Phuctor processes almost four million publicly known keys, and the results of successful breaking of the keys are disclosed privately to the owner, to the email address included in the key. Also, the key is removed from the service.

Things aren’t that bad, though

Reaching this result, however, relies on the risk of key collision, which can occur under certain conditions, such as generating the keys on a system with a broken entropy source or if the GPG implementation has been tampered with.

Alternatively, someone could add an invalid signature to a broken key and then upload it to the server.

Basically, there is no fault with the RSA encryption scheme, but with how the keys have been generated and manipulated.

Hanno Böck, a German freelance journalist who last year analyzed the data on servers holding the public keys, believed he found a high amount of vulnerable keys. Upon closer analysis, however, he found that the instances he encountered were actually faulty keys.

He could not determine what accounted for the corruption and assumed that they could be the result of network errors, hard disk failures, or software bugs. Böck says that anyone can upload a key to such a server, without any verification being carried out.

“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,” the journalist wrote on Sunday.

He also added that importing a corrupted key into a local installation of GnuPG cannot be done, as the attempt would be rejected because signature validation would not pass.

Number of key submissions and amount of broken moduli
Number of key submissions and amount of broken moduli

Photo Gallery (2 Images)

Phuctor, RSA key super-collider
Number of key submissions and amount of broken moduli
Open gallery