Sign up ×
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.

Is there a known pair of distinct bit strings (A,B) such that SHA-1(A) == SHA-1(B)?

If the answer is no than how can SHA-1 be considered broken?

share|improve this question

1 Answer 1

up vote 31 down vote accepted

We call a primitive broken, if there is any attack faster than bruteforce/what we expect of an ideal primitive. Broken does not mean that there are practical attacks.

There are no known collisions in SHA-1. Still we call collision resistance of SHA-1 is broken, because there is a theoretical attack that can find collisions using fewer than $2^{80}$ calls to SHA-1.

In particular an $n$ bit hash function should have at least the following properties:

  1. $2^n$ pre-image resistance (both first and second pre-image)
    The generic attack is simply trying inputs until one fits the hash
  2. $2^{n/2}$ collision resistance
    The generic attack is generating inputs, and comparing their hashes against each other. The birthday problem tells you once you have about $2^{n/2}$ different values, two of them will likely be the same. In case of SHA-1 this that finding a collision takes about $2^{80}$ operations.

A function getting broken often only means that we should start migrating to other, stronger functions, and not that there is practical danger yet. Attacks only get stronger, so it's a good idea to consider alternatives once the first cracks begin to appear.

share|improve this answer
What's so special about the number $2^{80}$? – Andrew Tomazos Aug 30 '12 at 22:49
@Andrew Tomazos - Fathomling: Using the "birthday paradox", there's a brute force attack against any hash of length 160 bits (like SHA-1) taking $2^{80}$ operations. Anything faster is a break. – maaartinus Aug 30 '12 at 22:57
@fgrieu I think the reason people care so little is because it's a generic attack against the mode, which is used by most current(Pre-SHA-3) hashes. If there were an attack against the compression function of similar strength that'd do much more damage to the reputation of the hash. And of course the number of compression function calls an attacker needs is still around $2^n$. [btw 2 k is the number of blocks, not k] – CodesInChaos Aug 31 '12 at 9:20
@CodeInChaos: I agree with your thinking. And thanks for the correction, I wish I could edit to: this attack has merely shifted the level of pre-image resistance we expect from these hashes from $2^n$ to $\min(2^n,2^{n+1}/K)$ where K is the number of blocks allowed in the message. – fgrieu Sep 1 '12 at 12:50
There may not be known collisions, but there are freestart collisions now: – Will Sargent Oct 8 at 16:20

Your Answer


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.