Add support for Ed25519 SSH keys

[Pim Vullers]

When I wanted to add my ECDSA SSH2 key I got the message that the key was invalid. This is probably caused because those keys use a different key identifier structure than the RSA and DSA keys. Please improve the detection to also add support for the newest kind of SSH keys.

The key I tried to add:
ecdsa-sha2-nistp256 AAAAE2VjZHNhLXNoYTItbmlzdHAyNTYAAAAIbmlzdHAyNTYAAABBBISztakMuof8TXWJMb9IpHdntowby/QVs6flRj7BiWwQQF5LNC0ByGHb53T2fWKYF8Jig4l70D3j4t1vJ6FZQ3g= pim@chaos

[Unit 193 (unit193)]

This is currently blocked by https://twistedmatrix.com/trac/ticket/5350 which could be partially fixed by http://twistedmatrix.com/trac/ticket/7413, except Ed25519 which would still need https://github.com/pyca/cryptography/issues/856.

http://twistedmatrix.com/trac/ticket/7693 would also be needed for the pyCA support.

[Damien Cassou (cassou)]

There has been update on http://twistedmatrix.com/trac/ticket/7413. Please update launchpad to take into account ecdsa keys. And it would be nice to also support Ed25519. Thanks

[Colin Watson (cjwatson)]

Don't get too excited. The movement on Twisted #7413 is a necessary prerequisite, but Twisted Conch still doesn't actually have concrete support for ECDSA keys, and Ed25519 is complicated further by the linked cryptography issue.

[Sami Olmari (olmari)]

ED25519 key I'd like to use too, so I'm just making noise here :)

[Bert JW Regeer (bregeer-ctl)]

OpenSSH on OS X sends ed25519 before rsa, this causes an hang until timeout:

https://bugs.launchpad.net/turnip/+bug/1621238

[Unit 193 (unit193)]

http://twistedmatrix.com/trac/ticket/8798 is progress towards both keys, and looks like ECDSA got support with http://twistedmatrix.com/trac/ticket/8828, now just Ed25519 is in https://twistedmatrix.com/trac/ticket/8966 (Though, http://twistedmatrix.com/trac/ticket/8854 might hold things up a tad.)

Still, there's progress and that's good.

[lszyba1 (szybalski)]

Hello,
Could somebody that is handling this ticket change the importance to major.
I'm unable to use launchpad without that key support.
My work requires it:
.ssh/id_ed25519.pub

I was hoping to convert some of the my bzr repo to git, and start using launchpad again and test drive the new git repo features in launchpad.

Please let me know who do I need to contact to get this enabled?
Thank you
Lucas

[Colin Watson (cjwatson)]

There's not much point arguing about the formal Importance of this bug. The reality is that we have the following chain of dependencies before we can fix this:

 1) upgrade Launchpad production to xenial (in progress)
 2) convert Launchpad build system to pip, so that we're no longer blocked on upgrading Twisted by conflicts between zc.buildout and pbr
 3) wait for a version of Twisted to be released that supports ED25519 keys
 4) upgrade to that version of Twisted

We already consider 1) and 2) to be high-priority, but 3) is out of our hands for the time being. Debating the value of the Importance field isn't going to speed anything up.

[Colin Watson (cjwatson)]

Update: we finished upgrading Launchpad production to xenial earlier this year; I just landed the conversion of our build system to pip; and I have a branch in progress to upgrade us to Twisted 16.5.0.

The upstream Twisted work doesn't seem to have finished yet, so we may be near the point where we've done everything we can for the time being. Versions of Twisted newer than 16.5.0 remove gmpy integration, so we'll need to take some care to avoid regressing performance on new connections, but that's doable.

[Colin Watson (cjwatson)]

lazr.sshserver 0.1.8 adds the baseline SSH authentication support that we need.

[Launchpad QA Bot (lpqabot)]

