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/