Full Disclosure mailing list archives
preimage attack on step reduced md5 - reduced to 16 of 64 steps - <=19.43mins
From: Georgi Guninski <guninski () guninski com>
Date: Sun, 21 Jun 2009 20:40:44 +0300
due to math disabilities, i tried algebraic attack on step reduced md5 to 16 steps (authentic md5 is 64 steps in the same input). basically i got 8.5K multivariate polynomial system exactly determined (#vars == #eqs) over $GF(2)$ - roughly half of it is linear and it is *quite* sparse (max 11 monomials per $eq$). the not reduced system is about 33K (\times 4) with *exactly the same structure*. i tried a groebner basis attack, fighting the bugs of the _coderz_ (sometimes you are the windshield, sometimes you are the bug -- straits). to cut a sad story short, in this scenario a preimage attack is less than 19.434343... minutes on a lame pc: (note that all of the input is 16 bytes == 128 bits) ;) #######printf 'jy\x89q\xabn3\xae\x16\x19\x7f3\x257vi' | ./md5 warning: aborting after step 16 the only change is #if 0 ...steps 17 to 64 including 00000000000000000000000000000000 - ;) #######printf '\x02\x91\x88\xb7\x06{\xcd\xb0c+T\x99\xf6d0\xa9' | ./md5 warning: aborting after step 16 the only change is #if 0 ...steps 17 to 64 including B00BB00BB00BB00BB00BB00BB00BB00B - ;) #######printf '\x1c\x01\x1f\xe3t\xea|\x8d=\x90\xb9\xdd\x9e\x08\xdb\x81' | ./md5 warning: aborting after step 16 the only change is #if 0 ...steps 17 to 64 including B33AB33AB33AB33AB33AB33AB33AB33A - ;) ####### -- joro _______________________________________________ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
Current thread:
- preimage attack on step reduced md5 - reduced to 16 of 64 steps - <=19.43mins Georgi Guninski (Jun 21)