Re: [Cfrg] Weak Diffie-Hellman Primes

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

Hi again,

[My bigger concern is other long-term parameters
in other places with longer runs of 1's or 0's.]

If you take the lowest 64 bits of the public value:

    r = (uint64) (2^X mod P);

because of the special format of the published
prime numbers as detailed in my original message
below, you know that the modulo P operation
touched this much larger number:

    (2^X mod P) + rP

I haven't worked out what advantage this gives
you in determining X, and likely don't know the
required math to do so.

I am HOPEFUL that this is a false alarm, but I don't
know how to prove that to myself.

Thank you for the consideration,

Mike


On Mon, Oct 12, 2020, at 14:22, Dan Brown wrote:
>  
> 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.