There's a New Way to Break RSA Encryption (arstechnica.com) 48
"Signature forgery." It's a new way to break RSA keys — and it doesn't require factoring. Ars Technica reports on new research using classical computing to "reduce the current RSA security level to an unacceptably low threshold" and lower the required computing resources by orders of magnitude.
There's "a gap in current RSA-type security assumptions," according to a paper co-authored by University of California, San Diego professor Nadia Heninger, who argues that gap "gives classical cryptanalytic evidence in favor of moving away from RSA entirely during the current post-quantum transition." The practical risk is limited, but still significant. Applying the attack against the deprecated use of 1024-bit keys took a handful of months on an academic CPU cluster, significantly less than the current estimates for 1024-bit factoring that would require resources that only nations or companies with massive resources could achieve. Widely used RSA implementations are also safe. Nonetheless, the research has taken cryptographers by surprise... "If this result holds up under peer review, it would indeed be a conceptual break-through," Karsten Nohl, a cryptography expert and the head of innovation at Allurity, said in an interview. "RSA is as difficult to break as it is to factor large integers, at least so we thought. The researcher suggests that you can practically break RSA without cracking its key...."
The key forgery attack Heninger and the other researchers devised poses an immediate threat to 1024-bit RSA. Even for 2048- and 4096-bit keys, the method reduces the security of RSA to unacceptable levels. The National Security Agency, National Institute of Standards and Technology, and European Union Agency for Network and Information Security require that any cryptosystem should provide a level of no less than 128 or more bits, meaning the operations required must exceed 2**128. The forgery attack drops these levels to 2**65, 2**90, and 2**119 for 1024-, 2048-, and 4096-bit keys respectively. These levels may further drop because Heninger's team did all the coding by hand and used no AI or GPUs in performing the forgeries. The researcher said these tools will "almost certainly" drop the security levels further.
The attack works only against blind-signature implementations of RSA... Still, some real-world systems continue to use blind-signature, also known as textbook, RSA... The paper's authors and other researchers stress that the new attack poses little real-world threat. It does, however, drastically lower the estimated security of textbook RSA, and it does so in a way no one knew of previously... The new attack will further increase the urgency of completely moving away from the cryptosystem.
Thanks to long-time Slashdot reader phatrabt for sharing the article.
There's "a gap in current RSA-type security assumptions," according to a paper co-authored by University of California, San Diego professor Nadia Heninger, who argues that gap "gives classical cryptanalytic evidence in favor of moving away from RSA entirely during the current post-quantum transition." The practical risk is limited, but still significant. Applying the attack against the deprecated use of 1024-bit keys took a handful of months on an academic CPU cluster, significantly less than the current estimates for 1024-bit factoring that would require resources that only nations or companies with massive resources could achieve. Widely used RSA implementations are also safe. Nonetheless, the research has taken cryptographers by surprise... "If this result holds up under peer review, it would indeed be a conceptual break-through," Karsten Nohl, a cryptography expert and the head of innovation at Allurity, said in an interview. "RSA is as difficult to break as it is to factor large integers, at least so we thought. The researcher suggests that you can practically break RSA without cracking its key...."
The key forgery attack Heninger and the other researchers devised poses an immediate threat to 1024-bit RSA. Even for 2048- and 4096-bit keys, the method reduces the security of RSA to unacceptable levels. The National Security Agency, National Institute of Standards and Technology, and European Union Agency for Network and Information Security require that any cryptosystem should provide a level of no less than 128 or more bits, meaning the operations required must exceed 2**128. The forgery attack drops these levels to 2**65, 2**90, and 2**119 for 1024-, 2048-, and 4096-bit keys respectively. These levels may further drop because Heninger's team did all the coding by hand and used no AI or GPUs in performing the forgeries. The researcher said these tools will "almost certainly" drop the security levels further.
The attack works only against blind-signature implementations of RSA... Still, some real-world systems continue to use blind-signature, also known as textbook, RSA... The paper's authors and other researchers stress that the new attack poses little real-world threat. It does, however, drastically lower the estimated security of textbook RSA, and it does so in a way no one knew of previously... The new attack will further increase the urgency of completely moving away from the cryptosystem.
Thanks to long-time Slashdot reader phatrabt for sharing the article.
Wat (Score:5, Funny)
"post-quantum transition"
At this point it's impossible to tell whether I'm done laughing or not.
Re: (Score:1)
Please do let us in on the joke and share your explanation of what you find so funny about this phrase.
Re: (Score:1)
This works without quantum computers and you don't even have to actually crack the key to implement it. This suggests that not the key but the implementation is flawed. So we fail fundamental logic tests. So, we are running downhill into the future with no idea what we are doing.
okkkkkkay (Score:1)
Shor's algorithm theoretically breaks RSA. Grover's algorithm theoretically breaks AES. Both of these are quantum algorithms, hence, RSA and AES are being deprecated in this "transition" to a "post quantum" world. The fact that this RSA weakness is not based on quantum computation is irrelevant -- it is just one more reason to move to the post-quantum world as quickly as possible.
As the author of the original article said, it "gives classical cryptanalytic evidence in favor of moving away from RSA entirely
Re:okkkkkkay (Score:5, Informative)
Re: (Score:2)
The fact that this RSA weakness is not based on quantum computation is irrelevant
It's extremely relevant. An actual computer that we can build today can exploit the new RSA weakness. We have no computers today that can run Shor or Grover and the timeline for one that can on a useful scale is somewhere between years and never.
Re: (Score:3)
Guess we forgot how funny it was that we suddenly went into a "current post quantum transition while somehow forgetting how we really got out of the pre-quantum phase.
For security, some people prepare in advance of threats instead of reacting to them when they arrive. 1024 bit RSA was implemented around 1999 as the standard. It was recommended around 2010 that 2048 bit replace it. 1024 bit had not been factored yet but 768 bit had been. The current threat to cryptographic systems right now is quantum computing. Moving to more secure algorithms before they are all cracked seems like the prudent thing to do.
Re: (Score:2)
Moving from 1024 to 2048 when 768 is broken is one thing. But so far, quantum computers have only managed 6 bits and had to cheat a bit to do it. It took longer than a child with pencil and paper would take. The new improved quantum computers that were going to do better than that some 6 years ago just kinda didn't happen. We'll get 'em next year?
Re: (Score:2)
Re: (Score:2)
Also how we got to post-quantum when quantum computers have yet to factor anything faster than a 6th grader with pencil and paper.
Re:Wat (Score:4, Interesting)
Well, to me it's funny to hitch this finding to post quantum as it is a totally orthogonal concern.
Along with saying RSA is *totally* useless because a rather niche application of it has an evident weakness, that is not claimed to be more generally applicable.
They may have an interesting and important finding, but are stirring up a bigger mess than is warranted by implying a broader impact to anything using RSA.
If you weren't considering migration from RSA an urgent issue before, this changes nothing.
Re: (Score:2)
He is old, he is not keeping track on what is going on in the word.
Every majour company is working on transition to quantum decryption save algorithms.
Just go to a random software conference and there will be plenty of talks about that.
Re: (Score:2)
He is old, he is not keeping track on what is going on in the word.
I'm keeping more track as I age, not less. Perhaps your capabilities have diminished further than mine? I was pretty young when I signed up, it would be surprising if you were younger than I am.
Every majour company is working on transition to quantum decryption save algorithms.
Every competent major company has done it already, but they didn't do it because quantum computing was here, they did it because it might come someday and they wanted cryptosystems which were proof against the potential vulnerability.
Just go to a random software conference and there will be plenty of talks about that.
Yes, from people selling shit to suckers. But since there are no practical quantum c
Time to cascade algorithms... (Score:2)
I'm beginning to think we need to do like VeraCrypt does as an option. Three algorithms. One optimized against QC, and two proven, solid ones that are somewhat resistant to that. Yes, it means three times the CPU to validate/sign the same stuff, but it protects us against catastrophic algorithm failure where one discover might reduce a keyspace to something trivial.
Downside of doing this is that some dedicated cryptographic processors have their die designed around the mathematical functions of that spec
Multi algorithm leads to multi core ? (Score:1)
Yes, it means three times the CPU to validate/sign the same stuff ...
That's OK, most will have 3x or more the number of CPU cores than when VeraCrypt first came out. :-)
Downside of doing this is that some dedicated cryptographic processors have their die designed around the mathematical functions of that specific algorithm, and it can get expensive to design for multiples.
If we are talking dedicated crypto processors, we could have different cores with different algorithms? It's already common to have different types of cores in a single CPU, high performance and power efficiency for example.
Re: (Score:2)
Re: (Score:2)
So its Schrodinger's laugh?
Re: (Score:2)
Re: (Score:2)
You're going to have to at least buy me dinner and sweet talk me first. Or won't you?
Re: (Score:2)
Haven't we all moved to Ed25519 years ago, though?
Re: (Score:2)
Haven't we all moved to Ed25519 years ago, though?
On my servers, I require three separate ssh keys to log in: AuthenticationMethods publickey,publickey,publickey. Logging in with passwords is not permitted over ssh, but that's not a big deal since any account with a password is blocked from logging in via ssh. If the account has a password, it is intended for logging in at the console only. They also permit S/KEY from the console. Also for the RSA key, at least 4096 bits is required: RequiredRSAsize 4096
Re: Wat (Score:2)
post quantum is funny and not funny at the same time its impossible to know which one.
Re: (Score:2)
You are both done laughing and not done laughing.
OK... (Score:5, Interesting)
I don't really care enough about RSA to read deeply into the paper, but it seems to exploit a service that will sign billions of your messages with the secret key that you are trying to crack... which I seem to recall was known to be a potential problem for RSA thirty years ago (so don't do that).
Re: OK... (Score:5, Interesting)
Re:OK... (Score:5, Informative)
Re: (Score:2)
You are refering to Bleichenbacher's attacks. This new one is closest to his 2006 attack which also lead to forgeries on a way of signing with RSA keys. [wikipedia.org]
The new attack is on a different (more basic) way of signing with RSA. So not the same attack and not on the same scheme.
As to who uses it, not too many people, but not nobody.. E.g. Privacy Pass uses the more basic way of signing. They are vulnerable.
The attack needs a lot of valid signatures before it can create a forgery. About as many signatures as Cloud
Not new, but ... (Score:5, Funny)
It's a new way to break RSA keys — and it doesn't require factoring.
Obviously [xkcd.com] ... :-)
Re: (Score:3)
Re: (Score:2)
sigh (Score:1)
> These levels may further drop because Heninger's team did all the coding by hand and used no AI or GPUs in performing the forgeries.
Using a GPU doesn't change the number of bits of useful encryption you have. Whoever wrote this has no understanding of what they're talking about.
Re: (Score:2)
> Dan Goodin
> Senior Security Editor
Lulz @ ars. Hard to get good help these days, I guess.
Re: (Score:1)
> These levels may further drop because Heninger's team did all the coding by hand and used no AI or GPUs in performing the forgeries.
Using a GPU doesn't change the number of bits of useful encryption you have. Whoever wrote this has no understanding of what they're talking about.
But i am worried that it will affect where in I/O a privileged application can even attempt it.
Re:sigh (Score:4, Informative)
Using a GPU versus a CPU (as was done here) increases how quickly you can churn through those remaining possible permutations (I read the actual paper.)
What was done on an academic CPU cluster could probably be just as easily performed on a well-tuned bitcoin rig at far far faster speed.
Let me get this straight (Score:3)
There is no practical exploit even if the method were applicable which it is not.
Hermes 2 Malware (Score:2)
2048-bit RSA that protects an AES-256 key that actually does the encryption - those of you that ever had a ransomware hit you from a cock.li address might have hope of recovering your stuff, yet!
Overblown... (Score:2)
The new attack will further increase the urgency of completely moving away from the cryptosystem.
Depends on what they mean by "the" cryptosystem. If they mean use of RSA in general, then not really, it narrowly only applies to a specific application of RSA allowing an authority to sign something without actually seeing the something, which almost never is done. It sounds like it does not speak to RSA more broadly.
Down to 80% tries (Score:2)
If you do the numbers, you see that with the new method you'd need about 80% as many attempts as before. That's still much.
Is that good? (Score:2)
Can I now recover my lost password for my Bitcoin wallet?
Does not break RSA signature as it SHOULD be used (Score:2)
This attack requires the combination of two things
1) the attacker is, at some point, in position to obtain RSA signature or decryption at will using the key under attack
2) and during this phase it is not enforced the use of a padding scheme, like RSASSA-PKCS1-v1_5, RSASSA-PSS, ISO/IEC 9796-2, RSAES-PKCS1-v1_5, RSAES-OAEP
Assuming this, the attack allows the adversary to obtain the private key.
The main case I see this is meaningful is if an adversary gains temporary and direct access to a signing or decrypti
Re: (Score:2)
uh, forget everything I wrote after "the attack allows". The attack does not allow key extraction. It allows to obtain a signature that was not obtained thru the oracle, in a new way.