The length of an RSA signature sent during the handshake

[1.41421 at gmail.com]

On Aug 25, 2010 2:17am, Damien Miller <djm at mindrot.org> wrote:
> On Tue, 24 Aug 2010, JCA wrote:



> > I have noticed that OpenSSH clients (at least version 5.1p1)

> > occasionally send an RSA signature during the handshake phase such

> > that if the RSA key pair used to generate it happens to be associated

> > to an N-byte long modulus, the signature is N - 1 bytes long. My

> > question is, Is this behavior correct? I mean, an RSA signature is an

> > unstructured byte string, and therefore any leading zeros should be

> > considered part of the signature, and a signature created with an RSA

> > key pair such that its associated modulus is N bytes long ought to be

> > N bytes long as well.



> How are you measuring length? The size of the signature blob is always

> the same length as rsa->n (search for "memmove" in ssh-rsa.c), but if

> you are decoding the blob to a bignum then its length will occasionally

> be shorter.

Well, what I am observing is the following: During the authentication phase  
the client sends two SSH_MSG_AUTH_REQUEST messages. Occasionally the second  
one is such that the second one is such that the RSA modulus is 257 bytes  
long (correct, for it is encoded as an mpint) whereas the RSA signature  
blob is 255 bytes long. This is all information contained in the different  
fields of the SSH_MSG_AUTH_REQUEST message itself. Now the truth is that  
looking into the code that you mention it would seem to be impossible for  
the client to generate a 255 byte signature with such an RSA modulus. I'll  
try and see if I can get client-side traces that illustrate the issue.



> If you consider RSA signing to function as a random mapping into

> integers of log2(n)/8 bytes, then the first byte will be zero with

> probability roughly equal to 1/256.



> -d