[curves] Ed25519 signatures from Curve25519 keys

[David Leon Gil]

Re signature nonces:

In general, I strongly prefer deriving the permanent nonce key via, e.g.,
PMAC (prefix/postfix MAC)-SHAKE[r=x]* or HMAC-SHA2-512 with a domain
separator.**

It's deterministic, it avoids using more entropy than necessary for
security, and it makes private keys (in serialized form) the same size as
public keys.

(I have been modifying the experimental Goldilocks code along these lines.)

*: For SHAKE, I would rather prefer a domain separator which is close to
uniform. E.g., Rijndael256('Ed25519').***  If you aren't using SHAKE as the
hash function for the signed material, you can set r=sig_nonce_bitlen
without loss of efficiency.)

(For longer curves, I think that Dodis's result on truncation of SHA2-512
to 256 bits implies that using the plain hash is as secure as HMAC in the
standard model. http://www.cs.nyu.edu/~puniya/papers/nist.pdf

I would hesitate to recommend doing this, however.)

** A domain separator is simply some string, preferably unique-ish, added
to reduce the powet of large-storage trade-off generic attacks on
short-length inputs.

*** The recent cryptanalysis of reduced-round Keccak/SHAKE as a stream
cipher has left me mildly concerned that non-uniform inputs may be
problematic.
On Jun 16, 2014 5:33 PM, "Trevor Perrin" <trevp at trevp.net> wrote:

