Rotors of M-209 cipher machine.

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 E is strong if:

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

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

Functions like bcrypt, 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:

Two encryption algorithms chained.

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:

Triple DES or TDES: encryption, decryption, encryption algorithms chained.

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:

Triple DES or TDES: encryption, decryption, encryption algorithms chained.

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, Part 1 and Part 2.

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:

Key Length in Bits for Approximately Equal Resistance to Brute-Force Attacks, per Schneier
Symmetric Encryption 56 64 80 112 128 256 448 1024
Cryptographic Hash 112 128 160 224 256 512 896 2048
Asymmetric Encryption 384 494 768 1792 2304 10753 39031 234205

And, from NIST and NSA:

Key Length in Bits for Approximately Equal Resistance to Brute-Force Attacks, per NIST/NSA
Symmetric Encryption 80 112 128 192 256
Elliptic Curve encryption 160 224 256 384 521
RSA (asymmetric encryption) 1024 2048 3072 7680 15380

Why 521? Shouldn't that be 512? It looks like a typo, as otherwise the ECC key sizes are twice the symmetric key sizes.

However, read NIST's Recommended Elliptic Curves for Federal Government Use. The value really is 521. Also see RFC 5480 and the manual page for the ssh-keygen program.

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

Symmetric Ciphers
Algorithm Key Length Notes
DES 56 No longer considered secure enough against brute-force attacks, because 256 = 72,057,594,037,927,936 is not a big enough search space given today's hardware. See the EFF project to build dedicated DES-cracking hardware.
FEAL 64
LOKI 64 LOKI89 is insecure, LOKI91 is better
Skipjack 80 Widely speculated to have an NSA back door when it was to have been in the Clipper chip that would have been widely installed in hardware.
3DES 112, 168
IDEA 128 Patented, requires license
REDOC II 160 Patented, requires license
CAST-128 or CAST5 40–128 Available royalty-free worldwide for commercial and non-commercial applications, despite earlier CAST work being patented.
CAST-256 or CAST6 128–256 Available royalty-free worldwide for commercial and non-commercial applications, despite earlier CAST work being patented.
AES 256 Advanced Encryption Standard, replaces DES. Algorithm was originally known as "Rijndahl"
GOST 256 Государственный Станарт Союза ССР, Gosudarstvennyy Standart Soyuza SSR, Russian for "Government Standard of the Union of Soviet Socialist Republics", which dates it
RC6 128–256
Twofish 128–256 See: Twofish
Blowfish 32–448 See: Blowfish
Khufu 512
Khafre 512
RC2 8–1024 Patented, proprietary algorithm, requires license
RC4 40–2048 A stream cipher, unlike the block ciphers otherwise making up this list. (see other stream ciphers here) Optionally usable in TLS/SSL, but recommended against as weaknesses are well known as described here.
RC5 128–2040 Variable length key, up to 2040 bits
REDOC III up to 20,480 Patented, requires license
Block Cipher
Modes Of
Operation

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.

Asymmetric Ciphers
Algorithm Key Length Notes
DSA 1024 U.S. government standard for a component of digital signatures
ECDSA 1024 U.S. government standard for a component of digital signatures
El Gamal 1024–4096 Used in GNU Privacy Guard. Key size is variable, 1024–4096 bit keys are used in GnuPG.
RSA typically 1024–4096 At least 2048 bits are recommended today. Your computer should be fast enough to comfortably handle that key size or larger, while your attacker's computer might be getting close to being able to discover 1024-bit keys.

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