Subject: [Cfrg] Thoughts on a Next-Generation Elliptic Curve Signature Scheme?

From: Alyssa Rowan <[email-masked]>
Date: Sat, 11 Jan 2014 18:35:51 +0000

At some point, clearly we're going to need a signature scheme for
these "Chicago curves" specified in SafeCurves, for later use to
replace ECDSA with something which is a more convenient fit for them
and doesn't want random numbers for each signature, for future use in
certificates, authentication, and the like.

I feel like now would be a good point, hence this request for ideas.

On 11/01/2014 17:40, Robert Ransom wrote:
> Dr. Bernstein's EdDSA is even worse: it prohibits every curve that
>  Dr. Bernstein himself has specified since Curve25519.

EdDSA seem like a pretty good start for a new signature scheme to me,
even if as it stands I think it's closely tied to Ed25519 itself
(basically, due to the size and construction?).

Schnorr-type signatures using an Edwards representation would be the
obvious natural candidate.

Either the Edwards curves or the Edwards isomorphism of one of the
Montgomery curves would do, although the ones specified as Edwards
curves would likely be cleaner, particularly Curve1174, Curve3617 and
E521: in fact, those would be the three I'd plump for, as I think they
provide three pretty good security/efficiency points.

We're going to need a hash, too. I suggest that we should use one of
the new hash algorithms that came out of the SHA-3 competition. All
the finalists have something to recommend them (I really like Skein
and BLAKE myself): but the least controversial in my eyes, and so the
one I'd on consideration suggest, is Keccak, given it was the winner
and thus has the additional backing of being SHA-3. (I can see ways
its particular attributes might prove helpful, too.)

Do you have any thoughts?

- -- 
/akr

---

From: Robert Ransom <[email-masked]>
Date: Sat, 11 Jan 2014 10:44:37 -0800

On 1/11/14, Alyssa Rowan <[email-masked]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>

EdDSA specifies some details that are irrelevant to how the signature
scheme works: it specifies that the coordinate field's order must be
congruent to 5 mod 8, and it specifies that the curve group must have
cofactor 8 (cofactor 4 is possible even mod 2^255 - 19, e.g. a=-1,
d=446 if I'm retyping it correctly).

> provide three pretty good security/efficiency points.

Please, not Curve1174.  If you don't like Curve25519's awkward
fractional value of Edwards-form d, use the isogenous curve with
a=-1,d=121665 over the same field.

> and BLAKE myself):

BLAKE2 is better than BLAKE.

> but the least controversial in my eyes, and so the

Because NSA wants other people to rely on Keccak?  Really?

I can see advantages to using a sponge, but “NSA wants us to eat it”
has never been a good argument.

Robert Ransom

---

From: Alyssa Rowan <[email-masked]>
Date: Sun, 12 Jan 2014 12:57:55 +0000

On 12/01/2014 06:29, Ilari Liusvaara wrote:
>> One problem with defining EdDSA for larger curves is that the 
>> needed hashes are large.

On 12/01/2014 06:40, Peter Gutmann wrote:
> Are they? [...]

EdDSA uses a hash to generate deterministic secret random exponents, to
avoid eating entropy when signing (like ECDSA does in its natural
habitat). That will need to be a big enough hash to cover the size we
need: 512 bits covers 2^255 - 19, but to cover Curve3617 or E521, we're
going to need a bigger boat.

On 12/01/2014 06:29, Ilari Liusvaara wrote:
> [...] And there are very few hashes with serious analysis that can 
> do >512 bits.

That's why I observed in the OP that Keccak (the eventual SHA-3) may
have some useful properties in this arena: the sponge function's
flexible output size, I think, makes it a natural fit.

However, there may be disagreement in the wider arena as to whether
NIST's endorsement of it counts as a positive, a NOP, or a negative,
in light of the wider situation.

I recognise that, and empathise with it: it deserves careful, open
consideration, and a discussion weighing up which hash we use, why, and
how, I think. Bullet tree time, to explore my thoughts on the matter:

• Suitability:
  - Keccak's output size (and parameters) are flexible.
    · This is _very_ handy for the curves bigger than 25519!
    · We could even if we wished set our own parameters to suit.
    · Of course, if we did that, it wouldn't be SHA-3, but we might be
      able to hardware-accelerate it anyway.
    · Possible suitable parameter selections? Positives & negatives.
  - This is less true of some other competitors.

