Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

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.

share|improve this answer
    
$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. –  user4982 Dec 16 '13 at 16:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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