Is there a proof for showing any cryptogram is crackable?

Question

I commonly hear statements along the lines of "all cryptograms are crackable - it's only a matter of time".

Is there a proof to show that any cryptogram is "crackable"? The proof may be of a more philosophical form rather than relying on mathematical proofs. I really don't know what to expect, but would be fascinated by anything that could show empirically that all cryptograms are crackable (as opposed to a proof that all known strategies for encryption are crackable)

Related: Is it enough to say that given enough time and resources, all brute-force attacks will eventually succeed?

Answer 1

Not all ciphers can be broken, even by infinitely powerful adversaries.

When used correctly, the One Time Pad (OTP) is information-theoretic secure, which means it can't be broken with cryptanalysis. However, part of being provably secure is that you need at least as much key material as you have plaintext to encrypt. Such a key needs to be shared between the two communicants, which basically means you have to give it to the other person through a perfectly secure protocol (e.g. by hand/trusted courier). So, actually it just allows you to have your trusted meeting in advance, rather than at the time of transmitting the secret information.

To illustrate this, consider what happens if one tries to brute force OTP:
Since you have allowed an attacker infinite computational resources, he can keep guessing keys and calculating the corresponding plaintext until every key has been tested. Supposing the message was $b$ bits long, this would leave him with $2^b$ possible keys, each of which would generate a unique plaintext, making $2^b$ plaintexts. What is important here is that this means they would have candidate plaintexts corresponding to every possible bit-string of length $b$. This means, even if you knew the message was "Meet me at the stadium at 2?:15" (where ? is 0, 1, 2 or 3), you still wouldn't have any idea what the ? was, because the possible plaintexts would contain this string with every possible value of ?.

Most cryptographic methods we use now are computationally secure. There are lots of different ways to show this, and I'll just sketch two of them below:

• We might come up with a reduction to a problem conjectured to be hard (e.g. the Diffie-Hellman Problem or Discrete Log Problem). That is, we prove that "If you can break my cipher, you can solve Some-Hard-Problem".
  Meaning our problem is at least a difficult to solve as Some-Hard-Problem. So, if the problem is indeed hard to solve, then so must be cracking our encryption.

• Another method used is that you might be able to prove a lower bound on the effort required to break a cipher, in terms of some security parameter. Then, the security parameter can be set such that this lower bound is higher than the strength of any computer that could possibly be built. Notice, the infinitely strong computer described in the question could still break such a scheme, but we could fix the parameter so high that it would be impossible to make a computer that could break it.

_{Possibly of interest: wikipedia:provable security}

Answer 2

I commonly hear statements along the lines of "all cryptograms are crackable - it's only a matter of time"

Using a perfectly random key which is as long as the message itself, not a pseudo-random key, cannot be broken no matter how fast the attacker's computer is. This scheme is called one-time-pad and its security is guaranteed by information theory and doesn't rely on the security of specific encryption algorithms or limited computation power.

While all other schemes can be broken by sufficient computation power, increasing key-sizes quickly get to the point where "enough time and resources" is unrealistically large. Every additional key bit of a symmetric cipher doubles the cost of breaking.

For example the chance of breaking a symmetric 256 bit key with the best conventional computer allowed thermodynamics using all the energy emitted by our sun over its whole lifetime still is still negligible. With slightly larger keys even the energy of the whole universe is insufficient.

So it is safe to say that brute-force with conventional computers (or quantum computers as we envision them) is no practical threat. For details about this, read How much would it cost in U.S. dollars to brute force a 256 bit key in a year?

With lots of resources you can break almost everything in practice by compromising an endpoint. Using a zero-day exploit to plant a Trojan, placing a camera looking at the keyboard, threatening the victim or their family, etc.

Sometimes it's also possible to cryptoanalyze the cipher itself, but that's pretty rare.

Answer 3

Here is the actual proof (hopefully in close to plain English) that to encrypt n bits with perfect security you need n bits of key, and if you have less your system is Information-theoreticly unsecure and can be broken by an adversary with unlimited computing power.

The basic principle of what we mean by secure here is, for all messages m in the message space (M) and for cypher-text c: P(m|c) = P(m) . ie the probability of m being the message is unchanged when you know c for all m's in M (which means all possible m's). ie ie knowing the cypher text is useless and your best guess is anything the same length as the message.

If we have a cypher-text c, we can try to decyrpt it with every possible key k in the keyspace (K). The maximum number of different potential messages we get from doing this is the number of possible keys (the size of the keyspace, |K|). If the size of the message space (|M|) is larger than (|K|), then there exist some messages m in M that we don't find by trying every key and that cannot be the actual message that was encrypted. ie P(m|c) = 0. As long as this message was possible beforehand (it wasn't absolutely known before looking at the cypher-text that it wouldn't show up), P(m|c) != P(m) and so it cannot be secure.

Pretty much every cipher practically fails this definition of security, and it can even be proved cyphers that are secure under this definition are basically one-time pads. I'll leave it to the other answers to describe more practical security definitions.

Answer 4

Consider that a cryptogram is only one very tiny piece of a secure message communication system. People focus unnecessarily on it because it contains and protects the actual secret, but every piece of the overall system has to be secure for the secret to remain protected.

That system includes not only the obvious technical problems (exchanging and protecting keys, computer hackers tampering with the equipment or network, traffic analysis, etc.) but with the people using it as well. They can be tricked into communicating with or trusting the wrong party, coerced into revealing their secrets, or fail to adequately guard whatever their responsibility is (weak passwords, casual behavior.)

I don't believe that AES will ever fall to a brute force attack. I don't think it's the weakest link in any of these systems, and therefore it's not profitable for an attacker to try, because there are so many other avenues to exploit.

So the answer to your question is no, not every cryptogram can be broken, primarily because they don't need to be. Instead, I would claim that almost every system can be broken, because every system deployed so far has had some weak components.