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  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]
Date: Fri, 28 Mar 2014 17:06:09 +0200
From: Georgi Guninski <guninski@...inski.com>
To: fulldisclosure@...lists.org
Subject: [FD] OT Crazy SAT encoding of md4 preimage

Warning:  If you can break this probably you
can break md5 and sha1, so take care

Some people broke large SAT formulas [1] related
to a problem of Erdos with plingeling.

The md4 preimage encoding in SAT is much smaller.

The CNFs are https://j.ludost.net/md4crazy/

17b is 17 bytes preimage of zero hash.

32b is 32 bytes preimage of zero hash.

easy is 16 bytes something trivial. 
One solution is easy with the right solver, 
second solution differing in the first 128 vars 
is hard (if it exists).

Suggested solvers are plingeling and cryptominisat
(latest stable, for cryptominisat run
--restrict=256. plingeling is the parallel version of lingeling).

plingeling-ats:  http://fmv.jku.at/lingeling/
cryptominisat:   https://gforge.inria.fr/projects/cryptominisat/

Good luck ;)

[1] http://cgi.csc.liv.ac.uk/~konev/SAT14/

_______________________________________________
Sent through the Full Disclosure mailing list
http://nmap.org/mailman/listinfo/fulldisclosure
Web Archives & RSS: http://seclists.org/fulldisclosure/

Powered by blists - more mailing lists