# How do we know a cryptographic primitive won't suddenly fail?

It took more than a decade from when MD5 looked like it was going to break to the point when it was actually broken. That's more than a decade of warning. One might suspect that we were fortunate that we got all that time. Even so, it took a long time for the world to move away from MD5.

How can we be sure that when our cryptosystems are flawed, that we'll have enough warning time to change them?

How can we be sure that, say, ECC won't get broken overnight?

• It was a wakeup call, which is why the SHA3 competition existed, even though nothing was known to be wrong with SHA2, only that it was similar in structure to SHA-1, which was similar in structure to MD5 – Richie Frame Jun 3 '15 at 23:33
• This actually happens all the time in the cipher competitions. Some fall immediately, but no one is using them, so who cares. Others show weakness but not total break. So we throw those out too. A number show no weakness, so we pick one. Then we wait a few more years. Eventually we start to use it. – mikeazo Jun 4 '15 at 2:06
• You can't be sure. You can't be sure any of them are secure, and you can't be sure you'll have advance warning of a break. See What's the mathematical model behind the security claims of symmetric ciphers and digest algorithms? and How to prove the security of the PRNG? for more. – D.W. Jun 4 '15 at 19:12
• You may want to read Introduction to modern cryptography by Katz&Lindell, They dedicate chapter 1.4 to the role of assumptions in Cryptography. The essence of it: We can't prove most cryptographic constructions unconditionally, because we only have mathematical assumptions about it. (ex.: We can't be sure that there isn't an algorithm for factoring in O(n)) – Yerg Jun 5 '15 at 6:41
• Related question: security.stackexchange.com/q/68377/47143 – kasperd Jun 5 '15 at 12:20

We don't ever know, in the information theory sense, that a crypto algorithm won't fail suddenly. If we ever knew that, we'd quit using it. However, it has been shown that when a crypto algorithm fails, it has a strong tendency to fail according to a two-step process:

• Most crypto algorithms fail quickly in the initial analysis phase, as we apply a pile of known crypto-breaking tools to the problem, along with gobs of expert opinion.
• The remaining algorithms have been shown to generally fail in phases. Attacks usually weaken the algorithm before finally breaking it. This is often measured in terms of bits. If a brute force attack would take 2^64 operations, and someone found a technique that takes 2^58 operations, then we say it has been weakened by 6 bits.

The latter is a perfect case for quoting "past performance does not predict future results." There is no guarantee that any future algorithm won't break at any unknown point in time. As a hedge against this, most modern crypto algorithms are designed in multiple rounds using one of the well known structures like a Feistel network. We generally understand how to make Feistel networks which fail gracefully, and those which do not have well-understood mechanics are often regarded with suspicion for many, many years. As a result, there is a tendency (not a guarantee) for measuring weakness in bits to be a reasonable indicator.

Perhaps a better question would be "how bad is it if your current crypto algorithm fails overnight?" If you can put a dollar figure to that, you can at least try to apply Bayesian statistics to put in place rational safeguards against this possibility.

We don't.$${}{}{}{}{}{}{}{}{}{}$$

Moderator note: This answer exists for historical significance, but it does not meet the guidelines for answering questions, so please do not use it as evidence that you can post similar answers here. This answer and its comments are frozen and cannot be changed. More info: meta.

• Longer version: security is about risk management. Will AES be broken tomorrow? Almost certainly not. Next year? Probably not. Next decade? Likely not. Next century? Who cares? At the point where you're using AES, you have far more likely risks than a break in your ciphers. – Stephen Touset Jun 4 '15 at 0:03
• This answer isn't useful. If this answer were the whole story, then there would be no reason to think that the likelihood of our ciphers breaking quickly is any different from the likelihood of them breaking gradually. In that case, there would be no reason to trust cryptography. Which may be the case! But I would expect to see an argument. (-1) – ogogmad Jun 4 '15 at 11:45
• In fact, this answer should be a comment. – ogogmad Jun 4 '15 at 11:46
• Your question in the comment is not the same question you asked. We don't KNOW that an algorithm won't be broken tomorrow the best that can be done is take steps to select an algorithm which has a low probability of being broken tomorrow. That falls short of the question of KNOWING and being SURE that an algorithm can't be broken quickly. – Gerald Davis Jun 4 '15 at 16:42
• I did provide a generalized answer to the more useful question "how can we reduce the RISK that an algorithm will be broken overnight" but honestly the most direct answer to the question you actually asked is above. The words KNOW, SURE, PROVE tend to have a literal meaning in cryptography. – Gerald Davis Jun 4 '15 at 16:52

