How are secure hashing and encryption algorithms proven?

Given that:

You should always use proven secure hashing and encryption algorithms, rather than attempting to write your own.

What's the process for criteria for an algorithm being proven?

Is it necessarily a peer review process? Does an algorithm need to withstand exploit attempts for N amount of time by M many experts?

Or, is there a mathematical proving process that security experts can apply on their own to evaluate an algorithm?

From the consumer perspective, how can early algorithm adopters vet new potential algorithms? Or put another way: When should security-concerned folks start considering new algorithm X?

My personal opinion: "proven secure" is more of an advertising slogan than anything else. The one-time pad and certain multiparty protocols can be shown to have some kind of information-theoretic security; these are exceptions to the rule. "Don't roll your own crypto" is still sensible advice however.

For the rest of this discussion, I'll try and stick to facts.

In public-key cryptography, there are three kinds of number-theoretical primitives in common use (RSA groups, prime-order groups based on finite fields F_p, prime-order groups based on elliptic curves) for which the security properties and arguments are based on a combination of experience and heuristics. For example, RSA has been around for 35-odd years now without anyone finding a way to break it when used properly; a lot of effort has gone into factoring integers but the best number-field sieving algorithms available today are still nowhere close to factoring 4096-bit RSA moduli. Similar considerations apply to taking discrete logarithms in finite fields.

What "provable security" does is construct a layer of cryptographic components on top of these primitives and prove that a certain formal definition of breaking the components is at least as hard as breaking a certain formal notion of security on one of the primitives. For example, one can prove that if you obtain my ElGamal public key and you give me any two messages of the same length, and I give you an ElGamal encryption of one of them back, then you cannot do any better than guess at random which of your two messages I encrypted --- unless you can also solve one of cryptography's basic hard problems over the group I'm using to do my ElGamal encryption, which has been studied since around the 1980s. (This is formally called the IND-CPA to DDH reduction for ElGamal and is a staple of public-key cryptography 101 courses.)

Does this mean that ElGamal is secure for a particular application? It depends, and it says nothing about "out of band" attacks such as malware on your computer, biased randomness generators etc.

I see the role of security proofs primarily as a layer of security within the cryptographic research community. Proposals for new primitives are rare, and need a jot of justification to be accepted. However, let's say you have a particular application where you want, for example, an encryption scheme for messages where you want anyone to be able to tell just from looking at a ciphertext if the plaintext is all zeroes or not, but nothing else. A cryptographer might be able to design such a scheme for you based on existing primitives or schemes, and then prove that breaking the new scheme with the additional feature is in some way at least as hard as breaking one of the existing and well understood schemes. For example, one could adapt ElGamal and prove that if you can tell an encryption of 01 from an encryption of 10 or 11, then you can also break ElGamal directly.

Within this specific context --- proving a scheme to satisfy some formal notion under the assumption that the primitives already satisfy some formal notion --- the word "proof" in cryptography means the same as it does in mathematics. Cryptographic proofs typically do not address the following points:

1. Does the primitive in question really satisfy the property?

2. Is the formal notion of security sufficient for a particular real-world application?

3. Is the proof correct? The amount of proof-reading done before a paper gets into CRYPTO is much less than for most mathematical journals; mistakes do happen.

To give another example: block cipher modes of operation. The security proof for (say) Galois-Counter Mode (GCM) is that if you had a perfect block cipher B then B-GCM (with random initialisation vectors and a few other things) would give you authenticated encryption. In contrast, ECB mode has no such security proof (and fairly obviously does NOT provide much security even with a perfect block cipher). AES is not a perfect block cipher, but a pretty good one judging by experience. But we can still say that AES-GCM is a much better choice than AES-ECB.

The original quote, in my opinion, would read better as:

"Cryptographers should not (usually) design new schemes for the sake of adding features without proving them to be at least as secure as existing ones. Everyone else should stick to standardised algorithms."

Is it necessarily a peer review process? Does an algorithm need to withstand exploit attempts for N amount of time by M many experts?

Or, is there a mathematical proving process that security experts can apply on their own to evaluate an algorithm?

Yes, yes, and sometimes.

Some algorithms can be proved secure under certain assumptions. However, those assumptions usually include the fact that some other primitive used has a property that cannot be proved. Examples include:

Those most basic building blocks in symmetric algorithms, however, cannot be proved to have all the properties assumed in the higher level construction.

Instead, they are conjectured to have them, shown to resist some simple attacks, fulfill statistical properties, etc. Then the algorithms are published and peer reviewed. If they see actual use and follow up papers from others, standing up to attacks for years or decades, then you can consider them "proven" even if not in the meaning of a mathematical proof.

In the case of asymmetric algorithms, they usually depend on a number theoretic assumptions instead. For example, ElGamal depends on the hardness of discrete logarithms. This is similar in that there is no proof of the non-existence of a fast discrete logarithm algorithm.

To see use and get attention from other cryptographers an algorithm usually has to be standardized, or at least be part of a competition for a standard such as have been run for block ciphers (AES), stream ciphers (eSTREAM) and hash algorithms (SHA-3).

Frankly, I don't think most people should start using an algorithm before standardization – or at least de facto standardization. "Early adopters" pretty much rules out "security concerned folks" here, unless older algorithms/protocols were clearly found to be weak like DES was before AES was standardized.

• If you consider also public key encryption then you may want to mention reductions security proofs. Additionally you may also want to mention provably secure hash functions such as VSH, where the collision resistance relies on a number theoretic assumption. Aug 20, 2014 at 9:55
• "Early adopters" is intended to mean "folks who adopt soon after an algorithm can be considered proven." Aug 20, 2014 at 14:35
• @svidgen, ok, in that case feel free to disregard the last paragraph. "After standardization" is my answer to your last question.
– otus
Aug 20, 2014 at 14:37
• Before giving you the check, could you edit in a brief clarification about where or how the algorithms are published for peer review? Sep 2, 2014 at 21:16