• NIST wanted to reduce the capacity after the competition.
  - Keccak authors defended that choice as safe.
    · Many SHA-3 entries were deliberately conservative.
    · It does reduce the margin of safety against second-preimage.
    · But we _wanted_ SHA-3 very conservative, 'just in case'.
    · BLAKE team reduced rounds of BLAKE2 for speed => still OK.
    · Is it an issue if it's still better than ρ?
  - Well, that escalated quickly. They couldn't have timed it worse.
    · Snowden revelations.
    · Coinciding with NIST proposing safety margin reduction in SHA-3.
    · Looked bad! Much grumbling.
    · NIST quickly backed down: didn't want to be seen poisoning the
      well.
  - SHA-3 will be Keccak, as submitted in final round, no changes,
    no nasty surprises, apparently.
    · Except the padding [10…1] might be swapped for Sakura's.
    · Which also seems sensible: pretty straightforward Merkle root.

• Why did NIST (and/or NSA, therefore) like it?
  - Stated reason: because it's nothing like SHA-2.
    · An attack weakening Merkle-Dåmgard constructs is unlikely to be
      directly relevant to sponge functions.
    · Fair enough. Seems legit.
  - Either they like strong, or they like secretly weak.
    · We aren't mindreaders, and have no way of knowing which.
    · C'est la vie!
  - Its software performance is... okay. It's not great.
    · Skein and BLAKE were twice the speed, and left it in the dust.
    · BLAKE2 is even faster!
    · Keccak lies around the middle of the pack, a little slower than
      SHA-2.
  - It's very fast in hardware.
    · Now _this_ is a _very_ consistent thing NIST/NSA like: because
      basically all their crypto implementations are hardware.
    · This is therefore fairly likely to have been a dominant factor.
    · Fast hardware performance is a negative in a PBKDF or a Hashcash,
      which we actually want to be slow to measure out workfactor of
      brute-force.
    · But it's a positive in a signature scheme, as long as the hash is
      strong enough to resist any plausible second-preimage attack.
    · And it is.
    · A collision would not suffice here.

• Is there anything wrong with Keccak?
  - As far as we know: nope.
  - It looked very strong during the competition: it still does.
  - I don't know anything to suggest it's weak. Theoretically it
    looks pretty good.
  - None of the other SHA-3 final round candidates look bad either.
  - Even SHA-2 still doesn't look bad, exactly.
    · Except for the length-extension, which isn't a threat here.
    · I do not think we want to use an NSA-designed algorithm in a new
      signature scheme, when we have new ones that were designed as
      part of an open competition and have been widely discussed.

• Speed?
  - As above, software: ...okay, but not great; hardware: excellent.
  - Will we get hardware?
    · Crystal ball time!
    · Eventually, probably yes, due to it being SHA-3. NIST pulls a lot
      of weight in that area.
    · If we use it in this signature scheme, that actually may make a
      small difference. TLS, etc, certainly wouldn't hurt adoption.
    · Would we be able to use any such hardware?
    · Without doubt, if the hardware exposes the sponge function
      itself. Otherwise, most probably; depends on what we choose.
  - How does hash performance impact?
    · Probably relatively little. Signatures usually cover small
      things; key exchanges, etc, and the EC code will dominate time.
    · The case where it does: signing larger files. Code signing, etc.
    · If that's a problem, there's a tried-and-true solution already:
      a detached signature covering a manifest of hashes, which could
      be anything we like, e.g., tree hash mode of Skein, whatever.
    · I/O however remains the firm bottleneck on anything big.
    · Keccak isn't _that_ slow.

So. Thoughts?

- -- 
/akr

---

From: Adam Back <[email-masked]>
Date: Sun, 12 Jan 2014 15:29:23 +0100

You know EdDSA is actually an EC Schnorr signature over an Edwards curve. 
In the original Schnorr setting it was proposed that you could even securely
truncate the hash to half the subgroup size, to make a signature which is
1.5x the subgroup size rather than 2x.  Recalling that a Schnorr sig is pub
key y=g^x, sig (r,s) r=g^k, s=k+H(r,m) and as verify is g^s =?  r*y^H(r,m)
there is an alternate and security equivalent verification labeling
c=H(r,m), signature (c,s), adapted verification c=?H(g^s*y^c,m) and so if H
is truncated then c can be half sub-group size.  That all works in EC
Schnorr also.

However there are some security arguments that truncated hash is not quite
as conservative, particularly for more advanced Schnorr related mechanisms,
like the DL variant of Brands representation problem based blind
certificates which can provide ZKPs of boolean forumlae involving blind
certified attributes, beyond simple signatures.

