You’re
evaluating cryptographic solutions and you come across the term bit length for
various security parameters. So, what is a bit length? And what size is
sufficient to secure your data? The most common bit length refers to the encryption
algorithm, and another important length refers to key management.
Algorithms
In a
digital system, data is represented as a sequence of bits. That is, a sequence
of 0’s and 1’s. A cryptographic algorithm is the means by which an encryption
device scrambles data. It is a mathematical function which converts unencrypted
data (called plaintext) into encrypted data (called ciphertext).
Most
commonly encountered algorithms are block algorithms. This means that they
operate on blocks of data of a fixed size, encrypting one block after another. An
example is the Advanced Encryption Standard (AES) algorithm, which takes 128
consecutive bits of plaintext and transforms it into 128 bits of ciphertext. The
block size of AES is said to be 128-bits. AES can be thought of as a
permutation on 128-bit blocks, mapping every 128-bit sequence to a unique, seemingly
unrelated 128-bit output sequence. Note: The block size does not bear directly
on the encryption strength.
Cryptographic Key
Now,
if the permutation is known, ciphertext can be reversed to its original
plaintext state. A cryptographic algorithm prevents unauthorized parties from
reversing the ciphertext by use of a key. A cryptographic key for an algorithm
is a string of bits (0’s and 1’s) of a defined length called the key length. An
algorithm that uses keys of length “n” is often called an n-bit algorithm. The
key is used in the definition of the algorithm itself, and each distinct choice
of key turns the algorithm into a distinct permutation. Without the key, the permutation
is not known and the ciphertext cannot be reversed.
An
adversary may attempt to decrypt ciphertext by guessing the key and using it to
see if the ciphertext decrypts into something that looks like plaintext. In
practice, this means testing every possible key until the one that was used is
found. A key search can be time-consuming if not impossible, even with modern
computers. The reason is the mathematics of exponentiation.
Inside the Math
An
n-bit key is a sequence of 0’s and 1’s of length n. Since there are two
possibilities for each bit in the key, there are 2n different n-bit
keys. Thus, if an algorithm used an 8-bit key, there would be 28 = different
256 keys to try. The number of keys grows exponentially. A 16-bit algorithm has
216 = 65,536 keys to try, and a 32-bit algorithm has 232
= 4,294,967,296 keys. Modern algorithms use length of 128 or 256 bits. 2256 is roughly the same as the
estimated number of particles in the universe.
Examples
of algorithms include DES (64-bit blocks, 56-bit keys), IDEA (64-bit blocks,
128-bit keys), and AES (128-bit blocks, and implementations supporting 128-,
192-, and 256-bit keys).
What Key Size is Sufficient?
How
large of a key is large enough to prevent a successful key search? Computers
can search through possibilities very quickly, but even they are eventually
overwhelmed by the task. The following table estimates the amount of time it would take to find the
correct key on a computer capable of trying one key every microsecond
(ms, a
millionth of a second), as well as on a parallelized network (one in which the
search is split among many computers) capable of testing a million keys every
microsecond.
|
Length of Key
|
Number of Keys
|
Testing 1 key per ms
|
Testing 106 keys per ms
|
|
32
bits
|
232
= 4.3 x 109
|
231ms = 35.8
minutes
|
2.15
milliseconds
|
|
56
bits
|
256
= 7.2 x 1016
|
255ms = 1142 years
|
10
hours
|
|
128
bits
|
2128
= 3.4 x 1038
|
2127ms = 5.4 x 1024
years
|
5.4
x 1018 years
|
|
256
bits
|
2255
= 5.8 x 1076
|
2255ms = 1.8 x 1063
years
|
1.8
x 1057 years
|
Summing It Up
Certain
things stand out from the table above. First, a 56-bit algorithm such as DES is
still secure against anything except an organized parallelized effort. Second,
the key space of a 128-bit algorithm is sufficiently large to resist a key
search from even national-scale efforts. And finally, even if the available
computing power and speed doubles every year, 128-bit keys will remain secure
over our lifetimes. No computer or network of computers will be able to search
every 128-bit key. For this reason, 128- and 256-bit algorithms are
recommended, and bit-sizes beyond these are considered superfluous.
