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 < anto...@delignat-lavaud.fr> 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 <cry...@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) > >> <sfluh...@cisco.com> wrote: > >> > >>> See SRF > >>> > >>> FROM: TLS <tls-boun...@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 > > _______________________________________________ > > TLS mailing list > > TLS@ietf.org > > https://www.ietf.org/mailman/listinfo/tls >
_______________________________________________ TLS mailing list TLS@ietf.org https://www.ietf.org/mailman/listinfo/tls
