Re: [Cfrg] [TLS] Additional Elliptic Curves (Curve25519 etc) for TLS ECDH key agreement

[Alyssa Rowan <[e-mail]>]

-----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-----