New key type (ed25519) and private key format

[Damien Miller]

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