full-disclosure - Re: code release: cryptographic attack tool

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>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <20070120184716.932.0@paddy.troja.mff.cuni.cz>
Date: Sat, 20 Jan 2007 19:02:08 +0100 (CET)
From: Pavel Kankovsky <peak@...o.troja.mff.cuni.cz>
To: Neil Kettle <mu-b@...35.com>
Cc: full-disclosure@...ts.grok.org.uk
Subject: Re: code release: cryptographic attack tool

On Sun, 14 Jan 2007, Neil Kettle wrote:

> Solving the resultant formula, and hence *breaking* MD5 (computing
> collisions, invariant IV's [which has already been done by similar
> techniques], etc..) is equivalent to SAT, and thus NP-Complete
> requiring exponential time by conjecture.

It is obvious the problem (cracking MD5) can be reduced to SAT. But can
you reduce SAT to the problem? I am afraid it is impossible. (CNF formulas
of arbitrary complexity vs. a linear chain of fixed width linking multiple 
instances of a fixed logical circuit. Who wins?)

--Pavel Kankovsky aka Peak  [ Boycott Microsoft--http://www.vcnet.com/bms ]
"Resistance is futile. Open your source code and prepare for assimilation."

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/