1
$\begingroup$

I understand that the following is becoming feasible, or already is:

Find any 2 data (d1 and d2), for which SHA1(d1) = SHA1(d2)

However, it is not entirely clear to me if there is evidence of the feasibility of:

Find d2 for a specific d1, such that SHA1(d1) = SHA1(d2)

My difficulty in understanding the available literature is that I typically see the attack referred to as "seeking collisions" rather than "seeking a collision"; implying that what is being identified is two data that happen to share a SHA-1, rather than finding a datum which shares the same SHA-1 as a specific target datum.

EDIT: My question is partially redundant to, though more specific in purpose than, this question Second pre-image resistance vs Collision resistance

Improve this question
$\endgroup$
3
  • $\begingroup$ By the way: withstanding the second attack is known as second preimage resistance. $\endgroup$
    – yyyyyyy
    Commented Jan 15, 2015 at 7:22
  • 1
    $\begingroup$ Thanks, I found another question thread using the specific term you provided. $\endgroup$
    – NickBorgers
    Commented Jan 15, 2015 at 18:53
  • $\begingroup$ @yyyyyy : $\;\;\;$ Yes, but incorrectly, since for second preimage resistance, d1 is chosen uniformly at random from the set of strings whose length is length(d0) (where d0 is the adversary's initial output). $\:$ In particular, any collision trivially allows one to find a d1 and an easy way to perform the OP's task for that d1. $\;\;\;\;\;\;\;$ $\endgroup$
    – user991
    Commented Jan 16, 2015 at 1:40

1 Answer 1

Reset to default
2
$\begingroup$

That's true. There should not be any publicly known attack on SHA-1 that allows for a given $d1$ to find a $d2$ such that $h(d1) = h(d2)$.

SHA-1 is vulnerable for finding a pair of $d1$ and $d2$ such that $h(d1) = h(d2)$.

The same, however, applies to MD5, which is unusable for SSL/TLS certificates and a successful attack has been performed. So, this kind of collision can allow (under some circumstances) more that you might think.

The notable difference between SHA-1 and MD5 attacks is the cost of such attacks. For MD5, the attack is very fast. For SHA-1, the attack would be very expensive, but for some groups (e.g. governments) feasible.

(There might be also some more differences that I am not aware of. However, both of them use the Merkle–Damgård construction, which implies some common security characteristics.)

Improve this answer
$\endgroup$
11
  • $\begingroup$ Interesting, I hope others weigh in to confirm. Related to the cost distinction, do you think it is more attributable to the additional 32 bits of length for a SHA-1 hash or the essential weakness in MD5's collision-resist characteristics? $\endgroup$
    – NickBorgers
    Commented Jan 14, 2015 at 19:49
  • $\begingroup$ Added a note about Merkle–Damgård construction. $\endgroup$
    – v6ak
    Commented Jan 14, 2015 at 20:26
  • $\begingroup$ @user2700751: Hmm… Just some intuition: The additional 32 bits would likely make it harder just $2^{16}$ times, i.e. $65,536$ times, because of birthday paradox. The number $65,536$ however applies for brute-force attacks. Since there are more efficient attacks, the number is likely to be smaller. Generating a SHA1 collision is said to cost $700,000 USD by 2015 (see casecurity.org/2014/11/18/…). Generationg MD5 collision is almost free, say $$0.01. That would mean it is 70,000,000 times harder to find a SHA1 collision than MD5 collision. $\endgroup$
    – v6ak
    Commented Jan 14, 2015 at 20:40
  • $\begingroup$ @user2700751 If we accept the numbers $65,536$ and $70,000,000$, it would mean that additional 32 bits make it $65,536$ times harder, while better construction make it $1,000$ times harder. There are, however, various pitfalls, namely: 1. Cost of MD5 collision was very roughly guessed. 2. Additional 32 bits seem to have added much less security. (This seems to apply for all Merkle–Damgård constructions.) 3. MD5 is slightly (but negligibly for there purposes) faster. I guess that better design has added more security than additional 32 bits, but I am not sure. $\endgroup$
    – v6ak
    Commented Jan 14, 2015 at 20:50
  • $\begingroup$ @v6ak I can generate an MD5 collision using an Amazon EC2 free trial, so it costs $0.00, meaning it would be infinitely harder to find a SHA1 collision. (My point being that that sort of comparison isn't very useful!) $\endgroup$
    – Reid Rankin
    Commented Jan 15, 2015 at 2:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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