Tell me more ×
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.
up vote 11 down vote favorite

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

If the answer is no than how can SHA1 be considered broken?

share|improve this question

1 Answer

up vote 14 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}$? – user1131467 Aug 30 '12 at 22:49
2  
@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
As for alternatives, SHA-3 is just around the corner, so hang in there! – Thomas Aug 31 '12 at 2:13
Collision resistance to $2^{n/2}$ level is much more desirable for a hash than pre-image resistance to $2^n$ level is. That second property does not hold for many real-life hashes, including MD5, SHA-0, SHA-1, SHA-2, and that's known (refs here) since 1999 at least; yet these hashes have seldom been considered seriously broken for this reason. This attack has merely shifted the level of pre-image resistance we expect from these hashes from $2^n$ to $2^{\min(n,n-k+1)}$ where $k$ is the number of blocks allowed in the message. – fgrieu Aug 31 '12 at 6:45
2  
@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
show 1 more 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.