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

*From*: Kristian Gjøsteen <kristiag+news@xxxxxxxxxxxx>*Date*: Wed, 28 Feb 2007 08:49:31 +0000 (UTC)

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

.

**References**:**My attempt to break Rijndael (SAT-attack)***From:*Thorsten Kiefer

**Re: My attempt to break Rijndael (SAT-attack)***From:*Kristian Gjøsteen

**Re: My attempt to break Rijndael (SAT-attack)***From:*Thorsten Kiefer

- Prev by Date:
**Re: disc erasure** - Next by Date:
**Re: Quantum Cryptography can not work** - Previous by thread:
**Re: My attempt to break Rijndael (SAT-attack)** - Next by thread:
**Re: My attempt to break Rijndael (SAT-attack)** - Index(es):