Subject: Re: [Cfrg] Curve25519 specification, test vectors, etc.

From: David McGrew <[email-masked]>
Date: Mon, 03 Mar 2014 04:31:27 -0500

Hi Dan, forwarding your note to the list to make sure that it doesn't 
get dropped by the system. (Still not sure what the issue is.)   David

On 03/03/2014 02:58 AM, D. J. Bernstein wrote:
> Apparently there's some interest in specifying protocols that use
> Curve25519 for DH, especially for forward secrecy. Five years ago I
> wrote a 45-page document
>
>     http://cr.yp.to/highspeed/naclcrypto-20090310.pdf
>
> with a complete specification of NaCl's default mechanism for public-key
> authenticated encryption, including
>
>     * a specification of Curve25519 secret keys and the corresponding
>       public keys (serialized as sequences of bytes);
>
>     * a specification of Curve25519 shared secrets;
>
>     * an example of two secret keys, two public keys, and the shared
>       secret, with three independent implementations (C code using NaCl;
>       Sage script using Sage's elliptic-curve functions; self-contained
>       Python script);
>
>     * a specification of secret-key authentication and encryption using
>       Poly1305 and Salsa20;
>
>     * an example of secret-key authentication and encryption, with two
>       independent implementations (Salsa20: C code using NaCl, and
>       self-contained Python script; Poly1305: C code using NaCl, and C++
>       code using GMP); and
>
>     * extensive security notes.
>
> There are also many different tests in the SUPERCOP benchmarking suite
> (http://bench.cr.yp.to/supercop.html), and in NaCl itself.
>
> Let me also mention three items that _aren't_ in this document:
>
>     1. ChaCha20. One can of course imagine a similar document that
>        replaces Salsa20 with ChaCha20, if that's of interest.
>        
>     2. Implementation advice. In particular, this specification does not
>        explain how to build high-performance constant-time Curve25519
>        software. Readers interested in this topic will have to study
>        various papers and several freely available interoperable
>        high-performance constant-time Curve25519 implementations.
>
>        It seems to me that, out of all the deployed implementations of
>        existing IETF cryptographic specifications, very close to 0% are
>        constant-time software, and precisely 0% are high-performance
>        constant-time software. It also seems to me that there's very
>        little useful advice in IETF specifications on achieving high
>        performance for cryptography (beyond bad advice such as limiting
>        DNSSEC RSA keys to 1024 bits), and essentially no advice in IETF
>        specifications on constant-time cryptographic software. It would
>        be strange for a higher-security specification to be delayed on
>        the grounds that the specification doesn't include such advice.
>
>        I do think that it's important for users to stick to constant-time
>        cryptographic software, and I do think that the ease of building
>        such software should be weighed heavily in selecting cryptographic
>        primitives and protocols, but I also think that state-of-the-art
>        implementation details should be covered separately from the
>        specifications that are needed for interoperability.
>
>     3. The Ed25519 signature system. This system isn't in NaCl yet (code
>        review still ongoing) but is fully defined in Section 2 of the
>        Ed25519 paper, available for free from the Ed25519 web site:
>
>           http://ed25519.cr.yp.to/papers.html
>
>        There is also a self-contained Python implementation of Ed25519,
>        including extensive test vectors:
>
>           http://ed25519.cr.yp.to/software.html
>
>        SUPERCOP also contains various Ed25519 tests.
>
> Btw, every message I've sent to [email-masked], including my first
> attempt to send this one a month ago, have been disappearing without a
> trace, despite David's attempts to diagnose and fix.
>
> ---Dan
> .
>

---

From: CodesInChaos <[email-masked]>
Date: Mon, 3 Mar 2014 12:04:51 +0100

Two potential pitfalls for a Curve25519 implementation:

* Parsing non standard public keys where the most significant bit is set.

  The Curve25519 spec requires parsing the input as a 256 bit integer
which is then reduced mod p.
  Some implementations parse it as 255 bit integer, ignoring the last
bit. (Similar to the way Ed25519 parses its public keys).

  Older versions of Curve25519-donna and LibSodium had this flaw. See
https://github.com/jedisct1/libsodium/issues/78 for details.

  I suggest adding a test vector for the public key with all bits set.

* The shared secret gets hashed with (H)Salsa20.

  The hashing differs between the original Curve25519 paper and NaCl.
  The Curve25519 paper specifies a hash based on Salsa20 with custom constants
  The NaCl paper specifies HSalsa20 (i.e. without xor-ing the input)
with standard constants and an all zero nonce.

  I have only seen the NaCl variant in practice.