# Tactics available to help prove security of a new system?

I believe that the accepted tactic to "prove" a system as secure is to allow the crypto-community to review it and if no vulnerabilities are found over a long period of time (5 or 6 years), then a new system can be accepted as secure until proven otherwise. Please correct me if I'm wrong.

That aside, are there any set of requirements a developer can proactively test their cipher system against before a public release?

I'm working on a large key (4096 bit), symmetric encryption system and I'm doing my best to be weary of the "anybody can make an encryption that they themselves cannot break" trick of believing that my cipher is unbreakable.

What kind of tests can I run on the process or the output? Are there good ways to measure entropy? What statistics should I expect after encrypting a section of data? I know there won't be some magic function that proves I'm secure, but I certainly don't want a public release followed immediately by being broken by a simple problem that some data analysis would have found.

-
I'll be the bad cop and say that if (1) you've already designed the cipher and only now are thinking about security, (2) are new to cryptanalysis and (3) you think a 4096 bit key is good — in fact if just one of these things — you are already in over your head. I don't want to discourage you and sometimes learning by doing is the best way but designing secure encryption schemes is very hard and requires years of expertise. (I say this as someone who myself would never dream of designing a block cipher or hash function.) –  PulpSpy Jul 19 '11 at 14:55
We've (my buddy and I) been looking into security the entire time, from day one. We've looked into many different attacks and have been researching implementation details in this field for almost 7 years. I ask this question because we have some very new techniques that need to be thoroughly tested and vetted before publication. I tried searching for common security tests but most scholarly sources tell you "it's secure when the community can't break it." I am looking for any/every way to prove this process. –  Corey Ogburn Jul 19 '11 at 15:08
If you have some funds available then perhaps setting up a kaggle would attract the talent to test your cipher. Of course you get what you pay for and, as others have pointed out, by far the most likely outcome is someone cracks your method and collects the cash. –  user13790 May 30 '14 at 2:40

1. Prove resistance to differential cryptanalysis.

For example, this presentation: Provable security against Impossible Differential Cryptanalysis. Or this paper: ProvableSecurity Against a Differential Attack (1995)

2. Prove resistance to linear cryptanalysis.

For example: On Measuring Resistance to Linear Cryptanalysis

3. Run a bunch of statical tests against the cipher.

-

A quite common way to actually prove something is building a system on already known components, and then proving the security of the composed system, given the security of the components.

Most often the paper has a theorem like

If the function F has property Y, then this new function G has property X.

The proof then shows that if someone can attack the property X of G, this gives an attack on the property Y of F.

Then we take for F a known cryptographic primitive, which was already studied by the community, and seems to have the necessary property.

Often this proof works even for whole families of algorithms at once. This way we can get a family of stream ciphers from a family of block ciphers (by a mode of operation), a keyed MAC from a hash function (HMAC), etc. And when the used base component is broken, you can simply switch to another one.

In some cases you can even build your composite system on more than one component, such that breaking only one of them will not help breaking your composed system (i.e. breaking your composite system means breaking all of the components).

Of course, this will most probably not help for a completely new system not based on anything.

-
This is a good approach for protocols built on standard building blocks, but unlikely to be useful to the poster, who says he is designing a new symmetric-key encryption scheme. –  D.W. Aug 4 '11 at 20:34

The most important take-away is that if you are asking this question, you are almost certainly not qualified to design a secure cryptographic primitive. Sounds harsh, but I mean it in all earnestness.

You wouldn't trust someone who hadn't been to medical school to do surgery on you. Similarly, we wouldn't trust someone who doesn't already know the research literature on cryptanalysis to design a new cipher. More importantly, history shows that amateurs who try to design a new cipher without having spent year studying the research literature almost inevitably invent something useless -- either a cipher that is insecure, or a cipher that is hopelessly non-competitive with the state of the art.

As Bruce Schneier once wrote, "anyone can invent a cipher they themselves can't break". The hard bit is to design a cipher that no one else can break. Usually cipher designers have blind spots for the weaknesses in their own design; by definition, they design their cipher to defend against all the attacks they can think of – but it's easy for there to be other attacks the cipher designer didn't think of, and in that case the cipher designer is unlikely to be aware that their own creation is flawed.

