Re: [Full-disclosure] 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/
Re: [Full-disclosure] code release: cryptographic attack tool
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/
Re: [Full-disclosure] code release: cryptographic attack tool
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). ___ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
Re: [Full-disclosure] code release: cryptographic attack tool
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 "How? In what way?" >> look in the .rar "> i used this lib for coding fuckmd5.cpp You did? I can't see any sign of tri-state logic in the final source code." ok for fuckmd5.cpp i just used qbyte.cpp only for know mask (the 0x1fff) in reality the mask is dynamic but in this case this is static and the code of fuckmd5.cpp is optimized :p but look in the .rar maybe you will understand :] sorry if the name "qbyte" isn't really appropriate if you have question : mail me ___ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
Re: [Full-disclosure] code release: cryptographic attack tool
"Slythers Bro" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > this is a mathematic tool where all bits of a double word have 3 states : > one , zero and > unknow > i implemented the addition , multiplication (with an integer), a new > concept "fusion" > (equivalent to = ) , and all basic booleean functions (binary version of > xor, or, no , and) > there are some utilities like error detection, error depth etc ... What axioms did you define? There is more than one way of describing notions analagous to addition, multiplication etc. with three-valued logic. Does your system form a ring or group? > i used this lib for coding fuckmd5.cpp You did? I can't see any sign of tri-state logic in the final source code. > if you want to use multithreading the code need modification > i think this tool is good for easy recomputation and error detection in > the case of a > cryptographic attack How? In what way? cheers, DaveK -- Can't think of a witty .sigline today ___ Full-Disclosure - We believe in it. Charter: http://lists.grok.org.uk/full-disclosure-charter.html Hosted and sponsored by Secunia - http://secunia.com/
