Re: [TLS] DH security issue in TLS

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 <crypto@brainhub.org> 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) <
> sfluhrer@cisco.com> wrote:
>
>> See SRF
>>
>>
>>
>> *From:* TLS <tls-bounces@ietf.org> *On Behalf Of * Pascal Urien
>> *Sent:* Tuesday, December 03, 2019 5:16 PM
>> *To:* tls@ietf.org
>> *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
>> TLS@ietf.org
>> https://www.ietf.org/mailman/listinfo/tls
>>
>