The surprising persistence of RSA keys in SSH | Hacker News Reader

The surprising persistence of RSA keys in SSH

utcc.utoronto.ca

42 pointstomwas5468 comments

For the longest time, to the best of my knowledge, instructions provided by GitHub and GitLab, probably the two most popular software with easy to access instructions on generating a SSH keys defaulted to displaying the RSA key generation instructions first instead of an Ed25519 key.

The good news is that GitLab uses Ed25519 keys as the recommended default [0]. GitHub still recommends RSA keys by default [1].

[0]: https://docs.gitlab.com/ee/ssh/README.html#generating-a-new-...

[1]: https://help.github.com/en/github/authenticating-to-github/g...

I’m still not sure why I should use Ed25519? Is it just cryptographically “tougher”?

As I understand it, it's computationally faster and the same key size confers much more security than RSA. That said, there are some elliptic curve skeptics out there that think the NSA has cooked certain curves or may have techniques we don't know about and that's why they've been pushing it so hard. The latter being less likely than the former. Don't use the NIST curves.

RSA getting weaker

ECDSA suspected backdoored by NSA

EdDSA/Ed25519 like ECDSA but community made

RSA32768 might be okay but weird

ECDSA isn't thought to be backdoored so much as designed on purpose to be very difficult to get right / very easy to get catastrophically wrong.

My first encounter with ED25519 was via Gitlab. Didn't have a clue there was something 'else' to do and it's good to be able to read the discussion here.

Can I assume RSA is still 'good enough' though and something to just 'phase out' as my servers come and go?

I think a big reason for the persistence of RSA keys is that they are easier to understand than eliptical curve.

Basically, every first year computer science student who has taken discrete math can write a (horribly broken, ineffecient) implementation of RSA encryption and decryption and have a pretty good intuitive understanding of what is going on.

In fact, I did that just for fun as a first year CS student.

With elliptical curves, I have read through the multiple websites and explanations and over several years and still feel I do not have an intuitive grasp of what is really going on.

In my second year, I had to do this on paper, showing every step. The prime sizes were about 10 digits as to keep things within a few sheets of paper.

It seems my memory of it was traumatizing, one of the few assignments I had where I remember where I sat in the library computing this assignment on paper. Without electronic assistance.

At least you took the sound advice of always using a library to do cryptography.

lol

Golf clap.

I’m going disagree with this. Elliptic curves are just a scalar private key multiplied with a static point to make a public key. It’s very easy to make a naive implementation and there are far fewer gotchas.

> Elliptic curves are just a scalar private key multiplied with a static point to make a public key

To a lot of people, this will sound like

"Monads are just monoids in the category of endofunctors"

Basically, every high school student knows what prime numbers are, what factors are, what exponentiation is, what modulo (remainder) is. A scientific calculator will have all the functions for you to do RSA encryption by hand with small primes.

You need more math courses to understand what it means to multiply a point by a scalar along a curve.

elliptical curve crypto really is pretty simple when explained geometrically.

https://arstechnica.com/information-technology/2013/10/a-rel...

But the explanation is lacking.

>A more interesting property is that any non-vertical line will intersect the curve in at most three places.

If this is correct, that means a line could intersect at 1,2, or 3 places.

>Let's imagine this curve as the setting for a bizarre game of billiards. Take any two points on the curve and draw a line through them; the line will intersect the curve at exactly one more place.

No that is not correct. I can already see two points where a horizontal line would only intersect 2 points and not intersect another. Basically, you can draw a line tangent to the curve on the left and intersect only 2 points instead of three.

These geometric explanations strike me as simplifications, and as I imagine what it would look like in code, I get the feeling that there would be all sorts of special cases, boundary conditions, and asymptotes.

The other part of RSA is that mathematicians have been doing math on primes for millennia, prime factoring is likely as hard as we think it is, and RSA, despite being pretty old. hasn't had problems crop up. The only downsides are key length and quantum computing.

Implementations of RSA have suffered from all sorts of problems that have led to real world attacks irrespective of the hardness of factoring prime numbers. The intuition behind RSA being hard is alluring in its simplicity, but it's deceptive. https://blog.trailofbits.com/2019/07/08/fuck-rsa/

How many of these types of issues are unique to RSA? Does it being old help in that more of them have been discovered, and there are known implementations that are usually good?

