Subject: [TLS] DH generator 2 problem?

From: Michael D'Errico <[email-masked]>
Date: Thu, 8 Oct 2020 13:54:10 -0400

Using finite-field Diffie-Hellman with a generator
of 2 is probably not the best choice.  Unfortunately
all of the published primes (RFCs 2409, 3526, and
7919) use 2 for the generator.  Any other generator
would likely be (not sure how much?) more secure.

The problem is that 2^X consists of a single bit of
value 1 followed by a huge string of zeros.  When
you then reduce this modulo a large prime number,
there will be a pattern in the bits which may help
an attacker discern the value of X.  This is further
helped by the fact that all of the published primes
have 64 bits of 1 in the topmost and bottom-most bits.
In addition, the larger published primes are very
similar to the shorter ones, the shorter ones closely
matching truncated versions of the larger primes.

If you were to manually perform the modulo-P operation
yourself, you would add enough zeros to the end of P
until the topmost bit is just to the right of the 1
bit from 2^X, and then you'd subtract.  This bit
pattern will always be the same, no matter the value
of X.  In particular, the top 64 bits disappear since
they're all one.  Continuing the mod-P operation, you
adjust the number of zeros after the prime P and then
subtract again, reducing the size of the operand.  The
pattern of bits again will be the same, regardless of
the value of X, the only difference being the number
of trailing zeros.

I have not looked at the cyclic patterns which happen
as you do this, but I wouldn't be surprised to find
that the "new" primes based on e (RFC 7919) have
easier-to-spot bit patterns than those based on pi.

This is speculation of course.

Should we define some new DH parameters which use a
different generator?  Maybe the primes are fine....

Mike

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 8 Oct 2020 18:23:32 +0000

I think the efforts these days are focused on using X25519, X448, etc.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Thu, 8 Oct 2020 19:08:52 +0000

> -----Original Message-----
> From: TLS <[email-masked]> On Behalf Of Michael D'Errico
> Sent: Thursday, October 08, 2020 1:54 PM
> To: TLS List <[email-masked]>
> Subject: [TLS] DH generator 2 problem?
> 
> Using finite-field Diffie-Hellman with a generator of 2 is probably not the best
> choice.  Unfortunately all of the published primes (RFCs 2409, 3526, and
> 7919) use 2 for the generator.  Any other generator would likely be (not sure
> how much?) more secure.

No, that is known to be not true.

In particular, if you can compute discrete logs to the base 2, you can compute discrete logs to any base (except in the cases where 2 generates an anomalously small subgroup, which is not the case in the above groups).

Here's how it works; suppose you were given the problem of solving the discrete log problem g^x = h, for some g, h.  Then, if you can solve discrete logs to base 2, you would solve these two problems:

2^y = g
2^z = h

Once you have solved those two problems, then you have x = y z^-1 mod p-1.

It's a little more complex if g, h is not in the subgroup that 2 generates, but not that much more (unless, as above, the size of that subgroup is far smaller than p-1).

> 
> The problem is that 2^X consists of a single bit of value 1 followed by a huge
> string of zeros.  When you then reduce this modulo a large prime number,
> there will be a pattern in the bits which may help an attacker discern the
> value of X.  This is further helped by the fact that all of the published primes
> In addition, the larger published primes are very similar to the shorter ones,
> the shorter ones closely matching truncated versions of the larger primes.
> 
> If you were to manually perform the modulo-P operation yourself, you
> would add enough zeros to the end of P until the topmost bit is just to the
> right of the 1 bit from 2^X, and then you'd subtract.  This bit pattern will
> always be the same, no matter the value of X.  In particular, the top 64 bits
> disappear since they're all one.  Continuing the mod-P operation, you adjust
> the number of zeros after the prime P and then subtract again, reducing the
> size of the operand.  The pattern of bits again will be the same, regardless of
> the value of X, the only difference being the number of trailing zeros.

Actually, for these group, the value of 2^x mod p can take on (p-1)/2 different values; there is no chance that the bit pattern will be trapped in some cul-de-sac, as you appear to be suggesting...

