[Cfrg] EdDSA and > 512 curve & hash (Re: [TLS] Additional Elliptic Curves (Curve25519 etc) for TLS ECDH key agreement)

[Adam Back <[e-mail]>]

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 SIGNED MESSAGE-----
>Hash: SHA512
>
>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
>-----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
>[e-mail]
>http://www.irtf.org/mailman/listinfo/cfrg