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 <[email protected]> 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)
<[email protected]> wrote:
See SRF
FROM: TLS <[email protected]> ON BEHALF OF Pascal Urien
SENT: Tuesday, December 03, 2019 5:16 PM
TO: [email protected]
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
[email protected]
https://www.ietf.org/mailman/listinfo/tls
_______________________________________________
TLS mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/tls
_______________________________________________
TLS mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/tls
