Re: My attempt to break Rijndael (SATattack)
 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 keyclauses and insert only 126 clauses of the key.
This takes 30 seconds to solve.
...
Then I remove the keyclauses 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 keyclauses(/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 SATsolver 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 (SATattack)
 From: Thorsten Kiefer
 Re: My attempt to break Rijndael (SATattack)
 From: Kristian Gjøsteen
 Re: My attempt to break Rijndael (SATattack)
 From: Thorsten Kiefer
 My attempt to break Rijndael (SATattack)
 Prev by Date: Re: disc erasure
 Next by Date: Re: Quantum Cryptography can not work
 Previous by thread: Re: My attempt to break Rijndael (SATattack)
 Next by thread: Re: My attempt to break Rijndael (SATattack)
 Index(es):
Relevant Pages
