RE: [openssl.org #3113] OpenSSL’s DH implementation uses an unnecessarily long exponent, leading to significant performance loss

2014-08-27 Thread Gueron, Shay 
Hello Rich, 

I would recommend to do that. Otherwise there will be unsuspecting users who 
will (unintentionally) use the long exponent 
...for example, this is what happened to me in the first attempts, and I did 
not understand why it was so slow :)...

It does not really cost anything significant in complexity, and is easy to do. 

Thanks, Shay

-Original Message-
From: Rich Salz via RT [mailto:r...@openssl.org] 
Sent: Tuesday, August 26, 2014 12:00
To: Gueron, Shay
Cc: openssl-dev@openssl.org
Subject: [openssl.org #3113] OpenSSL’s DH implementation uses an unnecessarily 
long exponent, leading to significant performance loss

It would be fairly easy to address just the exponent issue. Add #define 
DH_FLG_NIST_EXP_LENGTH 0x01 int DH_generate_key_ex(DH* dh, unsigned long flags) 
{ if (flags  DH_FLG_NIST_EXP_LENGTH)
dh-length = calc_nist_length(dh);
return DH_generate_key(dh);
}
Where calc_nist_length() is like the NSS code quoted in the original post.

I can do this if you think it worthwhile.

--
Rich Salz, OpenSSL dev team; rs...@openssl.org

-
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.

RE: [openssl.org #3113] OpenSSL’s DH implementation uses an unnecessarily long exponent, leading to significant performance loss

2014-08-27 Thread Gueron, Shay via RT 
Hello Rich, 

I would recommend to do that. Otherwise there will be unsuspecting users who 
will (unintentionally) use the long exponent 
...for example, this is what happened to me in the first attempts, and I did 
not understand why it was so slow :)...

It does not really cost anything significant in complexity, and is easy to do. 

Thanks, Shay

-Original Message-
From: Rich Salz via RT [mailto:r...@openssl.org] 
Sent: Tuesday, August 26, 2014 12:00
To: Gueron, Shay
Cc: openssl-dev@openssl.org
Subject: [openssl.org #3113] OpenSSL’s DH implementation uses an unnecessarily 
long exponent, leading to significant performance loss

It would be fairly easy to address just the exponent issue. Add #define 
DH_FLG_NIST_EXP_LENGTH 0x01 int DH_generate_key_ex(DH* dh, unsigned long flags) 
{ if (flags  DH_FLG_NIST_EXP_LENGTH)
dh-length = calc_nist_length(dh);
return DH_generate_key(dh);
}
Where calc_nist_length() is like the NSS code quoted in the original post.

I can do this if you think it worthwhile.

--
Rich Salz, OpenSSL dev team; rs...@openssl.org

-
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.

__
OpenSSL Project http://www.openssl.org
Development Mailing List   openssl-dev@openssl.org
Automated List Manager   majord...@openssl.org

[openssl.org #3113] OpenSSL’s DH implementation uses an unnecessarily long exponent, leading to significant performance loss

2014-08-26 Thread Rich Salz via RT 
It would be fairly easy to address just the exponent issue. Add
#define DH_FLG_NIST_EXP_LENGTH 0x01
int DH_generate_key_ex(DH* dh, unsigned long flags)
{
if (flags  DH_FLG_NIST_EXP_LENGTH)
dh-length = calc_nist_length(dh);
return DH_generate_key(dh);
}
Where calc_nist_length() is like the NSS code quoted in the original post.

I can do this if you think it worthwhile.

--
Rich Salz, OpenSSL dev team; rs...@openssl.org

__
OpenSSL Project http://www.openssl.org
Development Mailing List   openssl-dev@openssl.org
Automated List Manager   majord...@openssl.org

[openssl.org #3113] OpenSSL’s DH implementation uses an unnecessarily long exponent, leading to significant performance loss

2014-08-26 Thread Stephen Henson via RT 
On Tue Aug 26 21:00:02 2014, rsalz wrote:
 It would be fairly easy to address just the exponent issue. Add
 #define DH_FLG_NIST_EXP_LENGTH 0x01
 int DH_generate_key_ex(DH* dh, unsigned long flags)
 {
 if (flags  DH_FLG_NIST_EXP_LENGTH)
 dh-length = calc_nist_length(dh);
 return DH_generate_key(dh);
 }
 Where calc_nist_length() is like the NSS code quoted in the original post.

 I can do this if you think it worthwhile.


It could be added via a ctrl to EVP_PKEY_METHOD so the length parameter is
included when parameters are generated.

OpenSSL 1.0.2 supports X9.42 DH parameter format as well which includes the 'q'
parameter.

Steve.
--
Dr Stephen N. Henson. OpenSSL project core developer.
Commercial tech support now available see: http://www.openssl.org

__
OpenSSL Project http://www.openssl.org
Development Mailing List   openssl-dev@openssl.org
Automated List Manager   majord...@openssl.org

[openssl.org #3113] OpenSSL’s DH implementation uses an unnecessarily long exponent, leading to significant performance loss

2014-01-27 Thread Bodo Moeller via RT 
 The -dsaparam option to dhparam converts DSA parameters to DH and sets the
length parameter.

Note that this isn't actually safe to do in general; it's OK for ephemeral DH
with no re-use of private keys.

A shortcoming of our internal format (following from a similar shortcoming of
the TLS DH format) is that DH groups and DH public keys don't come with the
subgroup order or cofactor: so in general we can't validate that the DH share
received from the peer is in the expected subgroup (or even that the generator
is for a prime-order subgroup in the first place), because we don't need what
that subgroup is.

For servers, we could change DH parameter generation to either create safe
primes with the exponent length set to the recommended length plus one, or to
create Lim-Lee primes and avoid that small-subgroup safety margin. (Or enhance
the internal data format and add subgroup checks, which has some advantages and
some disadvantages. With Lim-Lee primes, with this we'd have twice the
necessary computational cost.)

For clients, when we receive a DH key from the server in the ServerKeyExchange
message, there's not much we can do about unnecessarily long exponents in
general because that message lacks the information needed to decide about
exponent length. We can hope that the generator is for a prime-order subgroup
or otherwise that the DH prime is a safe prime, but I don't think that this
is generally guaranteed by the TLS specification: so someone might get a
practical attack from it. What we could do is check for well-known DH groups
and set the exponent length accordingly. Has anyone ever done a survey for TLS
servers supporting DH, to check how widely used well-known groups are vs.
custom DH groups?


It used to be the case that DH was little supported in SSL/TLS. Now it's more
widely supported, but there's also ECDH support. My immediate reaction about
this DH performance issue would be to recommend using ECDH instead. Given the
complications, is improving the classical DH case worth the effort?

__
OpenSSL Project http://www.openssl.org
Development Mailing List   openssl-dev@openssl.org
Automated List Manager   majord...@openssl.org

[openssl.org #3113] OpenSSL’s DH implementation uses an unnecessarily long exponent, leading to significant performance loss

2013-08-20 Thread Gueron, Shay via RT 

Hello all,

OpenSSL’s DH implementation uses an unnecessarily long exponent, leading to 
significant performance loss

OpenSSL handles the Diffie Hellman (DH) protocol in a very conservative way. By 
default, the length of the private key equals to the bit-length of the prime 
modulus. For example, DH2048 will use a 2048-bit exponent (and two such 
exponentiations are executed for a key exchange).

This is an overkill: NIST suggests that 224 bit exponent is sufficient for 112 
bit security (which is what DH2048 offers).

There is no API to specify the exponent’ length when generating the key. 
However, there is a parameter in the DH struct, which that defines the size of 
the exponent:

struct dh_st
  {
  /* This first argument is used to pick up errors when
  * a DH is passed instead of a EVP_PKEY */
  int pad;
  int version;
  BIGNUM *p;
  BIGNUM *g;
  long length; /* optional */
  BIGNUM *pub_key;  /* g^x */
  BIGNUM *priv_key; /* x */

  int flags;
  BN_MONT_CTX *method_mont_p;
  /* Place holders if we want to do X9.42 DH */
  BIGNUM *q;
  BIGNUM *j;
  unsigned char *seed;
  int seedlen;
  BIGNUM *counter;

  int references;
  CRYPTO_EX_DATA ex_data;
  const DH_METHOD *meth;
  ENGINE *engine;
  };

So, by *manually* changing the ‘length’ field, a user can control the exponent 
length and reduce it to a more desirable size.

Unfortunately, users of the OpenSSL library, such as Apache (and it seems that 
nginx also), are either unaware of the implementation’s default, or are not 
aware of the performance impact of choosing such a long exponent (this leads to 
~9X performance loss, compared to DH2048 with a 224 bits exponent).

This performance overhead is significant when moving to Perfect Forward 
Security (PFS) protocols (e.g., RSA  DHE).

We should point out that the NSS library defaults to the NIST recommended 
values --- here is a snippet.

/* Lengths are in bytes. */
static unsigned int
dh_GetSecretKeyLen(unsigned int primeLen)
{
/* Based on Table 2 in NIST SP 800-57. */
if (primeLen = 1920) { /* 15360 bits */
return 64;  /* 512 bits */
}
if (primeLen = 960) { /* 7680 bits */
return 48;  /* 384 bits */
}
if (primeLen = 384) { /* 3072 bits */
return 32;  /* 256 bits */
}
if (primeLen = 256) { /* 2048 bits */
return 28;  /* 224 bits */
}
return 20;  /* 160 bits */
}

We would like to propose a way to alleviate what seems to be an unnecessary 
overhead.

For OpenSSL, we recommend to *consider* the following:

Change the implementation to default the private key (exponent) to the NIST 
recommended values. The change is very easy to carry out.
This way, the longer exponent would be the choice that is actively  explicitly 
required by the user. Specify in the documentation what the default exponent 
length is. Then, automatically have servers that use OpenSSL enjoy a much 
faster DH speed on TLS sessions that use DH (for PFS).

For the server applications (e.g., Apache) that use OpenSSL library, we 
recommend to *consider* the following:

Change the implementation so that it invokes the DH functions with the NIST 
recommended key size. Especially, as browsers (e.g., using NSS) use 224 bit on 
their side of the key exchange, anyway.



***
Shay Gueron (1, 2), and Vlad Krasnov (1)
(1) Intel Corporation, Israel Development Center, Haifa, Israel
(2) University of Haifa, Israel
***
Copyright(c) 2013, Intel Corp.

-
Intel Israel (74) Limited

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.

__
OpenSSL Project http://www.openssl.org
Development Mailing List   openssl-dev@openssl.org
Automated List Manager   majord...@openssl.org

[openssl.org #3113] OpenSSL’s DH implementation uses an unnecessarily long exponent, leading to significant performance loss

2013-08-20 Thread Stephen Henson via RT 
On Tue Aug 20 09:00:56 2013, shay.gue...@intel.com wrote:


 OpenSSL’s DH implementation uses an unnecessarily long exponent,
 leading to significant performance loss

 OpenSSL handles the Diffie Hellman (DH) protocol in a very
 conservative way. By default, the length of the private key equals
 to the bit-length of the prime modulus. For example, DH2048 will
 use a 2048-bit exponent (and two such exponentiations are executed
 for a key exchange).

 This is an overkill: NIST suggests that 224 bit exponent is sufficient
 for 112 bit security (which is what DH2048 offers).

 There is no API to specify the exponent’ length when generating the
 key. However, there is a parameter in the DH struct, which that
 defines the size of the exponent:


The -dsaparam option to dhparam converts DSA parameters to DH and sets the
length parameter.

Steve.
--
Dr Stephen N. Henson. OpenSSL project core developer.
Commercial tech support now available see: http://www.openssl.org

__
OpenSSL Project http://www.openssl.org
Development Mailing List   openssl-dev@openssl.org
Automated List Manager   majord...@openssl.org