yyyyyyy's answer is the correct short version.

There is only a single cryptographic algorithm that is mathematically proven secure: the one-time pad. It's hardly ever used because it's impractical: the key size is as large as the data to protect. You can prove that any algorithm that is secure against an adversary with infinite computational power is essentially equivalent to a one-time pad, and thus impractical in most situations.

Every practical cryptographic algorithm requires an assumption that some mathematical function cannot be computed in practice (because, for sizes used in practice, the best-known method require billions of computers to work for billions of years, or maybe even require more energy than exists in the universe). We believe that these functions cannot be computed faster because lots of very smart people have spent years of their lives trying in vain. It is, mathematically speaking, possible that someone will find a vastly faster method one day. We consider it unlikely because so many people have failed, but it cannot be ruled out.

A gradual break is more likely than a sudden break because scientific progress tends to make small increments at a time. Scientists are dwarves standing on the shoulder of giants (as Newton famously wrote, as did others before and after him). The popular image of a scientist suddenly becoming enlightened and coming up instantly with a novel, practical idea hardly ever happens. It takes time, and often multiple people, for ideas to mature. Before an actual cryptographic primitive is broken, it's extremely unlikely that there won't be warning signs, such as theoretical advances in a related topic, slight improvements in our understanding of the mathematical structure of the primitive that lead to small but still impractical reduction of computation requirements to break it, etc.

All of this applies to algorithms that have been vetted by the world's top cryptographers. An algorithm proposed by a person or a small team working on their own may well be thoroughly broken because someone else thought of something they didn't. When you involve a significant number of experts, the risk of “nobody thought of this” dwindles.

• Perhaps one might add that the one-time pad is only "perfectly secure" in the information-theoretical sense — modern cryptography knows more security definitions, under some of which the one-time pad is completely broken. – yyyyyyy Jun 4 '15 at 14:58
• @fgrieu Would it be ok to say that there is a single family of algorithms, the one-time pad and essentially equivalent variants (the key point being at least as much key material as payload, hence impractical)? – Gilles 'SO- stop being evil' Jun 5 '15 at 12:49
• The one time pad is the only provably secure encryption, but it is not the only provably secure cryptographic algorithm. Message authentication codes based on the Wegman Carter construction are also provably secure. And they are also more practical because the number of consumed bits only grows logarithmic with message size - not linear. One of the algorithms provide confidentiality, the other provides integrity, if you want both confidentiality and integrity you need to combine the two. – kasperd Jun 5 '15 at 18:06
• @yyyyyyy If you analyze OTP under a model for authenticated encryption, it will of course appear to be broken. But that's because you are using the wrong model to analyze it, since OTP was never designed to provide authentication. If you instead look at OTP protected with a Wegman Carter MAC, the result will come out differently. – kasperd Jun 5 '15 at 18:12
• @kasperd Of course. The intention of my comment was not to condemn the one-time pad, but rather to point out that the term "proven secure" is incomplete and thus potentially misleading: it fails to mention the considered notion of security. – yyyyyyy Jun 6 '15 at 11:40

The simple answer is nobody can prove that an algorithm won't break in a given period of time. The achievable goal is to increase the probability that no effective attack will be developed without warning. There are a couple of characteristics that indicate a particular cipher may remain secure and if degraded will do so 'gracefully'.

1. Time. Time is the major test of an algorithm's strength. The fact that researchers all around the world have had a decade to break SHA-2 and so far failed is a good sign. It doesn't mean that SHA-2 won't be broken tomorrow but the risk is significantly reduced compared to when SHA-2 was brand new. For that reason I have more confidence in the security of SHA-2 relative to SHA-3 over the short to medium term. Sometimes older is better.

