Two security researchers break RSA 4096 bit keys with 'Phuctor'

Researchers break into the final realm of Cryptographic keys; should we be afraid? Experts say RSA encryption is still safe

Two security researchers have supposedly broken into three pairs of one of the strongest RSA 4096 bit keys by using their online tool known as “Phuctor.” How far is this true? Well, Hanno Böck confirms this news is not true and further proves that the RSA cryptosystem has not been broken yet.

RSA is a public key cryptosystem which is majorly used when one needs to ensure security during the transmission of potential data. This method of transmission of storing data and sending it in a particular format to specific person is known as cryptography. Generally, a cryptosystem would comprise of three algorithms: one for Key generation, second for encryption and third for decryption.

The security of RSA cryptosystem depends on a public key which is used for data encryption and from this a private key is generated which is used for data decryption. The private key is very important and should be kept secret.

The public key is further comprised of two values, one of this is the modulus and it is made up of two large prime numbers which is further responsible for the security of the RSA bit keys. The public and private keys are interconnected, hence if an attacker succeeds in finding the value of public key they can use mathematical factorization method to determine the corresponding private key and thus break the RSA cryptosystem.

Factoring the two large prime numbers involved in the public key is very difficult hence RSA encryption is considered to be a very strong cryptosystem.

On Sunday; however two security researchers Stanislav Datskovskiy and Mircea Popescu, surprisingly were able to factor one of the keys that belonged to H. Peter Anvin also known as ‘hpa’. Anvin is a Linux kernel developer and he is well known for his contribution to the open source community.

The two security researchers, Datskovskiy and Popescu have created their own online tool known as “Phuctor: The RSA Super Collider” which is used to check if there is any common factor in the moduli of two different public keys.

The Phuctor tool, basically calculates the greatest common divisor (GCD) of two large numbers by using the euclidean algorithm method. With the GCD it is able to find the shared prime number and in turn it can calculate the private key.

As per its creators, Phuctor is able to process almost four million publicly known keys and if the tool is able to break any of the keys then this is informed privately to the owner by sending an email to the address that has been included in the key, furthermore the key is also removed from service.

In his Sunday’s blog post, Popescu mentioned: “expect a key to be factored just a little before Elvis comes back as the Queen of England.”

As per the security researchers, Anvin’s private key must have been created recently and to be very specific they have mentioned the creation date as September 22, 2011; however they feel that most probably the key is no longer being used by its creator, Anvin.

In response to Popescu’s blog, Hanno Böck, a German freelance journalist updated the Hacker news stating that the news regarding RSA key being broken is incorrect. However, he felt that he needs to address this matter with a detailed explanation and hence wrote his blog post on Sunday.

In his blog post, Böck mentioned that just previous year he had analyzed the data on servers that holds the public keys. Then, he had found a huge number of vulnerable keys on that server which took him by surprise. However, when he got to a much closer analysis he realized that those vulnerable keys were actually the faulty keys.

Hence, Böck believes that the RSA encryption system is much stronger and there is no fault with this system yet. He feels that the major fault is with the generation and manipulation of these public keys.

Böck, was not able to determine the exact reason for this corruption and just assumed that the faulty keys could be due to network errors, hard disk failures or software bugs.

He feels that the faulty keys could be a result of some one just uploading a key to the server without any proper verification or another possibility could be that someone could have added an invalid signature to a broken key and uploaded it to the server.

In his blog post, Böck mentioned: “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.”

In addition, Böck feels that one cannot import a corrupt key into the local installation of GnuPG because logically as the key would not pass the signature validation it would be rejected by the server.

As per Böck the actual factoring of RSA 4096 bit key can occur only under certain conditions; one if the keys have been generated with some broken entropy source and other condition when GPG implementation has been tampered.

Hence, it can be concluded that the RSA cryptosystem is strong and has not been broken yet!