A vulnerability in the creation of RSA keys turns an algorithm from 1643 into a code cracker. The IT security researcher and journalist Hanno Böck has discovered a vulnerability in RSA keys. He describes how he can crack the encryption using an algorithm that was first described in 1643 by the mathematician Pierre de Fermat.
The algorithm is actually intended to quickly calculate prime factors of large numbers. But this only works if the prime numbers are similar in size. The problem with the vulnerability is that the algorithm used to generate the RSA keys randomly generates a prime number and looks for the next one. As a result, the 2 prime numbers are very close to each other and therefore suitable to be decrypted by the Fermat algorithm. According to Böck, the insecurely created RSA keys can be cracked in milliseconds.
.jpg){kind=link}
Canon and Fuji printers use insecure keys
These keys are traced back to an older SafeZone crypto database. It was developed by Inside Secure, which was acquired by Rambus in 2019. Böck found such easily crackable keys on the internet that were generated by Canon and Fuji printers in 2020 and 2021.
He also found 4 keys on PGP key servers. Usually, these are used to encrypt emails. Based on the user ID, however, Böck suspects that these are test keys that are not actually used. Someone may have discovered the vulnerability before him and tested it with these keys.
According to Böck, only a few devices are currently affected by the vulnerability: "Nevertheless, it shows one thing: It's worth looking for old, known vulnerabilities."
The algorithm works for two similarly large prime numbers
Of course, if the RSA keys are generated correctly, Fermat's algorithm fails. If the two prime numbers used to generate an RSA key were randomly generated, they almost always differ in the first few bits - and Fermat's algorithm only works efficiently if the two numbers are of similar size. But flawed key generation routines can generate weak keys that are vulnerable to attack.
Fermat's factorization algorithm is relatively easy to understand: If you have a large number that is the product of two prime numbers, you can define the two prime numbers as a+b and ab. The value a is the middle between the two prime numbers - since large prime numbers are odd, there is always an integer value in the middle. The value b is the distance from this number in the middle to the two prime numbers.
This results in N=(a+b)(ab), which can be converted to b^2=a^2-N using simple algebraic rules.
Now an attempt is made to guess the value a. We remember: This is the middle between the two prime numbers - and for similarly large prime numbers it is about the same size as the square root of N . The square root of N is not an integer, so it is rounded first.
An attempt is made to guess the middle between the prime numbers
The rounded square root of N thus serves as the first guess for a . Using the already mentioned formula b^2=Na^2, one can calculate whether the correct a was guessed: If b^2 is the square of an integer, a was guessed correctly. If not, the guessed value is increased by one and the process is repeated. This can be repeated any number of times, the longer, the higher the chance of factoring the number. With vulnerable keys, this usually works with very few attempts, in the end, I gave up after 100 attempts.
If you guessed a correctly, the rest is easy: you now know b^2. From this b can be calculated and from this the prime numbers p and q. If you know the two prime numbers, you can calculate the entire RSA private key.
Comments / 0