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?
$\begingroup$
$\endgroup$
2
asked Aug 30, 2012 at 22:00
-
7$\begingroup$ We finally have an actual collision in SHA-1 $\endgroup$– CodesInChaosFeb 24, 2017 at 12:50
-
$\begingroup$ The link for shatter.io quesion Does “Shattered” actually show SHA-1-signed certificates are “unsafe”? $\endgroup$– kelalakaNov 20, 2018 at 19:45
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
8
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:
- $2^n$ pre-image resistance (both first and second pre-image)
The generic attack is simply trying inputs until one fits the hash - $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.
answered Aug 30, 2012 at 22:26
-
$\begingroup$ What's so special about the number $2^{80}$? $\endgroup$ Aug 30, 2012 at 22:49
-
7$\begingroup$ @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. $\endgroup$ Aug 30, 2012 at 22:57
-
6$\begingroup$ @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] $\endgroup$ Aug 31, 2012 at 9:20
-
1$\begingroup$ @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. $\endgroup$– fgrieu ♦Sep 1, 2012 at 12:50
-
4$\begingroup$ There may not be known collisions, but there are freestart collisions now: sites.google.com/site/itstheshappening $\endgroup$ Oct 8, 2015 at 16:20
$\begingroup$
$\endgroup$
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.
See also:
