On Thu, May 14, 2009 at 10:13:16AM -0700, Robert Relyea wrote: >> > So the question is, will a final solution from your equations give us > a > solution relevant to the real MD-5. >>
i am ready to bet up to 2 beers that an oracle that solves the final equations will give a *real* preimage attack on md5. i did some tests with input that is not used in constructing the equations - basically all the equations are polynomials of the input. substituting the input in the final equations makes all of them zero. with constant input the proggie generates the real md5 hash MINUS four 32bit constants that are taken care of when constructing the equations. >> > MD-5 works by starting with an initial state, breaking a message up > into > 16 byte blocks, then combining that initial state with the input. The > resulting output is feed back into the algorithm as the new initial > state and you repeat for the next block. The final output is the final > hash. > > I would guess, from your statement, you are probably trying to solve > given the initial state, what block will produce a given output. While > such a solution is interesting in some cases, we rarely hash a single > block in MD5. (those cases are interesting in that the hash is usually > depending on the preimage protection of MD5 - like certain password > protocols). > > Even more devastating, though, is if your can solve given an arbitrary > initial state and a desired output block. This would be and effective > 2nd-preimage attack. In this case I can construct any message I want > and > calculate the 16 byte block needed to i am looking for the initial 16 bytes and i give the desired output. the initial state in md5 is constant for me. i look for md5(16bytes)= b00bb00b00bb00bb00b i have the 0xboobs hash and look for the 16 bytes (basically i am not sure only 16 bytes can give me 0xb00b, but 0xcafe would do too). >> > OK, getting bits in steps 58 and 57 are interesting, but not > necessarily > disastrous for MD-5. Reduced round attacks are a common tool to try > to > gauge the inherent strength of an algorithm. Getting solutions for a > couple of bits of state at step 58 and 57 could be combined with a > reduced round attack, but again does not mean the fall of MD-5 is > imminent. > > (I'm assuming you are finding bits in the actual MD-5 steps 58 and 57. > That is 6-7 steps backwards from the output. If this is steps 58 and > 57 > counting the other direction (that is only 6-7 steps from our initial > input), then these solutions are much more interesting.) > yes backwards. finding the first 6-7-8-9 steps will reduce the numbers of variables and probably polybori won't crash. -- dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
