Re: [Cfrg] Weak Diffie-Hellman Primes

[Dan Brown <[e-mail]>]

Hi Mike and CFRG list,

Not sure where to draw line between false alarms and well-intentioned concerns, since these can intersect, so I tried to understand Mike's DLP attack strategy ...

Somehow he aims to find bits, the 2^j, in the quotient of 2^X over P.  But there are nearly X/2 such bits, so finding them all would cost as much as exhaustive search.

(C.f. Polar rho method, taking sqrt(X) steps.) ​

Likely misunderstood the proposed method, but am at least trying.


Sent with BlackBerry Work (www.blackberry.com)
________________________________
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://urldefense.proofpoint.com/v2/url?u=https-3A__www.irtf.org_mailman_listinfo_cfrg&d=DwICAg&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q-lhj0sp26wE&r=qkpbVDRj7zlSRVql-UonsW647lYqnsrbXizKI6MgkEw&m=tZVPiwvPHNhVOmq07mAv6dmVDQlZzwq_f8amSXXto_E&s=NyJBFGx6gbKbkDE1W9v4dZEZXff-kNCuzGyswktikEk&e=

----------------------------------------------------------------------
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.