So actually Bernstein went in the opposite direction, not only using
sub-group size, but double sub-group size hash, basically because he could
without increasing the signature size, and thereby slightly even further
reducing the dependency on hash security and hash properties.  I do not
consider its necessary, just its because he could, slightly more security
almost for free.  But I think an EdDSA variant that used a 512-bit curve
could safely use a 512-bit hash, because even the double width hash is
over-engineering.  As far as that goes even sub-group sized hash in vanilla
Schnorr has security provability and over Schnorr/EC Schnorr hash property
advantages over DSA.

EdDSA also uses the deterministic DSA k trick (computed from m and x the
private key).

Adam

On Sun, Jan 12, 2014 at 12:57:55PM +0000, Alyssa Rowan wrote:
>-----BEGIN PGP SIGNATURE-----
>
>iQIcBAEBCgAGBQJS0pFTAAoJEOyEjtkWi2t6u8kP/RU8tw+inyh6x7gCdA8VGlAr
>Bge6q7/MYsil6BeIjTNRo6mjpEfsC9svDDkClpoBAN36nkPCesVf/Zz8Wn9/4qfD
>vnK2Fcek3/VDGKxoZCMSRRegQm2eMdxTT+HLujVcyJOBPc4SR+KtQx1/+TIF9jhs
>f0wur2h9P0eYyzIVzPNrsxo4XL2vGKmPrJPmOsDL9W9G78w6qMH5+ao3CPxIYFeu
>ngOQzLa9P9tBZbneV06OGwgjRnhMfuB9C2Mt2uqXd6PsGrEZIjkdeuQLDejA7PBb
>WR2lgd5A5SDIp1T04Bou4KUJnByJ3tWUWobMHhfdlKudOg/MG4YUC/b78fvJCWte
>VV0kq9WTT+Y4ZcV9KdgmQipyGp+BG1X6u9xQgeOJ5QbuEzfU3uauQrx2OA7YitjV
>dQTdvbnpmH9/i0zsZisrS4QjEx3UAblqXI9uPiOcG+lq3qQqHq148LGN6IxRik1r
>prj0BY589IappMs1SSuKpi3eumSUpQg47XjBVvyi/ElP5dPB5ns0qVaFC6C7C6Bs
>Qkn0ztifMR4pvqHUOOwbBbFQCpyNpfo+hl4TN9WJ4kTW5M7cc05+CLqfJEmu4MUw
>+RAHXiqHyoG0sUjdX5MDgGTsZCLI9CroGKLRJsxLfxWFiWkLE5tBFxYXKDmywKNr
>Vypa5YYU/pYf3vMpJ67A
>=Agth
>-----END PGP SIGNATURE-----
>_______________________________________________
>Cfrg mailing list
>[email-masked]
>http://www.irtf.org/mailman/listinfo/cfrg

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Sun, 12 Jan 2014 09:45:37 -0500

On 01/12/2014 07:57 AM, Alyssa Rowan wrote:
>     · And it [keccak] is.

What makes you say that a collision attack isn't relevant against a
signature scheme?  The classic collision attack against a signature
scheme is:

 * attacker generates A, B, such that H(A) = H(B)
 * attacker asks victim to sign A
 * victim signs A over digest H
 * attacker applies signature to B

This is how the hashclash/rogue-CA project did its work [0], and it's a
conceivable attack against anything from OpenPGP certifications to
document signatures to revision control [1].

Or am i misunderstanding the context in which you're saying that a
collision would not suffice?

Regards,

	--dkg

[0] http://www.win.tue.nl/hashclash/rogue-ca/
[1]
http://joeyh.name/blog/entry/size_of_the_git_sha1_collision_attack_surface/

---

From: Robert Ransom <[email-masked]>
Date: Sun, 12 Jan 2014 07:04:00 -0800

> collision would not suffice?

In the specific case of an EdDSA-like Schnorr signature scheme, the
*beginning* of the input to the message hash function would be
unpredictable to the attacker (thus achieving ‘randomized hashing’ for
free).  This makes collision attacks harder with any reasonable hash
function.

(Note that Schnorr's original signature scheme put R at the *end* of
the hash input; that would not mitigate collision attacks.)

Robert Ransom

---

From: Robert Ransom <[email-masked]>
Date: Sun, 12 Jan 2014 07:13:16 -0800

On 1/12/14, Adam Back <[email-masked]> wrote:

> over-engineering.

It can for the hash of the message.

