Re: [TLS] DH security issue in TLS

[Antoine Delignat-Lavaud <[e-mail]>]

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]."
> 
> 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 <[e-mail]> 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.
>> 
>> 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)
>> <[e-mail]> wrote:
>> 
>>> See SRF
>>> 
>>> FROM: TLS <[e-mail]> ON BEHALF OF Pascal Urien
>>> SENT: Tuesday, December 03, 2019 5:16 PM
>>> TO: [e-mail]
>>> 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 :
>>> 
>>> g**xy = 1       with y an even integer
>>> g**xy = g**x   for y an odd integer
>>> 
>>> 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 _______________________________________________
>>> TLS mailing list
>>> [e-mail]
>>> https://www.ietf.org/mailman/listinfo/tls
> _______________________________________________
> TLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/tls