|
Packit Service |
31306d |
curve25519-sha256@libssh.org.txt Aris Adamantiadis <aris@badcode.be>
|
|
Packit Service |
31306d |
21/9/2013
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
1. Introduction
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
This document describes the key exchange methode curve25519-sha256@libssh.org
|
|
Packit Service |
31306d |
for SSH version 2 protocol. It is provided as an alternative to the existing
|
|
Packit Service |
31306d |
key exchange mechanisms based on either Diffie-Hellman or Elliptic Curve Diffie-
|
|
Packit Service |
31306d |
Hellman [RFC5656].
|
|
Packit Service |
31306d |
The reason is the following : During summer of 2013, revelations from ex-
|
|
Packit Service |
31306d |
consultant at NSA Edward Snowden gave proof that NSA willingly inserts backdoors
|
|
Packit Service |
31306d |
into softwares, hardware components and published standards. While it is still
|
|
Packit Service |
31306d |
believed that the mathematics behind ECC cryptography are still sound and solid,
|
|
Packit Service |
31306d |
some people (including Bruce Schneier [SCHNEIER]), showed their lack of confidence
|
|
Packit Service |
31306d |
in NIST-published curves such as nistp256, nistp384, nistp521, for which constant
|
|
Packit Service |
31306d |
parameters (including the generator point) are defined without explanation. It
|
|
Packit Service |
31306d |
is also believed that NSA had a word to say in their definition. These curves
|
|
Packit Service |
31306d |
are not the most secure or fastest possible for their key sizes [DJB], and
|
|
Packit Service |
31306d |
researchers think it is possible that NSA have ways of cracking NIST curves.
|
|
Packit Service |
31306d |
It is also interesting to note that SSH belongs to the list of protocols the NSA
|
|
Packit Service |
31306d |
claims to be able to eavesdrop. Having a secure replacement would make passive
|
|
Packit Service |
31306d |
attacks much harder if such a backdoor exists.
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
However an alternative exists in the form of Curve25519. This algorithm has been
|
|
Packit Service |
31306d |
proposed in 2006 by DJB [Curve25519]. Its main strengths are its speed, its
|
|
Packit Service |
31306d |
constant-time run time (and resistance against side-channel attacks), and its
|
|
Packit Service |
31306d |
lack of nebulous hard-coded constants.
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
The reference version being used in this document is the one described in
|
|
Packit Service |
31306d |
[Curve25519] as implemented in the library NaCl [NaCl].
|
|
Packit Service |
31306d |
This document does not attempt to provide alternatives to the ecdsa-sha1-*
|
|
Packit Service |
31306d |
authentication keys.
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
2. Key exchange
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
The key exchange procedure is very similar to the one described chapter 4 of
|
|
Packit Service |
31306d |
[RFC5656]. Public ephemeral keys are transmitted over SSH encapsulated into
|
|
Packit Service |
31306d |
standard SSH strings.
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
The following is an overview of the key exchange process:
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
Client Server
|
|
Packit Service |
31306d |
------ ------
|
|
Packit Service |
31306d |
Generate ephemeral key pair.
|
|
Packit Service |
31306d |
SSH_MSG_KEX_ECDH_INIT -------->
|
|
Packit Service |
31306d |
Verify that client public key
|
|
Packit Service |
31306d |
length is 32 bytes.
|
|
Packit Service |
31306d |
Generate ephemeral key pair.
|
|
Packit Service |
31306d |
Compute shared secret.
|
|
Packit Service |
31306d |
Generate and sign exchange hash.
|
|
Packit Service |
31306d |
<-------- SSH_MSG_KEX_ECDH_REPLY
|
|
Packit Service |
31306d |
Verify that server public key length is 32 bytes.
|
|
Packit Service |
31306d |
* Verify host keys belong to server.
|
|
Packit Service |
31306d |
Compute shared secret.
|
|
Packit Service |
31306d |
Generate exchange hash.
|
|
Packit Service |
31306d |
Verify server's signature.
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
* Optional but strongly recommanded as this protects against MITM attacks.
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
This is implemented using the same messages as described in RFC5656 chapter 4
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
3. Method Name
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
The name of this key exchange method is "curve25519-sha256@libssh.org".
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
4. Implementation considerations
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
The whole method is based on the curve25519 scalar multiplication. In this
|
|
Packit Service |
31306d |
method, a private key is a scalar of 256 bits, and a public key is a point
|
|
Packit Service |
31306d |
of 256 bits.
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
4.1. Private key generation
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
A 32 bytes private key should be generated for each new connection,
|
|
Packit Service |
31306d |
using a secure PRNG. The following actions must be done on the private key:
|
|
Packit Service |
31306d |
mysecret[0] &= 248;
|
|
Packit Service |
31306d |
mysecret[31] &= 127;
|
|
Packit Service |
31306d |
mysecret[31] |= 64;
|
|
Packit Service |
31306d |
In order to keep the key valid. However, many cryptographic libraries will do
|
|
Packit Service |
31306d |
this automatically.
|
|
Packit Service |
31306d |
It should be noted that, in opposition to NIST curves, no special validation
|
|
Packit Service |
31306d |
should be done to ensure the result is a valid and secure private key.
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
4.2 Public key generation
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
The 32 bytes public key of either a client or a server must be generated using
|
|
Packit Service |
31306d |
the 32 bytes private key and a common generator base. This base is defined as 9
|
|
Packit Service |
31306d |
followed by all zeroes:
|
|
Packit Service |
31306d |
const unsigned char basepoint[32] = {9};
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
The public key is calculated using the cryptographic scalar multiplication:
|
|
Packit Service |
31306d |
const unsigned char privkey[32];
|
|
Packit Service |
31306d |
unsigned char pubkey[32];
|
|
Packit Service |
31306d |
crypto_scalarmult (pubkey, privkey, basepoint);
|
|
Packit Service |
31306d |
However some cryptographic libraries may provide a combined function:
|
|
Packit Service |
31306d |
crypto_scalarmult_base (pubkey, privkey);
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
It should be noted that, in opposition to NIST curves, no special validation
|
|
Packit Service |
31306d |
should be done to ensure the received public keys are valid curves point. The
|
|
Packit Service |
31306d |
Curve25519 algorithm ensure that every possible public key maps to a valid
|
|
Packit Service |
31306d |
ECC Point.
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
4.3 Shared secret generation
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
The shared secret, k, is defined in SSH specifications to be a big integer.
|
|
Packit Service |
31306d |
This number is calculated using the following procedure:
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
X is the 32 bytes point obtained by the scalar multiplication of the other
|
|
Packit Service |
31306d |
side's public key and the local private key scalar.
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
The whole 32 bytes of the number X are then converted into a big integer k.
|
|
Packit Service |
31306d |
This conversion follows the network byte order. This step differs from
|
|
Packit Service |
31306d |
RFC5656.
|
|
Packit Service |
31306d |
|
|
Packit Service |
31306d |
[RFC5656] https://tools.ietf.org/html/rfc5656
|
|
Packit Service |
31306d |
[SCHNEIER] https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html#c1675929
|
|
Packit Service |
31306d |
[DJB] https://cr.yp.to/talks/2013.05.31/slides-dan+tanja-20130531-4x3.pdf
|
|
Packit Service |
31306d |
[Curve25519] "Curve25519: new Diffie-Hellman speed records."
|
|
Packit Service |
31306d |
https://cr.yp.to/ecdh/curve25519-20060209.pdf
|