8 ms·

Off-by-One: The Curious Case of 2047-Bit RSA Keys (2019)

48 points by oedmarap 5y ago

hinkley 5y ago
The whole point of the long keys is the search space, isn’t it? If the leading bit has to be 1 then effectively you have a 2047 bit key either way. 1 followed by 2047 random-looking bits.
- anyfoo 5y ago
  If you want to do it that way, it's much less than 2047 bits for RSA, though. Also compare with AES keys for example, which can be much shorter while still being harder to crack.
- sp332 5y ago
  According to Table 2 (page 67) of this NIST report, 2048-bit RSA only has about 112 bits of entropy anyway. https://csrc.nist.gov/publications/detail/sp/800-57-part-1/rev-5/final https://csrc.nist.gov/publications/detail/sp/800-57-part-1/r...
  - bmurray7jhu 5y ago
    An 2048 bit RSA key has 112 bits of security, but not necessarily 2048 bits of entropy. RSA 2048 only has about ~112 bits of security because there are faster-than-brute-force algorithms for integer factorization. A 2048 bit RSA key is generated from two 1024 bit primes. Let's assume we randomly choose each prime from the range 2^1023 to 2^1024. Per the Prime Number Theorem, there are ~ N / ln (N) primes below N. That means that there are 2^1024 / (1024 ln 2) - 2^1023 / (1023 ln 2) ≈ 1.3e305 1024-bit primes. It follows that a 1024 bit prime has ~1023 bits of entropy and that a 2048 bit RSA key has ~2022 bits of entropy.
    - labawi 5y ago
      2048 bit RSA can have at most ~2022 bits of entropy. It can and often does have much less¹, depending on how the keys were generated (debian). That may or may not be an issue, depending on the resulting distribution of keys, i.e. how usable is the information that only a teeny fraction of keys are possible (Infineon). ¹ Entropy interpreted as the number of possible, roughly equal-likelihood outcomes.
- wrs 5y ago
  Not being a random key, it’s not precisely a “search space”, but to your point, from the article: “the difficulty of factoring 2047-bit keys is only marginally lower than that for full 2048-bits”.
usr1106 5y ago
Edit: ignore this. I might need new reading glasses... article mentions a CSR containing a private key. Isn't that a absolute no no? CSRs you send around, but private keys should never leave your machine. Where machine could even he a hardware token in the ideal case. Confused.
- userbinator 5y ago
  Where does it say that? The CSR contains a public key. It says "Sign a certificate signing-request (CSR) containing the public-key. "
  - usr1106 5y ago
    Thanks, edited my comment. Not sure what I read...
userbinator 5y ago
One bit theoretically means it halves the possibilities, but in practice there's so many in the absolute sense that there's no practical difference in security.
sec400 5y ago
On the included estimations of the frequency that this occurs. I scraped a collection of (mainly developer) public keys for a previous project and got the following numbers. sqlite> select count(*) from keys; 1627715 Quite a difference between the ratio of 2047/2048 bit keys and 1023/1024 bit keys. sqlite> select count(*) from keys where strength = "2048"; 936441 sqlite> select count(*) from keys where strength = "2047"; 466 sqlite> select count(*) from keys where strength = "1024"; 39068 sqlite> select count(*) from keys where strength = "1023"; 5908 Interestingly also: sqlite> select count(*) from keys where strength = "2049"; 13 sqlite> select count(*) from keys where strength = "2050"; 5 sqlite> select count(*) from keys where strength = "2051"; 1 sqlite> select count(*) from keys where strength = "2052"; 0
- eqvinox 5y ago
  I vaguely remember a recommendation to use non-power-of-two key lengths, but that was ~15 years ago and I have absolutely no memory of any details (might even have been a DSA thing.) I do, however, have a whole bunch of 2111-bit keys still in use (cycled a few times of course.)
diebeforei485 5y ago
> Why not roll the dice on the full interval and check the product after the fact? See earlier point about the time-consuming nature of RSA key generation. Starting over from scratch is expensive. They lose a bit of entropy by pre-setting the leading bit to 1. There have been discussions about this in the past - https://news.ycombinator.com/item?id=19374758 https://news.ycombinator.com/item?id=19374758
bmurray7jhu 5y ago
NIST is considering "resistance to misuse" when assessing post-quantum crypto schemes. A final desirable, although ill-defined, property is resistance to misuse. Schemes should ideally not fail catastrophically due to isolated coding errors, random number generator malfunctions, nonce reuse, keypair reuse... https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Crypt...
superkuh 5y ago
The most shocking part of this article is that 1800 bit rsa keys are significantly stronger than 2048 bit keys and that there are discontinuities in toughness at base 10 numbers like 1000 and 2000 bits.
- saagarjha 5y ago
  *only if the RSA primes are not randomly generated, as was the case with the Infineon hardware.
  - superkuh 5y ago
    Ah! Okay. Much less shocking. Thanks.

