# Why would this algorithm be vulnerable to a preimage attack?

If I created this algorithm:

Break the message $$M$$ up into $$n$$ blocks $$m_1,\ldots,m_n$$ of 512 bits each.

Compute the hash by alternating AND and OR operations on the blocks. More specifically:

• The first block and the second block are combined using AND
• The result is combined with the third block using OR
• The result is combined with the fourth block using AND
• The result is combined with the fifth block using OR • and so on…

In other words, $$h(M) = (\ldots(((m_1 \wedge m_2) \vee m_3) \wedge m_4) \vee m_5) \ldots )$$

Why would this be vulnerable to a preimage attack?

• This question was part of a facebook group on cyber security and nobody seems to know the correct answer – Brooney Apr 12 '20 at 14:20

Firstly, remember what is the pre-image attack*;

• The pre-image attack is that given a hash value $$h$$ one need to find an $$x$$ such that $$h = \operatorname{Hash}(x)$$. The founded value doesn't need to be the pre-image that is used for the given hash value rather it can be any input value that its hash matches the given hash value, i.e. $$x' \neq x$$ and $$h = \operatorname{Hash}(x')$$.

Let call $$\operatorname{H}_\ell (M) = (\ldots(((m_1 \wedge m_2) \vee m_3) \wedge m_4) \vee m_5) \ldots [\vee|\wedge]\, m_{n-2})$$ i.e words just before the last two operation. And

$$\operatorname{H}(M) = \big(\operatorname{H}_\ell (M) [\vee|\wedge]\, m_{n-1}\big) [\vee|\wedge]\, m_n$$

The number of the blocks determines the order of the last two operations, the $$\vee$$ is the last or $$\wedge$$.

Now the trick is that

• by using $$\wedge$$ you can make any bit zero $$x \wedge 0 =0$$ and
• by using $$\vee$$ you can make any bit one $$x \vee 1 =1$$.

Therefore only using the last two blocks - actually using only two blocks - the attacker can create any hash value.

There are much more simple attacks as a note by Fgriue:

• $$h = \operatorname{H}(h)$$
• $$h = \operatorname{H}(h\mathbin\|h)$$ since $$h = h \wedge h$$
• $$h = \operatorname{H}(1^n\mathbin\|h)$$ since $$h = 1^n \wedge h$$
• $$h = \operatorname{H}(h\mathbin\|h\mathbin\|h)$$ since $$h = (h \wedge h) \vee h$$
• $$h = \operatorname{H}(\bar h\mathbin\|h\mathbin\|h)$$ since $$h = (\bar h \wedge h) \vee h$$

* The formal definition can be found in this seminal work Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance by P. Rogaway and T. Shrimpton.

• Yes. The simplest preimage attack is that $H(h)=h$. Others are that $H(h\mathbin\|h)=h$, $H(1^n\mathbin\|h)=h$, $H(h\mathbin\|h\mathbin\|h)=h$, $H(\bar h\mathbin\|h\mathbin\|h)=h$. – fgrieu Apr 12 '20 at 20:03
• @fgrieu that is brilliant. I've added them. Thanks. – kelalaka Apr 12 '20 at 20:15