Its stil based on a problem highly related to prime numbers.

Rsa fits on a tshirt, Export of cryptography from the United States - Wikipedia https://en.m.wikipedia.org/wiki/Export_of_cryptography_from_...

I'm still waiting for AWS EC2 to allow non-RSA keys. I've got other keys for everything else but an RSA for EC2.

This may not work for your requirements, but one approach worth considering is to create your instances without a key pair and then leverage Systems Manager to push your ed25519 keys to the system.

This can be done with RunCommand, a manual Session Manager connection, or by storing your public keys in parameter store and pulling them in via a startup scrip in Instance Metadata.

To take advantage of SessionManager or RunCommand, you do need to have the SSM agent installed along with an IAM role. This isn’t a fit for every set of requirements.

The latter approach can be accomplished with a minimal IAM role and the AWS CLI. In the event your subnet doesn’t have NAT, you will need an SSM endpoint in your VPC.

What service are you referring to? My EC2 instances running CoreOS Container Linux (moving to Fedora CoreOS as we speak...) have an ed25519 host key only and users can ssh in using their ed25519 key pair. Yeah, we don't create them using AWS web UI, but using terraform / ignition.

So when I use the EC2 web dashboard and try to add my SSH key, it gives me an error unless it's an RSA key. Obviously once I'm logged into a given sever over SSH, I can change my key to be whatever is supported by the underlying VM OS.

I was expecting this to be higher up. They're the only reason I still have an RSA key.

Neither the pgpcard (which I got from g10code while they were still selling them) nor my 100 or so Yubikeys purchased over the last 5 years support ed25519.

As far as I understand, none of the hw token vendors support ed25519, because none of the secure element vendors do.

Your best bet is AFAIK ECDSA with NIST parameters.

Yubikey is supporting ed25519 as of firmware 5.2.3 (https://www.yubico.com/blog/whats-new-in-yubikey-firmware-5-...)

Now THAT is a good news piece :)

