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" <[email protected]> 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" <[email protected]> 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 >> [email protected] >> https://moderncrypto.org/mailman/listinfo/curves >> > > > _______________________________________________ > Curves mailing > [email protected]https://moderncrypto.org/mailman/listinfo/curves > > >
_______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
