<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><br><div><div>On Jul 17, 2014, at 6:44 AM, David Leon Gil <<a href="mailto:coruus@gmail.com">coruus@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div dir="ltr">And, just to make sure I'm understanding this right:<div><br></div><div><div>Assume a 32B protokey and Shake256 as the hash function. The best generic attacks on the signature scheme:</div><div><br></div>

<div>- Time: 2^256</div><div>  - Distinguish Goldilock keys from random elements of q448</div><div>  - Recover protokeys from public keys or signature nonces</div><div>- Time: 2^256</div><div>  - Find a pair of messages such that S(m0) == S(m1'), such that,</div>

<div>    if m0 and m1 are messages chosen to satisfy properties P0 and P1,</div><div>    m1' == m1||p1, where p1 is a block of 'rate' bytes indistinguishable from       random bytes.</div><div>- Time: ~2^224</div>

<div>  - Solve discrete logarithm problem in q448</div></div></div></blockquote><br><div>This looks right, though I don’t know what properties P0 and P1 are.</div><br><blockquote type="cite"><div dir="ltr"><div>So I think that I'm fairly happy with Shake256 (but obviously wouldn't be with Shake128), even if the scheme doesn't provide additional collision resistance.</div>

<div><br></div><div>(SHA3-224 is standardized, but there's no equivalent Shake instance. Since signatures don't need more than 56 bytes of output, it would be fine to use that instead of Shake256.)</div><div><br>
</div>
<div>----</div><div><br></div><div>There's a rather speculative potential benefit to deriving nonceg as</div><div><br></div><div>     H(privatekey || message)</div><div><br></div><div>which is that -- if a non-generic attack on Shake256 can produce collisions with cost <<< 2^224 -- you could then prove that you *didn't* sign one half of a colliding message by revealing the private key.</div>

<div><br></div><div>The probability of such an attack existing seems too low for this dubious benefit.</div></div></blockquote><div><br></div><div>I think this is pretty speculative, since you can always make an exception to your nonce computation for that one risky message.</div><div><br></div><div>Also, if you compute the challenge as H(nonceg || pubkey || message) or similar, then a collision attack isn’t enough.  This is a nice property even though the generic collision attack is slower than DL.</div><br><blockquote type="cite"><div dir="ltr"><div>-----</div><div><br></div><div>The advantage of doing everything message-first I forgot to mention: Suppose that you put private keys in a crypto coprocessor of some sort (or on another server). You can sign messages of arbitrary length by only transmitting 200 bytes of data (the sponge state after absorbing the message).</div></div></blockquote><div><br></div><div>Hm, that’s a good point.</div><div><br></div><div>— Mike</div><br><blockquote type="cite"><div class="gmail_extra"><div class="gmail_quote">On Wed, Jul 16, 2014 at 10:07 PM, David Leon Gil <span dir="ltr"><<a href="mailto:coruus@gmail.com" target="_blank">coruus@gmail.com</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<span>Thank you! I stand corrected (and also saved the trouble of writing a note retracting my silly argument).<div><br></div>
<div>(And thank you for the links.)<br><div><br></div>
<div>Best,</div>
<div><br></div>
<div>David</div>
</div></span><div>—<br>Sent using alpine: an Alternatively Licensed Program for Internet News and Email</div><div class="HOEnZb"><div class="h5">
<br><br><div class="gmail_quote"><p>On Wed, Jul 16, 2014 at 8:57 PM, Michael Hamburg <span dir="ltr"><<a href="mailto:mike@shiftleft.org" target="_blank">mike@shiftleft.org</a>></span> wrote:<br></p><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">


<div>Top replying!  I believe that the birthday attack still applies.</div>
<div><br></div>
<div>The state is divided into two pieces, of sizes $rate and $capacity = $statesize - $rate.  The message blocks are xor’d into the $rate-sized piece, but the $capacity-sized piece is not changed.</div>
<div><br></div>
<div>If the attacker can find two messages mA and mB which cause a collision on the $capacity-sized piece, he can set the message blocks for the next round to set the $rate-sized pieces of stateA and stateB to anything he wants (in particular, to the same thing), thereby causing a collision on the entire state.</div>


<div><br></div>
<div>This birthday attack requires 2^($capacity/2) work and storage.  There’s probably also a rho attack which requires less storage.</div>
<div><br></div>
<div>So postfixing with the nonce or key doesn’t help.</div>
<div><br></div>
<div>Cheers,</div>
<div>— Mike</div>
<br><div>
<div>On Jul 16, 2014, at 5:46 PM, David Leon Gil <<a href="mailto:coruus@gmail.com" target="_blank">coruus@gmail.com</a>> wrote:</div>
<br><blockquote type="cite">
<div dir="ltr">> Certainly not if you hash the message first.  That drops security to 128<br>> bits vs collision attacks.  Even if those attacks aren’t realistic, that’s<br>> pretty far below the design security of the system.<br>

<div>
<h1 style="font-family:Times"><font size="4">The use of sponge functions in keyed modes</font></h1><p style="font-family:Times;font-size:inherit">

