From the literature, it looks like the security proofs of sponge functions depend on how well they approximate a random permutation, Since a block cipher also ideally behaves like a random permutation does that mean strong block ciphers make for strong sponge functions?

As in, can I expect:

extern char *input,*output;
extern int input_length,output_length;

char block[16] = {0};
char key[16] = {0};
for(i = 0; i < input_length; i++) {   
    block[0] ^= input[i]
for (i = 0; i < output_length; i++) {
    output[i] = block[0];

to be a cryptographically strong sponge hash of rate 8 bits and capacity 120 bits and hence be strong against $2^{60}$ attacks?

  • 1
    $\begingroup$ What's a bit annoying here is that you need to make relatively strong assumptions about the block cipher, not just that it's a PRP. $\endgroup$ Commented Dec 9, 2014 at 12:29

1 Answer 1


I believe that, in this specific case, you are correct; it would appear to take $2^{60}$ effort to find a collision in the above function.

On the other hand, there is one nit with this approach: this makes stronger assumptions on the block cipher than is typically assumed. A block cipher behaves as a random permutation if it is keyed by a random unknown key; there is no such requirement that holds if it is keyed by a publicly known key. AES is believed to act like a random permutation even with a fixed key, however that might not hold in general. You could come up with an artificial block cipher that meets the normal requirements, but doesn't work as a sponge function.

  • $\begingroup$ I thought the general idea when doing this was to use the input as the key and encrypt the constant. $\endgroup$
    – Joshua
    Commented Dec 9, 2014 at 17:19
  • $\begingroup$ @Joshua: well, I haven't gone through the sponge proofs in detail; however as generally stated, they want a permutation, and encrypting a constant based with the current state as the key wouldn't be invertible. In addition, the same objection would remain: standard block ciphers assume that the key is unknown; allowing the key to be known (and partially influencable by the adversary) doesn't fall under this model. $\endgroup$
    – poncho
    Commented Dec 9, 2014 at 18:57
  • $\begingroup$ My mistake. The only time I reached for a sponge-like function I didn't need invertible. Also, password hashing was done by using the password as the key to encrypt the salt before true hashing was well-understood. $\endgroup$
    – Joshua
    Commented Dec 9, 2014 at 22:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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