<p>MIXCOLUMNS prevents attacks that focus on only a few S-boxes, because the mixing of the columns requires all S-boxes to participate in the encryption.  (The designers of Rijndael called this a "wide trail strategy.")  The reason analysis of an S-box is hard is due to the use of the finite field inversion operation.  The inversion "smooths out" the distribution tables of S-box entries, so the entries appear (almost) uniform, i.e., indistinguishable from a random distribution without the key.  It's the combination of the two features that makes Rijndael provably secure against known attacks.</p>

<p>As an aside, the book <a href="http://rads.stackoverflow.com/amzn/click/3540425802">The Design of Rijndael</a> is a very good read, and discusses the theory and philosophy of cryptography.</p>

CC BY-SA 2.5
2010-09-12T18:30:37.493Z
Good explanation. Thanks. As a matter of fact, I had access to the book, but didn't know which part to read (regarding my question). Do you suggest any special chapter or section?
Sadeq Dousti
CC BY-SA 2.5
2010-09-12T19:56:50.277Z
I read it over two years ago, out of a library, so I don't have the table of contents in front of me, and I'm not sure I could give a concrete answer to your question, except that I liked the way they designed the S-boxes to be easily implementable.  However, one thing I can suggest is Stinson's explanation of AES and other substitution-permutation networks in Cryptography: Theory and Practice.  It's Chapter 3 of the edition I have, and it looks as though you can download the book for free at this link: http://www.ebookee.com/Douglas-Stinson-Cryptography-Theory-and-Practice_119170.html
Aaron Sterling
CC BY-SA 2.5
2010-09-13T02:36:50.793Z
Thanks for suggesting Stinson's book. Could you also look up the [Table of Contents](http://books.google.com/books?id=tfjd6icCUoYC&pg=PR11) of The Design of Rijndael, and see if it reminds anything useful?
Sadeq Dousti
CC BY-SA 2.5
2010-09-13T11:05:32.543Z
Thanks for the link! :-)  Yes, section 3.6 and chapter 5 were both very interesting to me, because they discussed "why," not just "what."
Aaron Sterling
CC BY-SA 2.5
2010-09-12T18:22:28.143Z
2010-09-12T18:22:28.143Z
Aaron Sterling
<p>As David said, we do not have such reductions for AES. However, this does not mean that Rabin or RSA cryptosystem are more secure than AES. In fact, I'd trust the (at least one-way, probably also pseudorandomess as well) security of block ciphers such as  AES/DES etc.. (perhaps with a bit more rounds than standardly used) more than the assumption that factoring is hard, precisely because there is no algebraic structure and so it's harder to imagine that there will be some kind of breakthrough algorithm.</p>

<p>One can construct block ciphers directly from one-way functions, which is a minimal assumption for much of crpyotgraphy, but the resulting construction will be terribly inefficient and hence not used.</p>

CC BY-SA 2.5
2010-09-19T03:10:43.330Z
Thanks Boaz. I think the Luby-Rackoff construct is one which provides provable pseudorandomess based on DES-like structures, right?
Sadeq Dousti
CC BY-SA 2.5
2010-09-20T01:56:05.413Z
yes. More accurately, you start with a one-way function, convert it to a pseudorandom generator using Hastad, Impagliazzo, Luby, Levin, then convert it to a pseudorandom function using Goldreich,Goldwasser,Micali, then indeed use Luby-Rackoff convert it to a pseudorandom permutation (i.e., block ci pher)
Boaz Barak
CC BY-SA 2.5
2010-09-19T02:26:27.293Z
2010-09-19T02:26:27.293Z
Boaz Barak
<p>Since one can convert any public-key encryption scheme into a secret-key scheme in a generic way, you can obtain secret-key schemes with similar provable security guarantees.</p>

<p>But that answer is pedantic:  for the typical deployed blockcipher we do not have a provable security analysis in the reduction-to-computational-problem sense.  There have been proposals for blockciphers with security reductions, but the computational baggage needed to facilitate a reduction renders them uncompetitive with more efficient schemes like the AES algorithms.</p>

<p>Interestingly, the provable security community has generally agreed that it is sound to take blockcipher security (pseudorandom permutation) as an assumption, and then reduce to it when analyzing higher-level protocols that employ the blockcipher as a component.  That is, unlike some other challenges in secure protocol design, it seems sufficient to trust cryptanalysts' intuition for security when it comes to blockciphers.</p>

CC BY-SA 2.5
2010-09-16T00:52:15.430Z
2010-09-16T00:52:15.430Z
David Cash
<p>Many public-key cryptosystems have some kind of provable security. For example, the <a href="http://en.wikipedia.org/wiki/Rabin_cryptosystem">Rabin cryptosystem</a> is provably as hard as factoring.</p>

<p>I wonder whether such kind of provable security exists for secret-key cryptosystems, such as AES. If not, what is the evidence that breaking such cryptosystems is hard? (other than resistance to trial-and-error attacks)</p>

