Re: naive groebner basis preimage attack on md5

[Robert Relyea]

Georgi Guninski wrote:

On Wed, May 13, 2009 at 10:42:38AM -0700, Robert Relyea wrote:

So to understand correctly, MD-5 is implemented in a series of operations module 2^32, so you can treat the whole thing as a GF(2^n) ring. I believe this is a ring (2 doesn't have a multiplicative inverse), not a field (there exists a field order 2^32, but it's from by polynomial arithmetic mod 2 all mod an irreducible polynomial). It appears that this doesn't matter since goebner basis appears to work for rings as well as fields.

no, you have misunderstood.

i am working over the field with 2 elements GF(2) and i emulate md5 with
multivariate polynomials over it.

OK, thanks That's actually what I thought at first, but somehow changed my mind after reading the rest of your descriptions.

when md5 uses A AND B, A,B are bits, i use: A*B NOT A is 1 + A.

(you may check by bruteforcing numerically).
addition modulo 2^32 is emulated with ADDER - roughly speaking the way
CPU adds ints.

So the question is, will a final solution from your equations give us a solution relevant to the real MD-5.

example of what the proggie finds.

You'll have to explain this. I presume this is a utility under sane?

huh? the program must be run under "sage 3.4.1"

Sorry I meant a utility under sage (not sane).

An md5 input had two components, internal state and next block to

hash. The question is, are you calculating a solution for both (internal state & next block to hash), or are you calculating next block to hash given a fixed internal state?

i am not sure i understand this. currently i work with 16 bytes input
(128 bits) and this is only one md5 block. clarify if you need more
info.

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

you are finding partial results for certain states. Are these states going fbackwards or forwards (that is are you finding results of what the step 3 bits in step 57 and 9 bits in step 58 *should be* to get the final result, or are you finding input values that generate 3 correct bits in step 57 and 9 in step 58). The former is not as interesting as

i am finding some bits in step 58 and 57. if the proggie is correct,
these bits are correct internal states for the attacked hash. i have no
information about the *input bits* yet.

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.) In short, you have found another point along they way that seems to indicate that MD-5 is weak. The success of collision attacks have also pointed this way. I'm already of the opinion that a full 2nd preimage attack against MD-5 is likely in the next 5 years, and believe we need to take steps to turn it off in that time frame. If your attack got into much lower rounds with more bits, I could probably use that to get more interest in shutting down MD-5.

the latter. Have you ran it significantly longer to find more bits in later states? I'm not sure, but I think there are 2nd pre-image attacks to partial rounds of MD-5 already.

no, i don't find much more bits.
part of the problem is the groebner solver polybori crashes with SEGV on
``interesting systems''
though finding even several internal states makes my life easier:
it may save costy additions mod 2^32, it overdetermines the final
system, possibly some trick with inverting the final steps may be
done...

At this stage, if I were you, I would contact someone like Lenstra, who not only has a grasp on the various MD-5 attacks, but also has access to some pretty good hardware. And he wouldn't have to look up groebner sets to understand what you are trying to do:).

bob

smime.p7s
Description: S/MIME Cryptographic Signature

-- 
dev-tech-crypto mailing list
dev-tech-crypto@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-tech-crypto