Researcher Uses 379-Year-Old Algorithm To Crack Crypto Keys Found In the Wild (arstechnica.com) 17
An anonymous reader quotes a report from Ars Technica: Cryptographic keys generated with older software now owned by technology company Rambus are weak enough to be broken instantly using commodity hardware, a researcher reported on Monday. This revelation is part of an investigation that also uncovered a handful of weak keys in the wild. The software comes from a basic version of the SafeZone Crypto Libraries, which were developed by a company called Inside Secure and acquired by Rambus as part of its 2019 acquisition of Verimatrix, a Rambus representative said. That version was deprecated prior to the acquisition and is distinct from a FIPS-certified version that the company now sells under the Rambus FIPS Security Toolkit brand.
Researcher Hanno Bock said that the vulnerable SafeZone library doesn't sufficiently randomize the two prime numbers it used to generate RSA keys. (These keys can be used to secure Web traffic, shells, and other online connections.) Instead, after the SafeZone tool selects one prime number, it chooses a prime in close proximity as the second one needed to form the key. "The problem is that both primes are too similar," Bock said in an interview. "So the difference between the two primes is really small." The SafeZone vulnerability is tracked as CVE-2022-26320. Cryptographers have long known that RSA keys that are generated with primes that are too close together can be trivially broken with Fermat's factorization method. French mathematician Pierre de Fermat first described this method in 1643. Fermat's algorithm was based on the fact that any number can be expressed as the difference between two squares. When the factors are near the root of the number, they can be calculated easily and quickly. The method isn't feasible when factors are truly random and hence far apart. The security of RSA keys depends on the difficulty of factoring a key's large composite number (usually denoted as N) to derive its two factors (usually denoted as P and Q). When P and Q are known publicly, the key they make up is broken, meaning anyone can decrypt data protected by the key or use the key to authenticate messages.
So far, Bock has identified only a handful of keys in the wild that are vulnerable to the factorization attack. Some of the keys belong to printers originally branded as Fuji Xerox and now belonging to Canon. Printer users can use the keys to generate a Certificate Signing Request. The creation date for the keys was 2020 or later. The weak Canon keys are tracked as CVE-2022-26351. Bock also found four vulnerable PGP keys, typically used to encrypt email, on SKS PGP key servers. A user ID tied to the keys implied they were created for testing, so he doesn't believe they're in active use. Bock said he believes all the keys he found were generated using software or methods not connected to the SafeZone library. If true, other software that generates keys might be easily broken using the Fermat algorithm. It's plausible also that the keys were generated manually, "possibly by people aware of this attack creating test data." The researcher found the keys by searching through billions of public keys that he either had access to, were shared with him by other researchers, or that were available through certificate transparency programs. UPDATE: The headline incorrectly stated that a "600-Year-Old Algorithm" was used. It's been changed to "379-Year-Old-Algorithm" to reflect the updated headline on Ars.
Researcher Hanno Bock said that the vulnerable SafeZone library doesn't sufficiently randomize the two prime numbers it used to generate RSA keys. (These keys can be used to secure Web traffic, shells, and other online connections.) Instead, after the SafeZone tool selects one prime number, it chooses a prime in close proximity as the second one needed to form the key. "The problem is that both primes are too similar," Bock said in an interview. "So the difference between the two primes is really small." The SafeZone vulnerability is tracked as CVE-2022-26320. Cryptographers have long known that RSA keys that are generated with primes that are too close together can be trivially broken with Fermat's factorization method. French mathematician Pierre de Fermat first described this method in 1643. Fermat's algorithm was based on the fact that any number can be expressed as the difference between two squares. When the factors are near the root of the number, they can be calculated easily and quickly. The method isn't feasible when factors are truly random and hence far apart. The security of RSA keys depends on the difficulty of factoring a key's large composite number (usually denoted as N) to derive its two factors (usually denoted as P and Q). When P and Q are known publicly, the key they make up is broken, meaning anyone can decrypt data protected by the key or use the key to authenticate messages.
So far, Bock has identified only a handful of keys in the wild that are vulnerable to the factorization attack. Some of the keys belong to printers originally branded as Fuji Xerox and now belonging to Canon. Printer users can use the keys to generate a Certificate Signing Request. The creation date for the keys was 2020 or later. The weak Canon keys are tracked as CVE-2022-26351. Bock also found four vulnerable PGP keys, typically used to encrypt email, on SKS PGP key servers. A user ID tied to the keys implied they were created for testing, so he doesn't believe they're in active use. Bock said he believes all the keys he found were generated using software or methods not connected to the SafeZone library. If true, other software that generates keys might be easily broken using the Fermat algorithm. It's plausible also that the keys were generated manually, "possibly by people aware of this attack creating test data." The researcher found the keys by searching through billions of public keys that he either had access to, were shared with him by other researchers, or that were available through certificate transparency programs. UPDATE: The headline incorrectly stated that a "600-Year-Old Algorithm" was used. It's been changed to "379-Year-Old-Algorithm" to reflect the updated headline on Ars.
Was it a Dyslexic-Aglorithm? (Score:2)
"Researcher Uses 600-Year-Old Aglorithm To Crack Crypto Keys Found In the Wild "
Re: (Score:2)
They fixed 600 to the actual number, but didn't fix Aglo... Hahaha.
Re: (Score:2)
Modular arithmetic (Score:1)
Re: (Score:1)
> Researcher Uses 600-Year-Old Aglorithm To Crack Crypto Keys Found In the Wild
I don't care the lack of accuracy, I cared that even the most significant digit was way off!
Remember, Children (Score:2)
Always mind your Ps and Qs,
cuz sqrt(N)-c ^2 / 2c
A third mistake (Score:2)
The TFS has the following which is wrong:
"Fermat's algorithm was based on the fact that any number can be expressed as the difference between two squares"
The TFA has it correct:
"Fermat's algorithm was based on the fact that any odd number can be expressed as the difference between two squares"
Re: (Score:2)
It is also on the internet, so why would you expect anything else?
Blockchain game (Score:1)
Poot (Score:2)
UPDATE: The headline incorrectly stated that a "600-Year-Old Algorithm" was used. It's been changed to "379-Year-Old-Algorithm" to reflect the updated headline on Ars.
Or roughly 347 billion Olympic-sized swimming pools.
RSA cracked with pen and paper (Score:2)
The public key was of the form 2^123 - a*2^60 + b with a very small a. I guessed the primes were either of the form 2^63 +/- x and 2^60 +/-y for small x and y, or of the form 2^62 +/- x and 2^61 +/-y. Found them with pen and paper.
It turned out they had used a table from The Art of Computer Programming and used the tenth
Re: RSA cracked with pen and paper (Score:2)
Re: RSA cracked with pen and paper (Score:2)
Re: RSA cracked with pen and paper (Score:2)
How bad is it (Score:2)
Copy-paste fail (Score:2)
How hard can it be to copy/paste "Hanno Böck" correctly, instead of turning it into "Hanno Bock" in TFS?