Re: Probably naive question - SHA1 + MD5 combination

Bryan Olson <fakeaddress@xxxxxxxxxxx> wrote:
Kristian Gjøsteen wrote:
Shamus Husheer <s.husheer@xxxxxxxxx> wrote:
For example, if the function SHA1(data+MD5(data)) were used (i.e.
append the MD5 of the data to the data, and take the SHA1 of the
combination), would it be a lot harder to find collisions?

No. You find a collision in SHA-1, say x_0 and x_1, then you simply
choose random messages y until MD5(x_0||y) = MD5(x_1||y), which by the
birthday paradox is feasible.

Can you justify that? I don't see it, even granting the that the
~2**64 work of breaking MD5 by birthday-attack is feasible.

Obviously, I can't, because I can't. I was trying to use the Joux attack,
and I misremembered. Sorry. Thanks for the correction.

What you do is find a collision in SHA-1, say x_0 and y_0. Then you find
another collision with the iv you get after processing x_0/y_0, say x_1
and y_1. Notice that SHA-1(x_0||x_1) = SHA-1(x_0||y_1) = SHA-1(x_1||y_0)
= SHA-1(x_1||y_1). Repeat say 128 times. Now you can generate 2^128
different messages that all have the same SHA-1 hash, by alternating
between the x_i and y_i.

The birthday paradox then provides an MD5 collision.

--
Kristian Gjøsteen
.

Relevant Pages

  • Re: What is md5sum?
    ... actually no two items in the list share the same MD5 sum. ... If hash functions we create were perfect, we wouldn't be using MD5 - we ... probability of a collision or reversing the function would be negligible ... better than others - and SHA-1 is considered more secure than MD5. ...
    (comp.os.linux.setup)
  • Re: Security myths
    ... it's the beginning of the end for MD5 and SHA-1 (Perhaps even the whole SHA ... The fact of the matter is, there is a valid certificate collision out ...
    (microsoft.public.security)
  • Re: On the risks of using a hash function as a MAC
    ... bits), it can be looked for by exhaustive search and, if the attacker ... no such flaw on SHA-1 has ever been found yet. ... > you still have to find a collision for SHA-1... ... For MD5, the attacker has to compute about 2^64 texts which he ...
    (sci.crypt)
  • Re: This Weeks Finds in Mathematical Physics (Week 226)
    ... Yeah, I said SHA-1 and MD5 are different, and I said they were both vulnerable ... Attacking hash functions by poisoned ... where Ldenotes the length of the axiom system A, ...
    (sci.physics.research)
  • Re: Re-secured Algorithm?
    ... >>MD5 collisions are actually trivial to generate. ... SHA-1 had real collisions in MD5. ... Personal attacks aside I doubt many ...
    (sci.crypt)