My attempt to break Rijndael (SAT-attack)
in [Cryptography]
|
Prev: help needed
Next: Varying Ciphertext
From: Thorsten Kiefer on 27 Feb 2007 11:42 Hi, I did some research on breaking Rijndael. I converted the Rijndael algorithm into a SAT-instance. Then I added the 1-literal clauses of the plaintext and the key. Then I ran my favorite SAT-solver on this instance, and the result was the correct encryption of the plaintext with the given key. Now what more intersting : I only add the 1-literal clauses of the plaintext and the ciphertext. Now the solution should contain the correct key. At the moment my SAT-solver does not terminate in finite time for this constellation. I call this the SAT-attack. Is anyone interested ? Shall I provide links to my programs ? Best regards Thorsten
From: Kristian Gj�steen on 27 Feb 2007 12:18 Thorsten Kiefer <toki782(a)usenet.cnntp.org> wrote: >I did some research on breaking Rijndael. >I converted the Rijndael algorithm into a SAT-instance. >Then I added the 1-literal clauses of the plaintext and the key. >Then I ran my favorite SAT-solver on this instance, and the result was >the correct encryption of the plaintext with the given key. Is this surprising? >Now what more intersting : >I only add the 1-literal clauses of the plaintext and the ciphertext. >Now the solution should contain the correct key. >At the moment my SAT-solver does not terminate in finite time for this >constellation. Do you think this is surprising? I don't. >I call this the SAT-attack. > >Is anyone interested ? Shall I provide links to my programs ? Nah. But you may be interested in algebraic attacks. -- Kristian Gj�steen
From: Thorsten Kiefer on 27 Feb 2007 17:55 Kristian Gj�steen wrote: > Thorsten Kiefer <toki782(a)usenet.cnntp.org> wrote: >>I did some research on breaking Rijndael. >>I converted the Rijndael algorithm into a SAT-instance. >>Then I added the 1-literal clauses of the plaintext and the key. >>Then I ran my favorite SAT-solver on this instance, and the result was >>the correct encryption of the plaintext with the given key. > > Is this surprising? > >>Now what more intersting : >>I only add the 1-literal clauses of the plaintext and the ciphertext. >>Now the solution should contain the correct key. >>At the moment my SAT-solver does not terminate in finite time for this >>constellation. > > Do you think this is surprising? I don't. > >>I call this the SAT-attack. >> >>Is anyone interested ? Shall I provide links to my programs ? > > Nah. But you may be interested in algebraic attacks. > Hi, I tried something different: I added the clauses for the plaintext, ciphertext and all 128 clauses of the key. It takes 24 seconds to solve this. Then I remove the key-clauses and insert only 126 clauses of the key. This takes 30 seconds to solve. .... Then I remove the key-clauses and insert only 116 clauses of the key. This takes 617 seconds to solve. If you assume the formula a*b^n for the time complexity, then you can find: time(n) = 24 * 1.2^n, where n is the number of missing key-clauses(/bits). time(128) = 3.27*10^11 second, which is about 10000 years (on my computer). So if you could accelerate the solver e.g. by parallel computing by a factor 10000, you could crack a Rijndael key in 1 year. Unfortunately my favorite SAT-solver is stochastic an therefore the time(n)-formula is not totally reliable. Is this more interesting now ? Regards Thorsten
From: Thorsten Kiefer on 27 Feb 2007 20:17 Sebastian Gottschalk wrote: > Or maybe you're just taken too few sample points. It should be b>=2. > Of course I took 7 sample points (n=0,2,4,6,8,10,12), and it shows 1.2 <= b <= 1.3 .
From: Kristian Gj�steen on 28 Feb 2007 03:49
Thorsten Kiefer <toki782(a)usenet.cnntp.org> wrote: >I added the clauses for the plaintext, ciphertext and all 128 clauses of the key. >It takes 24 seconds to solve this. >Then I remove the key-clauses and insert only 126 clauses of the key. >This takes 30 seconds to solve. >... >Then I remove the key-clauses and insert only 116 clauses of the key. >This takes 617 seconds to solve. > >If you assume the formula a*b^n for the time complexity, then you can find: >time(n) = 24 * 1.2^n, where n is the number of missing key-clauses(/bits). This would be completely devastating for Rijndael, since the time for recovery of 128 bit key should be approximately 2^127 ~ 10^40. It would also be _very_ surprising (not to mention embarrassing for the cryptographic community). >time(128) = 3.27*10^11 second, which is about 10000 years (on my computer). >So if you could accelerate the solver e.g. by parallel computing by a factor 10000, >you could crack a Rijndael key in 1 year. > >Unfortunately my favorite SAT-solver is stochastic an therefore the time(n)-formula >is not totally reliable. > >Is this more interesting now ? Not really. You need to show that your formula really describes the behaviour of the system when n increases. I don't see anything that suggests this is the case. -- Kristian Gj�steen |