Breaking merkle damgård construction that uses bitwise and?

Question

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

My solution

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:

13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084095

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 f(1*512).

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?

Second attempt

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.

Answer 1

Collision attack is finding distinct messages $x$ and $y$ such that these two messages has the same hash value; $hash(x) = hash(y)$. There is no restriction on the length of the $x$ and $y$.

For a hash function with output size $\ell$, the generic cost of finding a colliding pair is $\mathcal{O}(2^{\ell/2})$-time with 50% probability. This is due to the birthday attack.

First block collision

By playing with the first block of a message we can find colliding pairs easily. For example, if the first bit of the IV is zero then two messages

• $m_1= 0\mathbin\| \text{rest of the message}$
• $m_2= 1\mathbin\| \text{rest of the message}$

is an example of collision since $0 \wedge 0 = 0$ and $0 \wedge 1 = 0$. Therefore the compression function will have the same inputs. If the first bit is not zero, apply it in the position where it has the first zero. This attack can be applied to any position where the IV has a zero.

Actually, we can find many collision pairs, easily. There are $2^k-1$ pairs for an IV that has $k$ zeroes.

Identical prefix collision

It is possible to play with the other blocks, too. Just keep the first block the same, and calculate the first compression, then the IV to the second block is the output of the first.

• $m_1= \text{prefix}\mathbin\| \text{block to collide 1}\mathbin\| \text{rest of the message}$
• $m_2= \text{prefix}\mathbin\| \text{block to collide 2}\mathbin\|\text{rest of the message}$

The same attack as in the first block collision applies here, too. No, difference.

Distinct prefix collision

Also, different prefix message collision is possible. Just calculate the compression of the prefixes, and try to collide the input with the next compression by using the AND's property.

• $m_1= \text{prefix 1 may be longer}\mathbin\| \text{block to collide 1}\mathbin\| \text{rest of the message}$
• $m_2= \text{prefix 2}\quad\quad\quad\quad\quad\quad\;\mathbin\| \text{block to collide 2}\mathbin\|\text{rest of the message}$

This is harder to achieve than the first block collision.