Georgi Guninski wrote:
You'll probably have to explain things a little more, most of us know the general working of crypto algorithms, not necessarily all the set theory behind it (groebner basis, and ideals are not normally part of the language of this group, even though they may be part of the language of papers describing attacks).. I'm pretty sure no one here has ran 'sane' before.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.
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.
example of what the proggie finds.
You'll have to explain this. I presume this is a utility under 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?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).
Also, is your partial result, these are bits in the md5 hash. It appears 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 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.
bob
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 md5implementation 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=49250
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