<p><strong>Remark:</strong> I'm familiar with AES operations (AddRoundKey, SubBytes, ShiftRows, and MixColumns). It seems that the hardness of AES stems from the MixColumns operation, which in turn must inherit its difficulty from some hard problem over Galois Fields (and thus, algebra). In fact, I can restate my question as: "Which hard <strong>algebraic</strong> problem guarantees the security of AES?"</p>

<cr.crypto-security><algebra><algebraic-complexity>
Hardness Guarantees for AES
Sadeq Dousti
# Hardness Guarantees for AES

(Asked by: username_0 on 2010-09-12)

Many public-key cryptosystems have some kind of provable security. For example, the [Rabin cryptosystem](http://en.wikipedia.org/wiki/Rabin_cryptosystem) is provably as hard as factoring.

I wonder whether such kind of provable security exists for secret-key cryptosystems, such as AES. If not, what is the evidence that breaking such cryptosystems is hard? (other than resistance to trial-and-error attacks)

**Remark:** I'm familiar with AES operations (AddRoundKey, SubBytes, ShiftRows, and MixColumns). It seems that the hardness of AES stems from the MixColumns operation, which in turn must inherit its difficulty from some hard problem over Galois Fields (and thus, algebra). In fact, I can restate my question as: "Which hard **algebraic** problem guarantees the security of AES?"

**Tags:** cr.crypto-security, algebra, algebraic-complexity


---

## 3 answers

### Answer by username_1 on 2010-09-12. Score: 8 | Accepted answer

MIXCOLUMNS prevents attacks that focus on only a few S-boxes, because the mixing of the columns requires all S-boxes to participate in the encryption. (The designers of Rijndael called this a "wide trail strategy.") The reason analysis of an S-box is hard is due to the use of the finite field inversion operation. The inversion "smooths out" the distribution tables of S-box entries, so the entries appear (almost) uniform, i.e., indistinguishable from a random distribution without the key. It's the combination of the two features that makes Rijndael provably secure against known attacks.

As an aside, the book [The Design of Rijndael](http://rads.stackoverflow.com/amzn/click/3540425802) is a very good read, and discusses the theory and philosophy of cryptography.

> **Comments:**
> **username_0**: Good explanation. Thanks. As a matter of fact, I had access to the book, but didn't know which part to read (regarding my question). Do you suggest any special chapter or section?  
> **username_1**: I read it over two years ago, out of a library, so I don't have the table of contents in front of me, and I'm not sure I could give a concrete answer to your question, except that I liked the way they designed the S-boxes to be easily implementable.  However, one thing I can suggest is Stinson's explanation of AES and other substitution-permutation networks in Cryptography: Theory and Practice.  It's Chapter 3 of the edition I have, and it looks as though you can download the book for free at this link: http://www.ebookee.com/Douglas-Stinson-Cryptography-Theory-and-Practice_119170.html  
> **username_0**: Thanks for suggesting Stinson's book. Could you also look up the [Table of Contents](http://books.google.com/books?id=tfjd6icCUoYC&pg=PR11) of The Design of Rijndael, and see if it reminds anything useful?  
> **username_1**: Thanks for the link! :-)  Yes, section 3.6 and chapter 5 were both very interesting to me, because they discussed "why," not just "what."  

---

### Answer by username_2 on 2010-09-19. Score: 11

As David said, we do not have such reductions for AES. However, this does not mean that Rabin or RSA cryptosystem are more secure than AES. In fact, I'd trust the (at least one-way, probably also pseudorandomess as well) security of block ciphers such as AES/DES etc.. (perhaps with a bit more rounds than standardly used) more than the assumption that factoring is hard, precisely because there is no algebraic structure and so it's harder to imagine that there will be some kind of breakthrough algorithm.

One can construct block ciphers directly from one-way functions, which is a minimal assumption for much of crpyotgraphy, but the resulting construction will be terribly inefficient and hence not used.

> **Comments:**
> **username_0**: Thanks Boaz. I think the Luby-Rackoff construct is one which provides provable pseudorandomess based on DES-like structures, right?  
> **username_2**: yes. More accurately, you start with a one-way function, convert it to a pseudorandom generator using Hastad, Impagliazzo, Luby, Levin, then convert it to a pseudorandom function using Goldreich,Goldwasser,Micali, then indeed use Luby-Rackoff convert it to a pseudorandom permutation (i.e., block ci pher)  

---

### Answer by username_3 on 2010-09-16. Score: 6

Since one can convert any public-key encryption scheme into a secret-key scheme in a generic way, you can obtain secret-key schemes with similar provable security guarantees.

But that answer is pedantic: for the typical deployed blockcipher we do not have a provable security analysis in the reduction-to-computational-problem sense. There have been proposals for blockciphers with security reductions, but the computational baggage needed to facilitate a reduction renders them uncompetitive with more efficient schemes like the AES algorithms.

Interestingly, the provable security community has generally agreed that it is sound to take blockcipher security (pseudorandom permutation) as an assumption, and then reduce to it when analyzing higher-level protocols that employ the blockcipher as a component. That is, unlike some other challenges in secure protocol design, it seems sufficient to trust cryptanalysts' intuition for security when it comes to blockciphers.


---

