Just Enough Cryptography

Cipher Strength and Key Length

What "Strong" Means

A cryptographic algorithm E 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 films 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 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 a cryptanalyst says 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 needs to 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 01010101...

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:
111100110111010111011010101000111000001010001111101110001011101

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

Oh, it's even worse than that....

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

plaintext --> encrypt --> encrypt --> ciphertext
                 ^           ^
                 |           |
                 K1          K2

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:

plaintext --> encrypt --> decrypt --> encrypt --> ciphertext
                 ^           ^           ^
                 |           |           |
                 K1          K2          K3

Yes, that should be 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:

plaintext --> encrypt --> decrypt --> encrypt --> ciphertext
                 ^           ^           ^
                 |           |           |
                 K1          K2          K1

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", August 2005, p 63, http://csrc.nist.gov/publications/nistpubs/800-57/SP800-57-Part1.pdf and http://csrc.nist.gov/publications/nistpubs/800-57/SP800-57-Part2.pdf

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:

All the way back to the start Terminology Symmetric and Asymmetric Ciphers One-Time Pads Cipher Strength and Key Length Next — Diffie-Hellman Key Negotiation and Secret Sharing Cryptographic Hash Functions Digital Signatures and Certificates Cultural Cryptography Further Reading

Back to the Security Index

Home Unix/Linux Networking Cybersecurity Travel Technical Radio Site Map Contact

Tweet