1
$\begingroup$

I am using AES-CBC as a hash function which is encrypting a block of length n. The blocks, m = (m1, m2, ..., mn). The IV is one block long and the encryption key is length 128, 192 or 256 bits.

Will I get collisions? And if so, how could I find examples?

I expect to find collisions every 2^(n/2) hashes but I don't imagine this would allow me to find any matches in the next 10000000 years.

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ Welcome to Cryptography.SE. What is the origin of this question? Why do you need to hash with PRP instead of a PRF? Consider that how many AES-CBC encryptions your machine can execute in one second then you can decide the necessary time on a single machine while omitting to build a hashTable to find the collision effectively. $\endgroup$
    – kelalaka
    Commented Nov 4, 2021 at 21:32
  • 1
    $\begingroup$ Interestingly, if you only encrypt one block, what will you get? $\endgroup$
    – kelalaka
    Commented Nov 4, 2021 at 21:37
  • $\begingroup$ With AES, the hash will be the ciphertext of the last message block. Will it be dependent on finding a hash every 2^(n/2) or every 2^(128|192|256)/2?? $\endgroup$
    – jongjena
    Commented Nov 4, 2021 at 21:39
  • 1
    $\begingroup$ A block cipher is a family of permutations where a key selects one of the permutations. That is the real effect of the secret key!. So you have a fixed permutation. $\endgroup$
    – kelalaka
    Commented Nov 4, 2021 at 21:44
  • 1
    $\begingroup$ Ah I see, as AES is an injective function I suppose there wouldn't be any collisions but this slide I found indicates otherwise. What is your interpretation? Page 73. ce.sharif.edu/~b_momeni/ce441/15-crypto-sym.pdf $\endgroup$
    – jongjena
    Commented Nov 4, 2021 at 21:48

1 Answer 1

Reset to default
2
$\begingroup$

I am using AES-CBC as a hash function which is encrypting a block of length n. The blocks, m = (m1, m2, ..., mn). The IV is one block long and the encryption key is length 128, 192 or 256 bits.

Questions:

  • What is the key? Is it fixed in advance, or is it something secret? BTW: if it's 'something secret', you don't have a standard hash function (where the entire descryption is public; you may have a MAC, but see below).

  • What is the hash output? Is it the entire encrypted message, or is it just the last block.

Here are the possibilities:

  • If the key is fixed in advance, and the hash is the entire encrypted message, then of course you will never have a collision (because you can decrypt and get the original message back - you couldn't do that if there were a collision). Of course, a hash that is as long as the original message isn't very interesting.

  • If the key is fixed in advance, and the hash is the last block, then it is easy to create collisions (and preimages) - all the attacker needs to do to generate a preimage is formulate the message (except for one block), insert the known start state (IV) and final state (the target hash), and work toward the middle - the necessary state of that one unspecified block can easily be found.

  • If the key is unknown and the hash is the last block, this is actually the construction known as CBC-MAC. For fixed length messages, it's a decent message authentication code - however, if the attacker can vary the message length, he can come up with forgeries and collisions.

Improve this answer
$\endgroup$

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.