Tell me more ×
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.
up vote 4 down vote favorite
1

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 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 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 at 16:16
1  
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 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 at 16:34

1 Answer

up vote 1 down vote

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

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.