Description of problem:

Cloning the bugzilla 'https://bugzilla.redhat.com/show_bug.cgi?id=1010607' which opened for fedora.


1. It is fairly hard to actually find out the exact cryptographic algorithms and their paramters used for a particular ssh session.  ssh -vvvv provides some hints, but you seem to need to already know what's going on to decipher the cryptic debug messages. This should be made a lot easier and more transparent. It should state simply a clearly, for example, that it is doing a Diffie-Hellman key exchange with parameters such and such.

2. For legal reasons, Fedora's openssh comes without elliptic curve cryptography (ECC) support, see bug 319901. It has been argued that this is a bad thing since ECC provides high security efficiently. It has also been argued that this might be a good thing, since constants used in ECC might contain a NSA backdoor (see also http://www.theguardian.com/world/2013/sep/05/nsa-how-to-remain-secure-surveillance). One way or another, the absence of any *option* to use ECC can't be a good thing.

3. Hoever, with ECC disabled, openssh defaults to discrete logarithm Diffie-Hellman (DH) for key exchange. This method uses dh.c:dh_estimate() to compute the group size DH parameter:

/*
 * Estimates the group order for a Diffie-Hellman group that has an
 * attack complexity approximately the same as O(2**bits).  Estimate
 * with:  O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3)))
 */

int
dh_estimate(int bits)
{

        if (bits <= 128)
                return (1024);  /* O(2**86) */
        if (bits <= 192)
                return (2048);  /* O(2**116) */
        return (4096);          /* O(2**156) */
}


Here the parameter "bits" is max(key size, block size, iv size, mac size), see kex.c:kex_choose_conf(), in the loop before "kex->we_need = need", also note the multiplication by 8 (because we_need is measured in bytes) in the call "nbits = dh_estimate(kex->we_need * 8)" in kexgexc.c:kexgex_client().

Now I do not have the slightest idea what the author of this piece of code is trying to say with the comments (what is q supposed to be, and its relation to the only parameter "bits"? Where do the number 86, 116, 156 come from?) However, I understand that a block cipher with 128 bit key size gives us a 1024 group size.

This is not in line with standard advice about cryptographic key lengths, which states that a 128 bit block cipher should be used with a group size of 3072 bits (192 bits with 7680 bit group size, 256 bits with 15360 bit group size), see http://www.keylength.com/en/compare/ (NIST; others are even more conservative). In fact, while today it practically impossible to break a 128 bit block cipher, it is considered fairly realistic to break a 1024 bit RSA, DSA or DH key.

I ask for a second opinion on my analysis, please. If I am right, dh_estimate() should be changed as follows:

/*
 * Estimates the group order for a Diffie-Hellman group that has an
 * attack complexity approximately the same as O(2**bits).  Estimates
 * are from "Recommendation for Key Management,"
 * Special Publication 800-57 Part 1 Rev. 3, NIST, 07/2012.
 */
int
dh_estimate(int bits)
{

        if (bits <= 128)
                return (3072);
        if (bits <= 192)
                return (7680);
        return (15360);
}

Note that dh.c contains the definition

#define DH_GRP_MAX      8192

which is less than 15360, so this probably has to be changed, and possibly other places have to be changed as a consequence (again there is no useful explanation for this definiton and its interdependences or consequences in the source code). If this cannot be done (perhaps the maximum is mandated by some part of the ssh protocol, or something), "return (4096);" should be replaced instead by "return (8192);"

Version-Release number of selected component (if applicable):
openssh-6.2p2-5.fc19.i686

How reproducible:
always

Steps to Reproduce:
1. ssh -vvvv localhost

Actual results:
...
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<1024<8192) sent
...

Expected results:
...
debug1: kexgex_client: Using discrete logarithm Diffie-Hellman key exchange with 256 bit private key size and 3072 bit group size (we_need*8 = 128)
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<3072<16384) sent
...