7

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++) {   
    AES128_ecrypt(key,block,block);
    block[0] ^= input[i]
}
for (i = 0; i < output_length; i++) {
    AES128_encrypt(key,block,block);
    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?

otus
  • 32,132
  • 5
  • 70
  • 165
John Meacham
  • 385
  • 1
  • 8
  • 1
    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. – CodesInChaos Dec 09 '14 at 12:29

1 Answers1

9

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.

poncho
  • 147,019
  • 11
  • 229
  • 360
  • I thought the general idea when doing this was to use the input as the key and encrypt the constant. – Joshua Dec 09 '14 at 17:19
  • @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. – poncho Dec 09 '14 at 18:57
  • 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. – Joshua Dec 09 '14 at 22:12