<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 id="the-use-of-sponge-functions-in-keyed-modes" style="color:rgb(0,0,0);font-family:Times"><font size="4">The use of sponge functions in keyed modes</font></h1><p style="color:rgb(0,0,0);font-family:Times;font-size:medium">
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="color:rgb(0,0,0);font-family:Times;font-size:medium">
Here's why (very informally):</p><p style="color:rgb(0,0,0);font-family:Times;font-size:medium">(Apologies for the detail, but I figure that it might be useful to users on the list less familiar with this area.)</p><h2 id="background-merkle-damgard" style="color:rgb(0,0,0);font-family:Times">
<font style="font-weight:normal" size="4">Background: Merkle-Damgard</font></h2><p style="color:rgb(0,0,0);font-family:Times;font-size:medium"><em>Merkle-Damgard.</em> Each update step consumes a message block and outputs an IV for the next message block.</p>
<p style="color:rgb(0,0,0);font-family:Times;font-size:medium">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="color:rgb(0,0,0);font-family:Times;font-size:medium">
So, this is why, if I did this reordering with SHA2-512, the resulting signature scheme would not be collision-resistant.</p><p style="color:rgb(0,0,0);font-family:Times;font-size:medium"><em>Sponge functions.</em> Just to recall the definitions, in Python-like pseudocode for clarity (and omitting the padding rule),</p>
<pre style="color:rgb(0,0,0)"><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="color:rgb(0,0,0);font-family:Times;font-size:medium">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 id="sponge-functions" style="color:rgb(0,0,0);font-family:Times"><font size="4" style="font-weight:normal">Sponge functions</font></h2><h3 id="hash-collisions" style="color:rgb(0,0,0);font-family:Times">Hash collisions</h3>
<p style="color:rgb(0,0,0);font-family:Times;font-size:medium">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 style="color:rgb(0,0,0)">
<code>msponge = Sponge(keccak, 200 - 64) # shake128
msponge.absorb(message)
mhash = sponge.squeeze(64)</code></pre><p style="color:rgb(0,0,0);font-family:Times;font-size:medium">(And so, in this case, the resulting hash has 256-bits of collision resistance.)</p><p style="color:rgb(0,0,0);font-family:Times;font-size:medium">
So, if what I did with the sponge was this,</p><pre style="color:rgb(0,0,0)"><code>csponge = challenge_sponge = Sponge(keccak, 200 - 64)
csponge.absorb(mhash)
csponge.absorb(gnonce)
challenge = sponge.squeeze(64)</code></pre><p style="color:rgb(0,0,0);font-family:Times;font-size:medium">a message collision <em>would</em>, just as in the MD-case, imply a challenge collision.</p><p style="color:rgb(0,0,0);font-family:Times;font-size:medium">
(Call the colliding message <code>mess</code>.)</p><h3 id="collision-resistant-signatures" style="color:rgb(0,0,0);font-family:Times">Collision-resistant signatures</h3><p style="color:rgb(0,0,0);font-family:Times;font-size:medium">
But here's what's happening in the code (simplified to omit the pubkey and DS):</p><pre style="color:rgb(0,0,0)"><code>sponge = Sponge(keccak, 200 - 64) # shake256
sponge.absorb(message)
sponge.absorb(gnonce)
challenge = sponge.squeeze(64)</code></pre><p style="color:rgb(0,0,0);font-family:Times;font-size:medium">(The sponge retains its full 200 byte state between absorb calls.)</p><p style="color:rgb(0,0,0);font-family:Times;font-size:medium">
If</p><pre style="color:rgb(0,0,0)"><code>(sponge.absorb(message).absorb(gnonce)
== sponge.absorb(mess).absorb(gnonce))</code></pre><p style="color:rgb(0,0,0);font-family:Times;font-size:medium">then the states must collide, i.e.,</p><pre style="color:rgb(0,0,0)"><code>sponge.absorb(message).state == sponge.absorb(mess).state</code></pre>
<p style="color:rgb(0,0,0);font-family:Times;font-size:medium">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="color:rgb(0,0,0);font-family:Times;font-size:medium">(There are obviously generic attacks with cost 2^512 in this case that find a colliding squeezed output.)</p><p style="color:rgb(0,0,0);font-family:Times;font-size:medium">
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="color:rgb(0,0,0);font-family:Times;font-size:medium">
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="color:rgb(0,0,0);font-family:Times;font-size:medium">
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="color:rgb(0,0,0);font-family:Times;font-size:medium">So...does this make sense?</p>
</div></div>