14
$\begingroup$

Many public-key cryptosystems have some kind of provable security. For example, the 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?"

|cite|improve this question
$\endgroup$
8
$\begingroup$

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 is a very good read, and discusses the theory and philosophy of cryptography.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – M.S. Dousti Sep 12 '10 at 18:30
  • 3
    $\begingroup$ 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: ebookee.com/… $\endgroup$ – Aaron Sterling Sep 12 '10 at 19:56
  • 1
    $\begingroup$ Thanks for suggesting Stinson's book. Could you also look up the Table of Contents of The Design of Rijndael, and see if it reminds anything useful? $\endgroup$ – M.S. Dousti Sep 13 '10 at 2:36
  • 2
    $\begingroup$ Thanks for the link! :-) Yes, section 3.6 and chapter 5 were both very interesting to me, because they discussed "why," not just "what." $\endgroup$ – Aaron Sterling Sep 13 '10 at 11:05
10
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks Boaz. I think the Luby-Rackoff construct is one which provides provable pseudorandomess based on DES-like structures, right? $\endgroup$ – M.S. Dousti Sep 19 '10 at 3:10
  • 3
    $\begingroup$ 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) $\endgroup$ – Boaz Barak Sep 20 '10 at 1:56
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.