How is a cypher algorithm verified?

Question

I've always thought about how the symmetric cyphers are verified. Let say I would invent a new cypher. (actually I don't :-)) How should I rationalize its security to the public? As far as I saw papers about cyphers and their security I've never seen any real mathematical proof about it's security. I just saw a kind of reasoning, not real mathematical proofs. How would you prove a symmetric cypher is secure? No idea... Thinking about it is getting me close to P!=NP like questions.

I see it like this, to be able to invent a new cypher, you...

1. must be well educated and known person to convince others to just listen to you
2. if you fulfil (1), the other people of your interest would study your algorithm, checking whether any of known method would be applicable against it's security.
3. the cypher should be discussed how resistant it is against those common methods. Probably you and people form (2) would do that.
4. the cypher must be suitable for CPUs, it must be fast and easy to compute, easy to implement even on CPU level and different platforms
5. somehow, the cypher must show it has no intended backdoors. For instance, constant arrays (S-Boxes) should be a well know common numerical series.

From my point of view, symmetric cryptography is much less about math then people think it is. Is't more about imagination how to mix the bits and confuse the data efficiently while using as little CPU instructions as possible. The verification is more about a discussion then about a real math.

Am I naive?

thanks

Answer 1

There is no mathematical proof that secure encryption systems can actually exist, let alone that any specific candidate is secure. At best, some encryption algorithm can be proven to be secure (for some notion of security) as long as some given mathematical problem remains intractable with existing knowledge. E.g. the Rabin cryptosystem can be proven (with some caveats that are a bit too long to explain) to be secure if it is not feasible to factor a given big integer into its prime factors.

Symmetric encryption algorithms (such as AES or 3DES) don't usually boast even that kind of proof.

In practice, the "gold standard" for cryptographic algorithm is survival. To gauge the security of some cryptographic algorithm, the procedure is the following:

1. Publish the algorithm with a complete unambiguous specification, along with a reference implementation and some test vectors (no, the reference implementation is not the specification; that's something else).

2. Let the design cook under the fiery gaze of many other cryptographers for some years.

3. If none of them found anything bad to say about the algorithm after that time, then the resulting algorithm is "probably good enough".

The crucial point is that you have to attract the collective interest of many researchers for a long time, which is not an easy task. Some key ingredients include the following:

• Make sure that you publish your algorithm with the utmost clarity, and using the terminology accepted among cryptographers. Don't make them chase wild geese; they won't. See (for instance) the eSTREAM portfolio for examples on how this is done. (In particular, avoid using the word "cypher", which brands you as "someone who watched the Matrix movie too many times" instead of "someone who actually knows a bit of cryptography.)

• The algorithm should be interesting in some way; for instance, it might be substantially faster than existing alternatives (see eSTREAM again to get some information on what "fast" means for cryptographers).

• Don't patent. For cryptographers, patents mean that they either won't be able to publish their result, or that the patent holder (you) will make money out of their efforts, or both. Patents also mean that nobody will actually use your algorithm, since unpatented alternatives exist and are, by definition, cheaper.

A high level of peer scrutiny is normally achieved as part of competitions where some organization goes to the trouble of formalizing the requirements, gathering candidates, and running regular meetings and conferences. NIST did just that when they wanted a new symmetric encryption algorithm: it was the AES competition.

If you operate out of such a competition, and your algorithm is not that interesting, then you could still salvage it by using it to protect valuable data. For instance, convince a satellite TV broadcaster to rely on your algorithm. Then some cryptographers may find it amusing to blast it into smithereens, just to show you that things shall not be done that way.

Answer 2

There is a few different approaches to this problem.

Formal proof: Very few crypto systems has been formally proven secure. However two notable examples that have been formally proven secure are the one-time-pad and message authentication codes based on almost strongly universal families of hash functions.

Both of those are impractical for most usage cases due to consuming key bits each time they are used. But in certain limited settings they could be usable.

Physical assumptions: Crypto systems based on noisy channels or quantum physics are proven secure under certain assumptions about physics.

Standard mathematical assumptions: Many crypto systems are proven secure based on some standard assumptions about intractability of certain mathematical problems. Examples include factorization, discrete logarithm, the RSA assumption.

Standard primitives: Block ciphers and cryptographic hashes are two classes of standard primitives. Lots of constructions that combine those two can be proven secure under the assumption that the primitives are secure. Should a primitive be broken, you can replace it with another primitive from the same class. For example you can switch from MD5 to SHA2 and keep using the same constructions.

Security against known attacks: When designing a new construction you can prove that it is secure against those attack methods that broke the older construction that you want to replace.

Fail to break it: The more experts in cryptography you can get to try breaking a construction and failing to do so, the more confidence you can get in the construction being actually secure.

Combinations of the above: For example quantum cryptography combines the two provably secure constructions that I mentioned with physical assumptions to produce a full system, which is secure assuming that our understanding of quantum physics is correct. Security proofs is however no guarantee against implementation flaws if what you implement is different from what you proved to be secure.

The standard mathematical assumptions and standard primitives are each subject to proofs against known attacks as well as failed attempts to break them. Lots of useful constructions are possible if you have a secure block cipher. Thus lots of experts are trying to break AES in order for us to know if AES can be considered a secure block cipher. And when AES was first introduced its security against known attack methods was analysed.