3
$\begingroup$

Given the following preconditions:

  • A plaintext A (~512bit length), that is hashed by using SHA-1 and truncated to (the first) 64 bits.
  • I know both, the plaintext and the truncated hash, and want to perform a Second Preimage Collision Attack.
  • Furthermore, a part of the new plaintext B, that should produce the same (truncated) hash value, is fixed (the same as in plaintext A), the remainder can be choosen randomly.

Are there any increased weaknesses when truncating SHA1 to the first 64 bits only (besides the decreased number of bits)?

Are there any other circumstances (like controlling a whole block of 512 bits, equality of both plaintexts in all but one word, controlling the last block, etc.), that could interfere with the truncation, so that there are further weaknesses that could facilitate the cracking?

Are there any attacks against SHA-1, that aim for a Second Preimage Resistance Attack?
Most of what I found were birthday attacks (that could increase the possibilty to find a collision from $1/(2^{80})$ to $1/(2^{60})$). I understand, that a preimage attack on full SHA-1 is not feasible, but a theoretical attack could help me to make the cracking of the partial hash possible.

The required number of tries to find a collision on this hash with a probability of 50% is $2^{63}$, right? This would take around 150 years on a single GPU.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Given message $A$, you have to find message $B$, such that the first 64 bits (say, MSB) of their hashes collide: $$ MSB_{64}(H(A)) = MSB_{64}(H(B)) $$

This problem is called Second Preimage Search for the function $MSB_{64}(H)$, or Partial Second Preimage Search for the hash function $H$ alone.

When $H$ is the full round SHA-1, there is no result, theoretical or practical, that would allow you to do it faster than by trying $2^{64}$ (on average) arbitrary strings for $B$. Clearly, your third restriction does not make the things easier, but still, you need to brute-force $2^{64}$ messages to solve the problem.

Improve this answer
$\endgroup$
1
  • $\begingroup$ $2^{64}$ is much less than would be recommendable currently. For instance, NIST recommendation for security level to use (starting in beginning of 2014) is at least 112 bits. This is because a search of $2^{64}$ is small enough that it may be within reach of some very large organizations. $\endgroup$
    – user4982
    Dec 16, 2013 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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