Re: My attempt to break Rijndael (SAT-attack)
- From: Thorsten Kiefer <toki782@xxxxxxxxxxxxxxxx>
- Date: Wed, 28 Feb 2007 18:14:02 +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.
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
.
- Follow-Ups:
- Re: My attempt to break Rijndael (SAT-attack)
- From: Thorsten Kiefer
- Re: My attempt to break Rijndael (SAT-attack)
- 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
- Re: My attempt to break Rijndael (SAT-attack)
- From: Peter Pearson
- My attempt to break Rijndael (SAT-attack)
- Prev by Date: Re: My attempt to break Rijndael (SAT-attack)
- Next by Date: Re: My attempt to break Rijndael (SAT-attack)
- Previous by thread: Re: My attempt to break Rijndael (SAT-attack)
- Next by thread: Re: My attempt to break Rijndael (SAT-attack)
- Index(es):
Relevant Pages
|