2. Widespread usage. Time gives experts the opportunity to attack an algorithm but it doesn't mean much that nobody has broken xyz algorithm for a decade if nobody has tried to break xyz algorithm for a decade. A break on a major algorithm (SHA-2, AES, ECC) is a big deal and will attract more attention that some algorithm your brother cooked up. Correspondingly a large amount of the cryptanalysis occurs on the common high usage algorithms. This is one reason why rolling your own crypto is dangerous. The only way to have any confidence that it is secure is to have a large number of credible experts try to break it over a long period of time. That simply will not happen with an obscure algorithm.

3. Bit strength. 128 bit security (2^128 operations) is for all practical purposes beyond brute force both today and for the conceivable future. So why are there algorithms with higher bit strength if 128 bit is already 'unbreakable'? It is an insurance policy. Many attacks reduce the complexity of an attack. So instead of 2^128 operations to find a collision it might 'only' take 2^90 or 2^84. Those are larger numbers but it is feasible given enough time, money, and improved efficiency (Moore's law). On the other hand a break which reduces the complexity for a collision from 2^256 operations to even 2^160 is not usable. One should migrate away from the algorithm because there would be an increased risk that more sophisticated attacks would reduce that further but it would not present an 0-day risk. This is not an absolute guarantee. The break may be so severe that it cripples even a higher bit strength implementation but combined with the other principles that should be astonishingly unlikely.

4. An open transparent cryptographic algorithm/system It should go without saying that you should not trust your secrets to closed source systems which can't be independently verified, but this happens more often than you might imagine. Whole drive hard drive encryption for example is notorious for being a 'magical black box'. Optimally you would want to independently verify how the hash or cipher text is being produced. Cryptographic algorithms are deterministic, so if a device or software claims to be using AES-256 then given the same inputs (cleartext, key, IV) it should produce the same output as another known AES-256 implementation. If it doesn't then one of them is not implementing AES-256.

5. Nothing up my sleeves. Most cryptographic systems require some form of constants. It is always a risk that the constants chosen were chosen because they reduce the effectiveness of the system in a way known to the author but not others. 'Random' constants are a red flag because random values are unprovable. If an algorithm uses e971c59327cabde08439c813b70dae1a as a constant and the author says don't work it was generated on a CSPRNG you should be alarmed. How can you verify that e971c59327cabde08439c813b70dae1a was the result of a random roll and not deliberately chosen because it weakens the algorithm. Nothing up my sleeve numbers are usually used as a way to introduce pseudorandom constants. For example using the first 32 bits of the fractional part of the square root of the first n prime numbers. There is a low risk that such numbers could be chosen and also satisfy the conditions that would weaken the algorithm.

Combined these factors greatly reduce the possibility that an algorithm will break without warning however we can't prove that a cryptographic system is secure today or will remain secure tomorrow.

## Provably secure hashing algorithms

There are 'provably secure' hashing algorithms. Most hashing algorithms use rounds of mix, rotate, and reduce functions and they are assumed there is no faster algorithm to 'break' them than brute force but the problem is that for all these algorithms there is no way to prove that no faster algorithm exists to find a collision. Provably secure hashing algorithms are based on mathematical proofs of known hard problems (like integer factorization). The 'provable' comes from the fact that it can be shown in a mathematical proof that a collision (or some other attack) will require a given number of operations in worst case scenario as long as no faster solution for the underlying mathematical problem is known. If that assumption turns out to be false so does the stated security but it does provide a stronger theoretical foundation as many of these mathematical problems are well understood.

The problem with provably secure hashing algorithms is they generally tend to take longer and require more resources for a given level of security when compared to traditional hashing algorithms. SWIFFT is an example of a provably secure hashing algorithm. It is not suitable for all circumstances so this isn't an endorsement of that algorithm for any particular usage. Given the lack of widespread usage it would violate at least one of the factors outlined above so I include it more for completeness.