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. 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. in the end i get a large nonlinear polynomial system. i can't find the complete solution, but sometimes i can find partial solutions. partial solutions are internal md5 states (bits) say the final system is 9000 equations in a little less variables. polybori tries to solve it and tells me: part of the solution is x7000=1 for me this means internal state, say, 58_resbit_10 = 1 >> 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" > 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. > Also, is your partial result, these are bits in the md5 hash. It > appears these are not bits in the hash. these are bits in the internal state. > 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. > 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... -- dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
