Re: My attempt to break Rijndael (SAT-attack)

Kristian Gjøsteen wrote:

Thorsten Kiefer <toki782@xxxxxxxxxxxxxxxx> 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

.

Relevant Pages

  • Re: My attempt to break Rijndael (SAT-attack)
    ... Then I added the 1-literal clauses of the plaintext and the key. ... the correct encryption of the plaintext with the given key. ... I only add the 1-literal clauses of the plaintext and the ciphertext. ... Do you think this is surprising? ...
    (sci.crypt)
  • My attempt to break Rijndael (SAT-attack)
    ... I did some research on breaking Rijndael. ... Then I added the 1-literal clauses of the plaintext and the key. ... the correct encryption of the plaintext with the given key. ... I only add the 1-literal clauses of the plaintext and the ciphertext. ...
    (sci.crypt)