48 points by oedmarap 5y ago

The whole point of the long keys is the search space, isn’t it? If the leading bit has to be 1 then effectively you have a 2047 bit key either way. 1 followed by 2047 random-looking bits.

anyfoo 5y ago
If you want to do it that way, it's much less than 2047 bits for RSA, though. Also compare with AES keys for example, which can be much shorter while still being harder to crack.
sp332 5y ago
According to Table 2 (page 67) of this NIST report, 2048-bit RSA only has about 112 bits of entropy anyway. https://csrc.nist.gov/publications/detail/sp/800-57-part-1/rev-5/final https://csrc.nist.gov/publications/detail/sp/800-57-part-1/r...
- bmurray7jhu 5y ago
  An 2048 bit RSA key has 112 bits of security, but not necessarily 2048 bits of entropy. RSA 2048 only has about ~112 bits of security because there are faster-than-brute-force algorithms for integer factorization. A 2048 bit RSA key is generated from two 1024 bit primes. Let's assume we randomly choose each prime from the range 2^1023 to 2^1024. Per the Prime Number Theorem, there are ~ N / ln (N) primes below N. That means that there are 2^1024 / (1024 ln 2) - 2^1023 / (1023 ln 2) ≈ 1.3e305 1024-bit primes. It follows that a 1024 bit prime has ~1023 bits of entropy and that a 2048 bit RSA key has ~2022 bits of entropy.
  - labawi 5y ago
    2048 bit RSA can have at most ~2022 bits of entropy. It can and often does have much less¹, depending on how the keys were generated (debian). That may or may not be an issue, depending on the resulting distribution of keys, i.e. how usable is the information that only a teeny fraction of keys are possible (Infineon). ¹ Entropy interpreted as the number of possible, roughly equal-likelihood outcomes.
wrs 5y ago
Not being a random key, it’s not precisely a “search space”, but to your point, from the article: “the difficulty of factoring 2047-bit keys is only marginally lower than that for full 2048-bits”.

usr1106 5y ago

Edit: ignore this. I might need new reading glasses... article mentions a CSR containing a private key. Isn't that a absolute no no? CSRs you send around, but private keys should never leave your machine. Where machine could even he a hardware token in the ideal case. Confused.

userbinator 5y ago
Where does it say that? The CSR contains a public key. It says "Sign a certificate signing-request (CSR) containing the public-key. "
- usr1106 5y ago
  Thanks, edited my comment. Not sure what I read...

userbinator 5y ago

One bit theoretically means it halves the possibilities, but in practice there's so many in the absolute sense that there's no practical difference in security.

sec400 5y ago

On the included estimations of the frequency that this occurs. I scraped a collection of (mainly developer) public keys for a previous project and got the following numbers. sqlite> select count(*) from keys; 1627715 Quite a difference between the ratio of 2047/2048 bit keys and 1023/1024 bit keys. sqlite> select count(*) from keys where strength = "2048"; 936441 sqlite> select count(*) from keys where strength = "2047"; 466 sqlite> select count(*) from keys where strength = "1024"; 39068 sqlite> select count(*) from keys where strength = "1023"; 5908 Interestingly also: sqlite> select count(*) from keys where strength = "2049"; 13 sqlite> select count(*) from keys where strength = "2050"; 5 sqlite> select count(*) from keys where strength = "2051"; 1 sqlite> select count(*) from keys where strength = "2052"; 0

eqvinox 5y ago
I vaguely remember a recommendation to use non-power-of-two key lengths, but that was ~15 years ago and I have absolutely no memory of any details (might even have been a DSA thing.) I do, however, have a whole bunch of 2111-bit keys still in use (cycled a few times of course.)

diebeforei485 5y ago

> Why not roll the dice on the full interval and check the product after the fact? See earlier point about the time-consuming nature of RSA key generation. Starting over from scratch is expensive. They lose a bit of entropy by pre-setting the leading bit to 1. There have been discussions about this in the past - https://news.ycombinator.com/item?id=19374758 https://news.ycombinator.com/item?id=19374758

bmurray7jhu 5y ago

NIST is considering "resistance to misuse" when assessing post-quantum crypto schemes. A final desirable, although ill-defined, property is resistance to misuse. Schemes should ideally not fail catastrophically due to isolated coding errors, random number generator malfunctions, nonce reuse, keypair reuse... https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Crypt...

superkuh 5y ago

The most shocking part of this article is that 1800 bit rsa keys are significantly stronger than 2048 bit keys and that there are discontinuities in toughness at base 10 numbers like 1000 and 2000 bits.

saagarjha 5y ago
*only if the RSA primes are not randomly generated, as was the case with the Infineon hardware.
- superkuh 5y ago
  Ah! Okay. Much less shocking. Thanks.