On top of that, the world doesn't really need new ciphers. Our current ones are pretty good. I mean, I'm not saying they're perfect, I'm not saying it is impossible to improve upon them, but I'm saying they're for the most part good enough for all engineering purposes – a modern cryptographic primitive is almost never the weakest link in the security of a system. So working on this problem is in some sense likely to be working on the wrong problem.

So the best advice I can give you on how is: give it up. Don't expect your cipher to be any good. (If you really, really want to learn how to design a new cipher, you could start by studying the research literature on cipher design and cryptanalysis – but be prepared that this will take years of dedicated study.)

As far as how to vet a new cipher, here's how it tends to work. Confidence in the security of cryptographic primitives usually comes from the fact that a lot of really smart, knowledgeable people have tried really hard to break these algorithms, without making much of a dent at all. Of course, this is not a guarantee that no clever attack exists – it is always possible there is some incredibly sneaky mathematical shortcut attack that no one has been clever enough to find, but the more people who try to find one and fail, the less likely that looks. For practical purposes, it seems unlikely that a garden-variety attacker is going to discover an attack that dozens of really smart people tried to find and failed.

It is important to understand that this process does not provide a "proof" of the security of the cryptographic primitive. We have no proof that SHA256, or AES, or RSA are secure – it is widely believed that they are secure, but I could not give you a mathematical proof of that fact, and who knows, it is always possible that widespread beliefs are wrong. There are fundamental reasons why it is incredibly difficult to produce an ironclad mathematical proof of security for most cryptographic primitives.

It is also important to understand that vetting a new primitive is extremely expensive: it takes person-decades of effort from intensely-talented specialists. This is one reason why there is little or no demand for new ciphers, particularly from amateurs who don't already have a deep understanding of the field. The extremely high cost of vetting a new cryptographic primitive is one reason that smart users of cryptography generally try to use existing, vetted primitives, rather than inventing their own. If you invent your own scheme, it is extremely unlikely you'll be able to arrange for as much analysis and vetting of your own scheme as the standard ones have already received – so don't do that. Don't "roll your own". Instead, I advise people to use existing, standard, accepted primitives, like AES, SHA256, RSA, etc.

-
While what you say is true, I recall that a lot of great inventions has been made by people who just did not know that the problem they are trying to solve is unsolvable. :) –  Arsen7 Aug 4 '11 at 7:03
I understand what your saying and I know I have a huge amount of work ahead of me, but I really feel like I'm on to something. I asked this question because even though I've gone through years of research, I accept the fact that I don't know everything and that I have a lot to learn from my peers in the field, not to mention we're in beta and if I don't ask it, somebody eventually will. I've worked for years researching, testing, breaking, re-breaking, and expanding on the cipher I do have. I'm going to fail a lot before I succeed, but I only need to succeed once. –  Corey Ogburn Aug 4 '11 at 15:04
+1, and I completely agree with the sentiment here, but want to make an addendum to "The hard bit is to design a cipher that no one else can break." - the really hard part is doing this while having something that is at all competitive from an implementation perspective. It wouldn't be that hard for someone with a decade or so of experience to come up with an algorithm that would be secure if you used, say, 10000 rounds, but which would probably not be secure if you wanted it to be as fast as, say, Rijndael or Twofish. Of course most such people know enough not to bother doing such things... –  Jack Lloyd Aug 4 '11 at 17:04
@Corey: Part of the problem is that it is inherently difficult to know when you fail; the most likely outcome is that you think you've succeeded, but actually you failed (actually there is a subtle flaw in your cipher that you are not aware of). I agree with Jack LLoyd that performance is also the key challenge. I'd say, if you want to succeed at your goals, your best bet is to start by trying to cryptanalyze ciphers others have designed. if you demonstrate ability in that (e.g., by publishing a cryptanalysis paper at a respected conference), then you might be ready to design a new cipher. –  D.W. Aug 4 '11 at 20:31

In addition, NIST Statistical Tests and Diehard Battery of Tests of Randomness are good tests.Some tests proposed here and here for stream ciphers. Passing these tests is essential but does not enough. For more information see introduction of first link.
Also Provable security may be useful.

-
Fair enough, but a word of warning: those statistical tests will only find blatant flaws (absolutely gaping-wide holes). So passing the test tells you almost nothing. It would be very easy to get a false sense of security from passing those tests. –  D.W. Aug 4 '11 at 20:33
Thank you for your comment. Yes, Passing these tests is essential but does not enough. –  ir01 Aug 4 '11 at 22:02