> Hi,
>
> I'm wondering about using Curve25519 keys to create and verify Ed25519
> signatures.  For example, imagine you have existing Curve25519
> long-term keys being used for a DH protocol, and you'd like to sign
> with these keys.
>
> Below is an attempt to provide security analysis, and work out the details.
>
> I've run parts of this by a few people (Mike Hamburg, Robert Ransom,
> CodesInChaos).  I try to credit them where appropriate, but that
> doesn't imply they endorse all of this.
>
>
> Joint security of signatures and DH
> ----
> Schnorr signatures (like Ed25519) have a security proof in the Random
> Oracle Model based on the (Elliptic Curve ) Discrete Log assumption
> [1].
>
> Many DH protocols have security proofs in a model where the attacker
> has access to a "Decision Diffie-Hellman" oracle.   Often the attacker
> can choose an arbitrary public key, cause a targeted key to perform a
> DH operation with the chosen public key, and then "reveal" the hashed
> output.   By hashing different inputs and seeing if the result equals
> the revealed value, the attacker gains a DDH oracle involving the
> targeted key and her chosen key.   These protocols can often be proven
> secure in the Random Oracle Model based on the "Gap-DH" assumption:
> i.e. the assumption that the Computational DH problem is hard even
> when given a DDH oracle.  Protocols that can be proven secure in such
> a model include ECIES [2], NAXOS [3], Ntor [4], Kudla-Paterson [5],
> HOMQV [6], and others.
>
> As in [7] section 4.4, it seems fairly easy to argue for "joint
> security" when the same key is used for Schnorr signatures and for a
> protocol with a Gap-DH/ROM security proof, provided the hash function
> is used carefully so that RO queries for the signature can be
> distinguished from RO queries for the DH-protocol.
>
> In particular:
>  - Giving the DH-protocol adversary a signing oracle doesn't help it,
> as the signing oracle can be simulated in the ROM without knowledge of
> the secret key [1,7].
>  - Giving the signature adversary access to parties running the
> DH-protocol (e.g. an eCK experiment [3] where the secret key is held
> by an honest party) doesn't help if the protocol can be simulated
> without knowledge of the secret key but with a DDH oracle.  If the
> signature adversary + simulator could use the DDH oracle to break the
> DL problem, then the Gap-DH assumption would be violated [7].
>
> So in principle this seems secure, do people agree?
>
>
> Public-key conversion
> ----
> A Curve25519 public-key is encoded as a 255-bit x-coordinate.  An
> Ed25519 public-key is encoded as a 255-bit y-coordinate, plus a "sign"
> bit.
>
> For a "unified" public-key format, I think it makes sense to stick
> with Curve25519:
>  - Curve25519 has seen more deployment than Ed25519, so existing
> public-keys are more likely to use the Curve25519 format.
>  - The sign bit isn't strictly necessary, since it can be assumed to
> be zero, and the private key can be adjusted to match (see below).
>  - The Curve25519 format is more efficient for DH since it can be used
> directly with the Montgomery ladder.  For signature verification, the
> conversion from Curve25519 format to an Ed25519 point can be combined
> with decompression, so using Curve25519 public keys to verify Ed25519
> signatures can be almost as fast for verification as Ed25519 public
> keys (according to Mike Hamburg).
>  - If code simplicity is more of a concern than speed, it's easy to
> convert the curve25519 x-coordinate into an ed25519 y-coordinate by
> ed_y = (curve_x - 1) / (curve_x + 1) mod 2^255-19 (page 8 of [8], hat
> tip Robert Ransom).  The inversion takes perhaps 10-20% (?) of the
> time for a variable-base scalar mult.  The y-coordinate can then be
> encoded along with a sign bit of 0, allowing existing Ed25519 code to
> be used.
>
>
> Private-key conversion
> ----
> If the Ed25519 public-key sign-bit is assumed to be zero, the private
> key may need to be adjusted (per Jivsov [9]).  In other words, if
> multiplying the Curve25519 private key by the Ed25519 base point
> yields an Ed25519 x-coordinate that's "negative" as defined in [8],
> the private key (a) must be negated modulo the order of the base point
> (q), i.e. a = q - a.
>
> Some existing curve25519 implementations set bit 254 of the private
> key within the scalarmult function, so will interfere with this
> negation (observation due CodesInChaos).   Robert Ransom proposed
> another way to implement the negation that avoids having to modify
> that code:
>  - Before hashing, flip the sign bit of R
>  - Before hashing, encode the sign bit of A as zero
>  - As the last step, negate S, i.e. S = q - S
>
> Jivsov argues that fixing the sign bit doesn't lose security, even
> against Pollard rho (anyone care to double-check the argument? - [9]
> section 8).  A side-channel that leaks only whether this negation was
> performed (or not) only reveals the sign bit of the original private
> key, so I think also doesn't reduce security.
>
>
> Hash inputs
> ----
> Ed25519 calculates SHA512(R || A || M), where:
>  - R is an Ed25519-encoded Schnorr commitment  (= nonce *  base point)
>  - A is an Ed25519-encoded public key
>  - M is the message to sign
>
> The key-derivation in the DH protocol must hash distinct inputs for
> the ROM security argument to hold.  CodesInChaos suggested beginning
> the key-derivation hash with 32 bytes of 0xFF, as this is an invalid
> Ed25519 point.
>
>
> Signature nonce
> ----
> In the original Ed25519 implementation [8], a single master key is
> used to derive both (a) the Ed25519 private scalar and (b) a secret
> key for nonce generation.  Without such a master key, either
>  - the nonce-generation key would have to be explicitly generated and
> stored
>  - the nonce would have to be taken from a (strong!) RNG
>  - the private scalar would have to be used as the nonce-generation key
>
> All of these seem adequate.  Not sure which is best?
>
> Anyways, what else have I missed?
>
>
> Trevor
>
>
> [1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.8213
> [2] http://www.cs.ucdavis.edu/~rogaway/papers/dhies.pdf
> [3] http://research.microsoft.com/pubs/81673/strongake-submitted.pdf
> [4] http://cacr.uwaterloo.ca/techreports/2011/cacr2011-11.pdf
> [5] http://www.isg.rhul.ac.uk/~kp/ModularProofs.pdf
> [6] http://eprint.iacr.org/2010/638
> [7] http://eprint.iacr.org/2011/615
> [8] http://ed25519.cr.yp.to/ed25519-20110926.pdf
> [9]
> https://datatracker.ietf.org/doc/draft-jivsov-ecc-compact/?include_text=1
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20140625/e850f796/attachment.html>