Join Log in
Score:1
avatar Crypto

AES-CBC Hash Function Collision Resistance

mp flag
jongjena

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.

277
0 + 0
aes
cbc
kelalaka avatar
in flag
kelalaka
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.
2
Reply
kelalaka avatar
in flag
kelalaka
Interestingly, if you only encrypt one block, what will you get?
1
Reply
mp flag
jongjena
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??
0
Reply
kelalaka avatar
in flag
kelalaka
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.
1
Reply
mp flag
jongjena
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. http://ce.sharif.edu/~b_momeni/ce441/15-crypto-sym.pdf
1
Reply
kelalaka avatar
in flag
kelalaka
If you encrypt one block, there is no collision, however, after one block, you will have.
0
Reply
mp flag
jongjena
The collisions are between the last ciphertext blocks on two plaintext messages. I'm not sure I follow
0
Reply
mp flag
jongjena
Ty v much :) +20 social credits
0
Reply
Score:2
poncho avatar Crypto
my flag
poncho

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.

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.