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

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

randomoracle.wordpress.com

48 pointsoedmarap17 comments

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

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.)

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.

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.

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/r...

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.

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.

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”.

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-Crypt...

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.

*only if the RSA primes are not randomly generated, as was the case with the Infineon hardware.

Ah! Okay. Much less shocking. Thanks.

> 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

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.

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.

Where does it say that? The CSR contains a public key. It says "Sign a certificate signing-request (CSR) containing the public-key. "

Thanks, edited my comment. Not sure what I read...

Reply on news.ycombinator.com