SSH is basically everywhere, and the key generation topic keeps coming regularly. At this point it probably deserves an entry in the Cryptographic Right Answers (https://latacora.micro.blog/2018/04/03/cryptographic-right-a...) to end debates once and for all

While not explicitly pointed toward SSH, the "Asymmetric signatures" section covers this. Their recommendation is to use Ed25519 and avoid all other options mentioned in the article.

Such a mixed signal from that blog. At first it explained broken security, and then recommended I run only binaries passed down from God. Luckily I'm a believer in rational security and wouldn't run this program if I actually cared about security.

Three of these four algorithms are only for signing and although you can use RSA to do either, in SecSH (and thus modern SSH) it is only used for signing.

So it's a red flag when articles like this start jabbering about using these signature algorithms for encryption:

> This is what is meant by asymmetric encryption. [Figure 2] If Bob encrypts a message with Alice’s public key, only Alice’s private key can decrypt the message. This principle is what allows the SSH protocol to authenticate identity. If Alice (client) can decrypt Bob’s (server) message, then it proves Alice is in possession of the paired private key. This is, in theory, how SSH keys authentication should work.

No. This isn't how SSH works, and it's confusing to me that people prefer to imagine how it could work rather than just read the specification. RFC4252 explains exactly how public key authentication is performed. Alice signs a standard message bound to this SSH session using her private key, and Bob can verify that this signature is correct using her public key.

> This principle is what allows the SSH protocol to authenticate identity.

This part is also confusing. I feel like it is important to clarify that identity is not "established" using cryptography, rather verified. When Bob claims to be the Bob, you don't know and can't know just from this claim if Bob is indeed the Bob. To verify that this Bob is indeed the Bob, you have him certify from someone else that you trust that he is indeed the Bob (or you just certify it yourself when your computer asks you to trust a new fingerprint).

This isn't that complicated.

The answer is, simply: ED25519 if you're using modern services that support it.

or RSA (4096 or at least 2048 bits) for services that cannot handle ED25519 (including AWS -- yes, still, even in 2020.)

So you should probably generate both to cover most possible scenarios:

    ssh -t ed25519      # for most purposes (not AWS)
    ssh -t rsa -b 4096  # for when you're not using something like Userify

>services that cannot handle ED25519 (including AWS -- yes, still, even in 2020.)

I assume this is about provisioning VMs, and even then only about setting the initial ssh key at provisioning time? I can't imagine why AWS would care what kind of ssh keys a VM uses after it's been provisioned.

If so, you can just create a temporary RSA key used to provision the VM, immediately replace it with an ed25519 one and throw away the RSA one. That's what I do with Azure VMs since Azure has the same RSA-only requirement silliness for what amounts to writing a blob of user-provided text to a file.

It should be "ssh-keygen", not "ssh".

    ssh-keygen -t ed25519
    ssh-keygen -t rsa -b 4096

Oops :) thanks for the catch!

If you setup SSH keys a while ago, you might want to run the below command to discover the type / key strength. If you're reading HackerNews comments, this might be good time to run an audit. Also; before going all in on Ed25519, native support from some cloud providers is limited.

$ for key in ~/.ssh/id_*; do ssh-keygen -l -f "${key}"; done | uniq

There's support in hardware tokens to consider too.

More if it did what? If you're avoiding the Yubikey's onboard ECDSA because you're worried ECDSA is weaker than EdDSA that's definitely crazy. The main thing the Yubikey is doing for you is protecting that private key from just straight up getting stolen, whereupon it could be some future quantum-proof magic and you're still screwed because now the adversary has it.

The OpenSSH FIDO implementation offers ECDSA because it makes sense to use ECDSA on older authenticators that don't offer anything better rather than go without. If there were any stand alone authenticators (as opposed to hybrid software like Microsoft Hello) that only offered RSA then I suspect OpenSSH would sigh and allow that too. For all that Safer Curves makes out it's the end of the world, bad guys really do steal SSH private key files and they don't actually perform crazy timing attacks on ECDSA because it's very hard.

is 2048/SHA256 long enough?

It should be noted that EdDSA is generally implemented in constant time, something that can't be said for RSA. (which different implementations - including OpenSSL which OpenSSH uses - have been found to implement it in a way that allows side channel attacks time and time again)

In addition I am pretty sure that if you compile OpenSSH with support only for EdDSA it does not need to be linked to OpenSSL.

> In addition I am pretty sure that if you compile OpenSSH with support only for EdDSA it does not need to be linked to OpenSSL.

With the proviso (IIRC) that you will also only have AES-CTR and ChaCha.

I do not know about AES but I do know that it also supports Poly1305 to be used with Chacha20.

It might be better to put the conclusion somewhere near the top or otherwise make it more visible - it's a convoluted topic in its details with a bunch of options with very similar names. There is a simple correct answer though, and it's worth emphasizing that.

The answer is Ed25519, as most people probably expected.

Or RSA 4096.

Ed25519 certainly looks the best given the fact that all the spooks (NIST, cryptlib, Crypto++ ...) lobby against it, and didn't implement it. Looks like that is the one they want nobody to use, even if it's the simplest. However, any elliptic curve in general can be backdoored, the FSF recommends RSA 4k only. Even if RSA side channel attacks are known.

Fuck RSA.[0][1]

> The fact that RSA is still in widespread use today indicates both a failure on the part of cryptographers for not adequately articulating the [many] risks inherent in RSA, and also on the part of developers for overestimating their ability to deploy it successfully.

