Re: [Cfrg] Weak Diffie-Hellman Primes

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

Hello,

Thank you for your message!

The algorithm I showed should run about 32 times faster
than brute force, even though it's doing a brute force
search.

According to Wikipedia, a 2048-bit Diffie-Hellman prime
is equivalent to 112 bits for a symmetric key, so perhaps
the special structure of both 2048-bit published primes
makes them equivalent to only 107 bits.

Mike


On Thu, Oct 15, 2020, at 16:00, Anna Johnston wrote:
> Hi Michael,
>   The attack you mentioned is logical. If I am not mistaken, the attack 
> is recovering, bit by bit, the quotient (v) in the equation: 2^X = vP + 
> r, where r = 2^X mod P. The fly in the attack is size. 
> (1) The smallest P in this list is over 700 bits: P > 2^{700}.
> (2) X is on the order of P, as 2 has order q where P=2q+1.
> (3) so, 2^X, in its unreduced form, is greater than 2^{2^{700}}
> (4) That means that v (the quotient) is greater than 
> 2^{2^{700}}/2^{700}=2^{2^{700}-700} which is still about 2^{2^{700}}, 
> or 2^{700} bits long. 
> 
> This size means that only a minuscule fraction of the quotient bits 
> could be computed/stored (not enough seconds in time or atoms in the 
> known universe).
> 
> Hope this helps,
> 
> Anna
> 
> > On Oct 15, 2020, at 09:15, Michael D'Errico <[e-mail]> wrote:
> > 
> > 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
> > 
> > _______________________________________________
> > Cfrg mailing list
> > [e-mail]
> > https://www.irtf.org/mailman/listinfo/cfrg
> 
>