# How do we prove that AES, DES etc. are secure?

How do we prove that AES, DES etc. are secure? I've read about them and know the basics on how they work, but I still don't quite understand how we can be sure they are secure? What are the proofs?

-
DES is known to be insecure. Relevant links: copacobana.org lasecwww.epfl.ch/memo/memo_des.shtml crypto.stackexchange.com/q/752/8762 –  Joe Oct 7 '13 at 0:52

Only ciphers where the key is at least as long as the message have been proven secure (such as the one time pad, or the Luby-Rackoff cipher used in a certain way). AES is conjectured to be 'computationally secure', but until someone proves that $P \neq NP$ and that there are one-way functions it is conceivable that nothing is computationally secure.

The conjecture of computational security rests on two 'heuristic' arguments: i) we're pretty sure that $P \neq NP$ and that there are one-way functions, and ii) lots of very smart people have tried for 15 years to break AES and so far very little progress has been made -- the best publicly known attacks are still wildly out of the range of feasibility.

Note that this is no longer the case with DES due mostly to the short key, so DES is no longer considered to be secure.

-
Thanks, but what does P and N mean? –  evening Oct 7 '13 at 1:03
I am not really going to be able to explain this in 600 characters. I suggest you start with wikipedia: en.wikipedia.org/wiki/P_versus_NP_problem –  J.D. Oct 7 '13 at 1:08
The first sentence is problematic, Luby-Rackoff is a block cipher construction proven computationally secure under certain assumptions, but it doesn't have a key as long as the message. I think you went to say something else and forgot to update the sentence. –  Thomas Oct 7 '13 at 1:19
@Thomas -- if the round functions are uniformly random functions and the encrypted message is strictly shorter than $2^{\frac{b}{4}}$ (where b is the block length) then a 4 round luby-rackoff cipher is secure even against information theoretic opponents (also, the 'key' length required to describe the functions is longer than the message). If the round functions are only pseudorandom functions then yes, you are correct - the resulting cipher is only computationally secure and unbounded opponents will eat it for lunch. See e.g. iacr.org/archive/crypto2003/27290510/27290510.pdf –  J.D. Oct 7 '13 at 2:01
The pure existence of one-way functions doesn't really say anything about real-live functions (i.e. the ones in use today) which are supposed to be one-way. Also, how do one-way functions relate to the security of a block-cipher like AES, which is a "two-way function"? –  Paŭlo Ebermann Oct 7 '13 at 11:33

We don't prove schemes like AES and DES secure. Instead, cryptanalysts try very hard to find attacks against the scheme. If, after much effort, no attack is found, we may with some justification consider the scheme secure.

The statement that a scheme is secure usually takes the form "any adversary that breaks the scheme with this much advantage must use at least this much time". For symmetric cryptography, this is often equivalent to saying that exhaustive key search is the best attack. Note that "breaking the scheme" is a technical notion, and the precise definition is often complicated.

Sometimes, schemes can be proved secure against certain classes of attacks. I think AES has been proved secure against certain forms of differential and linear cryptanalysis. This does not prove that no other attacks exist, of course.

Sometimes, schemes can be proved secure under the assumption that a smaller scheme is secure in some sense. E.g. the Merkle-Damgård construction shows that hash functions can be constructed from compression functions.

Sometimes, we can prove that a scheme is secure under number-theoretic or complexity-theoretic assumptions. Unfortunately, these schemes are often very slow compared to schemes like AES. It is also not a priori clear why a "natural mathematical problem" must be harder than the "man-made problems" posed by schemes like AES.

In idealized models, there are many provably secure schemes (typically indifferentiability proofs) that are both interesting and valuable, but these do not describe the real world, so the results must be interpreted and used with care.

-