Re: [TLS] DH security issue in TLS

[Pascal Urien <[e-mail]>]

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



Le mer. 4 déc. 2019 à 18:16, Antoine Delignat-Lavaud <
[e-mail]> a écrit :

> 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
>