4

Reviewing the SSH keys of hosts that I connect to (as gathered by PuTTY in registry key HKEY_CURRENT_USER\SoftWare\SimonTatham\PuTTY\SshHostKeys), I find that they all start with 0x10001 (65537) or 0x23 (35), most often followed by 2048-bit composite values with no small factor. I conclude they are RSA keys, and that 0x23 (35) is the second most common public exponent in my sampling.

What software commonly generates RSA keys with that public exponent 0x23 (35)? Why that value, which is not prime, and thus slightly complicates the selection of the factors of the public modulus?

2
  • is there anything common between the hosts that have that?
    – ilkkachu
    Oct 20, 2016 at 21:37
  • 2
    @grochmal: this Q is about (pub)keys from servers received by putty. The RSA keys putty generates use 37, with a not-very-explanatory comment in sshrsag.c: #define RSA_EXPONENT 37 /* we like this prime */ Oct 21, 2016 at 3:17

2 Answers 2

5

Versions of OpenSSH up to 5.3 AFAICT then they switched to F4=65537. I don't recall seeing an explanation for why they used 35, but I haven't read every line of everything.

5
  • Good one (+1). I always thought they generated the exponent too. But then again, that's part of the pubkey, so it is public anyway.
    – grochmal
    Oct 21, 2016 at 10:02
  • 1
    Here is where they changed it to 65,537, with the commit message: switch from 35 to the more common value of RSA_F4 == (2**16)+1 == 65537 for the RSA public exponent; discussed with provos; ok djm@
    – forest
    Jun 8, 2022 at 2:49
  • 1
    This sheds a tiny bit of light, 35 sounds like it was a suboptimal choice without other explanation than cargo culting mail-archive.com/cryptography%40metzdowd.com/msg13282.html Jun 24, 2022 at 14:15
  • @Bruno Rohée: yes, 35 is suboptimal, but if we trust the original SSH used an e relatively prime to (p-1)(q-1), choosing odd numbers > 31 that you unearthed, then e=35 may be seen as an improvement over the smallest valid e (e=33) from the standpoint of key generation time: e=33 is compatible with only (9/20)²≈20% of choices on n, when e=35 is compatible with (5/8)²≈39% of n. Putty pushes that to e=37, which is compatible with (35/36)²≈95% of n.
    – fgrieu
    Jun 28, 2022 at 5:50
  • Yeah it seems like it was actually an improvement, and not one introducing a never seen before public exponent in the ecosystem, that would possibly have broken fragile code. Interoperability was a concern and I wouldn't be surprised if some late 90s code interacted badly with RSA_F4... Jun 28, 2022 at 13:31
4
+25

The OpenSSH rsa_generate_private_key() function that was changed in version 5.4 to use the more common 65537 (RSA_F4) was introduced in key.c by this commit back in 2000, and already have the public exponent at 35. However, if you go back in time that function already existed in rsa.c before and the first revision from 1999 was already using 35 from the start, its creation part of a large refactoring effort to stop using gmp and to use OpenSSL's libcrypto functions instead.

Trying to see when 35 was first introduced, and found that in the 1.0 release of Tatu Ylönen's SSH the public exponent was generated by the following code (function derive_rsa_keys() called from rsa_generate_key() in rsa.c) which would have stumbled on 35 often, but not always.

  /* Find a suitable e (the public exponent). */
  mpz_set_ui(e, 1);
  mpz_mul_2exp(e, e, ebits);
  mpz_sub_ui(e, e, 1); /* make lowest bit 1, and substract 2. */
  /* Keep adding 2 until it is relatively prime to (p-1)(q-1). */
  do
    {
      mpz_add_ui(e, e, 2);
      mpz_gcd(&aux, e, &phi);
    }
  while (mpz_cmp_ui(&aux, 1) != 0);

That code stayed the same until ssh-1.2.12 which is the most recent OpenSSH ancestor in the original SSH line. In OSSH-1.2.16 (intermediate ancestor to OpenSSH) it also stayed the same, and afterwards it seems during the SSH import in the OpenBSD tree, the refactoring to use libcrypto instead of libgmp in 1999 happened immediately and introduced the fixed 35. If CVS is to be trusted it's Niels Provos that did the work (but likely in close communication with Markus Friedl and others), and as the commit message doesn't mention a reason only him should know for sure why he chose 35.

However, from my point of view, even if it wasn't the best choice for keygen performance (Peter Gutmann going as far as calling it cargo culting) it was the safe conservative choice, as with so many SSH keys in usage already with 35 as public exponent, there was quasi certainty this would not introduce any breakage.

2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .