Cipher Strength and Key Length

What Does It Mean If A Cipher Is "Strong"?

We want to protect the confidentiality of some data, which means we need to encrypt it. But which cipher should we choose? This page explains how to select a cipher that will be strong enough. Security relies on more than simply selecting the cipher, we also must be careful of how we use it and how we generate and manage the keys.

A cipher algorithm is strong if:

• Given some pairs of plaintext and corresponding ciphertext, an attacker can only guess at the key used, even if they have a copy of the algorithm. Knowledge of a strong algorithm provides no advantage to the attacker.
• You can't search for "close" keys. Popular movies and TV shows to the contrary, decryption of real algorithms is all-or-nothing. No partial messages start to appear. If your key is off by just one bit, the output appears to be essentially random.
• A slight change in the plaintext or in the key causes a drastic change in the ciphertext. That is termed confusion. The drastic change is not localized but is spread throughout the resulting ciphertext. That is termed diffusion.

Note that each of those features implies the others. For strong asymmetric cryptography, an additional feature is:

• Given a copy of the algorithm and one of the keys in the pair, an attacker can only guess at the other key.

Inventing New Cryptosystems and Calling Them "Strong"

What if someone says that they just invented a new and very secure cipher algorithm?

That means that they must be either a mathematical genius or a fool. Which is the far more likely explanation?

What if someone says that a cipher algorithm must be kept secret for security?

We have known that "security through obscurity" is ineffective for well over a century. Auguste Kerckhoffs (1835-1903) mathematically proved that the security of a cryptosystem must not depend on keeping its algorithm secret, as discussed on a previous page. See his article "La cryptographie militaire", from Journal des sciences militaries, vol IX, pp 5-38, Jan 1883.

19th century computing pioneer Charles Babbage wrote the following in his autobiography, Passages from the Life of a Philosopher:

One of the most singular characteristics of the art of deciphering is the strong conviction possessed by every person, even moderately acquainted with it, that he is able to construct a cipher which nobody else can decipher. I have also observed that the cleverer the person, the more intimate is his conviction. In my earliest study of the subject, I shared in this belief, and maintained it for many years.

In a conversation on that subject which I had with the late Mr. Davies Gilbert, President of the Royal Society, each maintained the he possessed a cipher which was absolutely inscrutable. On comparison, it appeared that we had both imagined the same law.

Both men had re-invented the flawed autokey system of Cardano and Vigenère.

What "Flawed" or "Weak" or "Attacked" Might Mean

When cryptanalysts say than a cipher or hash algorithm is flawed or weak, or that it can be successfully attacked, they do not necessarily mean that it can be trivially broken. They mean that it was not quite as strong as we thought it was. The attack very likely remained theoretical rather than practical.

But keep in mind that a defined algorithm stays exactly the same for all time, while attacks only get better. The mathematical understanding and computer speed used in attacks will improve over time. A theoretical weakness now may turn into something very serious in the future.

Strong and Weak Keys

The key must be hard to guess — for example, something better than the binary representation of the string secret — and so they need to look fairly random.

English text has little randomness. The entropy or unpredictability of typical English text is between 1.0 and 1.5 bits per character, as low as 0.6 to 1.3 bits per character for some samples. [Shannon, Claude E.: "Prediction and entropy of printed English", The Bell System Technical Journal, 30:50-64, January 1951]

What's more, some algorithms have some specific key patterns that are called weak. These weak keys inadequately obscure the cleartext information, the ciphertext leaks information about the cleartext or about the key itself. These weak keys are typically those with large blocks of all zeros or all ones, or large blocks of alternating 010101010101... or 001100110011... or similar.

Keys should appear to be highly random binary patterns. For example, a randomly generated 64-bit key in hexadecimal (base 16):
79baed51c147dc5d
And the binary equivalent, broken into 8-bit blocks:
01111001 10111010 11101101 01010001 11000001 01000111 11011100 01011101

Functions like bcrypt, Argon2, PBKDF2, and scrypt can be used for key stretching, making a human-selected passphrase much resistant to attacks.

Why is Triple-DES only 112 bits, when DES is 56 bits?

Oh, it's even worse than that. But first, realize that worrying about 3DES is like rearranging deck chairs on a sinking coal-fired steamship calling CQD or SOS on a spark-gap transmitter.