r18714 in stable (http://bazaar.launchpad.net/~launchpad-pqm/launchpad/stable/revision/18714) is part of this bug's fix.

[Colin Watson (cjwatson)]

turnip (git.launchpad.net) and txpkgupload (upload.ubuntu.com and ppa.launchpad.net) now have the necessary support for ECDSA, although this won't be effective until my next Launchpad branch is deployed. Both will need further upgrades once Twisted supports Ed25519.

[Launchpad QA Bot (lpqabot)]

r18721 in stable (http://bazaar.launchpad.net/~launchpad-pqm/launchpad/stable/revision/18721) is part of this bug's fix.

[Colin Watson (cjwatson)]

Launchpad now supports ECDSA keys. Note also that the problem where merely sending unsupported key types to Launchpad used to cause an authentication hang, as mentioned in comment #5, has been fixed for a while (see bug 830679).

I don't plan to advocate particularly strongly for people to use ECDSA keys with Launchpad by default, as there are some theoretical concerns about ECDSA (the origins of the particular chosen curves are murky and some people find that suspicious, and it shares the same weakness in the face of poor random number generators that DSA has; on the other hand, it allows effectively-much-better key lengths). Those concerns aren't enough to refuse support as long as OpenSSH thinks it appropriate to support them, but at the moment I would still recommend RSA out of the set of public key algorithms we offer.

Ed25519 is still blocked on having support for it in Twisted, but Launchpad is now essentially current on Twisted releases so it should be very easy for us to add support once that blocker is resolved. Once that happens, I would be very happy to advocate for the use of Ed25519 with Launchpad.

[Ondřej Surý (ondrej)]

Thank you.

> and it shares the same weakness in the face of poor random number generators that DSA has

Depends, see RFC 6979.

> Ed25519 is still blocked on having support for it in Twisted.

Is this related to using Ed25519 OpenPGP keys? Or is it a separate issue?

[Colin Watson (cjwatson)]

> Depends, see RFC 6979.

That's a fair point. OpenSSL 1.1 implements a variant of this which essentially hashes together some random data with the private key and the message, so it's non-deterministic but should still avoid the classic attack on (EC)DSA when the RNG is weak. And, of course, PuTTY implemented something similar for its DSA implementation way back in 2001, and carried that over to ECDSA as well, so PuTTY users should be safe.

Unfortunately, OpenSSL 1.0 *doesn't* implement this strengthening of how the k parameter in (EC)DSA is generated, and OpenSSL 1.1 was a major API change that OpenSSH hasn't yet adapted to (although there has been some gradual progress on that front, and some people have applied a patch against upstream's advice; if you follow debian-devel then you've probably seen me debating what to do about that). So that still leaves a lot of clients vulnerable to this attack in practice, if their random number generator happens to be weak.

> Is this related to using Ed25519 OpenPGP keys? Or is it a separate issue?

That's separate; comment #6 has the details. The problem with Ed25519 OpenPGP keys is that they require GnuPG 2, and getting that to work in non-interactive contexts is a real pain due to the way it likes to spawn opportunistic daemon processes. I did try to get Launchpad's test suite to work with it when we were upgrading to run on Ubuntu 16.04 a while back, but I ended up giving up and forcing GnuPG 1 for now. If you need this, then it'd be a good idea to file a separate bug so that we remember that we need to work on it.

[Ondřej Surý (ondrej)]

> OpenSSL 1.1 implements a variant of this

Yeah, it's a shame that RFC 6979 implementation didn't get into OpenSSL 1.1.x yet - I was looking at it the other day while refactoring BIND 9's crypto and I wanted to get rid of random calls in (EC)DSA algorithms. (GnuTLS has already implemented this.)

> If you need this

Nah, I was just curious :). Thanks for the answers.

[Kain (kain-kain)]

If this isn't expected to progress this year even, you could at least add documentation and reference to the UI for SSH key management.

[Colin Watson (cjwatson)]

What documentation are you looking for? It does specify which key types are permitted.

I think there's some hope of progress though. I've been working on a prerequisite for this in Twisted (https://github.com/twisted/twisted/pull/1053), and once that lands I think I might pick up the stalled Ed25519 issue.

[Kain (kain-kain)]

Calling out such a limitation directly on https://launchpad.net/%7Euser/+editsshkeys I think would be the easiest. Otherwise, theres no indicator that now-common keytypes may not be allowed.

[Colin Watson (cjwatson)]

I guess there might be some justification for that. I'm pushing a branch for review now.

[James McCoy (jamessan)]

I see the ECDSA part was removed from the subject, but last I tried (~2 weeks ago) a 521 bit ecdsa key didn't work.

[Colin Watson (cjwatson)]

@jamessan, please could you file a separate bug explaining what happened?

[James McCoy (jamessan)]

@cjwatson, see https://bugs.launchpad.net/launchpad/+bug/1802642

[Colin Watson (cjwatson)]

(The ECDSA problem was specific to bazaar.launchpad.net, and is fixed now; more details in the log of the bug @jamessan filed.)

[Launchpad QA Bot (lpqabot)]

r18822 in stable (http://bazaar.launchpad.net/~launchpad-pqm/launchpad/stable/revision/18822) is part of this bug's fix.

[dkg (dkg0)]

thanks for the work, @cjwatson. what will it take to get ed25519 available on launchpad.net?

[Colin Watson (cjwatson)]

@dkg0 We need to fix https://twistedmatrix.com/trac/ticket/8966. I think it ought to be done in a few more pieces than the current (partial and now stale) PR for it though; first we need to add support for writing the openssh-key-v1 private key format (I added support for reading it a few months back), and then Ed25519 on top of that.

There's also https://github.com/pyca/cryptography/issues/3509. But realistically we aren't going to have a sufficient version of OpenSSL on Launchpad production systems for quite a while (the bug-fixed version that cryptography needs hasn't even been released yet; I'm not comfortable with running a version of OpenSSL not receiving Ubuntu security support on Launchpad production; and we're currently on 16.04, but even 18.04 doesn't have 1.1.1). I think in practice that means that we'll need to ensure that Twisted has a fallback to some other mechanism, perhaps something based on PyNaCl. I haven't fully worked out the details of that yet.

[Colin Watson (cjwatson)]

It's been a while and there's been some progress, so here's an update:

 * cryptography 2.6 has been released with X25519 and Ed25519 support.
 * Ubuntu 18.04 has been updated to OpenSSL 1.1.1.
 * I've pushed PRs to Twisted (https://twistedmatrix.com/trac/ticket/9681 and https://twistedmatrix.com/trac/ticket/9682) to begin the process of being able to write OpenSSH's newish (v1) private key format, which is the only format OpenSSH supports for Ed25519 keys; while this isn't strictly needed in order to support Ed25519 as a server, doing this first makes the patch series much more manageable.

Still to do:

 * Finish support for writing OpenSSH v1 private keys (https://twistedmatrix.com/trac/ticket/9683).
 * Add curve25519-sha256 key exchange support to Twisted. (I have a tested branch for this, waiting on the items above.)
 * Add Ed25519 key support to Twisted. (I have a tested branch for this, waiting on the items above.)
 * Either:
  * Upgrade Ubuntu 18.04 to OpenSSL 1.1.1b or newer (1.1.1 had a signature verification bug: https://github.com/openssl/openssl/issues/7693), and upgrade the relevant Launchpad production systems from Ubuntu 16.04 to 18.04, which may be tractable; or:
  * Add a fallback mechanism to Twisted allowing it to support Ed25519 keys using PyNaCl or similar if a sufficient version of OpenSSL isn't installed.
 * Wait for a Twisted release with all this in it, and upgrade Launchpad to it. We're on a relatively recent version at the moment, so this part should be easy enough.

[Christian Reis (kiko)]

Colin, it looks like the Twisted PRs you listed in comment #29 are all fixed, which is great. Did your additional (key and key exchange) PRs get reviewed?

[Colin Watson (cjwatson)]

The current blocker is https://github.com/twisted/twisted/pull/1202, which has had one review but isn't yet landed. Once that happens I'll push my branch for the actual Ed25519 key type, which is otherwise ready to go.

That still leaves the deployment issues I mentioned. IIRC from the last time I asked distro folks about this, upgrading Ubuntu 18.04 to OpenSSL 1.1.1b wasn't likely to be viable, as the changes were rather more invasive than the version difference suggests; so we probably are going to need some form of PyNaCl-based fallback code regardless. I haven't started on this yet.

[Colin Watson (cjwatson)]

https://github.com/twisted/twisted/pull/1202 has landed, so I've pushed https://github.com/twisted/twisted/pull/1210 for the next stage of review.

[Viorel-Cosmin Miron (uhl-hosting)]

2011 .

[Christian Reis (kiko)]

Looks like the patch in merge 1210 is failing tests on Windows. If you need any help with that let me know.

Colin, could you use a backport (or PPA-hosted) libssl 1.1.1b or is there more to it?

[Colin Watson (cjwatson)]

The Windows failures were an unrelated problem (https://twistedmatrix.com/trac/ticket/9760), now fixed or at least worked around.

We *could* use a backport of OpenSSL, but I'm extremely reluctant to do so for Launchpad production since that would mean tracking security updates ourselves, with OpenSSL being something that frequently gets security updates. I'm working on a PyNaCl-based approach instead.

[Ole-Martin Bratteng (ombratteng)]

Also doesn't support the new sk-ecdsa and sk-ed25519 keys

[Colin Watson (cjwatson)]

@ombratteng Indeed, and I agree we should do that. However, it's cumbersome for this bug to keep drifting every time somebody invents a new SSH key type (note that the original bug report only mentioned ECDSA). Please could you file a new bug report about this?

[Launchpad Janitor (janitor)]

Status changed to 'Confirmed' because the bug affects multiple users.

[Bartosz Woronicz (mastier1)]

@Colin could you tell me what is the current status ?
Is there any help, testing required ?

[Colin Watson (cjwatson)]

Comments 29-35 sort of explain it, but it's a bit buried in the bug metadata spam. At this point I'm assuming that upgrading Ubuntu 18.04 to OpenSSL 1.1.1b or newer isn't viable or it would have been done already. Therefore, what we currently need is to add a fallback mechanism to Twisted allowing it to support Ed25519 keys using PyNaCl or similar if a sufficient version of OpenSSL isn't installed. I started on this a while back but haven't finished it yet.

[Colin Watson (cjwatson)]

I've proposed https://github.com/twisted/twisted/pull/1607, which should help move things along. We'll still probably have to upgrade the relevant Launchpad systems to 18.04 as well, since even 16.04's Python 3 is a little too old to support the latest released version of Twisted properly.

[mahmoh (mahmoh)]

Hi Colin,

We're approaching the ten year anniversary of this bug ... to celebrate could you allow import of ed25519 keys with a WARNING that they are UNSUPPORTED for Launchpad vs. the Invalid message and dropped?

This would allow them to be referenced and used externally to launchpad and someday hopefully supported easily once all the dependencies are fixed in another ten years? ;)

Much appreciated.

[Paride Legovini (paride)]

As new keys types are being added, it would be great to also have support for ecdsa-sk and ed25519-sk to get support FIDO/U2F hardware authenticators [1].

[1] https://www.openssh.com/txt/release-8.2

[Colin Watson (cjwatson)]

@paride That really needs to be a separate bug - each of these involves specific work in Twisted to get it working, and this is a big enough job as it is!

[Colin Watson (cjwatson)]

It's been a while since my last status update, mainly because I got a bit stalled on sorting out mypy type-checking for the PyNaCl fallback code. I came back to it this weekend, solved the problem I'd been stuck on, and finally made some decent progress:

 * updated https://github.com/twisted/twisted/pull/1607 to address review comments, simplifying the fallback code a fair bit in the process
 * wrote a similar fallback for curve25519 key exchange, which might not be worth sending upstream since it's only needed for even older OpenSSL versions than the ones that need the Ed25519 fallback
 * attempted to upgrade our Twisted backport to 21.2.0 to simplify the patch stack, only to discover that that won't work on 16.04's Python 3.5 due to relying on enhancements to the typing module that were added in later 3.5 patch releases
 * resigned myself to backporting all this to Twisted 20.3.0, prepared a draft branch for that (also including https://github.com/twisted/twisted/pull/1692, for https://answers.launchpad.net/launchpad/+question/700482), and got its tests passing on 16.04
 * prepared a lazr.sshserver branch with minor changes needed for RSA SHA-2 signature support
 * prepared a Launchpad branch to add an Ed25519 key type and accept uploads of Ed25519 public keys
 * successfully authenticated against a local Bazaar codehosting service using an Ed25519 key

With the exception of the mentioned Twisted pull requests, this is all just on my laptop so far, and it needs a bit more tidying up before I send it for review and start trying to get things landed. All the same, this is finally looking quite plausible, and we should be able to get it onto production soon.

[Colin Watson (cjwatson)]

Our various SSH endpoints (bazaar.launchpad.net, git.launchpad.net, ppa.launchpad.net, and upload.ubuntu.com) now all have the necessary protocol-level support for Ed25519, and we'll be rolling out the authserver support shortly so that it's possible to use it.

[Colin Watson (cjwatson)]

This is now all deployed, and I've been able to authenticate to all Launchpad services using an Ed25519 key.