Why is SHA-1 considered broken?

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

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

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.

Even when there were no known collisions in SHA-1, we still called collision resistance of SHA-1 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.

• 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: sites.google.com/site/itstheshappening – Will Sargent Oct 8 '15 at 16:20

Yes, it is considered broken since SHA-1 collision has been found. On 23 February 2017, Google announced the first SHA-1 public collision using the SHAttered attack (100k faster than the brute force attack). The collision was demonstrated on two different PDF files. Therefore it is considered broken. 