My attempt to break Rijndael (SAT-attack)
in [Cryptography]
|
Prev: help needed
Next: Varying Ciphertext
From: Thorsten Kiefer on 28 Feb 2007 12:23 <posted & mailed> Thorsten Kiefer wrote: > 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 If you don't like probabilistic algorithms, then look at that : http://theorie.informatik.uni-ulm.de/Forschung/Poster/3sat.gif
From: Thorsten Kiefer on 28 Feb 2007 12:24 <posted & mailed> Thorsten Kiefer wrote: > <posted & mailed> > > Thorsten Kiefer wrote: > >> 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 > > If you don't like probabilistic algorithms, then look at that : > http://theorie.informatik.uni-ulm.de/Forschung/Poster/3sat.gif Uhm I mean http://theorie.informatik.uni-ulm.de/Forschung/Poster/search.gif
From: Thorsten Kiefer on 1 Mar 2007 01:48 <posted & mailed> Thorsten Kiefer wrote: > 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. OK, It has been running for 900 minutes now, and it is still searching... So b tends towards 1.4 (at the moment).
From: Thorsten Kiefer on 1 Mar 2007 10:55 <posted & mailed> Thorsten Kiefer wrote: > <posted & mailed> > > Thorsten Kiefer wrote: > >> 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. > > OK, It has been running for 900 minutes now, and it is still searching... > So b tends towards 1.4 (at the moment). OK, the solver hasn't found the solution within 1460mins (b>1.4). So I stopped it for now, and I'm searching for another solver to get a more reliable formula the time complexity.
From: Peter Pearson on 1 Mar 2007 11:22
On Wed, 28 Feb 2007 17:46:03 +0100, 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. If someone has tried the same approach and failed, then it's not interesting. If someone has proven that Rijndeal-breaking SAT problems do not form an especially easy subset of SAT problems, then it's not interesting. Otherwise, the original poster is voluntarily pursuing an investigation with an admittedly small (but nonzero) probability of producing an important result, and it's worth hearing the final report, even if it's just, "Tried this; didn't work." -- To email me, substitute nowhere->spamcop, invalid->net. |