I'm preparing for a exam in crypto course, and i'm doing some practice problems.
I'm now playing with this problem:
A certain organization tried to modify the Merkle-Damgard construction:
In this construction ∧ is a bit-by-bit and. The IV is fixed and public in both constructions. Suppose f is a collision resistant compression function that takes a 512 bit message block, and a 512 bit chaining value. The function outputs a 512 bit result. Show that is is not collision resistant
So I know that it uses bitwise and, which I think is probably the central design flaw.
After playing with bitwise and for a little bit, I notice that if I take a random bitstring and perform bitwise and with a bitstring of only 1's, then it just outputs the bitstring of ones.
So if I pick two message of lentgh:
Which in binary is just 512 one's, then the final bitwise and that takes place, will just render a bitstring of 512 1's.
So I pick these two messages m1 and m0 of that specific length (I'm not completely sure that that is doable) and try hashing them with this construction.
This means that for the hashing of m1 and m0, the result will be two applications of
This way these two messages should render the same hashed values, thus causing a collision.
Does my attack make sense? can someone come up with something better?
Now, I just realized (were told) that I have free access to the IV .
So, I still need two messages of the same length, and I make the messages have a length of 512 bits.
one message, m0, is just the complete opposite of the IV. That means if the IV was "1010" then m0 would be "0101". Then the resulting bitstring, would just be zeros.
The other message, m1, is just a bitstring of zeros. since a bitwise and, and only result in "1" when two one's are present, the entire resulting bitstring will also be zeros.
Since the two messages are the samme length, the padding block will have no effect.