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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
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.