Sunday, July 20, 2008

Are AES 256-bit keys too large?

ice This may seem an odd question given that since the mid 70's discussions about cryptographic keys have been mainly concerned about their potential shortness. While the risks of using short keys are apparent, there are risks lurking at the other end of the gamut as well. We can have too much of a good thing, and also think we have a good thing when we in fact don't.

The adoption of the AES cipher has progressed quite rapidly, greatly assisted by being mandated as a US government standard. As a technology AES has nonchalantly skipped along the Gartner hype cycle and nestled into the Plateau of Productivity. AES supports key lengths of 128, 192 and 256 bits, and many commercial offerings, to encrypt laptops or USB sticks for example, supply AES at the maximum 256-bit key length. Will attackers be able to bypass the high level of security implied by AES-256? In at least two significant cases, the answer is likely to be yes. But we require some background first.

The economics of AES keys

Modern block ciphers encrypt by mixing data over a series of rounds to produce a complex nonlinear relationship between the plaintext (message), ciphertext and key. For AES-128 , AES-192 and AES-256 the number of rounds is 10, 12 and 14 respectively. So AES-256 requires a further 4 rounds over AES-128 to mix the additional key bits, and is consequently only 40% slower. Thus a 128-bit key can be doubled (squaring the effort of exhaustive attack) for a relatively modest cost in performance. Therefore, unless performance is critical, maximal length 256-bit keys are a natural choice for AES deployments.

haystack So given that AES-256 is likely to be deployed widely, what type of security can we expect? Well, when a secret key cipher has a key length of n bits this is interpreted to mean that, in the absence of any weaknesses, the security of the cipher is proportional to the cost of a brute force attack on a key space of size 2^n. That is, a needle-in-a-haystack search problem where there are of 2^n pieces of hay. On average the correct key will be recovered after 2^(n-1) guesses, or searching half the key space. So AES-256 should be secure against an attacker who has materially less than 2^(255) = 10^(76) resources at their disposal. Well, unless you have a need to approximate the number of hydrogen atoms in the observable universe, you will never encounter a number as large as 10^(76). So there is little hope in attacking AES-256 by direct brute force methods, but is this the only way to get at the data protected by such large keys?

AES and Passwords

It is common for laptop and USB encryption solutions to use one of the following key management systems:

  • Derive the device-encryption key directly from a user-supplied password, using a method such as the Password-Based Key Derivation Function.
  • Randomly generate the device-encryption key, and then encrypt this key by a key derived from a user-supplied password

doll The latter approach is preferable since it actually protects data with a full length key, and further does not require data re-encryption when the user changes their password. It is possible to create more intricate chains of key encrypting keys, similar to those encapsulating Russian dolls, but ultimately the security of the device-encryption key reduces to the strength of user passwords.

How large a password space do we need to provide the same security as a 256-bit key space? Assuming that the password consists of characters drawn from the set of 94 printable ASCII keyboard characters, the password would have to be 40 characters in length. That is, a user would have to select a random 40 character password to achieve the same security against a brute force guessing attack on an AES-256 key. Such passwords would probably take about 20 seconds to be entered by a typical person.

In practice we can expect user passwords to be less than 15 characters in length, and certainly not chosen uniformly. So we have an example of strong cryptography being bypassed via far weaker passwords. Some laptop encryption vendors now offer two-factor authentication to protect their keys, but such solutions are not widely deployed as yet.

AES in Security Protocols

Another place where we need to re-evaluate the security of AES-256 is in protocols like S/MIME, SSL and TLS where data is protected by a bulk encryption method, but the key of the bulk encryption method is protected by a public key. For example, TLS now supports AES-256 as a ciphersuite, in particular, in combination with RSA for key establishment. Since the AES-256 key is derived deterministically from the keying material protected by RSA encryption, then the strength of the RSA key should be proportional to the strength of the AES-256. But how large does an RSA key need to be so that it provides similar security to an AES-256 key?

In 2001 this problem was considered by the well-known and respected researcher Arjen Lenstra and his results indicate that the equivalent RSA key length to match AES-256 security would be more than 13,000 bits! Since RSA is commonly deployed in the range of 1024 to 4096 bits, we therefore have a huge discrepancy as compared to AES-256 security. The size of RSA keys can in theory be increased indefinitely, but computational efficiency becomes the limiting factor. For RSA and discrete logarithm system that use n-bit keys, the computational cost of using these systems (particularly for decryption) is proportional to n^3 operations. So if the key size is doubled from n bits to 2n bits, then performance will decrease by a factor of approximately 8. Increasing a 1024 bit key 13-fold will reduce performance by a factor of over 2000.

For protocols such as TLS and S/MIME, the security of AES-256 will be bypassed by attacking the public key system protecting the AES keys. In this case, without consideration for other contextual security parameters, AES-256 provides a false sense of security.

Length is not always Strength

AES 256-bit keys will certainly thwart direct brute force attacks far beyond our lifetimes. Adi Shamir, one of the co-inventors of RSA, has stated that "cryptography is typically bypassed, not penetrated". In this post we have considered two cases where this can happen: long keys being protected by weaker passwords, and long keys being protected by much shorter (weaker) keys. The moral seems clear: don't use very long keys in a given environment unless the security of the other parameters involved is similar, since the weakest link will be the target. Unfortunately you just won't find any other practical security parameter up to par with an AES-256 key.

Related Posts


oliver said...

Very interesting discussion. Some certification authorities still offer lower levels of encryption than 128, but it is a curious case to ask if 256 bit SSL Certificates are too large! Sometimes it seems more ceremonial, but website security and SSL encryption is required and needed by visitors to trust your site.

boy labyog said...

interesting post thanks for sharing by the way I'm laby.

Laby[big suits for men]