openssh unix dev - Dec 2013 - New key type (ed25519) and private key format

Hi,

Markus has just committed a few changes that add support for the Ed25519
signature algorithm[1] as a new private key type. This algorithm has a
few benefits: it is fast (comparable to ECDSA and RSA), offers 256-bit
security and doesn't require random numbers to generate a signature.
This last property means it completely avoids (EC-)DSA's horrible,
private-key leaking problem when fed from a predictable random number
generator.

Ed25519 is not supported in OpenSSL, so we used a public-domain
implementation (from SUPERCOP). Unfortunately this means that we could
not use the PEM key format that we have used for RSA, DSA and ECDSA keys
until now, so Markus made a new one.

The new key format looks a lot like the old one (a blob of base64
encoded key material with beginning and end markers), but offers quite
a bit more protection to the key from offline attacks against the
passphrase. The new format uses a bcrypt-based key derivation function
that makes is brute-force attacks against stolen private keys far
slower.

So far, it is only required for Ed25519 keys but it is possible to
request it for other key types too by adding the '-o' flag to ssh-keygen
when generating a key. It's also possible to convert existing keys to
the new format by specifying the -o flag when changing the passphrase
('-p').

Ed25519 and the new key format to support it represented a fair amount
of new code in OpenSSH, so please try out a snapshot dated 20131207 or
later. There are certain to be some portability bugs in there that need
to be shaken out...

-d

[1] http://ed25519.cr.yp.to/ed25519-20110926.pdf

On Sat, Dec 7, 2013 at 10:40 AM, Damien Miller <djm at mindrot.org>
wrote:
> Hi,
>
> Markus has just committed a few changes that add support for the Ed25519
> signature algorithm[1] as a new private key type. This algorithm has a
> few benefits: it is fast (comparable to ECDSA and RSA), offers 256-bit
> security and doesn't require random numbers to generate a signature.
> This last property means it completely avoids (EC-)DSA's horrible,
> private-key leaking problem when fed from a predictable random number
> generator.
>
> Ed25519 is not supported in OpenSSL, so we used a public-domain
> implementation (from SUPERCOP). Unfortunately this means that we could
> not use the PEM key format that we have used for RSA, DSA and ECDSA keys
> until now, so Markus made a new one.
>
> The new key format looks a lot like the old one (a blob of base64
> encoded key material with beginning and end markers), but offers quite
> a bit more protection to the key from offline attacks against the
> passphrase. The new format uses a bcrypt-based key derivation function
> that makes is brute-force attacks against stolen private keys far
> slower.
>
> So far, it is only required for Ed25519 keys but it is possible to
> request it for other key types too by adding the '-o' flag to
ssh-keygen
> when generating a key. It's also possible to convert existing keys to
> the new format by specifying the -o flag when changing the passphrase
> ('-p').
>
> Ed25519 and the new key format to support it represented a fair amount
> of new code in OpenSSH, so please try out a snapshot dated 20131207 or
> later. There are certain to be some portability bugs in there that need
> to be shaken out...
>
> -d
>
> [1] http://ed25519.cr.yp.to/ed25519-20110926.pdf
Awesome. Tested. I had installed the latest from cvs using --prefix=/usr/local

It works fine, but it doesn't generate the ed25519 key upon make install,
thus
preventing me from launching sshd.

I've attached a diff on bugzilla:

https://bugzilla.mindrot.org/show_bug.cgi?id=2179

>
> _______________________________________________
> openssh-unix-dev mailing list
> openssh-unix-dev at mindrot.org
> https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev


-- 
This message is strictly personal and the opinions expressed do not
represent those of my employers, either past or present.

Damien Miller <djm at mindrot.org> wrote:
> Markus has just committed a few changes that add support for the Ed25519
> signature algorithm[1] as a new private key type. This algorithm has a
> few benefits: it is fast (comparable to ECDSA and RSA), offers 256-bit
> security and doesn't require random numbers to generate a signature.
Actually DJB et al.'s paper claims 128-bit security.

Looking at myproposal.h, I see that the new algorithm is called
"ssh-ed25519" without "@openssh.com".  Is that intentional
or an
oversight?

-- 
Christian "naddy" Weisgerber                          naddy at
mips.inka.de

Le 7/12/13 07:40, Damien Miller a ?crit :
> Hi,
> 
> Ed25519 is not supported in OpenSSL, so we used a public-domain
> implementation (from SUPERCOP). Unfortunately this means that we could
> not use the PEM key format that we have used for RSA, DSA and ECDSA keys
> until now, so Markus made a new one.
> 
> The new key format looks a lot like the old one (a blob of base64
> encoded key material with beginning and end markers), but offers quite
> a bit more protection to the key from offline attacks against the
> passphrase. The new format uses a bcrypt-based key derivation function
> that makes is brute-force attacks against stolen private keys far
> slower.
>
Hi Damien, Markus,

I do not understand why Ed25519 not being in Openssl couldn't let you
use the pem-like format described in RFC4716. In fact that would have
been a good occasion of getting rid of the complex PEM decoder from
libcrypto and implement your own (with relevant subset of ASN.1
decoding). Maybe you did not want something as complex as PEM.

When designing your new format, did you take in consideration some of
the criticism over the existing PEM format to improve it ? One of the
functionalities I could see useful would be to embed the public key
authenticated but not encrypted into the key file. That way, it is
always possible to determine if a key is useful before asking the
passphrase to the user (current workaround needs the actual encrypted
key and a cleartext public key file, which can be confusing). The key
format of putty could have been a good candidate. Some food for thoughts
on [1].

Did you publish some specs already ? I cannot find it yet on openssh.org.

Regards and good week-end,

Aris

[1]
http://www.chiark.greenend.org.uk/~sgtatham/putty/wishlist/key-formats-natively.html

On Sat, 7 Dec 2013, Damien Miller wrote:
> Hi,
> 
> Markus has just committed a few changes that add support for the Ed25519
> signature algorithm[1] as a new private key type. This algorithm has a
> few benefits: it is fast (comparable to ECDSA and RSA), offers 256-bit
> security
Turns out that I'm wrong about this: Ed25519 offers 128 bit security,
not 256.

-d