[curves] Ed25519 signatures from Curve25519 keys

Wed Jun 25 11:48:49 PDT 2014

Apologies, I wasn't clear about the change I was playing with for
Goldilocks, which does indeed do exactly what I like with SHA-2-512, but
kind of in reverse.

I am playing with generating a random element of p448 and deriving the
nonce key from SHAKE on that. I have a mild preference for going in this
direction, though I don't think that there is any particular security
difference either way.

Yes. (Obviously that is an extremely paranoid reaction to an attack on 6/24
rounds. But it is a one-time cost.)

BTW, might I suggest the term EddyDSA for this sort of scheme? A slightly
mixed up acronyn for Edwards doubly deterministic DSA...
On Jun 25, 2014 10:31 AM, "Mike Hamburg" <mike at shiftleft.org> wrote:

>
> On 6/25/2014 8:37 AM, David Leon Gil wrote:
>
> 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.)
>
> Is your goal in doing this to reduce the size of serialized private keys?
> The private keys are already derived from the 256-bit symmetric key.  You
> might consider using goldilocks_underive_private_key().
>
> *** The recent cryptanalysis of reduced-round Keccak/SHAKE as a stream
> cipher has left me mildly concerned that non-uniform inputs may be
> problematic.
>
> Is this the 6-round cube attack, or is there a stronger one?
>
> Cheers,
> -- Mike
>
>  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
>>
>
>
> _______________________________________________
> Curves mailing listCurves at moderncrypto.orghttps://moderncrypto.org/mailman/listinfo/curves
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20140625/436cfd7c/attachment.html>