Subject: [Cfrg] Using SHAKE as the hash scheme

From: Bryan Ford <[email-masked]>
Date: Fri, 24 Jul 2015 18:00:20 +0200

Following up on Dan Brown’s suggestion of considering SHAKE as a hash, I would like to elaborate on this a bit further and offer a concrete proposal in this direction.  I’ll use eddsa as a base and fiddle only with the hash stuff, treating all other issues as orthogonal (at least among the Schnorr-based schemes).

Let’s call this scheme ‘edshake’ for lack of a better name.  edshake differs from eddsa only in hash functions.  For the 25519 curve, we set H to be SHAKE128(M,512) or SHAKE128 with 512-bit output; for Goldilocks we use SHAKE256(M,1024).  We rely on the fact that the SHAKE functions can produce arbitrary-length output, specifying below which and how many output bytes are taken from each call to the SHAKE function H.  We also rely on SHAKE not having the length-extension weaknesses that SHA2 do; this design is likely NOT suitable for use with SHA2.

secret key expansion/elaboration:
	a = H(sk)[0:b/8]
	seed = H(sk)[b/8:2*b/8]

signing:
	r = H(m || seed || ‘r')[0:2*b/8]
	h = H(m || R || A || ‘c’)[0:2*b/8]

All else works the same as eddsa.

Key benefits:

- Simplicity of construction, leveraging both SHAKE’s lack of length-extension attacks and its ability to produce arbitrary-length output.

- Just one size of hash algorithm used for everything, for a given security parameter - in contrast with, for example, Ed25519 using SHA-512 internally but most plausibly SHA-256 for the prehash to support IUF.

- Further, just one underlying symmetric crypto primitive (Keccak-1600) supports both the 128-bit and 256-bit security modes to be matched with the 25519 vs Goldilocks curves - in contrast with SHA256 vs SHA512, which require different underlying hash function implementations.  This can reduce the size of implementations that wish to support both security strengths.

- For small messages this construction requires only two calls to the underlying hash/sponge function during signing, in contrast with the schemes that use a prehash, all of which I believe require at least three calls to the hash in total.  Of course we might not care that much about the number of hash calls for a minimum-sized signature since the public-key calculations will dominate, but we might care a little.

- The construction supports IUF efficiently without either using a prehash or running large messages through the hash function twice.  In an optimized implementation of this signature scheme, the Initialization function just initializes a single SHAKE instance, and the Update function incrementally feeds only complete blocks of the possibly-long message m into it, and caches partial blocks without immediately absorbing them.  The Finalize+Sign function then (1) clones the SHAKE state, (2) absorbs (final partial message block || seed || ‘r’) into one copy of the state to compute r, (3) computes R, (4) absorbs (final partial message block || R || A || ‘c’) into the other copy of the state to compute the Schnorr challenge h.  (Incidentally, I would prefer ‘h’ to be called ‘c’ because it’s a challenge and there are several hashes here that could as well be called ‘h', but that’s a minor point of taste.)

- In the hopefully unlikely event that a signature implementation must use an underlying Keccak/SHA3 implementation that offers no way to clone the sponge state, all is not lost.  That signature implementation can simply absorb the message twice into two separate Keccak sponge instances, which remain in lock-step throughout the message and hence still support IUF but diverge only at the end.  But this seems unlikely to be an issue for SHA3 since there aren’t so many “legacy” implementations of SHA3 out there yet.

Note: The ‘r’ and ‘c’ suffixes appended in signing are just for clean domain-separation, although I think they are actually unnecessary and could safely be dropped.  There should be a negligible probability the secret ‘seed’ could collide with (R || A), and in any case (R || A) will be twice as long as seed and thus always differentiated on length (which SHAKE’s padding and extension-attack-resistance ensures is adequate for differentiation).

Of course this construction would not provide as much conservative strength against internal collision weaknesses in the hash function as using a “double-width-pipe” hash like SHA3-256 (for curve25519) and SHA3-512 (for Goldilocks) would.  But the SHAKEs will also be faster because they process more data for each sponge function call.

In keeping with DJB’s great prototyping spirit, here is a quick patch adding edshake to signatures.py.  Since I couldn’t in 10 minutes find a handy Python implementation of SHAKE, the code rather incorrectly uses SHA2-512(M) in lieu of SHAKE128(M,512) - i.e., SHAKE128 with 512-bit output.  Again, this is just to explore potential advantages of using SHAKE as the hash and is not intended to weigh in one way or another on the many other orthogonal design issues under discussion.

Cheers
Bryan

diff --git a/ietf/cfrg/signatures.py b/ietf/cfrg/signatures.py
index 7563c17..19a48b2 100644
--- a/ietf/cfrg/signatures.py
+++ b/ietf/cfrg/signatures.py
@@ -119,13 +119,14 @@ assert expmod(I,2,q) == q-1
 assert isoncurve(B)
 assert scalarmult(B,l) == (0,1)
 
-for scheme in ['brown','eddsa','hamburg','ladd','liusvaara']:
+for scheme in ['brown','eddsa','hamburg','ladd','liusvaara','edshake']:
 
   brown = (scheme == 'brown')
   eddsa = (scheme == 'eddsa')
   hamburg = (scheme == 'hamburg')
   ladd = (scheme == 'ladd')
   liusvaara = (scheme == 'liusvaara')
+  edshake = (scheme == 'edshake')
 
   if hamburg:
     def H(m):
@@ -137,6 +138,10 @@ for scheme in ['brown','eddsa','hamburg','ladd','liusvaara']:
   if eddsa or ladd or liusvaara:
     def H(m):
       return hashlib.sha512(m).digest()
+  if edshake:
+    def H(m):
+      return hashlib.sha512(m).digest()	# XXX pretend this is SHAKE128(M,512)
+      # return somelib.shake128(m,512).digest()		# what we want
 
   if eddsa or hamburg or liusvaara:
     def prehash(m):
@@ -178,6 +183,8 @@ for scheme in ['brown','eddsa','hamburg','ladd','liusvaara']:
         a -= a % 8
         a %= 2**(b-2)
         a += 2**(b-2)
+      if edshake:
+        return a,(sk + 'r')
       return a,sk[b/8:]
   
     def secretscalar(sk):
@@ -203,6 +210,8 @@ for scheme in ['brown','eddsa','hamburg','ladd','liusvaara']:
     if liusvaara:
       m = selfdelim(hashid) + selfdelim(context) + selfdelim(prehash(m))
       rinput = '\x02' + selfdelim(seed) + m
+    if edshake:
+      rinput = m + seed + 'r'	# should pad to sponge rate
 
     if hamburg:
       r = prf(sk,rinput)
@@ -220,12 +229,14 @@ for scheme in ['brown','eddsa','hamburg','ladd','liusvaara']:
       hinput = 'CHAL' + context + pk + R + m
     if liusvaara:
       hinput = '\x03' + encodeint(b,16) + R + pk + m
+    if edshake:
+      hinput = m + R + pk + 'c'
 
     h = H(hinput)
     inth = decodeint(h)
     if brown:
       S = ((truncate(inth) + a * decodeint(R)) * linv(r)) % l
-    if eddsa:
+    if eddsa or edshake:
       S = (r + inth * a) % l
     if hamburg or ladd or liusvaara:
       S = (r - inth * a) % l
@@ -256,13 +267,15 @@ for scheme in ['brown','eddsa','hamburg','ladd','liusvaara']:
       if liusvaara:
         m = selfdelim(hashid) + selfdelim(context) + selfdelim(prehash(m))
         hinput = '\x03' + encodeint(b,16) + encodepoint(R) + pk + m
+      if edshake:
+        hinput = m + encodepoint(R) + pk + 'c'
       h = decodeint(H(hinput))
   
       if brown:
         h = truncate(h)
         h2 = decodeint(encodepoint(R))
         if scalarmult(R,S) == edwards(scalarmult(B,h),scalarmult(A,h2)): return
-      if eddsa:
+      if eddsa or edshake:
         if scalarmult(B,S) == edwards(R,scalarmult(A,h)): return
       if ladd or liusvaara:
         if R == edwards(scalarmult(B,S),scalarmult(A,h)): return