[Full-disclosure] preimage attack on step reduced md5 - reduced to 16 of 64 steps - <=19.43mins

[Georgi Guninski <guninski@xxxxxxxxxxxx>]

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/