> 
> I have not looked at the cyclic patterns which happen as you do this, but I
> wouldn't be surprised to find that the "new" primes based on e (RFC 7919)
> have easier-to-spot bit patterns than those based on pi.

I would be surprised; do you have some reason that would suggest why bits derived from the binary expansion of 'e' would be somehow qualitatively different from bits derived from the binary expansion of 'pi'?

> This is speculation of course.

Might I suggest you learn a bit of number theory to go along with your speculation?

> 
> Should we define some new DH parameters which use a different
> generator?  Maybe the primes are fine....

If the prime is fine, so is the generator...

---

From: "Michael D'Errico" <[email-masked]>
Date: Thu, 08 Oct 2020 22:20:03 -0400

> This is speculation of course.

I retract this part of my message due to
the fact that the format of the primes in
the recent spec is the same as the format
going back to the original MODP primes.

Mike

---

From: "Michael D'Errico" <[email-masked]>
Date: Fri, 09 Oct 2020 08:35:45 -0400

I have not written any code, but have just been thinking
about what is going on and I am pretty sure that the
bottom 64 bits of 2^X mod P tell you information which
can help you determine X.  The top bits are also suspect
but I haven't worried about those yet.  My original
message below explains which primes I'm talking about.

They all have a solid block of 64 bits with value one in
both the uppermost and bottom-most bit positions.
This construction seems to make the primes a very bad
choice for use with a Diffie-Hellman key exchange.

If you think about how a modulo operation takes place
(the long way, one bit position at a time), you compare
the operand to (a shifted version of) P and if it's bigger
you subtract P and shift P one bit to the right.  If the
operand is not bigger than P, you just shift P one bit to
the right without doing a subtraction.

Due to the construction of all of the primes in the RFCs
cited below, you will get a trace of this in the bottom
64 bits.  There will be a one whenever a subtraction
occurred and a zero otherwise.  This is because if you
calculate the two's complement of the prime (followed
by a bunch of zeros), there will be a lone 1 preceded by
at least 63 zeros.  Instead of subtracting, you can add
this two's complement number, so a 1 will be placed
wherever a subtraction happened or a 0 if there was
no subtraction.

I've not worked out how to use these 64 bits to then
reconstruct X, but this seems like it was purposeful
so I'm fairly certain it reduces the complexity of
determining X from 2^X mod P.  (In fact, there may
be a use for more than just 64 of the bottom bits.)

A private discussion I had seems to indicate that these
particular primes would be bad even with a different
generator (because number theory).  I am hopeful
that it's possible to construct better primes which are
more secure than these (even using a generator of 2)
for use with Diffie-Hellman.

Mike

---

From: Watson Ladd <[email-masked]>
Date: Fri, 9 Oct 2020 07:44:01 -0700

> message below explains which primes I'm talking about.

POC || GTFO

Sincerely,
Watson Ladd

---

From: Michael D'Errico <[email-masked]>
Date: Fri, 9 Oct 2020 11:06:27 -0400

> POC || GTFO

I showed how to do it just by using your brain.  If
I'm wrong please explain.

And, no, you don't get to decide who belongs here.

Also I tried reading your thesis.  It's waaay over
my head, but I think I learned that quaternions are
two-by-two matrices, really ----ing cool.

Mike

---

From: "Christopher Wood" <[email-masked]>
Date: Fri, 09 Oct 2020 08:17:51 -0700

This is a reminder to keep discourse here courteous and respectful. We want this mailing list to be maximally useful for all readers. Dismissive or otherwise disrespectful replies are counter to that goal. Please check out the official Code of Conduct [1] for more information.

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] https://ietf.org/about/administration/policies-procedures/code-of-conduct/
[2] https://mailarchive.ietf.org/arch/browse/cfrg/

---

From: Dan Brown <[email-masked]>
Date: Fri, 9 Oct 2020 17:11:23 +0000

Dear Michael,

Your concern that special primes in Diffie--Hellman might be weaker has some
truth: the famous and ingenious special number field sieve (SNFS) works
against primes with special structure.  See 
https://eprint.iacr.org/2016/961 
for a recent application (which, as an extra wrinkle, is also able to hide
the special structure). 

