Subject: [Cfrg] updated Python script for signature proposals

From: "D. J. Bernstein" <[email-masked]>
Date: 22 Jul 2015 08:25:59 -0000

http://ed25519.cr.yp.to/cfrg/signatures.py has various updates. It still
doesn't have the PRF details for 'brown'. The 128-bit hash and 320-bit
PRF for 'hamburg' are also wild guesses.

I see that one of the spec bugs---verification failing because of a
missing negation---has been resolved in Mike's slides the same way as in
the script, namely computing

   S = (r - inth * a) % l

but I also don't think this is the best resolution. EdDSA's

   S = (r + inth * a) % l

is slightly simpler than subtraction for small implementations, and it's
trivial to put the minus sign into the public key instead of the scalar.
EdDSA actually goes a step beyond this, juggling the order of operations
so that the simplest implementations can avoid all scalar negations and
all point negations; this seems to require (R,S) signatures rather than
(h,S) signatures, but it would clearly work as a tweak for all the
schemes except 'hamburg'.

Another way to simplify the script would be to switch 'ladd' to the
point encoding used by the other schemes. The point encoding is actually
underspecified in most proposals, so I just copied the EdDSA encoding;
but Watson's proposal clearly specifies an extra byte (33 bytes instead
of 32 for Curve25519) and clearly specifies a comparison to (q-1)/2,
which is slightly more complicated than extracting the bottom bit of x.
Does anyone have reasons to deviate from the EdDSA encoding?

It's clear that there are some particular issues where the proposals
have reasons for diverging, but there are some other discrepancies that
seem to be easily removable distractions.

---Dan

---

From: Watson Ladd <[email-masked]>
Date: Wed, 22 Jul 2015 06:15:45 -0700

> Does anyone have reasons to deviate from the EdDSA encoding?

I'll switch to EdDSA encoding then.

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: "D. J. Bernstein" <[email-masked]>
Date: 23 Jul 2015 23:13:40 -0000

> I'll switch to EdDSA encoding then.

Script updated: http://ed25519.cr.yp.to/cfrg/signatures.py

Perhaps another issue where easy consensus is possible is the size of
the secret key:

   * Three schemes ('brown', 'eddsa', 'hamburg') start from a 256-bit
     secret key. Signing uses two hash/PRF calls to derive the long-term
     scalar and one-time scalars (a,k). For 'brown' and 'eddsa' this is
     structured as sk->a,seed and then seed,m->k; for 'hamburg' it's
     structured as sk->a and separately sk,m->k.

   * Two schemes ('ladd', 'liusvaara') start from a 512-bit secret key
     (a,seed). Signing uses one hash call.

One could argue that, since secret keys are rarely communicated, there's
not much performance benefit in having a short secret key. However:

   * I'm told that, for small devices (including HSMs), secure long-term
     key storage is a serious cost, and people appreciate having this
     cost chopped in half.

   * Saving a hash call is only a small signing speedup. (For larger
     curve sizes, the savings would be two SHA-512 calls, but this is
     even less noticeable compared to the larger curve computations.)

   * More importantly, if an 'eddsa' user cares more about this hash
     call than about the space for the secret key, then the user is free
     to store the sk->a,seed output, eliminating this cost from signing.
     (Similarly, Mike mentioned the option of storing sk,a.)
     
     In other words, specifying a 512-bit secret key a,seed is really
     just skipping the specification of the sk->a,seed hash function.
     Choosing this function to fit nicely with subsequent hashing steps
     is beneficial for small signing implementations.

Furthermore, this initial hashing helps protect the user if sk has less
randomness than expected. Nobody knows any attacks against, e.g., a
randomness burp that clears the first 64 bits of sk, while clearing the
first 64 bits of the long-term scalar would bring the scalar within
range of feasible "kangaroo" attacks. For DH this argument has to be
weighed against code-size/auditing arguments, since many DH applications
don't need hashing; but for signatures there's a hash function anyway,
and this particular usage of hashing has extremely low cost.

---Dan