My attempt to break Rijndael (SAT-attack)
in [Cryptography]
|
Prev: help needed
Next: Varying Ciphertext
From: Greg Rose on 1 Mar 2007 11:47 In article <45e45f6e$0$4730$6e1ede2f(a)read.cnntp.org>, Thorsten Kiefer <toki782(a)usenet.cnntp.org> wrote: >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 ? Nicolas Courtois gave a talk along these lines at a recent symmetric crypto workshop in Germany. Let's see... http://www.dagstuhl.de/en/program/calendar/semhp/?semid=30851 (I'm right up the back, Nicolas is the big guy in the middle next to Eli). Greg. -- Greg Rose 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C Qualcomm Australia: http://www.qualcomm.com.au
From: Thorsten Kiefer on 1 Mar 2007 12:26 Greg Rose wrote: > In article <45e45f6e$0$4730$6e1ede2f(a)read.cnntp.org>, > Thorsten Kiefer <toki782(a)usenet.cnntp.org> wrote: >>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 ? > > Nicolas Courtois gave a talk along these lines at > a recent symmetric crypto workshop in Germany. > Let's see... > http://www.dagstuhl.de/en/program/calendar/semhp/?semid=30851 > (I'm right up the back, Nicolas is the big guy in > the middle next to Eli). > > Greg. Seems like someone already did this for DES. Has anyone ever tried Rijndael ? Get my programs from http://nillakaes.de/dtest.tar.gz Simply carefully follow the instructions in the README. The program only works with siege_v4 (see google). -Thorsten
From: Mike Amling on 1 Mar 2007 04:36
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). We might note that 24 unknown bits in the key could be recovered from a plaintext/ciphertext pair by brute force in about one second. --Mike Amling |