0: PoC||GTFO 20 (https://www.alchemistowl.org/pocorgtfo/pocorgtfo20.pdf) 20:09 (p 68)

1: Why yes, that is a direct quote.

It's not about the answer itself but the structure of the piece. For that kind of info, this is the better template:

https://codahale.com/how-to-safely-store-a-password/

This is outdated in terms of recommending bcrypt blindly. Bcrypt has some flaws (leading null bytes, being only "cpu hard") that are addressed by newer hashing functions. Argon2 in independent mode or hybrid mode seems to be the most common recommendation among security luminaries today.

Right. I'm not sure "Use X. Use X. Use X. Use X. Use X. Use X. Use X. Use X. Use X." where X is outdated and no longer a best practice is a good template.

The conclusion has the line:

> […] while EdDSA performs much faster and provides the same level of security with significantly smaller keys.

For non-embedded systems, how important is the speed and/or size consideration?

Keys are (IIRC) only used on initial contact, and the bulk of traffic operations will use symmetrical algorithms, so it it that big of a deal?

Perhaps throwing around a comparatively short "id_ed25519.pub" is easier?

> For non-embedded systems, how important is the speed and/or size consideration?

Let's put it this way, ed25519 keys take up this much space:

  sTSv4xsmaTqwhi3Qzj16w+zlRBxBvn+F3IVmxUwNkTg=

While RSA 4096 keys take up this much space:

  vUvYsQlH1yvH3KE+uJbbb8TwgvVruQpFaLzoUThFPrGKVJ+qgJqmNaMclqGnTfFb
  a6y9n4h4c5rWRX1jmzr/w72StPYbxdmxq/aTZWPWEaokQHupbk24idxxJDJXhFOm
  nJYLKe3R+14ps4n396r5sF9iyC5azqUPXKUX5k94O1wSeUrqSkW19Qu5jVYhAbBq
  aI1oUlf6Aij2pcrCIEORGqhFClLhN1H4turNPJlsw7wTeq1YVvOWYM6PKSGrlt8I
  mEgXoNnlsHnFDTZpu7ndyT2+fGfVHlVqRqEiKL53PzVUqDZYIOiclH92Y6yWOze+
  WteZjvrk1S2jdcuyEpn9mBCoz2o1koiS4F2Y8wsRtD4YZC1RSIcaul/vWp/tETqn
  zCcVysEdEbVkuzBcEc2g2P6pky4QT1o8IR/g33TRFOjkrNGekf/8ZNLhAPuoclxa
  K0LKpzV09MT5YIunkZgH+ZwDhKOcCaXweVYHoiO/BO/gP9DS93LlbsvVcrm02CYh
  V9Cl98iUuBgPLT/xMP7C4ZxwR2Dtc0kLP8fJqmy3HaeNqyEk1eEF1hGPsizWjQo8
  rABXBxNuoKD2m0SGmy4BDtQKLibushIlhoNMrkmvdNahOaEUPAgCLRYK1CN7082p
  CaYk76FZ32ZBSQ4yiFrLrewBhYdJTxkUdLgUFGo2Ie8=

In other words ed25519 keys are something you can reasonably expect people to copy-paste and otherwise work with as if they were URLs or content-addresses like md5 file hashs. RSA keys... aren't. You can work around this with keyservers and the like, but that adds more moving parts and more opprotunities for things to break for no reason.

It can take a surprisingly long time to do the initial exchange on a smart card.

smart card is kind of embedded system by it self.

The only downside to Ed25519 is that it will fall to quantum computing before RSA 4096.

Except nobody knows when that's gonna really happen. I've personally switched to ed25519-sk wherever I could.

Same, the short key looks much nicer and both will fall to quantum anyhow. Haven't run into any incompatibilities among the services I use.

OpenSSH has a post-quantum hybrid algo using SNTRUPrime and ed25519.

> * ssh(1), sshd(8): Add experimental quantum-computing resistant key exchange method, based on a combination of Streamlined NTRU Prime 4591^761 and X25519.

https://www.openssh.com/txt/release-8.0

As far as I know elliptic curves at the same size as RSA are stronger both in a quantum and post-quantum setting.

True, in fact an elliptic key with 4096 bits would be way overkill. But there is also the issue of support.

Ed25519 and RSA3072 offer around 128 bits of entropy, which is kind of on margin even classically. RSA 4096 offers more protection against brute force, around 144 bits if I recall correctly. Of course, RSA is vulnerable to side channel attacks (though these nay not be in the threat model of many people).

You could use ed448 with 224 bits of security with still shorter keys than common RSA variants. But then it’s not supported in most places.

> which is kind of on margin even classically

Is it though? It requires around 2^128 operations to be broken. It does not seem very marginal to me.

It is not like AES where you have to deal with batch-attacks or cryptographic hash functions where collisions for a n-length output require only sqrt(2^n) attempts.

That’s not how it works!

That 128 bits is theoretical upper bound, not necessarily an achievable security rate. That’s the point of margin.

Is that because elliptic curve cryptography is more sensitive to quantum brute force in general, or is the key size of ed25519 the real factor?

And the only downside to RSA 4096 is that it will fall before Niederreiter using binary Goppa codes?

The upside of RSA is that we'll likely have evidence of ed25519 being breakable (~1500 qubits) before breaking RSA 4096 is possible (~8000 qubits). [https://crypto.stackexchange.com/questions/35137/how-many-qu...]

The number of usable qubits in a single computation is expensive and has been growing slowly and until that changes I figure it's more likely to be surprised by a break of ed25519 but not RSA 4096 than to be surprised by a break of both.