Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sponge hashes like Keccak(SHA-3) and CubeHash, xor a message block into part of the internal state. Why use a reversible operation like xor for that, instead of replacing that part of the state with the message block?

  1. It clearly has no effect on pre-image and collision resistance. It's trivial to transform collisions/pre-images between the different mixing schemes.
  2. It causes some weirdness if the attacker learns the internal state of the hash. This shouldn't happen, but makes me slightly uncomfortable.
  3. Perhaps it increases security in a universal hashing scenario. Might make it impossible to construct key independent collisions. But my understanding of this is pretty foggy.
  4. When replacing it's not necessary to store that part of the state between permutations. Reduces the memory usage in some scenarios.
  5. When replacing instead of xor-ing the truncated permutation seems like a pretty normal compression function, with the sponge becoming a standard MD style construction with a tagged last block.
share|improve this question
    
I nebulously remember reading that replacing and XORing is equivalent from a security perspective. –  Paŭlo Ebermann Jan 6 '13 at 10:48
    
Replacing throws away the replaced part of the internal state. Of course, if the remaining part of the state is long enough, that might not matter, but then why bother even calculating the part you're going to replace anyway? And then you need to decide how you're going to mix the part you just replaced with the rest of the state... –  Ilmari Karonen Jan 6 '13 at 16:05
    
@IlmariKaronen "if the remaining part of the state is long enough, that might not matter" If it's not long enough, you're already doomed since in many cases(collision, preimage,...) the attacker can trivially cancel out the existing state. | "how you're going to mix the part you just replaced with the rest of the state" The same way you mix the xor-ed part of the state with the rest of the state. | For hashing where the attacker knows the whole message, replacing vs. xor-ing obviously makes no difference at all. But there are some subtle differences if some part of the message is secret. –  CodesInChaos Jan 6 '13 at 16:16
2  
My point with the last sentence was that replacement is not really "mixing" at all; it just means throwing away part of the state and using that space to store the unmixed input for some later mixing step. At some point, you'll have to combine the input and the existing state in some nontrivial way; certainly that way doesn't have to be XOR -- it could be modular addition, or multiplication, or even something like an S-box -- but it has to be something other than just replacement. XOR seems as good a choice as any to me. –  Ilmari Karonen Jan 6 '13 at 16:28
1  
Keccak alternates an unkeyed permutation of the state and injecting the message into the state. Injecting into the state means xor-ing the message block with part of the state. If you change "xor" to "replace" with no further changes the new hash would be just as secure as Keccak regarding collisions and pre-images. –  CodesInChaos Jan 6 '13 at 16:34

2 Answers 2

Section 4.3 of the paper Cryptographic sponge functions analyzes the Overwrite-mode for a sponge, which does just what you propose: instead of XORing the next part of the message into the non-hidden part of the state, replace the non-hidden part of the state by it.

They show that it can be implemented on top of the Duplex mode (which outputs the non-hidden part of the state), and for this reason has equivalent security as the usual Sponge mode (which XORs the message part), with the cost of two bits of capacity or bitrate used for padding and a frame bit.

This is also intuitively clear: All the security claims of a sponge are relative to the capacity, i.e. the size of the hidden part of the state. What you do with the non-hidden part doesn't really matter, as long as your new data somehow comes into play.

share|improve this answer
1  
Sorry to sound negative, but I don't think this really answers the question? It provides a useful side-point, but doesn't do anything towards explaining why xor over replacement (just that as far as the proof goes they're interchangeable) –  figlesquidge Feb 3 at 11:55

As a simplified case, consider a sponge hash function made from an ideal 160-bit block cipher with a 256-bit key, and mixes in a 32-bit word each round. It would be better to use an LFSR to generate the sequence of keys for each round, but let's say this simplified hash function is

$$ \begin{align} H(0) &= 0 \\ H(N) &= E(0, H(N-1) \oplus \mathtt{words}[N-1]) \\ \end{align} $$

where $\oplus$ is 160-bit exclusive-or and words[] is the message suitably padded and represented as an array of 32-bit integers.

You're correct that this construction provides 128-bits of state that an attacker can't directly manipulate. Now, consider the sequence of states generated by hashing a very long message where each $\mathtt{word}[ N ]$ is identical (say zero). This construction will, after an average of $2^{80}$ steps enter into a cycle with an average length of $2^{80}$ steps. That is, it will act as an ideal permutation of 160-bit values. Note that for a fixed value of the final word in the words array, there are $2^{160}$ possible values for the final $H$ hash value.

Consider the alternative construction $$ \begin{align} G(0) &= 0 \\ G(N) &= E(0, \mathsf{mask128}( G(N-1) ) \oplus \mathtt{words}[ N-1 ] ) \\ \end{align} $$

where $\mathsf{mask128}(V)$ returns a copy of $V$ with its least significant 32 bits all set to zero. This is equivalent to the remove-instead-of-xor case.

Consider again how this $G$ function behaves when words is a very long sequence of identical values. After an average of $2^{64}$ iterations, it will go into a cycle of size $2^{64}$. In other words, it acts as a random permutation of 128-bit values. Note that for a constant value of the final word in the words array, there are only $2^{128}$ possible final $G$ hash values. (The possible final $G$ hash values are the values for which $D(0, G(N-1)) \mathbin\& (2^{32}-1) = \mathtt{word}[N-1]$ where $\&$ is bitwise and.)

Consider the following attack that generates two messages $M$ and $M'$ with identical hash values (a weak collision of the hash): begin with $K$ and $K'$, the beginnings of the two messages you want to collide. Generate $K$ from $M$ by appending 320 random bits (call this the $K$-seed), and then iteratively append a constant 32-bit word (say zero). Do the same to generate $K'$ from $M$ using random $K'$-seeds. Keep a mapping $J$ of $H(M)$ hash values to the $K$-seed values (and number of appended words) that generated them and a mapping $J'$ of $H(M')$ values to the $K'$-seed values (and number of appended words) that generated them. Stop as soon as $J$ and $J'$ have one key in common. You have found a week collision on $H$ or $G$.

The average complexity of this attack for $H$:
An average of $2^{80}$ values in $J$ and $2^{80}$ values in $J'$. This means a work factor of $2^{81}$ in time and $2^{81}$ in space required.

The average complexity of this attack for $G$:
An average of $2^{64}$ values in $J$ and $2^{64}$ values in $J'$. This means a work factor of $2^{65}$ in time and $2^{65}$ in space required.

Now, the work factor of the attack against $H$ can be brought down to $2^{65}$ by choosing a value of $\mathtt{word}[N-1]$ that has a constant value when XOR-ed with the least significant bits of $H(N-1)$.

We see that for an active attacker, this simple attack isn't any more difficult against $H$ than $G$. However, for non-adversarial uses (for instance, checksumming and de-duplicating long constant-length documents with a constant 32-bit footer) $H$ is superior to $G$, and there may arise other real-world use cases where an attacker is similarly constrained in the values he or she may inject into the words[] array. Using replace-instead-of-XOR may be the tiniest of footholds to give an attacker, but there's no reason to give an attacker even such a tiny foothold.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.