So, as I understand it, this isn't true for sponge functions: a collision in message hashs does not imply a collision in nonce-postfixed message hashs.</p><p style="font-family:Times;font-size:inherit">

Here's why (very informally):</p><p style="font-family:Times;font-size:inherit">(Apologies for the detail, but I figure that it might be useful to users on the list less familiar with this area.)</p>
<h2 style="font-family:Times">

<font style="font-weight:normal" size="4">Background: Merkle-Damgard</font>
</h2><p style="font-family:Times;font-size:inherit"><em>Merkle-Damgard.</em> Each update step consumes a message block and outputs an IV for the next message block.</p><p style="font-family:Times;font-size:inherit">Thus, if H(m) == H(n), then H(m || g) == H(n || g). (So a message collision implies a collision in nonce-postfixed messages if len(m) == len(n).)</p><p style="font-family:Times;font-size:inherit">

So, this is why, if I did this reordering with SHA2-512, the resulting signature scheme would not be collision-resistant.</p><p style="font-family:Times;font-size:inherit"><em>Sponge functions.</em> Just to recall the definitions, in Python-like pseudocode for clarity (and omitting the padding rule),</p>

<pre><code>class Sponge(object):
  def __init__(permutation, rate):
    state = zeros(permutation.blocksize)
    capacity = permutation.blocksize - rate
    position = 0
  def absorb(bytes):
    i = 0
    while i < len(bytes):
      if position == (rate - 1):
         permutation(state)
         position = 0
      state[position] ^= bytes[i]
      i++; position++
  def squeeze(length):
    i = 0
    out = ''
    while i < length:
      if position == (rate - 1):
        permutation(state)
        position = 0
      i++; out += state[position]
    return out</code></pre><p style="font-family:Times;font-size:inherit">So, note what's happening here: Each block of the message is absorbed into at most <em>rate</em> bytes of the sponge. Every time <code>rate</code> bytes is filled, the permutation is applied. When the sponge is squeezed, at least <em>capacity</em> bytes of the sponge's state is hidden.</p>



<h2 style="font-family:Times"><font size="4" style="font-weight:normal">Sponge functions</font></h2>
<h3 style="font-family:Times">Hash collisions</h3><p style="font-family:Times;font-size:inherit">Let's define a hash collision in the usual way; two messages for which the hash output is the same value. So, here's how a sponge derives a hash:</p>
<pre><code>msponge = Sponge(keccak, 200 - 64)           # shake128
msponge.absorb(message)
mhash = sponge.squeeze(64)</code></pre><p style="font-family:Times;font-size:inherit">(And so, in this case, the resulting hash has 256-bits of collision resistance.)</p><p style="font-family:Times;font-size:inherit">

So, if what I did with the sponge was this,</p>
<pre><code>csponge = challenge_sponge = Sponge(keccak, 200 - 64)
csponge.absorb(mhash)
csponge.absorb(gnonce)
challenge = sponge.squeeze(64)</code></pre><p style="font-family:Times;font-size:inherit">a message collision <em>would</em>, just as in the MD-case, imply a challenge collision.</p><p style="font-family:Times;font-size:inherit">

(Call the colliding message <code>mess</code>.)</p>
<h3 style="font-family:Times">Collision-resistant signatures</h3><p style="font-family:Times;font-size:inherit">

But here's what's happening in the code (simplified to omit the pubkey and DS):</p>
<pre><code>sponge = Sponge(keccak, 200 - 64)  # shake256
sponge.absorb(message)
sponge.absorb(gnonce)
challenge = sponge.squeeze(64)</code></pre><p style="font-family:Times;font-size:inherit">(The sponge retains its full 200 byte state between absorb calls.)</p><p style="font-family:Times;font-size:inherit">

If</p>
<pre><code>(sponge.absorb(message).absorb(gnonce)
 == sponge.absorb(mess).absorb(gnonce))</code></pre><p style="font-family:Times;font-size:inherit">then the states must collide, i.e.,</p>
<pre><code>sponge.absorb(message).state == sponge.absorb(mess).state</code></pre><p style="font-family:Times;font-size:inherit">But the state is 200 bytes; the probability of a message that produces a <em>hash</em> collision also producing a <em>state</em> collision is extremely small.</p><p style="font-family:Times;font-size:inherit">(There are obviously generic attacks with cost 2^512 in this case that find a colliding squeezed output.)</p><p style="font-family:Times;font-size:inherit">

So this is essentially the argument for Shake256 providing 2^512 security strength in this mode of operation; and for Shake128 providing 2^256 security strength.</p><p style="font-family:Times;font-size:inherit">

I, too, am somewhat conservative: Shake256 is fast enough for most applications. (It is, I believe, still somewhat faster than SHA2-512.) So, happy with that.</p><p style="font-family:Times;font-size:inherit">

And I'll follow up with some citations to the security proofs that are less-handwavy, but more mathemetical in the next couple of days.</p><p style="font-family:Times;font-size:inherit">So...does this make sense?</p>

</div>
</div>
</blockquote>
</div>
<br></blockquote></div><br></div></div></blockquote></div><br></div>
</blockquote></div><br></body></html>