I just happened to be considering new yubikeys, maybe I will finally migrate everything. Though I could support ed25519 with my previous idea on handling it (where yubikeys serve as decryption device for elsewhere stored crypto machine.

I’ll try to upgrade, thanks

You can't upgrade the Yubikeys. You have to buy a new one.

https://support.yubico.com/support/solutions/articles/150000...

"When we do release new firmware, we ensure the new YubiKey will function the same as older versions, so there is no need to purchase new YubiKeys to ensure compatibility."

Seems false, doesn't it?

Ugh that's really frustrating. If it's for security, why can't they just blank the key like they do when the master key is used?

Ahh, I should have made that more clear in my comment. Definitely frustrating, as those dang keys aren’t cheap!

This might be a dumb question, but 100 yubikeys? Do you use this many yourself, or do you give them to other people?

1 yubikey per service provider?

Yeah, we use ed25519 almost everywhere, except we have some networking gear that doesn't support it.

Why would it be surprising?

4k and especially 8kbit RSA provide greater assumed security, and the cpu/communication performance of 4/8kbit RSA is perfectly adequate for SSH. They also provide greater compatibility.

Why would I downgrade my cryptographic security to use a different cryptosystem with performance characteristics which aren't very relevant for interactive logins and get reduced compatibility at the same time?

I'd be much more interested in an ed448 or a ed25519+SPHINCS+ hybrid for SSH authentication -- at least they wouldn't be unambiguously less secure than what I'm currently using per our best current understanding.

Same deal for GPG/PGP: they added ed25519 which has less security than the keys most people were already using (4kbit RSA)... when the performance advantages are essentially irrelevant for the application. The non-performance related advantages seem small relative to to the compatibility and security posture.

It's startling how much software "validates" SSH keys by seeing if it starts with "ssh-rsa"

Unless there’s a good reason for not using RSA, this is a non-issue

Check out the paper "Ron was wrong, Whit is right" for a survey of keys found on the web and the surprising number of RSA keys that have weaknesses.

Discussion of said paper (2012):

* https://news.ycombinator.com/item?id=3591429

Why do RSA keys have weaknesses? Wasn't the company found to be compromised and selling products that make weak keys or something like that?

completely different. RSA group != RSA the algorithm (though they were created by the same people initially).

I may have been thinking of this:

https://www.google.com/amp/s/mobile.reuters.com/article/amp/...

Newer keys, especially ed25519, are very short. This makes working with them much easier. Copy-pasting them to remote machine is more reliable, examining authorized_keys us faster and so on.

> copy-pasting them to remote machine is more reliable,

This has basically nothing to do with the underlying cryptosystem.

Instead of explicitly configuring RSA keys, SSH could have been setup where you put their SHA256 hash in the authorized key file. (The pubkey itself would sent by the user at auth time and checked against its hash)

That may be true, but just because ed25519 might be better, doesn't mean RSA is a "problem"

In the field of security, much more than in the rest of technology, age is an important factor of being a problem. SHA1 is merely starting to see attacks that can finally be demonstrated rather than theorized, that still take hundreds of CPU-year, 20 years after its inception. But we haven't waited all that time to retire SHA-1, because we know that eventually all schemes fail.

Same holds for RSA.

Are there attacks on RSA with appropriate key sizes? We replaced SHA-1 because the attacks, even if just theoretical, were clearly on the horizon (and we replaced with sha-256 which is basically the same thing with a few tweaks and some parameters increased). RSA certainly has attacks, but they have been compensated with bigger key sizes. Is there any reason to suspect that 4096 bit RSA will be unsafe anytime soon, other than quantum computers?

Disclaimer: Iana cryptographer

There is a good reason, its just buried in complex crypto math and I won't be the one to explain it for you. If you are still using RSA, you should have upgraded to 4096 bit RSA by now. If not, you should be regenerating and changing your keys and not using one 5 or 10 year old 2048-bit RSA key because "2048 should be enough for anyone" and not thinking "I reused this key all over the place and im lazy and i'm sentimental and don't like change". People's key practices are just as bad as their password practices. His personal blog post was not meant to be a comprehensive lesson. But you can do what you want.

If this is the first time you're hearing about RSA starting to be phased out, and the new Ed25519, look into it. Or click this if you're lazy. https://medium.com/risan/upgrade-your-ssh-key-to-ed25519-c6e...

Also of note, is Ed25519 does not harden itself with additional "bits" in the normal RSA sense, it relies on "rounds" of KDF to apply more brute-force protection to the passphrase (you did set a passphrase on your key right?). I would suggest using the -a option with 1000 or more rounds. If you pick 50,000 rounds you might be waiting 5 minutes to log in though.

Also of note, ECDSA (the other one) has had curve trust concerns due to NIST possibly being subverted by the NSA. You can read for days on this, but bottom line is we've all agreed to move on. https://security.stackexchange.com/a/227771 / https://safecurves.cr.yp.to/

> Also of note, is Ed25519 does not harden itself with additional "bits" in the normal RSA sense, it relies on "rounds" of KDF to apply more brute-force protection to the passphrase

That doesn't make sense. Key stretching your pass phrase, and the number of bits your key pair is, is totally separate. The reason people dont talk about number of bits in Ed25519, is that the security margins are higher and many of the more efficient algos for cryptoanalyzing this stuff dont work on elliptic curves, so you dont have to be constantly changing the key strength to keep up with better computers, its just always 256 bits.

Exactly, I was trying to point this out, that they were seperate. I only mention increasing the rounds of your passphrase in the same sentence because you do this when generating the key to increase security, and if you don't specify it, it gets overlooked. You don't have to specify any additional bits in the key strength, but you should specify additional rounds in the passphrase. Agreed they are unrelated reasons internally, but its a good way to add an additional level of protection.

Except Ed25519 only has 128 bits of security, not 256

I was under the impression the key size was 256 bits but the security level was 128 bits.

But IANA cryptographer.

Can you please provide a citation for 2048-bit RSA not being enough? That is counter to apparently reliable advice elsewhere.

I didnt say it wasn't enough. I said you should upgrade to elliptic curve crypto, or if you have to stay on RSA, re-generate with 4096 because it's better. A 2048 bit RSA key only provides 112 bits of security - claimed to be suitable until the year 2030. RSA-2048 is still techncially ALLOWED by NIST, but that is the literal cutoff mark, below which is disallowed. The spec dates back to 2012 with "NIST Special Publication 800-57 Part1". This specification is up to Revision 5 now, the most recent of which is named "NIST Special Publication 800-57 Part 1 rev 5" published May 2020. https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.S... . There is no new news regarding the 2048 length since 2012. This estimate also does not factor in CLASSIFIED quantum cryptography thats hidden from the public. I personally don't trust them after the Snowden documents either. Plenty of sites are still using 2048 for compatibility and speed, but if you are re-generating your key now, its advised to upgrade to elliptic curve, or if you must stick on RSA, 3072 or 4096, because 2048 is the literal cutoff point. This document also describes the migration process. NIST SP 800-131A Rev. 2 - Transitioning the Use of Cryptographic Algorithms and Key Lengths https://csrc.nist.gov/publications/detail/sp/800-131a/rev-2/...

The GPG documentation specifically says that 4096 is not "better".

https://www.gnupg.org/faq/gnupg-faq.html#no_default_of_rsa40...

4096 _does_ take a lot of extra CPU resources, and it _is_ diminishing returns. But anyone who prioritizes this above all else is arguing either from a vantage point of distributed scaling across servers that cost money to handle millions of extra cycles per key times millions of keys, or from a place of defending the status quo just for the sake of defending their past choices, which I hate. Their motives for defending it have to be questioned. The page says you gain very little, because by this point we are moving away from RSA to elliptic curves, from which you gain A LOT. Section 11.5 states: "If you need more security than RSA-2048 offers, the way to go would be to switch to elliptical curve cryptography — not to continue using RSA." This is the entire point of this HN Thread. A lot of smartcard and hardware vendors have a vested interest in the status quo 2048-bit RSA because they are stingy with embedded CPU resources or monetary resources in the cost of switching algos. And theres specifically an issue with GNUPG and Elliptic Curves and license compatibility https://www.yubico.com/blog/big-debate-2048-4096-yubicos-sta... If you are an end-user with personal keys only, and fast computers, switching to a 3072 or 4096 bit key is a no brainer. The largest overhead of additional CPU cycles is only consumed on generation, not on verification. Interoperability is nearly always ensured, and you gain some 16% percent security (which is NOT "almost nothing"). Beyond that, you should switch to Ed25519 (which uses less CPU resources anyway). Continuing to argue this point is beyond the scope of this discussion. You can research yourself why RSA-2048 is being deprecated, and everyone who can switch is switching Ed25519. Or maybe the OP will write another blog post better than I can, since nobody listens to me anyway. The point was to get you to switch away from RSA, not continue using it with 4096.

> Also of note, is Ed25519 does not harden itself with additional "bits" in the normal RSA sense

Yes, it does, it is just not Ed25519 anymore, check out Curve448 and EdDSA-Ed448, same Edwards curve construction, more bits, more security. It's just that Ed25519 is plenty strong for many use cases.

Also, don't confuse the strength of the KDF with the strength of the curve itself as others have noted - Ed25519 is the same strength whether you hash your passphrase 1 or 50000 times. But with the 1 round your key might be easier to brute force if you have a weak passphrase.

I havent confused them. Its phrased like that to alert people they can't change the key strength by bit-ness, but they can change the KDF password-strength, on GENERATION, which is peoples first gateway into Ed25519. And X448 opens another can of worms, ssh-keygen still does not support that algo. OpenSSL 1.1.1 does, with: openssl genpkey -algorithm Ed448 but that doesn't relate to this discussion of use for SSH public keys. The support is very bare bones and only allows C code access meant for use in TLS servers, not SSH command line tools. They recently added EVP_PKEY_get_raw_public_key() relating to Ed25519/Ed448 but that doesnt help in actually running a command to generate these X448 algo Curve keys yourself for use in SSH keys.

So if you know how to use X448/Ed448 public/private keypairs with SSH, do tell.

FWIW the .ssh/authorized_keys command= restriction for sftp doesn’t prevent arbitrary command execution if your system is configured with procfs.

https://seclists.org/fulldisclosure/2014/Oct/35

> OpenSSH 6.7 contains a mitigation,

> OpenSSH 6.7 was released on 2014-10-06.

I am not sure why this matters? If you have not updated your system for 8 years, I am sure you have worse problems than restricted account privilege escalation.

ssh-keygen defaults to RSA

I'm surprised that this isn't a bigger deal. Most people won't specify a type and use whatever the default is.

I think this varies by os.

As the author mentions, defaults can play a significant role. In particular, it would probably help for ssh-keygen to default to ed25519.

... and break tons of usages where the software does not support newer schemes?

Switching defaults is always a complex trade-off.

Reply on news.ycombinator.com