> EdDSA also uses the deterministic DSA k trick (computed from m and x the

Deterministic generation of message keys is the primary reason that
EdDSA requires a double-length hash function.

EdDSA relies on the hash function having double-length output in two ways:

* Message key generation relies on the output being noticeably longer
than the group order in order to generate *uniform* exponents.

* EdDSA also uses the hash function to expand the secret-key bitstring
into (a) the secret exponent of the public key and (b) a secret
bitstring used to key the message key generation hash function.

I'm quite sure that I've said all of this before quite recently.

Robert Ransom

---

From: Adam Back <[email-masked]>
Date: Sun, 12 Jan 2014 16:36:49 +0100

>free).  This makes collision attacks harder with any reasonable hash

Actually that is a signature security threat-model artificiality.  While it
is true that it makes birthday collision harder for an attacker using a
signing oracle, if the attacker is the signer, its still the same.  And in
real life we care about that just as much.

Also Alyssa mentioned applications in PBKDF2 and hashcash which are like key
stretching and proof-of-work relying on 2nd-preimage respectively.

Adam

---

From: Adam Back <[email-masked]>
Date: Sun, 12 Jan 2014 16:53:50 +0100

>bitstring used to key the message key generation hash function.

My point is compared to the deterministic CRNG that eg DSA specifies for k
generation, follow that pattern, but using SHA3-512 as the building
block, seeded with d, the private key, is certainly doable to scale EdDSA to
512-bit curve without needing a 1024-bit hash function.

Some KDF functions are designed to provide the needed one-way security
beyond the hash input size of the underlying hash or MAC function.  So I was
suggesting this as an alternative method than using a not-widely-used hash
or hash-parameterization (Keccak).

Adam

---

From: Mike Hamburg <[email-masked]>
Date: Sun, 12 Jan 2014 10:30:56 -0800

> or hash-parameterization (Keccak).

My personal preference here is for either SHA512 or SHA3, in that order.  But is SHA3 defined yet?

I don't care that SHA2 was designed by NSA.  The SHA2 functions are widely deployed and have survived more than a dozen years of public analysis.  Their performance is good enough that they won't be the bottleneck in an EC signature implementation.  SHA512 has a wide enough output and a high enough security level to be suitable for many of these curves, though for some curves it will need to be evaluated twice in order to be wide enough.

BLAKE2 is probably fine.  But it hasn't had as much time in the spotlight as SHA2 or Keccak.

The SHA3 finalists are also fine.  But we should test timings to see whether their extreme performance is a gain in an EC hash setting.

Using a widely-deployed and widely-respected hash function will ease implementation and improve acceptance and deployment of any new standard we might make.

I also wonder if a new signature scheme should support hash-and-sign, or just signing where you have the full message.  Hash-and-sign is less secure because of collision attacks, but the API is much nicer especially for deterministic hashes, and that matters.

Cheers,
-- Mike

---

From: Vadym Fedyukovych <[email-masked]>
Date: Mon, 13 Jan 2014 00:29:44 +0200

> than the group order in order to generate *uniform* exponents.

Choosing a message key (an initial random in interactive system)
from a large interval is a well-known idea for a group of a hidden order.
For a group of known order, reducing almost anything modulo group order
would likely result in quite a non-uniform distribution.
It is non-trivial to see how/whether hash of roughly twice-bitlength of group order 
would be better than hash smaller than group order.

Hash bitlength is rather non-critical while choosing a challenge,
that should be just a large enough set.

Vadym Fedyukovych

---

From: Watson Ladd <[email-masked]>
Date: Sun, 12 Jan 2014 14:39:42 -0800

> would be better than hash smaller than group order.

Completely wrong for trivial reasons. Let's say we are picking a
random number up to k by taking one up to n and reducing.
Write n=kq+r, with r the remainder. Then the bias is exactly r/n,
which for n the square of k is at most 1/k, and hence negligible if
k is big enough. This is clearly better than if the hash length is
smaller than the group order, in which case a significant number of
group elements will never be picked.

Sincerely,
Watson Ladd

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Vadym Fedyukovych <[email-masked]>
Date: Mon, 13 Jan 2014 02:13:35 +0200

> group elements will never be picked.

Wrong conclusion starting from irrelevant definition.

Observable S (response in Schnorr protocol) is from ring modulo group order.
For a non-uniform probability distribution of S,
one would consider bias like max_{i,j} | p(S(H_i)) - p(S(H_j)) |,
for uniform distribution of H (hash function samples).
No chance to reduce such a bias by increasing hash bitlength.

Additional consideration may be helpful
to decide whether bias is small enough.

Vadym Fedyukovych