Full Disclosure mailing list archives
Re: code release: cryptographic attack tool
From: Pavel Kankovsky <peak () argo troja mff cuni cz>
Date: Sat, 20 Jan 2007 19:02:08 +0100 (CET)
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/
Current thread:
- code release: cryptographic attack tool Slythers Bro (Jan 05)
- Re: code release: cryptographic attack tool Dave "No, not that one" Korn (Jan 08)
- Re: code release: cryptographic attack tool Slythers Bro (Jan 12)
- Re: code release: cryptographic attack tool Andrew Farmer (Jan 12)
- Re: code release: cryptographic attack tool Neil Kettle (Jan 14)
- Re: code release: cryptographic attack tool Pavel Kankovsky (Jan 20)
- Re: code release: cryptographic attack tool Slythers Bro (Jan 12)
- Re: code release: cryptographic attack tool Dave "No, not that one" Korn (Jan 08)