A blogger with the handle "Soatok" has written about considerations in safely using RSA. His first recommendation is not to use RSA at all any more. Failing that, if you must use RSA, he has various recommendations to mitigate the problems that using RSA entails.
Every RSA keypair must be represented as all of the following:
- RSA Secret Key (sk)
- Operation (sign or decrypt)
- Mode (padding or KEM-DEM)
- Hash function (signatures, MGF1)
- Modulus size
- Public exponent
- RSA Public Key (pk)
- Operation (encrypt or verify)
- Mode (padding, etc.)
- Hash function (signatures, MGF1)
- Modulus size
- Public exponent
Any time you change any of these configuration parameters, it MUST be used with a new asymmetric key-pair. The new key MUST NOT be used with the same raw key bytes as any previous key.
Elliptic Curve Cryptography (ECC) is apparently easier to work with, but both will be susceptible to cracking with quantum computers some day.
Previously:
(2019) Crown Sterling Demos 256-bit RSA Key-cracking at Private Event
(2016) Upgrade Your SSH Keys
(2015) 512-bit RSA Keys Cracked in Four Hours for only $75
(2014) NSA and RSA - Claims of More Evidence
Related Stories
Blackmoore and gishzida both write:
A Reuters story claims that a group of professors from Johns Hopkins, the University of Wisconsin, the University of Illinois and elsewhere now say they have discovered that a second NSA tool exacerbated the RSA software's vulnerability. The professors found that the tool, known as the "Extended Random" extension for secure websites, could help crack a version of RSA's Dual Elliptic Curve software tens of thousands of times faster. From the story:
While Extended Random was not widely adopted, the new research sheds light on how the NSA extended the reach of its surveillance under cover of advising companies on protection.
RSA, now owned by EMC Corp, did not dispute the research when contacted by Reuters for comment. The company said it had not intentionally weakened security on any product and noted that Extended Random did not prove popular and had been removed from RSA's protection software in the last six months. "We could have been more skeptical of NSA's intentions," RSA Chief Technologist Sam Curry told Reuters. "We trusted them because they are charged with security for the U.S. government and U.S. critical infrastructure." Curry declined to say if the government had paid RSA to incorporate Extended Random in its BSafe security kit, which also housed Dual Elliptic Curve.
An NSA spokeswoman declined to comment on the study or the intelligence agency's motives in developing Extended Random.
NCommander adds: This was also submitted by chloride, who added this note:
Interestingly, OpenSSL would be very vulnerable to attack, were it not for an easily-fixed bug that prevented the library from running if Dual EC was enabled. Also interesting, one of the authors of Extended Random, Eric Rescorla, works at Mozilla and is a member of the Web Applications Security Working Group at W3C.
Just recently, I moved my personal website to HTTPS, making sure to use a secure 2048-bit RSA key and TLS 1.2, and guarding against vulnerabilities such as POODLE and Logjam. It took some work, but not that much work, even for doing the research. Yet there are some people who just don't care.
Due to a new technique, 512-bit keys are now completely vulnerable for as little as $75.
The technique, which uses Amazon's EC2 cloud computing service, is described in a paper published last week titled Factoring as a Service .
[...] The researchers concluded that despite widespread awareness that 512-bit keys are highly susceptible to breaking, the message still hasn't adequately sunk in with many administrators. The researchers wrote:
512-bit RSA has been known to be insecure for at least fifteen years, but common knowledge of precisely how insecure has perhaps not kept pace with modern technology. We build a system capable of factoring a 512-bit RSA key reliably in under four hours. We then measure the impact of such a system by surveying the incidence of 512-bit RSA in our modern cryptographic infrastructure, and find a long tail of too-short public keys and export-grade cipher suites still in use in the wild. These numbers illustrate the challenges of keeping an aging Internet infrastructure up to date with even decades-old advances in cryptanalysis.
The article reports finding a significant number of sites that are still using 512-bit RSA keys to protect HTTPS, DNSSEC, ssh, e-mail (SMTP, POP3, and IMAP), and other services.
Arthur T Knackerbracket has found the following story:
Whether you're a software developer or a sysadmin, I bet you're using SSH keys. Pushing your commits to Github or managing your Unix systems, it's best practice to do this over SSH with public key authentication rather than passwords. However, as time flies, many of you are using older keys and not aware of the need to generate fresh ones to protect your privates much better. In this post I'll demonstrate how to transition to an Ed25519 key smoothly, why you would want this and show some tips and tricks on the way there.
If you've created your key more than about four years ago with the default options it's probably insecure (RSA < 2048 bits). Even worse, I've seen tweeps, colleagues and friends still using DSA keys (ssh-dss in OpenSSH format) recently. That's a key type similar to RSA, but limited to 1024 bits size and therefore recommended against for a long time. It's plainly insecure and refused for valid reasons in recent OpenSSH versions (see also the changelog for 7.0).
The sad thing about it is that I see posts on how to re-enable DSA key support rather than moving to a more secure type of key. Really, it's unwise to follow instructions to change the configuration for PubkeyAcceptedKeyTypes or HostKeyAlgorithms (host keys are for a later post). Instead, upgrade your keys!
Compare DSA with the technology of locks using keys like this one. You wouldn't want this type of key to unlock your front door, right?
List all your keys:
You're probably thinking... "I'm using my key for a long time, I don't want to change them everywhere now." Valid point, but you don't have to! It's good to know you can have multiple keys on your system and your SSH client will pick the right one for the right system automatically.
It's part of the SSH protocol that it can offer multiple keys and the server picks the one your client will have to prove it has possession of the private key by a challenge. See it in action adding some verbosity to the SSH connect command (-vvv). Also if you're using an SSH agent you can load multiple keys and it will discover them all. Easy as that.
Submitted via IRC for Bytram
Medicine show: Crown Sterling demos 256-bit RSA key-cracking at private event
On September 19, in a conference room at the Pelican Hill Resort in Newport Beach, California, Crown Sterling CEO Robert Grant, COO Joseph Hopkins, and a pair of programmers staged a demonstration of Grant's claimed cryptography-cracking algorithm. Before an audience that a Crown Sterling spokesperson described as "approximately 100 academics and business professionals," Grant and Hopkins had their minions generate two pairs of 256-bit RSA encryption keys and then derive the prime numbers used to generate them from the public key in about 50 seconds.
In a phone interview with Ars Technica today, Grant said the video was filmed during a "business session" at the event. The "academic" presentation, which went into math behind his claims and a new paper yet to be published, was attended by "mostly people from local colleges," Hopkins said. Grant said that he didn't know who attended both sessions, and the CEO added that he didn't have access to the invitation list.
During the presentation, Grant called out to Chris Novak, the global director of Verizon Enterprise Solutions' Threat Research Advisory Center, naming him as a member of Crown Sterling's advisory board. The shout-out was during introductory remarks that Grant made about a survey of chief information security officers that the company had conducted. The survey found only 3% had an understanding of the fundamental math behind encryption.
The video of the demonstration is here. (The video was briefly marked as private, but is now back again.) The demo was displayed from a MacBook Pro, but it appeared that it was being run in part via a secure shell session to a server. Grant claimed that the work could be used to "decrypt" a 512-bit RSA key in "as little as five hours" using what Grant described as "standard computing."
(Score: 2, Insightful) by Anonymous Coward on Sunday February 13 2022, @05:03AM (4 children)
it's a trap
(Score: 5, Interesting) by DrkShadow on Sunday February 13 2022, @05:51AM
https://safecurves.cr.yp.to/ [cr.yp.to]
(Score: 2, Funny) by Anonymous Coward on Sunday February 13 2022, @02:11PM (1 child)
Better than Curve12345, which is the one I use to secure the elliptical locks on my luggage.
(Score: 0) by Anonymous Coward on Monday February 14 2022, @07:33PM
Idiot
(Score: 1, Insightful) by Anonymous Coward on Sunday February 13 2022, @03:23PM
(Score: 5, Interesting) by DrkShadow on Sunday February 13 2022, @05:19AM (17 children)
I remembered an article that said the NSA recommended using RSA as quantum-secure. 'Cause who knows about those other new-fangled keys.
I tried to look it up and found,
(https://www.securezoo.com/2019/08/nist-sp-800-52-rev-2-guidelines-for-the-selection-configuration-and-use-of-transport-layer-security-tls-implementations/)
So that's interesting.. they recommend extremely high bit-length RSA keys. In the past again, I've seen others in the security community say that anything over 2048 bits provides negligible benefit (the security doesn't scale linearly).
https://www.yubico.com/blog/big-debate-2048-4096-yubicos-stand/ [yubico.com]
So, Microsoft (security - MS Security group is good) has a report on this: https://www.microsoft.com/en-us/research/publication/quantum-resource-estimates-computing-elliptic-curve-discrete-logarithms/ [microsoft.com]
The results, 110-bit ECC is comparable to 512-bit RSA; 512-bit ECC to 2048 RSA. The results don't carry the simulation results past 521-bit ECC keys, so there's no direct comparison to 3072-bin RSA. (It looks like.. probably 640-700-bit ECC to 3072-bit RSA, at 6000 qubits, 2*10**13 Toffoli gates.)
Reading again, it seems the FIPS recommendations to not *discourage* ECC, but says only that *custom* curves not be used.
(Score: 1, Funny) by Anonymous Coward on Sunday February 13 2022, @05:36AM
RSA-8192 or we riot.
(Score: 1, Interesting) by Anonymous Coward on Sunday February 13 2022, @05:51AM (6 children)
> the increase in bits of security is only 18, a mere 16%.
I don't know anything about cryptography, so this is probably a stupid question, but shouldn't 18 extra bits be 2¹⁸*n more secure?
(Score: 1, Informative) by Anonymous Coward on Sunday February 13 2022, @08:01AM (4 children)
The bits in RSA keys are not independent. The more bits of the key you know, the easier it is to determine what the rest of the key is. Therefore, they calculated that increasing the key from 2048 to 4096 bits only adds 18 bits of security, which is 16% to the total number of bits of security for RSA-2048. The reason why they call that "mere" is because the cost is roughly 6 times longer processing time for that 18 bits more of security.
(Score: 2) by tangomargarine on Sunday February 13 2022, @08:12AM (3 children)
How exactly is it possible to know that whatever subset of bits is correct until you have the entire key?
Like how on TV they'll show a hacker cracking a lock, and the numbers will show up on the display one-by-one "as they discover them"...only you don't know whether you have the correct combination on a digital lock until you get the entire thing right. Physical tumbler locks, sure, but not digital ones.
"Is that really true?" "I just spent the last hour telling you to think for yourself! Didn't you hear anything I said?"
(Score: 0) by Anonymous Coward on Sunday February 13 2022, @08:37AM
There are many ways. A partial key read from something like Heartbleed, running a brute, doing various side-channel analysis, faulty keys, partial factorization, cryptographic attacks, etc. As an example and mentioned in the other comment, the current estimate (it may actually be worse in practice) is that RSA-2048 only takes 112 bits to break starting from nothing precisely because of this inherent bias.
(Score: 0) by Anonymous Coward on Sunday February 13 2022, @12:48PM
>> How exactly is it possible to know that whatever subset of bits is correct until you have the entire key?
Duh, once you have "1,2,3,4" it's pretty easy to guess the fifth number, similarly the next letter in "p,a,s,s,w,o,r" doesn't require a PhD in cryptography .
(Score: 1) by jurov on Sunday February 13 2022, @05:23PM
The RSA private key is two large prime numbers. And there are quite good algorithms for guessing primes, in fact the key itself was generated using fast primality test.
(Score: 1, Interesting) by Anonymous Coward on Sunday February 13 2022, @12:57PM
I'm not sure about the *n, 18 bits of security is just a factor of 2^18.
Bits of security are only loosely related to bits of key length, especially with a system like RSA that needs very long keys. So getting only a few extra bits in exchange for a much longer key is just how RSA is. Symmetric algorithms do much better (a symmetric algorithm has bits of security equal to the key length, unless it has been broken, or if it is a weird algorithm like 3DES that is weaker than it should be), although RSA needs a lot of key even by public key standards.
A 2048 bit RSA key gives you 112 bits of security (according to NIST; the exact difficulty is approximate and is probably a little harder), which is still sufficient. 1024 bit keys are weak, but it's still easier to break the security of the system they are used on than to try to break the key. Shorter keys than that are not much use any more. 512 and 768 bit keys are practical to break (depending on how motivated and wealthy you are).
All of the recommendations are extremely conservative. A variety of considerations go into the recommendation of which key length to use, including the possibility of unknown attacks on the system, the need to keep data encrypted with a key for a long period of time, and general risk aversion. In practice, no one is going to break a 2048 bit key. But if you are protecting billions of dollars worth of financial records or national security secrets, being extra conservative makes sense.
Longer keys are annoying in interactive protocols (lots of smart cards and similar can't handle anything more than 2048 bits, and it slows down the protocol handshake). On the other hand, if you're using it to sign software for distribution, and your users are only going to verify it once, and they have a PC or at least a smartphone to do the verification, there is almost no downside.
The original article isn't really attacking the security of the RSA algorithm, it's more complaining about the difficulty in working with protocols that are based on it. But if you are using such a protocol, you probably don't have much choice in the matter.
(Score: 4, Interesting) by DrkShadow on Sunday February 13 2022, @06:12AM (2 children)
Following up, I kept reading. Why do the Microsoft results stop at 521 ECC bits?
The answer is: there aren't larger (accepted) curves.
The conclusion is: ed25519 is a 256-bit ECC curve, comparable (in qubits) to a 1200-bit RSA key.
For a classical computer, going by (https://www.tenable.com/blog/new-in-nessus-elliptic-curve-cryptography-with-ssh), 224-bit ECC is comparable to 2048-bit RSA, and 256-bit ECC (ed25519) is comparable to 3072-bit RSA.
---
The largest available ECC key (https://safecurves.cr.yp.to/), E-521, offers the report's 521-bit security (comparable to a 2400-bit RSA key). I looked at how to use that with SSH (for which RSA-3072 is the default), and found..
ECDSA supports "bit-length" -- 256, 384 or 521 bits, in one of three selectable curves. One source said, "ECDSA was standardized in 2005." Another source, "NIST Curves in SSH P-256, P-384, and P-521 have been a part of SSH for awhile. The default for ECDH changed to Curve25519 in OpenSSH 6.5 (Jan. 2014)." -- which is shortly after the vulnerability in the NIST curves was discovered (2013). So, ECDSA is vulnerable to the NSA with its three selectable bitlengths.
For OpenSSH currently, there's no secure ECC key > 256 bits (comparable to RSA1300 on a quantum computer RSA3072 on classical).
Someone needs to open an OpenSSH feature request. We must future-proof!
(Score: -1, Troll) by Anonymous Coward on Sunday February 13 2022, @07:40AM (1 child)
This is how we are going to keep secret that Runaway1956 is actually Tom Cotton, of 42 Wallaby Way, Sydney? I am not configured, nor secured. Crap, now his bidness be going down.
(Score: -1, Troll) by Anonymous Coward on Sunday February 13 2022, @03:20PM
(Score: 4, Interesting) by Anonymous Coward on Sunday February 13 2022, @10:56AM (3 children)
Mere 16%? That's a weird/suspicious way of presenting it. 18 bits of security is 262144 times harder to brute force.
The idea of the NSA etc having to spend > 100,000 times more to crack my stuff just because I doubled my RSA key length from 2048 to 4096 is good enough reason to use 4096 bit keys for me. Hey if quantum computers come out and the multiplier turns out to be only "1000X" harder well that's still good.
If you're just doing low security stuff like protecting soylentnews passwords with https then 2048 bit keys are fine (if users are stupid enough to use the same passwords elsewhere for anything important then that's their problem). But if you're doing higher security stuff e.g. GPG/PGP stuff for personal signing/encryption etc you should use larger keys.
(Score: 0) by Anonymous Coward on Sunday February 13 2022, @10:28PM (2 children)
The reason why it is referred to dismissively is that there are better ways to get even larger gains in security. Why spend over five times the resources when you can spend a fifth of your current requirement for even larger gains?
(Score: 1, Interesting) by Anonymous Coward on Monday February 14 2022, @09:44AM (1 child)
There are also lots of pitfalls in using ECC. When is a safe curve a safe curve? If you stick to Curve25519 you're maxing out at 128 bits of security (equivalent to 3072 bit RSA[1]). Whereas RSA has been around for significantly longer, and if the implementation that you're using for 2048 bit is not broken then moving to 4096 bits or even higher will increase security to more than what Curve25519 offers.
If you're using a broken implementation of RSA then switch to a non-broken one.
[1] https://csrc.nist.gov/publications/detail/sp/800-57-part-1/rev-5/final [nist.gov] (page 54 and 55)
By the way, according to the actual NIST doc going from 2048 to 3072 is 112 bits to 128 bits whereas Yubico claims going from 2048 to 4096 is 112 bits to 129 bits and they have nothing to back it up other than a graph they drew AND also based on NIST info: https://www.yubico.com/blog/comparing-asymmetric-encryption-algorithms/ [yubico.com]
So I'm gonna believe the NIST doc in the 3072 number and I'm gonna guess that the additional 1000+ bits are worth a bit more than 1 bit despite what Yubico claims. To me it seems more likely at that time that Yubico was trying to spin or play down their lack of 4096 bit RSA support.
(Score: 0) by Anonymous Coward on Monday February 14 2022, @10:15PM
Forgive me. I did not realize that the only two options forever were ever increasing sizes of RSA or curve25519. It is true that Yubico miscalculated the amount of bits of security. They probably generalized the linear relationship with ECC to RSA. The actual relationship between size and bits of security for RSA is logarithmic not linear, but RSA-4096 only gets you to around 160 bits of security. Sounds good doesn't it?
However, we don't live in that world. In the real world, we have more options than just those two. If you want more bits of security, than curve25519 offers, you can use curve448. The 224 bits of security is even higher. It and others have wide support in the cryptographic community for security and safety. As a bonus, the requirements are less than the competition and a tiny fraction of the equivalent RSA-11150. Or you can use a completely different scheme that has similar security levels with less requirements because they don't have the same logarithmic relationship. To reiterate the original point, the security gain for RSA-4096, however large it really is, is still smaller than the competition and takes more resources to boot.
(Score: 4, Interesting) by JoeMerchant on Sunday February 13 2022, @02:22PM (1 child)
That 3072bit recommendation came out several years ago, and is only onerous in terms of the entropy required to secure a long term use key. If your key is transient (and the best security architectures rely on transient keys whenever possible) then generation of a 3072 but RSA pair is trivial.
🌻🌻🌻 [google.com]
(Score: 1, Interesting) by Anonymous Coward on Monday February 14 2022, @10:08AM
And if you go to 4096 you're getting more bits of security than what Curve25519 can provide (at least based on the NIST doc: https://csrc.nist.gov/publications/detail/sp/800-57-part-1/rev-5/final [nist.gov] (page 54-55)
With RSA you don't have to worry about whether a curve is safe or not, with ECC you do.
You just need to worry if someone has figured out a faster way to find the prime factors of a large integer (or similar). And there'd be a significant possibility that clever method might be able to be applied to efficiently cracking ECC too.
My other "worry" would be whether using ecdhe-rsa (for perfect forward secrecy) might weaken stuff too much if one day there's a weakness in the curve used for the ecdhe bit. But that's not an RSA security weakness. It's more a trade off between having PFS vs going for pure RSA and no ECC. Apparently using purely RSA for PFS is too slow.