Therefore, applied cryptography like TLS already uses vetted primes in
Diffie--Hellman, with careful guidance from cryptographers such as those in
CFRG, which specialize in such fundamentals.  (Full disclosure: I proposed
some primes for DH to the CFRG list (for reductionist security), but never
followed through with an I-D.)

Scott explains below very well, as one'd expect, why the generator choice
should generally not matter (random self-reducibility).

Best regards,

Dan

> From: TLS <[email-masked]> On Behalf Of Scott Fluhrer (sfluhrer)
> Sent: Thursday, October 8, 2020 3:09 PM
> To: Michael D'Errico <[email-masked]>; TLS List <[email-masked]>
> Subject: Re: [TLS] DH generator 2 problem?
> 
> > Using finite-field Diffie-Hellman with a generator of 2 is probably
> > not the best choice.  Unfortunately all of the published primes (RFCs
> > 2409, 3526, and
> > 7919) use 2 for the generator.  Any other generator would likely be
> > (not sure how much?) more secure.
> 
> In particular, if you can compute discrete logs to the base 2, you can
compute
> discrete logs to any base (except in the cases where 2 generates an
> anomalously small subgroup, which is not the case in the above groups).
> 
> Here's how it works; suppose you were given the problem of solving the
> discrete log problem g^x = h, for some g, h.  Then, if you can solve
discrete logs
> to base 2, you would solve these two problems:
> 
> 2^y = g
> 2^z = h
> 
> It's a little more complex if g, h is not in the subgroup that 2
generates, but not
> that much more (unless, as above, the size of that subgroup is far smaller
than
> p-1).
> 
> >
> > The problem is that 2^X consists of a single bit of value 1 followed
> > by a huge string of zeros.  When you then reduce this modulo a large
> > prime number, there will be a pattern in the bits which may help an
> > attacker discern the value of X.  This is further helped by the fact
> > that all of the published primes have 64 bits of 1 in the topmost and
bottom-
> most bits.
> > In addition, the larger published primes are very similar to the
> > shorter ones, the shorter ones closely matching truncated versions of
the
> larger primes.
> > would add enough zeros to the end of P until the topmost bit is just
> > to the right of the 1 bit from 2^X, and then you'd subtract.  This bit
> > pattern will always be the same, no matter the value of X.  In
> > particular, the top 64 bits disappear since they're all one.
> > Continuing the mod-P operation, you adjust the number of zeros after
> > the prime P and then subtract again, reducing the size of the operand.
> > The pattern of bits again will be the same, regardless of the value of
X, the
> only difference being the number of trailing zeros.
> 
> Actually, for these group, the value of 2^x mod p can take on (p-1)/2
different
> values; there is no chance that the bit pattern will be trapped in some
cul-de-
> sac, as you appear to be suggesting...
> 
> >
> > I have not looked at the cyclic patterns which happen as you do this,
> > but I wouldn't be surprised to find that the "new" primes based on e
> > (RFC 7919) have easier-to-spot bit patterns than those based on pi.
> 
> I would be surprised; do you have some reason that would suggest why bits
> derived from the binary expansion of 'e' would be somehow qualitatively
> different from bits derived from the binary expansion of 'pi'?
> 
> >

----------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

---

From: "Michael D'Errico" <[email-masked]>
Date: Fri, 09 Oct 2020 15:15:05 -0400

> This is a reminder to keep discourse here courteous and respectful.

I am hoping this comment was not directed at me.
I find myself biting my tongue frequently, but will
try to do a better job of it going forward in any
case.

> We want this mailing list to be maximally useful for all readers. 
> Dismissive or otherwise disrespectful replies are counter to that goal. 
> Please check out the official Code of Conduct [1] for more information.
> 
> 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]. 

I am not really interested in pursuing this further.
If the cryptographers want to run with it, that's
fine.  I'm more of a protocol implementer person
and will refocus my attention there, or not, haven't
decided.

Mike

---

From: "Michael D'Errico" <[email-masked]>
Date: Mon, 12 Oct 2020 12:49:39 -0400

On Fri, Oct 9, 2020, at 11:17, Christopher Wood wrote:
> [1] ...

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