What is the difference between "key length" and "bit strength"?

Question

On occasion, I hear the terms "key length" and "bit strength" used interchangeably. Are these the same things? Or are they different?

Answer 1

I'd use bit length for the size of something, such as a key.

I'd use bit strength as the base 2 logarithm of the cost of an attack. i.e. it costs about 2^n basic operations to break something.

A brute force attack against an n bit key that simply tries to guess the key costs 2^(n-1) calls to the encryption function on average, which lead to this convention of expressing the strength of an algorithm in bits.

Thus you could understand "n bit strength" as "Breaking this costs approximately as much as breaking a symmetric encryption algorithm with an n bit key."

But they differ in other cases. A few examples:

• An RSA key with a length 2048 bits only has a strength of about 112 bits.
• A hash with length 128 bits can only have 64 bits of collision resistance.
• 3DES takes a 168 bit key, but only offers 112 bits of security, due to a meet-in-the-middle attack.

Answer 2

They are pretty similar but are slightly different. The key length is simply the length, in bits, of the key used for cryptographic operations. If the key is chosen randomly and the algorithm doesn't have any vulnerabilities, then the bit strength is exactly the same as the key length.

The bit strength is a measure of how resistant something is to guessing (the amount of entropy). It can apply to things like passwords as well (which are technically a key in that they unlock information, but are very different from something like a properly formed encryption key used for stream encryption.)

Many things can reduce the actual bit strength of a key. Problems in the random number generator or cryptanalysis attacks on an encryption system can reduce the number of guesses you have to make to attack the system, thus reducing the bit strength or key strength below the number of bits actually used in the key.

Say for example that I had a key that was 64 bits long. The key length is 64 bits because that is the length of the key used on a stream to encode it. Lets say, however, that we figure out that the first byte of the string is always the same as the first byte of the key, this would mean that we could eliminate many guesses for trying to guess the key. Even though the encryption works with 64 bits of key, we only need to guess 56 bits of the key because we know 8 of them, thus, the bit strength is only 56 bits.

Similarly, if we take the example of a password, a password may be 8 characters long and thus take 8 bytes (64 bits) to store, but if the password can only be numbers and upper and lower case letters, then many values can't be used, so the bit strength is much lower than if the password was entirely random bits rather than a limited set of characters.

Answer 3

When the bit strength is k, this means: "the algorithm stands its ground against attackers who cannot compute at least 2^k-1 elementary operations".

When the bit length is k, this means: "the key, or at least the main component of the key, can be represented as a sequence of k bits".

Exhaustive search is about trying all possible keys until one works. This is the least subtle of all attacks. On average, if the bit length is k, then it takes 2^k-1 tries to find the actual key. Therefore, bit length and bit strength are equal when the algorithm is search that exhaustive search, although being the stupidest of attacks, is also the best possible (or at least the best known).

That exhaustive search is the best possible attack is the normal situation for strong "symmetric" algorithms (symmetric encryption like AES, MAC algorithm such as HMAC...). AES-128 uses a 128-bit key and is expected to offer a strength of 128 bits. On the other hand, for asymmetric algorithms such as RSA or ECDSA, keys are not simple sequences of bits; they have a lot of mathematical structure, and that structure can be exploited to break them faster. For instance, the main component of a RSA pubic key is a big number called the modulus, and factorizing the modulus into its prime factors is sufficient to recover the private key. Integer factorization can be done much more efficiently than simply enumerating possible private keys !

RSA is a good example. An "RSA-2048" key is a RSA key such that the modulus is a number between 2²⁰⁴⁷ and 2²⁰⁴⁸. The modulus, when encoded in binary, thus takes 2048 bits -- this is the bit length of the key. Factoring the modulus with the best known algorithms would take up about 2¹⁰⁰ or so simple operations, so the bit strength is about 100 bits. Encoding the complete public key into bits would need storing not only the modulus but also the public exponent, so it will need a bit more than 2048 bits (not much more, because the public exponent is a short integer).

Translating bit lengths into bit strengths for asymmetric algorithms requires taking care of a lot of subtle details and making predictions on future technology, and sometimes requires downright divination. See this site for a lot of data on this subject. Formally, from the NIST point of view, a 2048-bit RSA key is "as good as" a symmetric algorithm with 112-bit strength (which is, incidentally, what 3DES is reputed to provide).