1
$\begingroup$

Currently, I have been assigned to attack a reduced version of SHA-1. What are we trying to achieve? How do we attack it?

$\endgroup$
2
  • 1
    $\begingroup$ Little search Higher-Order Differential Attack on Reduced SHA-256 and definitions are there... $\endgroup$
    – kelalaka
    Jan 13 at 21:53
  • $\begingroup$ @kelalaka I did read this paper. Unfortunately it was too difficult for me to understand. Thought someone could explain it briefly. Thanks for your help! $\endgroup$ Jan 13 at 21:56

1 Answer 1

1
$\begingroup$

The answer is not easy, however, a good starting point is Florent Chabaud and Antoine Joux's paper on SHA-0 and SHA-1

Simple Introduction

In, MD4, SHA-0,SHA-1, and SHA-2 there is a compression function. $$C:\{0,1\}^\ell \to :\{0,1\}^n$$ where $n$ is the output size and $\ell$ is the block lenght to process.

The compression function $C$ can be viewed as a block cipher where the key is the message, this is meaningful since the only part is the input. And, SHACAL is called the block cipher of the SHA-1 and similarly SHACAL-2 for SHA-2.

Now, we have a block cipher, and we have the input ( the initial values $H_i$s and the output value ( the hash - the digest). We need to find the key. If we can find the key we have pre-image attacks and collisions. This might lead one to consider that we are attacking as in the differential attacks, not exactly, but in a similar way.

The authors first started with weakened SHA-1 (SHI1) where the input expansion is not considered and the ADD is converted to X-or so that there is no non-linear part. With single bit perturbation and corrections on the inputs, they showed to find collisions with a mask.

enter image description here

Later, the only converted ADD to X-or (SHI2) to extend the attack. They find a differential mask $\mathcal{M}$ that can be applied to plaintext (input) to find collisions.

   lookRandomCollision(h, block):
      m = ramdom_message(1-block).
      h = Hash(m)
      m' = mask(m)
      h' = Hash(m')
      If h=h':
         return (m)
      else: 
         return -1

    while (1):
        success lookRandomCollision(SHA-1, 512)
        if seccess != -1:
            print("The collision pair is - ", m, mask(m))

The success of the attack is the success probability of the mask $\mathcal{M}$ to introduce collisions. If the success probability of the mask is $1/t$ then around $c\cdot t$ random pairs one will find the collision.

After these, they look at real SHA-0 and SHA-1 to find such a mask. They find one for SHA-0 with $2^{61}$-complexity time. The mask they found for SHA-1 doesn't have good complexity than the generic collision i.e it has complexity $> 2^{80}$.

The article is well written from understanding the attack from low-level compression function (no non-linear part) to higher-level function that includes non-linearity.

And, with high probability, NSA was aware of this so they modified SHA-0's input expansion on SHA-1 with an introduction of rotation.

Why is it dangerous

Consider the case as the SHA-1 is broken, we have a Prefix block(s) $P$ and Suffix block(s) $S$ and we are looking for a collision

$$Hash(P\mathbin\| m \mathbin\|S) = Hash(P\mathbin\| m' \mathbin\|S)$$

If we can find a good differential mask $\mathcal{M}$ with good probability then we can execute the attack on the block $m$. If the part of the file is part of the redundancy as in PDF files, then one can create two different PDFs that have the same hash values. A real danger, of course, requires more than this. The change in the $m'$ has an advantage for the signer. This can be doable, too.

$\endgroup$

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.