spent some time on this. i tried algebraic preimage attack on md5 - working in $GF(2)[x0 .. x_i]$ and using groebner basis with arguments that avoid crashes.
to my surprise i got unexpected correct *partial* results that pass the insanity check. example of what the proggie finds. the final states of md5 with unrolled loops are: a = XX(I, a, b, c, d, inp[ 8], S41, 0x6FA87E4F) # 57 <-- this is step number d = XX(I, d, a, b, c, inp[15], S42, 0xFE2CE6E0) # 58 c = XX(I, c, d, a, b, inp[ 6], S43, 0xA3014314) # 59 b = XX(I, b, c, d, a, inp[13], S44, 0x4E0811A1) # 60 a = XX(I, a, b, c, d, inp[ 4], S41, 0xF7537E82) # 61 d = XX(I, d, a, b, c, inp[11], S42, 0xBD3AF235) # 62 c = XX(I, c, d, a, b, inp[ 2], S43, 0x2AD7D2BB) # 63 b = XX(I, b, c, d, a, inp[ 9], S44, 0xEB86D391) # 64 the proggie calls a ``state'' the value of the tuple: (step,whichoperand,whichoperation,bit) ['resbit' means the return of XX()] given only a md5 hash and unknown input, in 38 minutes and 1G ram the proggie correctly finds states: '57_resbit_resbit_0=0', '57_resbit_resbit_6=0', '57_resbit_resbit_8=1', '58_resbit_resbit_12=0', '58_resbit_resbit_13=1', '58_resbit_resbit_19=0', '58_resbit_resbit_21=0', '58_resbit_resbit_22=0', '58_resbit_resbit_29=0', '58_resbit_resbit_30=0', '58_resbit_resbit_31=0', '58_resbit_resbit_7=1' i.e. 3 bits of the result of step 57 and 9 bits of the results of step 58 (it finds other stuff too and continues running). about the implementation: md5 uses bitwise operations + addition modulo 32 and they can be implemented in $GF(2)[x0 .. x_i]$ so i start with symbolic input [x0 .. x_127] and work with the md5 implementation in $GF(2)[x0 ... x_i]$. every state of the algorithm is polynomial of the input. drama is with 128 variables, expressions are quite complicated and do not fit in current VM. so i use a trick - when an expressions $E$ is ``too big'' i introduce new variable $x_i$, add equation $ x_i = E $ and return the new var $ x_i $. $i = i+1$ this makes the final system at least well defined (numequations <= numvars). sage program is available at: https://bugzilla.mozilla.org/show_bug.cgi?id=492506 -- georgi -- dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
