Re: [Cfrg] Weak Diffie-Hellman Primes

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

Hi,

I've figured out just a bit more.  I'm actually trying
not to work on this problem, but my brain keeps
thinking about it anyway.  The special format of
the prime numbers in RFC's 2409, 3526, and
7919 allow you to create an interesting device to
calculate the private value from a Diffie-Hellman
public value using on the order of N bits (size of
prime P).

The lowest 64 bits of the Diffie-Hellman public
value Y = (2^X mod P) contain a record of when
the mod operation performed a subtraction of a
shifted version of P (see my original message
quoted below).  You can reconstruct a larger value
the modulo operation was working on by adding
back:

    uint64 y = Y;    // low 64 bits of public value

    Y += y * P;    // mod P touched this number

This updated version of Y contains the number
that the mod P operation was working on 64 steps
prior to finishing.  But since the generator was 2
(and 2^X is a solitary 1 followed by a huge string
of zeros), this new larger value of Y will have 64
zeros at the end which can be removed:

    Y >>= 64;    // remove 64 zero bits

This process can now repeat using the lowest 64
bits of Y again:

repeat {

    uint64 y = Y;

    Y += y * P;

    Y >>= 64;

} until (???);

This process unwinds the modulo P operation all
the way back to 2^X in steps of size 64.  The only
thing missing is the terminating condition, which
I'm pretty sure would be: Y contains a single bit
with value 1 (somewhere in the top 64 bits).  If
so, then the value of y would be zero a few times
in a row and then contain a single one bit.

If you can reliably determine when the algorithm
has finished, you could build a device which
computes X from Y using roughly N bits.  It would
be really slow, but it would be guaranteed to find
the answer (32 times faster than brute force
reversing the mod P operation one bit at a time
on average?).

Perhaps there is a way to make this algorithm
(much) faster?

Even if there isn't, it is very interesting to me that
these primes exhibit such a strange feature.

Mike


> From: Michael D'Errico <[e-mail]>
> Sent: *Oct 10, 2020 6:01 PM
> To: [e-mail]
> Subject: [Cfrg] Weak Diffie-Hellman Primes
> 
> 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