Encrypting twice in a row, using the same algorithm and two keys, does produce ciphertext:

However, if the encryption algorithm is what is called a cryptographic group, then there exists some third key K3 where a single encryption with K3 alone produces the same ciphertext. Consider this from the attacker's point of view — all you need to decrypt is K3, so double encryption as above uses twice the work and provides no more security than one encryption step!

Even if the cipher is not a cryptographic group (and DES is not), there is something called a meet in the middle attack that makes the sequence of encryption operations no more secure against a brute-force attack than just encrypting it once.

OK, so chaining multiple encryption steps is not useful...

Triple-DES works by encrypting with one key, then decrypting with a second key, and then encrypting with a third key:

Yes, for DES those are three 56-bit keys and 3×56 = 168 bits. However, due to that pesky meet in the middle attack mentioned above, the complexity (meaning the computational work required) for an attacker is no greater than it would be for encrypting with one key, decrypting with the second, and then encrypting again with the first key:

Since you get no better security against determined cryptanalysis, the effective strength is no better than that of a 112-bit symmetric key no matter if you use (K1,K2,K3) or just (K1,K2,K1) as above. [see ref 1 below]

Now, in 1990 a known-plaintext attack on two-key 3DES was found, and US NIST rates two-key (K1,K2,K1) 3DES at 80 bits equivalent strength, and three-key (K1,K2,K3) 3DES at 112 bits equivalent strength. [see ref 2 below, and note the vast amounts of plaintext-ciphertext data required!] I find it very interesting that the NSA's formerly classified Skipjack cipher has an 80 bit key. The coincidence of 80 bit key length is a bit striking....

Also see the well-written Wikipedia article on Triple DES, which points to further papers.

References:
[1] R. C. Merkle and M. Hellman, "On the Security of Multiple Encryption", Communications of the ACM, vol 24, no 7, 1981, pp 465-467. This is summarized as "Triple encryption, with three independent keys, is as secure as one might naively expect double encryption to be" in Bruce Schneier, Applied Cryptography, John Wiley, 1996, ISBN 0-471-12845-7, sections 11.3 and 15.1-15.3.
[2] "A known-plaintext attack on two-key triple encryption", van Oorschot, et al., EuroCrypt '90, and NIST Special Publication 800-57, "Recommendation for Key Management", Part 1, Part 2, and Part 3.

OK, So How Long Are The Keys?

The algorithms work differently, so you cannot simply compare key lengths to decide which is more secure against a brute-force search.

Very generally speaking, to get the same strength as an N-key symmetric cipher, an elliptic curve algorithm or a cryptographic hash needs to have a key 2N times as long, and an asymmetric cipher needs to have a key roughly 10N times as long or longer. Sorry, that's just the way the math goes. This is why asymmetric encryption is nice for key management, but symmetric algorithms are then used for bulk data encryption. [See section 1.8.4 of Handbook of Applied Cryptography, Menezes, van Oorschot, and Vanstone, 1997, available as a free PDF download]

One analysis of this is found in Applied Cryptography, Bruce Schneier, ISBN 0-471-12845-7. Thanks to Naftali Fasten for a really nice summary of parts of its chapter 7. A table based on that is:

And, from NIST and NSA:

And now, some specific examples of cipher algorithms and their key lengths:

Block ciphers must be used in some specific mode — Electronic Codebook or ECB (usually very insecure), Cipher Block Chaining or CBC, Cipher Feedback or CFB, Output Feedback or OFB, Counter or CTR, Galois/Counter Mode or GCM, and more.

The Wikipedia page has a basic overview. For the full details see "Evaluation of Some Blockcipher Modes of Operation" by Phillip Rogaway, University of California, Davis. It's a 159–page evaluation carried out for the Cryptography Research and Evaluation Committees for the Government of Japan.

A number of Elliptic Curve Cryptography algorithms are available. For a while it seemed that ECC provided a backup in case a general-purpose quantum computer was finally developed. But in 2015 the NSA announced that post-quantum cryptography would need some other basis. A Post-Quantum Crypto conference series was already running. Key sizes will be large, at least several thousand bits and ranging up to several million bits for some algorithms, and much study remains to investigate their theoretical security.

Next ❯ Diffie-Hellman Key Negotiation and Secret Sharing