Re: code release: cryptographic attack tool

[Neil Kettle <mu-b () 65535 com>]

Andrew Farmer wrote:
> On 12 Jan 07, at 08:05, Slythers Bro wrote:
> > hi,
> > sorry but i know nothing about the real physical "quantic theory"
> > i'am not a physician
> > i just know there are 3 states : 0 ,1 and unknow
> <...>
>
> This approach won't work for anything beyond the most trivial  
> cryptographic computations: attempting to reverse MD5 through basic  
> logic like this will "stall" as soon as you come to an operation  
> where both operands are unknown. In MD5, this will occur at the stage  
> where the message is added to word A in the 64th round. By the time  
> you get to the end of the 60th round, all bits will be "unknown".
>
> Any attack on a cryptosystem (such as MD5) of this form will need to  
> take into account complex correlations between bits. To carry your  
> quantum-physics analogy a bit further, you need to be able to keep  
> track of "entanglement" between bits. However, the storage necessary  
> to carry out such an attack on a large system like MD5 may very well  
> be large enough as to be completely infeasible (i.e, above 2^48 bits).

well it depends on how you model the dependencies, in computational
terms, modeling unrestricted dependencies between bits is equivalent
to constructing propositional formulae over the binary variables in
question (for MD5 this would be input/IV bits).

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. This would probably only
require polynomial space, but the time would kill you.



Out of interest, similar techniques have been applied to DES, an
obfuscated DES implementation computing DES blocks by constructing a
Binary Decision Diagram of several conjoined rounds of the cipher.
However, you will never be able to build the complete BDD (for all
rounds) as this would permit computing a key for a known plain-text in
time linear in the number of key bits!.

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

-- 
---------------------------------------------------------------------------
Neil K
(mu-b -[ at ]- 65535.com)

    "Computer Science is no more about computers
         than astronomy is about telescopes."

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