[curves] Ed448-Goldilocks SHAKE

[Michael Hamburg]

Nice work, David.  I definitely like the idea of shared secrets of any length, and SHAKE as an alternative for hashing.

More comments inline.

On Jul 15, 2014, at 5:59 PM, David Leon Gil <coruus at gmail.com> wrote:

> Following up on my comments re using Shake with Goldilocks, rather than the NSA-designed SHA2-512:
> 
> (This is, needless to say, not endorsed by Mike.)
> 
> # Experimental code
> 
> An implementation based on Mike Hamburg's July 11 Goldilocks release is available at https://github.com/coruus/ed448-goldilocks
> 
> A compatible 'libkeccak' is available at https://github.com/coruus/keccakc (the 'next' branch has a simple CMake build system).
> 
> (It uses the Keccak team's C implementation of the permutation (but nothing else from KeccakCodePackage). I intend to merge Ronny van Keer's slightly faster assembler for the Keccak permutation from SUPERCOP at some point.)
> 
> It builds; tests and benchs pass.

Is this on Sandy Bridge or something else?  What do your benches look like?  I only have numbers for Haswell, SBR and a couple ARM boards.

> ## Signatures
> 
> Here's the strategy, w.r.t. signatures, where H is a Shake instance:
> 
> privatekey = H(proto, ds_goldi_derivepk)
> nonceg = H(message, pk, ds_goldi_signonce)
> challenge = H(message, nonceg, pubkey, ds_goldi_signonce)
> 
> Note the following: If verifying multiple signatures, the sponge state after absorbing the message only needs to be calculated once. (Double-hash and envelope-MAC aren't necessary for a sponge function.) This is useful for some applications, and doesn't hurt performance elsewhere.

I’m not entirely comfortable with hashing the message first, because then a hash collision breaks the system.  On the other hand, it does allow a deterministic streaming mode for signatures.  So there’s a tradeoff here.  I think I prefer putting the message in last, and if you want streaming signatures you’ll have to randomize them.

> ## Questions
> 
> 1. Would people be comfortable with Shake128[c=256] for generating nonceg and challenge? The recent security proofs indicate that this provides 256-bit security strength for 'keyed' modes of operations; all of the uses of H are 'keyed' in the correct sense. (Right now the default is Shake256.)

Certainly not if you hash the message first.  That drops security to 128 bits vs collision attacks.  Even if those attacks aren’t realistic, that’s pretty far below the design security of the system.

If the key goes in first, it might be OK.  Is it provably secure at > 224 bits that way?

> 2. Are there any attacks that hashing the sum and product of the pubkeys prevents that just hashing pubkeys doesn't, for ECDH? (This is fairly expensive…)

Is it fairly expensive?  I didn’t see a significant difference in benchmarks, between doing that step and leaving it out.

The idea of sum and product is is that it’s equivalent to hashing in the unordered tuple of the two public keys.  It might be simpler to compare and then hash them in lex order or something, but that’s how I did it.

> (Note also that this fixes a minor bug in word.h that made Goldilocks not build. The makefile is set up with -march=native, so it should build on any Mac, at least.)

Thanks, I uploaded your word.h fix.  The reason that I didn’t set march=native is that clang (at least the version on Macs) doesn’t yet detect Haswell, so it effectively becomes -march=‘some old pentium’ -msse2 instead of -maes -mavx2 -mbmi2.

> ## Tunable parameters
> 
> Applications can now request a derived shared secret of arbitrary length.
> 
> The size of the 'protokey' can be tuned, with a few changes to assertions. I'd prefer for it to be, say, 48 bytes, but for the moment it's still 32 bytes.

Cool cool.

> ## Trevor:
> 
> Re using the same key for signing and DH:
> 
> You can still, of course, with this design, do this.
> 
> But -- you could also derive two private keys from the protokey. This gives you security only on the CDH assumption (rather than Gap-DH); you can bootstrap from a known DH public key by (the private key holder) cross-signing PoPs once. (This may be unacceptable for your application; not sure. Are you thinking about for Axolotl, Noise, or?)
> 
> ## Mike:
> 
> I think that Blake2 is faster than Shake256 (but maybe not Shake128(?)) at present. I believe that it too is designed to be safe used like this. Keccak will, eventually, be blazingly fast, but not until silicon implementations. 
> 
> (One of my goals at present is to eradicate SHA1 and SHA2 as quickly as possible; this will increase the pressure on Intel and ARM provide hardware support for Keccak.)

My goal is neither “maximize performance” nor “get rid of NSA-designed things”, but rather, “let’s have a simple, fast, strong, conservative Edwards curve”.  Other things being equal, I’m also going for easy support, not uprooting the old standards.  Keccak is good stuff, but I think SHA-512 is currently more conservative and respected, and it’s definitely more widely deployed.  Blake2 just hasn’t had enough time in the spotlight.  Of course, in your fork you can do whatever you want :-)

Hardware Keccak may be somewhat difficult to come by.  You can’t just make an instruction which does one round of it on a vector register, because the state is 1600 bits.  Even for SHA, only two shipping processors that I know of (Apple A7 and VIA’s chips) have instructions for SHA2, and that’s only SHA256.  Having a separate one-per-chip accelerator core is a pain because of context switches and such.

> Thoughts on naming: How about Ned448, for nonceless deterministic ECDSA? (Because this design is a little different -- though equivalent in RO -- from plain Ed's?)

I need to de-alias the names here.  There’s at least the curve, point encoding, signature and ECDH formats, and the software library, and probably only one of them should be “Ed448-Goldilocks”.  Probably the curve.

The ‘deterministic' part is an implementation detail, and the “ECDSA” part is a signature algorithm and format, and the 448-part is curve specific.  I’m not sure what “Ned448” would be; I think it would be better to give that combination of things a compound name.

> -dlg

Cheers,
— Mike
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20140716/03520051/attachment.html>