Subject: [TLS] DH security issue in TLS

From: Pascal Urien <[email-masked]>
Date: Tue, 3 Dec 2019 23:16:14 +0100

I wonder if g**x , with x =(1-p)/2 is checked in current TLS 1.2
implementation ?

In RFC https://tools.ietf.org/html/rfc7919
"Negotiated Finite Field Diffie-Hellman Ephemeral Parameters for Transport
Layer Security (TLS)"

"Traditional finite field Diffie-Hellman has each peer choose their secret
exponent from the range [2, p-2].
Using exponentiation by squaring, this means each peer must do roughly
2*log_2(p) multiplications,
twice (once for the generator and once for the peer's public key)."

Not True !!!
Even for p= safe prime (i.e. Sophie Germain prime, p=2*q+1, with p & q
prime number) secret exponent x= (p-1)/2 is a security issue since :

g**xy = 1       with y an even integer
g**xy = g**x   for y an odd integer

If p is not a safe prime (like in RFC 5114) other issues occur...

Pascal

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 3 Dec 2019 23:03:20 +0000

See SRF

From: TLS <[email-masked]> On Behalf Of Pascal Urien
Sent: Tuesday, December 03, 2019 5:16 PM
To: [email-masked]
Subject: [TLS] DH security issue in TLS

I wonder if g**x , with x =(1-p)/2 is checked in current TLS 1.2 implementation ?

In RFC https://tools.ietf.org/html/rfc7919
"Negotiated Finite Field Diffie-Hellman Ephemeral Parameters for Transport Layer Security (TLS)"

"Traditional finite field Diffie-Hellman has each peer choose their secret exponent from the range [2, p-2].
Using exponentiation by squaring, this means each peer must do roughly 2*log_2(p) multiplications,
twice (once for the generator and once for the peer's public key)."

Not True !!!
Even for p= safe prime (i.e.. Sophie Germain prime, p=2*q+1, with p & q prime number) secret exponent x= (p-1)/2 is a security issue since :

SRF: actually, g**xy  = 1 in both cases, as g**x = 1 (for the g, p values specified in RFC7919); this is easily seen as all listed p values are safe primes, and in all cases, g=2 and p=7 mod 8.

In any case, why would that be a security issue?  If both sides are honest (and select their x, y values honestly), the probability of one of them selecting (p-1)/2 as their private value is negligible (even if our selection logic allowed that as a possible value – it generally doesn’t).  If we have two honest parties with an adversary replacing one of the side’s key share with g**(p-1)/2, well, the protocol transmits signatures of the transcript, and so that’ll be detected. If you have an honest side negotiating with a dishonest one, well, the dishonest one could select (p-1)/2 as its private value – however, they could also run the protocol honestly (and learn the shared secret and the symmetric keys, which are usually the target), and there’s nothing the protocol can do about that.

Now, if an honest party reused their private values for multiple exchanges, a similar observation would allow an adversary to obtain a single bit of the private value.  He would do that by performing an exchange with the honest party mostly honestly, selecting a value x as his private value, but instead of transmitting g**x as his key share, he would transmit -g**x.  Then, the shared value that the honest party would derive is:

  g**xy  with y an even integer
  -g**xy  with y an odd integer

The adversary can compute both these values, and determine which is being used later in the protocol.

So, the adversary can learn a single bit of the private value (which doesn’t translate to him learning any bit of the shared secret, much less the symmetric keys) – however, he cannot leverage this to learn anything else of the private key.  I do not believe that a single bit is worth worrying about.  And, again, if we generate a fresh DH private value for every exchange (which we encourage people to do for PFS), even that single bit doesn’t apply to any other exchange.

If p is not a safe prime (like in RFC 5114) other issues occur....

Pascal

---

From: Andrey Jivsov <[email-masked]>
Date: Tue, 3 Dec 2019 17:52:21 -0800

https://tools.ietf.org/html/rfc7919#section-5.1 prohibits x=(p-1)/2 because
this results in a peer's public key g^x= 1.

Allowing this makes some man-in-the middle attacks on TLS easier, because
the attacker can predict the value of the ephemeral secret key on another
leg of the connection.

On Tue, Dec 3, 2019 at 3:03 PM Scott Fluhrer (sfluhrer) <[email-masked]>
wrote:

> See SRF
>
>
>
> *From:* TLS <[email-masked]> *On Behalf Of * Pascal Urien
> *Sent:* Tuesday, December 03, 2019 5:16 PM
> *To:* [email-masked]
> *Subject:* [TLS] DH security issue in TLS
>
>
>
> Even for p= safe prime (i.e.. Sophie Germain prime, p=2*q+1, with p & q
> SRF: actually, g**xy  = 1 in both cases, as g**x = 1 (for the g, p values
> specified in RFC7919); this is easily seen as all listed p values are safe
> primes, and in all cases, g=2 and p=7 mod 8.
>
>
>
> In any case, why would that be a security issue?  If both sides are honest
> (and select their x, y values honestly), the probability of one of them
> selecting (p-1)/2 as their private value is negligible (even if our
> selection logic allowed that as a possible value – it generally doesn’t).
> If we have two honest parties with an adversary replacing one of the side’s
> key share with g**(p-1)/2, well, the protocol transmits signatures of the
> transcript, and so that’ll be detected. If you have an honest side
> negotiating with a dishonest one, well, the dishonest one could select
> (p-1)/2 as its private value – however, they could also run the protocol
> honestly (and learn the shared secret and the symmetric keys, which are
> usually the target), and there’s nothing the protocol can do about that.
>
>
>
> Now, if an honest party reused their private values for multiple
> exchanges, a similar observation would allow an adversary to obtain a
> single bit of the private value.  He would do that by performing an
> exchange with the honest party mostly honestly, selecting a value x as his
> private value, but instead of transmitting g**x as his key share, he would
> transmit -g**x.  Then, the shared value that the honest party would derive
> is:
>
>
>
> So, the adversary can learn a single bit of the private value (which
> doesn’t translate to him learning any bit of the shared secret, much less
> the symmetric keys) – however, he cannot leverage this to learn anything
> else of the private key.  I do not believe that a single bit is worth
> worrying about.  And, again, if we generate a fresh DH private value for
> every exchange (which we encourage people to do for PFS), even that single
> bit doesn’t apply to any other exchange.
>
>
>
>
>
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Pascal Urien <[email-masked]>
Date: Wed, 4 Dec 2019 17:23:11 +0100

Hi all

https://tools.ietf.org/html/rfc7919 seems somewhat confusing because the
order of the generator (2) is q=(p-1)/2 and not  (p-1 )

So in place of
"Traditional finite field Diffie-Hellman has each peer choose their secret
exponent from the range [2, p-2]."
It should suggest to use
"Traditional finite field Diffie-Hellman has each peer choose their secret
exponent from the range [2, q-1]."

I put below some basic background that could help to understand the DH
security

If a safe prime p=2q+1 is congruent to 7 modulo 8, then it is a divisor of
the Mersenne number
with its matching Sophie Germain prime (q) as exponent.
a Mersenne prime is a prime number that is one less than a power of two.
That is, it is a prime number of the form Mn = 2**n - 1 for some integer n.

2**q-1 = kp;
2**(p-1)/2 = 1 mod p
Therefore 2 is a generator of order q=(p-1)/2

(p-1) is a generator of order 2, since (p-1)**2 = (p**2+1-2p) = 1 mod q

Example
p=7 = 2x3 +1, q=3
p = 7 mod 8
6 = 2x3
1 group of order 6, phi(6)= 2 generators (q-1)
1 group of order 3, phi(3)= 2 generators (q-1)
1 group of order 2, phi(2)= 1 generators

2 4 1
3 2 6 4 5 1
4 2 1
5 4 6 2 3 1
6 1

Le mer. 4 déc. 2019 à 02:52, Andrey Jivsov <[email-masked]> a écrit :

> https://tools.ietf.org/html/rfc7919#section-5.1 prohibits x=(p-1)/2
> because this results in a peer's public key g^x= 1.
>
> On Tue, Dec 3, 2019 at 3:03 PM Scott Fluhrer (sfluhrer) <
> [email-masked]> wrote:
>
>> See SRF
>>
>>
>>
>> In any case, why would that be a security issue?  If both sides are
>> honest (and select their x, y values honestly), the probability of one of
>> them selecting (p-1)/2 as their private value is negligible (even if our

---

From: Antoine Delignat-Lavaud <[email-masked]>
Date: Wed, 04 Dec 2019 17:16:07 +0000

Hi Pascal,

TLS 1.2 does not mandate servers to use safe DH primes. As a client, you 
get g and p from the server. You don't know if p is a safe prime, or 
indeed if it is a prime at all. You don't even know if g is a generator 
of Zp* - it could also be a generator for a small order subgroup. In 
that sense, RFC 7919 is correct in that, in general TLS 1.2, clients 
could pick any private exponent between 2 and p-2 when you have no 
information on p and g. When using an arbitrary server-selected prime 
and generator there is no guarantee that the server selected a share 
that is not in a small subgroup, and similarly there is no guarantee for 
the server that the client share is not of small order. In fact you 
don't even have this guarantee either with ECDH (where the curves are 
chosen from a fixed list) because some curves also have small subgroups.

If you want the guarantee that your DH key exchange is contributive, 
that is, that neither single party can determine with high-probability 
the DH secret produced by the key exchange, you can either 1. use one of 
the safe groups defined in RFC7919. When using these groups, you should 
pick an exponent between 2 and q-1. 2. Figure out all of the low-order 
elements of Zp* and check that the DH secret is not one of them.

Most implementations will do (2), i.e. they check that g^xy is not 0, 1, 
p-1. This is sufficient if p is a safe prime, but it is too expensive to 
check that p and p-1/2 are prime. For X25519 most implementations now 
check that x(yG) <> I, as it is much simpler than checking xG and yG for 
the 8 small order elements. You may be interested in checking Section 
III.B of [1]

Best,

Antoine

[1] http://antoine.delignat-lavaud.fr/doc/ndss15.pdf

On 2019-12-04 16:23, Pascal Urien wrote:
> Hi all
> 
> https://tools.ietf.org/html/rfc7919 seems somewhat confusing because
> the order of the generator (2) is q=(p-1)/2 and not  (p-1 )
> 
> So in place of
> 
> "Traditional finite field Diffie-Hellman has each peer choose their
> secret exponent from the range [2, p-2]."
> It should suggest to use
>  "Traditional finite field Diffie-Hellman has each peer choose their
> secret exponent from the range [2, q-1]."
> 
> If a safe prime p=2q+1 is congruent to 7 modulo 8, then it is a
> divisor of the Mersenne number
>> Allowing this makes some man-in-the middle attacks on TLS easier,
>> because the attacker can predict the value of the ephemeral secret
>> key on another leg of the connection.
>> 
>> On Tue, Dec 3, 2019 at 3:03 PM Scott Fluhrer (sfluhrer)
>> <[email-masked]> wrote:
>> 
>>> See SRF
>>> 
>>> FROM: TLS <[email-masked]> ON BEHALF OF Pascal Urien
>>> SENT: Tuesday, December 03, 2019 5:16 PM
>>> TO: [email-masked]
>>> SUBJECT: [TLS] DH security issue in TLS
>>> 
>>> "Traditional finite field Diffie-Hellman has each peer choose
>>> their secret exponent from the range [2, p-2].
>>> Even for p= safe prime (i.e.. Sophie Germain prime, p=2*q+1, with
>>> p & q prime number) secret exponent x= (p-1)/2 is a security issue
>>> since :
>>> 
>>> SRF: actually, g**xy  = 1 in both cases, as g**x = 1 (for the g, p
>>> values specified in RFC7919); this is easily seen as all listed p
>>> values are safe primes, and in all cases, g=2 and p=7 mod 8.
>>> 
>>> In any case, why would that be a security issue?  If both sides
>>> are honest (and select their x, y values honestly), the
>>> probability of one of them selecting (p-1)/2 as their private
>>> value is negligible (even if our selection logic allowed that as a
>>> possible value – it generally doesn’t).  If we have two honest
>>> parties with an adversary replacing one of the side’s key share
>>> with g**(p-1)/2, well, the protocol transmits signatures of the
>>> transcript, and so that’ll be detected. If you have an honest
>>> side negotiating with a dishonest one, well, the dishonest one
>>> could select (p-1)/2 as its private value – however, they could
>>> also run the protocol honestly (and learn the shared secret and
>>> the symmetric keys, which are usually the target), and there’s
>>> nothing the protocol can do about that.
>>> 
>>> exchanges, a similar observation would allow an adversary to
>>> obtain a single bit of the private value.  He would do that by
>>> performing an exchange with the honest party mostly honestly,
>>> selecting a value x as his private value, but instead of
>>> transmitting g**x as his key share, he would transmit -g**x.
>>> Then, the shared value that the honest party would derive is:
>>> 
>>> So, the adversary can learn a single bit of the private value
>>> (which doesn’t translate to him learning any bit of the shared
>>> secret, much less the symmetric keys) – however, he cannot
>>> leverage this to learn anything else of the private key.  I do not
>>> believe that a single bit is worth worrying about.  And, again, if
>>> we generate a fresh DH private value for every exchange (which we
>>> encourage people to do for PFS), even that single bit doesn’t
>>> apply to any other exchange.
>>> 
>>> Pascal _______________________________________________
>>> TLS mailing list
>>> [email-masked]

---

From: Pascal Urien <[email-masked]>
Date: Thu, 5 Dec 2019 17:51:30 +0100

Hi All

I found in NIST Special Publication 800-56A Revision 3
5.6.2.3.1 FFC Full Public-Key Validation Routine
2. Verify  that  1 = y q mod p.

This test is implemented in OPENSSL

This test relies on the fact  that q and p are prime

Pascal

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 6 Dec 2019 08:32:18 +0000

>2. Verify  that  1 = y q mod p. 

This only works for FIPS 186-style DH values where q is present, not PKCS #3
values as used in SSH and SSL/TLS.  Only TLS-LTS sends the q value allowing
this check.

Peter.