My attempt to break Rijndael (SAT-attack)
in [Cryptography]
|
Prev: help needed
Next: Varying Ciphertext
From: Thorsten Kiefer on 28 Feb 2007 10:26 Sebastian Gottschalk wrote: > Thorsten Kiefer wrote: > >> 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 . > > Your values for n are too low, your sample points too dense. Try n=24, > n=32, n=36, n=40 and see how you 'b' jumps high. OK, I assume b=1.3 and n = 24. According to my formula this will take 24s * 1.3^24 = 13027s = 3.6 hours. I'll will try that. Maybe I can give you the result tomorrow.
From: Peter Pearson on 28 Feb 2007 10:58 On Wed, 28 Feb 2007 01:06:35 +0100, Sebastian Gottschalk wrote: > Thorsten Kiefer 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). > > Or maybe you're just taken too few sample points. It should be b>=2. > >> Unfortunately my favorite SAT-solver is stochastic an therefore the time(n)-formula >> is not totally reliable. >> >> Is this more interesting now ? > > No. Hey, don't be so grumpy. It is, too, interesting. Keep at it, TK. -- To email me, substitute nowhere->spamcop, invalid->net.
From: Thorsten Kiefer on 28 Feb 2007 11:00 Peter Pearson wrote: > On Wed, 28 Feb 2007 01:06:35 +0100, Sebastian Gottschalk wrote: >> Thorsten Kiefer 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). >> >> Or maybe you're just taken too few sample points. It should be b>=2. >> >>> Unfortunately my favorite SAT-solver is stochastic an therefore the >>> time(n)-formula is not totally reliable. >>> >>> Is this more interesting now ? >> >> No. > > Hey, don't be so grumpy. It is, too, interesting. Keep at it, TK. > WILL DO SO !!!!! ;-))))
From: Thorsten Kiefer on 28 Feb 2007 11:44 Peter Pearson wrote: > On Wed, 28 Feb 2007 01:06:35 +0100, Sebastian Gottschalk wrote: >> Thorsten Kiefer 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). >> >> Or maybe you're just taken too few sample points. It should be b>=2. >> >>> Unfortunately my favorite SAT-solver is stochastic an therefore the >>> time(n)-formula is not totally reliable. >>> >>> Is this more interesting now ? >> >> No. > > Hey, don't be so grumpy. It is, too, interesting. Keep at it, TK. > Thanks for your support Peter. Are you interested in the source code ? So that you can reproduce my results ? It's all programmed in D, and my favorite SAT solver is siege_v4 (do you know a better one ?). I'm currently running the solver for n=24. I hope I have the result tomorrow.
From: Thorsten Kiefer on 28 Feb 2007 12:14
Sebastian Gottschalk wrote: > Peter Pearson wrote: > >> Hey, don't be so grumpy. It is, too, interesting. Keep at it, TK. > > No, it's not interesting. Rijndael has be designed such that a simple SAT > won't help in any way. Once he tries to solve some less trivial cases (way > more unknown keybits), he'll for sure step upon a growth factor of ~2 per > keybit. Do you know Schöning's SAT algorithm ? It solves SAT instances in (3/4)^n, where n is the number of variables. It is the world record algorithm. The clue is that it is a probabilistic algorithm. An so is siege_v4 (my favorite algorithm). This means that the growth factor is below 2. Look here: http://theorie.informatik.uni-ulm.de/Forschung/Poster/3sat.gif |