Comparing key sizes

Not all cryptographic algorithms provide the same level of security for a fixed size of key. A 128-bit AES key provides roughly the same security as a 256-bit elliptic curve key or as a 3,072-bit RSA key. We need to look at exactly how the security provided by cryptography is defined to understand why this is true.

Leading cryptographic standards like FIPS 140-2 define the strength of encryption in terms of how much work it takes for an adversary to find the key that he needs to decrypt encrypted data. So if the work needed to recover a 128-bit AES key is roughly the same as the work needed to recover a 256-bit elliptic curve key or a 3,072-bit RSA key, then we say that encryption using each of these keys provides the same level of cryptographic strength.

In the case of a symmetric algorithm, it's easy to understand how much work is needed. An ideal symmetric algorithm is one for which there's no better way to recover a key than just trying all possible keys to see which one is the right one, and for an n-bit key, this takes 2n tries. In practice, this can be more difficult to understand than it sounds. A Triple-DES key, for example, actually has 192 bits, only 168 of which are actually used to encrypt or decrypt data (the rest are parity check bits). But for Triple-DES, there's a way for an attacker to recover a key in only 2112 tries, so that the 168 bits of key that are used to encrypt data really only provide 112 bits of strength.

For an elliptic curve algorithm, it's slightly more complicated. There's an algorithm called "Pollard's rho algorithm" that can find an elliptic curve key, and this takes much less time than just trying all possible keys. It only has to try the square root of the number of keys on average. So instead of needing 2n tries, an attack based on this technique only needs about the square root of 2n tries, or 2n/2tries. This is why a 256-bit elliptic curve key is about as strong as a 128-bit AES key: the work needed to find a 256-bit elliptic curve key (the square root of 2256, or 2128) is about the same as the work needed to find a 128-bit AES, which also requires performing 2128 operations.

With other public key algorithms, it's trickier. Suppose that you want to find an RSA key by factoring an RSA modulus into n = pq. There's a complicated algorithm called the "general number field sieve" that's fairly fast, and it can factor a 3,072-bit number with about the same level of work that it would take to try all 2128 possible 128-bit AES keys. Because of this, we say that a 3,072-bit RSA key provides the same level of security as a 128-bit AES key.

Leave a Reply

Your email address will not be published. Required fields are marked *