10

The Windows CNG supports keys of varying sizes, e.g. RSA up to 16384 bits: http://msdn.microsoft.com/en-us/library/windows/desktop/bb204778(v=vs.85).aspx.

My understanding is that in crypto today we tend to top out at 4096 for most things because of the cost of processing and what not.

My question: what are the practical uses of large keys, e.g. 8192 - 16384, right now, if any?

Steve
  • 15,263
  • 3
  • 39
  • 66
  • This should probably be on http://crypto.stackexchange.com/ – copy Apr 28 '13 at 02:57
  • 2
    @copy - I think it's fine here too. It's one of those topics that overlap both here and on Crypto. For example, check the number of questions tagged [tag:cryptography] on Sec.SE. Besides, whichever of the two subsites it ends up on, it'll probably be answered by the same people anyway. ;) – TildalWave Apr 28 '13 at 03:13
  • I'd rather use ECC than huge RSA. A 256 bit curve is about as strong as 3000 bit RSA and the advantage of ECC increases the higher the desired security level. – CodesInChaos Apr 28 '13 at 12:48

2 Answers2

6

For security, there is no need to go beyond 2048 bits for RSA, which is already quite some overkill. 1024 bits are already at the threshold of the feasible. We go to 2048 instead of, say, 1400 bits, because we just love powers of 2. See this site for estimates of "strength" that various organizations have come up with. Summary: RSA-2048 is quite safe for the time being, and when it ceases to be safe, it will be due to technology that does not work like technology we know today.

In the not-near future, quantum computers, if they work at all, will break all RSA keys, regardless of their length. Classical computers, on the other hand, are likely to never be able to break 2048-bit RSA because of the involved energy consumption. That is, unless some half-mad mathematician discovers a killer algorithm for integer factorization, which is, as always, an unpredictable event.

Bigger keys are largely used to appease the paranoia and flatter the ego of people who are in position to decide about technical details but lack the actual competence to do so. Big keys imply obvious network and computational overhead (a 4096-bit key will produce signatures which are twice bigger than 2048-bit RSA signatures, and it will cost about eight times as much CPU), but also interoperability issues: 2048 bits work everywhere, 4096 bits are more restrictive, and bigger keys are not widely supported yet. Thus, there are real, factual, measurable disadvantages to big keys, while the security gain can be qualified as, at best, esoteric: bigger keys are stronger only in the face of unknown technology or science, about which we can only speculate wildly.

Community
  • 1
Thomas Pornin
  • 326,555
  • 60
  • 792
  • 962
  • Is the mathematician half mad because he discovers a killer algorithm for integer factorization, or is he half mad because he is a mathematician? –  Apr 28 '13 at 13:02
  • 6
    Rather, he is a mathematician because he is half-mad. – Thomas Pornin Apr 28 '13 at 13:03
1

One use for large keys in public-key cryptography that springs to mind is OTP (One-Time Pad):

In cryptography, the one-time pad (OTP) is a type of encryption which has been proven to be impossible to crack if used correctly. Each bit or character from the plaintext is encrypted by a modular addition with a bit or character from a secret random key (or pad) of the same length as the plaintext, resulting in a ciphertext. If the key is truly random, as large as or greater than the plaintext, never reused in whole or part, and kept secret, the ciphertext will be impossible to decrypt or break without knowing the key.[1][2] It has also been proven that any cipher with the perfect secrecy property must use keys with effectively the same requirements as OTP keys.[3] However, practical problems have prevented one-time pads from being widely used.

Source: Wikipedia (text emphasis is my own addition)

I can only assume for other possible uses to be:

  • Futureproofing: It has been proposed we'll be needing a lot larger keys once we're in the age of quantum computing. Personally, I don't really like to call these quantum computers, but rather N-state computers. Not sure if it's been proposed before, but I believe it shows better what computing powers we'll be dealing with and why parallelism won't matter so much any more. I.e. Cost of brute-forcing will sharply decrease with ability to compute against all possible (smaller) key values at the same time.

  • Ciphertext variance: Assuming the encryption algorithm used is broken and the plaintext can be determined easier on shorter keys by analyzing ciphertext variance, use of larger keys should increase this variance beyond the ability of the attacker to determine the key used to encrypt it in a reasonable time-frame. I'm no cryptologist tho, so this is pure speculation.

  • Key depletion: This one is probably a bit far-fetched (in the same way our Universe is a bit huge), but if we imagine an extremely large system that has the need to exchange large numbers of keys (e.g. our Sun with each Hydrogen atom a unique key recipient) that for whatever reason need to be unique, this is where larger keys would have an obvious advantage over smaller (but sufficiently large to be considered cryptographically secure) keys. Of course, even 4096-bit keys should be large enough to see the end of Universe before depletion, so...

  • Paranoia: The largest prime factor behind bigger is better (pun intended).

TildalWave
  • 10,801
  • 11
  • 47
  • 86
  • 2
    OTP is a symmetric (theoretical, because the key is too big) algorithm for encryption. It's not related to public key cryptography. Also, your post seems to be regarding symmetric key cryptography mostly, not public key cryptography. – copy Apr 28 '13 at 05:05
  • @copy - You're probably right, but I wanted to have a go at it anyway. I can't pretend to be too knowledgeable on the subject, but one way to learn is to make mistakes, and I'll be looking forward (no joke) where I failed and learn new things (or unlearn old ones LOL). If I got any at least partially correct, I'll have a small party tho. :) I'm curious though, why do you think that my (admittedly) speculative musings don't apply to PKI as well? – TildalWave Apr 28 '13 at 05:23
  • If quantum computers appear, all public key cryptography based on integer factorization and the DLP will be broken completely, whereas quantum attacks against symmetric ciphers require at least 2^(n/2) steps (this is what your Futureproofing point is about) – copy Apr 28 '13 at 15:35
  • The number of atoms in the observable universe is estimated at up to about 10^82. Public-key cryptography doesn't work that way, but 2048 bits of key material means about 3x10^616 possible keys. To reach 10^82 possible values, you need just under 272.5 bits of entropy (2^272.5 = 1.07x10^82). – user Apr 29 '13 at 13:42
  • @MichaelKjörling - You're taking it too literal. If we calculate the theoretical number of hydrogen atoms in Sun, then we'd get roughly a number 10^52. That is of course nothing compared to ~ 10^1232 possible values for a 4096-bit key. Being more precise with such numbers is beyond the point, for example our Sun will emit during its entire lifetime roughly 1.21e+62 photons (rough estimate) before it turns into a red giant and engulfs Earth in the process. You only need key lengths of 207 bits to hold as many unique keys, and you're still left with enough to see it collapse into a white dwarf. – TildalWave Apr 29 '13 at 15:54