[Full-disclosure] code release: cryptographic attack tool
peak at argo.troja.mff.cuni.cz
Sat Jan 20 18:02:08 GMT 2007
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 is hosted and sponsored by Secunia.