4
$\begingroup$

I see a common claim that AES-256 is the gold standard and is good future proofing, often in the same wind as "just use 2048-bit keys for RSA". Security documents seem to recommend both AES-256 and 2048-bit RSA keys, and 2048-bit RSA keys are often used in the key exchange for a 256-bit AES key.

I believe:

  • Using AES-256 is "future-proofing" your system
  • Using 2048-bit keys in RSA is being practical and not worrying about future-proofing

Is it hypocritical to increase AES to 256-bit keys without increasing the RSA key length?

$\endgroup$
4
  • 2
    $\begingroup$ Note that the 256-bit version of AES has 14 rounds, whereas the 128-bit version only has 10. While no severe attacks have been found on the 10-round version, the 14-round version is, in theory, more resistant to cryptanalysis, even ignoring the larger key size. $\endgroup$
    – forest
    Feb 14, 2019 at 11:38
  • $\begingroup$ Unless the attacks are related to the key schedule, that's probably correct. If they are related to the key schedule then AES-256 may be more vulnerable in some situations (I'm talking about the related key attack of course, although that one is not applicable to AES encryption if implemented correctly). Note too that AES-256 is merely 40% slower than AES-128 in most situations; it's not that big a performance penalty. OTOH RSA-4096 is much slower than RSA-2048 and only adds some 20-30 bits of actual security according to Lenstra equations (then again, those few bits are sorely needed IMHO). $\endgroup$
    – Maarten Bodewes
    Feb 14, 2019 at 17:22
  • $\begingroup$ @MaartenBodewes Only 12? According to this, even a 3072-bit RSA key has about 22 more bits of security than a 2048-bit RSA key, assuming the GNFS complexity is estimated correctly. $\endgroup$
    – forest
    Feb 15, 2019 at 9:11
  • 1
    $\begingroup$ @forest Yeah, I got distracted a bit while I was researching what was wrong and didn't update that value. I thought it was too small. I had 112 bit in mind for 2048 bit keys and 4096 got me 126 or so with the equations. However, it seems that the Lenstra equations will give you a value below 100 for 2048 bit keys (!). That's much lower than the NIST estimates, which I thought were in line with Lenstra. Funny enough, I initially wrote over 20 bits as a guesstimate. I've changed it into 20-30 bits of security - another guesstimate. NIST doesn't show 4096 after all. $\endgroup$
    – Maarten Bodewes
    Feb 15, 2019 at 12:51

2 Answers 2

9
$\begingroup$

Using AES-256 instead of, say, AES-128 is not merely ‘future-proofing’: AES-128 provides a security level far below the standard of 128 bits today. If your application has four billion users, the expected cost of breaking one of them by the best generic brute-force attack is about $2^{96}$ evaluations of AES-128, which can be parallelized. This might not break your toy application, but it is well within the realm of human feasibility. Not so for AES-192 and AES-256: even up to a whopping sixteen quintillion users, the expected cost of the same attack on AES-192 is an unimaginable $2^{128}$ evaluations of AES-192.

So if you want AES—which invites timing side channel attacks on software implementations, unlike, say, ChaCha—then you should pick AES-192 or AES-256 without further thought. This saves you the effort of thinking about whether AES-128 provides adequate security for your application. AES-192 and AES-256 are marginally costlier than AES-128, so if you have an overwhelming performance concern then we can discuss the finer details when you present a budget measured in joules or nanoseconds or cycles per unit of processing in your application, and not until then.

The story is more complicated for RSA, and depends on what you're doing with it:

  • If you're using it for signatures, you will presumably have some way to rotate signatures—unlike confidentiality, authentication generally need not last for decades.
  • The number of RSA keys is likely to be considerably smaller than the number of AES keys, if for no other reason than that generating an AES key costs a few dozen CPU cycles while generating an RSA key involves a search through complicated primality tests.
  • RSA computations are substantially costlier than AES computations at any reasonable key size, so your budget for time might actually be measured in milliseconds rather than nanoseconds, like human response times.
  • RSA key sizes are substantially larger than AES key sizes, so your budget for time might actually be measured in kilobytes rather than bytes.

All these considerations might figure into your application: it would not be hypocritical to pick AES-256 and then spend your time worrying about RSA, if RSA-4096 is too costly. Heuristically, we might infer that RSA-2048 is safe for the time being because the current factorization record is RSA-768, and while we're overdue for an RSA-1024 factorization, there's a big gap from there to RSA-2048. But it is also true that a 2048-bit RSA modulus certainly doesn't attain a 128-bit security level either. The best cost estimate I'm aware of gives an area-time cost per key of about $2^{103}$ if we conservatively read $o(1)$ as zero, rather than the cost $2^{112}$ advertised by keylength.com, NIST, etc.

That said: Can I interest you in Ed25519 or X25519, which confidently provide a 128-bit security level—meaning the best attack has expected cost $2^{128}$ curve additions no matter how many users there are—with 32-byte keys and 64-byte signatures, and at much lower cost to generating a key or making a signature or decrypting a message than RSA will ever attain? Then, unless your bottleneck is verifying signatures or encrypting messages, you don't have to spend time thinking about whether RSA-2048 is secure enough as you use it in your application. (See also this earlier answer to a similar question about AES-128 and X25519.)

$\endgroup$
3
$\begingroup$

AES has no known attacks that break the security. There are 2 common attacks types that wait in the future for any block cipher.

  1. Brute-force attack: In which you search for all possible key You can use current records as a base for calculation against this attack. You can see some top most system capabilities in this answer. Even the $~2^{96}$ of the collaborative calculations of the bitcoin miners is not much a threat in a short term for AES-128.
  2. Grover's algorithm that is Quantum search for unstructured data. Is has $\mathcal{O}(\sqrt{2^n})$ complexity. For AES, this means, once built the AES-128 has 64-bit security and AES-256 has 128-bit security.

For the RSA case. we have factorization algorithms and some other attack types (20-years of RSA) due to improper uses. We can concentrate here, two;

  1. Against standard RSA attacks, it is recommended that 2048-bit modulus is secure, see the keylength.
  2. Once the Shor' Algorithm, the quantum factoring is built, the RSA is no more secure. Everybody needs to switch quantum resistant public key systems.

As you can see, they are different algorithms and has different attack types. Many already used AES-128 for many years without switching AES to 256-bit, however, increased the RSA modulus many times. The practice is calculating your risks and applying the recommendations as that can be found as in the keylength.com.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.