full-disclosure - preimage attack on step reduced md5 - reduced to 16 of 64 steps

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Message-ID: <20090621174044.GA7607@sivokote.iziade.m$>
Date: Sun, 21 Jun 2009 20:40:44 +0300
From: Georgi Guninski <guninski@...inski.com>
To: full-disclosure@...ts.grok.org.uk
Subject: preimage attack on step reduced md5 - reduced to
	16 of 64 steps -	<=19.43mins

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/