Dubious use of BN_num_bits in sshconnect1.c

[alex at foogod.com]

Hiho...

I have recently encountered problems using OpenSSH 2.3.0p1 to connect to a SSH 
1.2.20 server, with messages such as the following:

  Warning: Server lies about size of server public key: actual size is 1151 
  bits vs. announced 1152.
  Warning: This may be due to an old implementation of ssh.
  respond_to_rsa_challenge: public_key 1151 < host_key 1024 + 
  SSH_KEY_BITS_RESERVED 128

..and a resulting refusal to continue.

I've done a bit of digging in the source, and have found the source of the 
problem to be the use of BN_num_bits to determine the length of the keys 
received in sshconnect1.c.  The problem is that BN_num_bits does not return 
the number of significant bits of a given bignum, but rather the position of 
the most significant 1 bit, which is not necessarily the same thing.

It is perfectly possible (and as demonstrated, does occur) for the remote end 
to generate an N-bit public key where the most significant bit is zero.  When 
this occurs, BN_num_bits returns a smaller number than the actual key size, 
but this number is erroneously used to check against key size requirements.

(this brings up a related flaw in the BN_rand/BN_pseudo_rand (which is the 
reason this bug doesn't show up with OpenSSH servers) in that when called to 
generate an N-bit (pseudo)random number, these functions actually return N-1 
bits of random data, with the msb set to 1, instead of the N random bits 
promised, but that's a side issue)

So..  I've put together a patch which I'm currently testing to fix this 
problem (it's taking a bit of time tho as the issue only pops up 
intermittently), but I have a couple of questions:

1) Am I missing something here which would make the use of BN_num_bits 
   actually correct in this context, or is this just a bug?
2) Why are the checks for "Server lies about ..." present?  I understand the 
   need for the "respond_to_rsa_challenge" check, but I'm assuming the other 
   key size validation attempts are due to some known issue with older SSH 
   server implementations generating incorrectly-sized keys?  Could someone 
   provide some details of exactly what the issue is that prompted these 
   checks?

I also note that BN_num_bits appears to be used in several other places 
throughout the source.  In many cases this is probably not an issue, but it's 
possible there are a few other places that could suffer from incorrect results 
because of this..

-alex