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?

  • $\begingroup$ This question was part of a facebook group on cyber security and nobody seems to know the correct answer $\endgroup$ – 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.

  • 5
    $\begingroup$ 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$. $\endgroup$ – fgrieu Apr 12 '20 at 20:03
  • 1
    $\begingroup$ @fgrieu that is brilliant. I've added them. Thanks. $\endgroup$ – kelalaka Apr 12 '20 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.