Diffie Hellman key exchange algorithms

[Rob Waite]

Also... in RFC 4419... the authors say that the private exponent should be a
random number x where 1 < x < (p-1)/2. This is the private secret that would
allow one to find the shared secret. They say later in the paper that the 
size
of this number can be reduced to make computation faster. They say that
it should be at least twice the size of the key material that will be 
generated
from the shared secret.

To me it appears that the size of the key material is a value kex->we_need
which is set in kex_choose_conf. This is passed into dh_gen_key multiplied
by 8. This is to convert it to bits needed from bytes. I believe in AES256's
case.. this would end up being 256 passed in here...

This is used in dh_gen_key by passing it to BN_rand as 2*need. This sets
the number of bits to make the random number created by BN_rand.

So from what I can gather.. OpenSSH follows the minimum size to make
the private exponent. If an attacker was to try to attack OpenSSH... they
would be able to eliminate a huge number of possible choices for the
private exponent. They would in fact know the number of bits.

In reality... I don't think even if they knew it was a 512 bit number... 
they
would not be able to crack it. But it seems to me that the security of the
underlying public key encryption system of OpenSSH could be strengthened
by making the size of the private exponent more variable. So.. for example..
if your public prime was 8000 bits long... your random needs to be less than
4000 bits long. So if the size of the private exponent was more variable... 
an
attacker would have to guess all of the numbers between 512 bits and 4000
bits (assuming that 256 is indeed the value of "need")

I may be reading the code incorrectly but this seems logical to me.
It is true that almost certainly.. no one is going to crack, let alone care
about the traffic I am sending across the net. But since when do 
cryptographers
make it easier for them ; )

Also... I have not done tests to see if expanding the length of the exponent 
makes
the initial key negotiation grindingly slow. If that is the case.. then 
maybe it doesn't
need to be 4000 bits long... but it seems that giving a little bit of 
randomness here
would be a good thing and not too hard to implement.
----- Original Message ----- 
From: "Rob Waite" <rwaite1 at tampabay.rr.com>
To: "Damien Miller" <djm at mindrot.org>
Cc: <openssh-unix-dev at mindrot.org>
Sent: Wednesday, September 26, 2007 11:14 PM
Subject: Re: Diffie Hellman key exchange algorithms


>>> In the code changes I sent
>>> earlier... you could
>>> force group exchange.
>
>>It's the default anyway :)
>
> If it is the default.. isn't the client software given the option to not
> accept group exchange?
> So by that reasoning... the client is given the power to decrease
> the level of security of your server (although... I
> realize that it is unlikely to actually be cracked anyway)
> They can send a SSH_MSG_KEXINIT that only has group1 for example.
>
>>The client doesn't get to choose what number they generate as it has to
>>match exactly what the server generated (DH is a deterministic protocol,
>>even if some of the inputs should be based on random numbers). If the
>>client and server's DH output differ then the IVs and {crypto, MAC} keys
>>will differ two and the connection will fail as soon as either end tries
>>to send any data.
>
> They are not able to choose the public prime but they do have the ability
> to choose their private exponent. The way I read the RFC is that the
> client software chooses the size of the private exponent. So it seems
> that they are given control on the strength of the private key used to
> encrypt their messages going out.
>
> I guess in general cases it doesn't matter. You have given someone
> a login to your server so you would have to trust that they are not
> trying to be bad. Once they get the file which you have already given
> them permission to... they could just give it to anyone. I guess you
> are unable to control the strength of the messages that they are sending
> you. And this is probably something that can't be worked around
> since the client's private exponent is known to them alone... so there
> is no way for the server to enforce a length.
>
> It just seemed to me that there are some things that the server can do
> to force increased security. Right now this is not configurable.. but can
> be done in code. For example... the server won't allow you to pick the
> key exchange methods allowed and block others that are not. This
> allows a user to log into the server with an old or weak client. They
> are given the control to decide to pick group1 instead of group exchange.
>
>
>
> ----- Original Message ----- 
> From: "Damien Miller" <djm at mindrot.org>
> To: "Rob Waite" <rwaite1 at tampabay.rr.com>
> Cc: <openssh-unix-dev at mindrot.org>
> Sent: Tuesday, September 25, 2007 1:10 AM
> Subject: Re: Diffie Hellman key exchange algorithms
>
>
>> On Tue, 25 Sep 2007, Rob Waite wrote:
>>
>>> Isn't dh_estimate() only used on the client to find the desired group
>>> size?
>>
>> Yes
>>
>>> This is then taken by the server and used to find p and g correct?
>>
>> Yes
>>
>>> OpenSSH is not configurable in this manner... but if someone wanted to
>>> force
>>> larger primes...
>>> couldn't they do this by altering the code?
>>
>> Yes - OpenSSH allows the client to request DH groups up to 8192 bits.
>>
>>> In the code changes I sent
>>> earlier... you could
>>> force group exchange.
>>
>> It's the default anyway :)
>>
>>> And if you picked only large primes in your moduli
>>> file...
>>> you should be able to force the client to get a large p as long as it is
>>> within the min
>>> and max sent by the client. I just started looking at the code again (it
>>> has
>>> been a while)
>>> but it seems like the server can control at the very least the size of
>>> the
>>> public and private
>>> numbers generated from p. He would not be able to control how powerful
>>> the
>>> client made
>>> their public and private numbers from the given p... but at least data
>>> sent
>>> out from the server would
>>> be forced to have the symmetric key encrypted using larges primes for 
>>> the
>>> assymmetric.
>>
>> The client don't have any special control over the output of the DH
>> protocol - the only get to specify one input (the server specifies the
>> others), and OpenSSH will refuse to accept the obviously bogus values of
>> that (see dh_pub_is_valid() in dh.c).
>>
>>> That is assuming that the server has its own symmetric cipher key and 
>>> the
>>> client has their own.
>>> If they do in fact share the same key... then I guess you would not be
>>> protected as the client
>>
>> The SSH protocol uses separate keys for client-to-server and
>> server-to-client.
>>
>>> could generate a small private number from p... no matter how large.
>>
>> The client doesn't get to choose what number they generate as it has to
>> match exactly what the server generated (DH is a deterministic protocol,
>> even if some of the inputs should be based on random numbers). If the
>> client and server's DH output differ then the IVs and {crypto, MAC} keys
>> will differ two and the connection will fail as soon as either end tries
>> to send any data.
>>
>> -d
>> _______________________________________________
>> openssh-unix-dev mailing list
>> openssh-unix-dev at mindrot.org
>> https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
>>
>
> _______________________________________________
> openssh-unix-dev mailing list
> openssh-unix-dev at mindrot.org
> https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev