[TLS] Weak Diffie-Hellman Primes (was: DH generator 2 problem?)

[Michael D'Errico <[e-mail]>]

On Fri, Oct 9, 2020, at 11:17, Christopher Wood wrote:
> Michael, since your question is more related to the cryptographic 
> primitives used by TLS than the protocol itself, the chairs encourage 
> you to continue this discussion on the CFRG mailing list [2]. 
> 
> Thanks,
> Chris, on behalf of the chairs
> 
> [1] ...
> [2] https://mailarchive.ietf.org/arch/browse/cfrg/

Hi,

As requested, I sent the message below to the CFRG
mailing list on the 10th.  I did not join the list, but have
been watching via the link [2] above and so far nobody
has said anything.

Mike


------------------------------------------------------------
To: cfrg at irtf dot org

Hi,

I'm not a member of this list, but was encouraged to
start a discussion here about a discovery I made
w.r.t. the published Diffie-Hellman prime numbers in
RFC's 2409, 3526, and 7919.  These primes all have
a very interesting property where you get 64 or more
bits (the least significant bits of 2^X mod P for some
secret X and prime P) detailing how the modulo
operation was done.  These 64 bits probably reduce
the security of Diffie-Hellman key exchanges though
I have not tried to figure out how.

The number 2^X is going to be a single bit with value
1 followed by a lot of zeros.  All of the primes in the
above mentioned RFC's have 64 bits of 1 in the most
and least significant positions.  The 2's complement
of these primes will have a one in the least significant
bit and at least 63 zeros to the left.

When you think about how a modulo operation is done
manually, you compare a shifted version of P against
the current value of the operand (which is initially 2^X)
and if it's larger than the (shifted) P, you subtract P at
that position and shift P to the right, or if the operand
is smaller than (the shifted) P, you just shift P to the
right without subtracting.

Instead of subtracting, you can add the 2's complement
I mentioned above.  Because of the fact that there are
63 zeros followed by a 1 in the lowest position, you will
see a record of when the modulo operation performed
a subtraction (there's a one) and when it didn't (there's
a zero).

You can use the value of the result you were given by
your peer (which is 2^X mod P) and then add back the
various 2^j * P's detailed wherever the lowest 64 bits
had a value of 1 to find the state of the mod  P operation
when it wasn't yet finished.  This intermediate result is
likely going to make it easier to determine X than just a
brute force search.

I don't plan to join this list, though I am flattered to have
been asked to do so.  I'm not a cryptographer.

Mike