Re: [Cfrg] Weak Diffie-Hellman Primes

[Mike Hamburg <[e-mail]>]

Hello Mike,



The limiting factor for DH security (and also RSA security) is a very complex
attack algorithm called the Number Field Sieve.  So attacks on 2048-bit DH
safe prime would take time:

* ~ 2^2048 using straightforward brute force
* ~ 2^1024 using collision-based brute force such as Pollard’s Rho
* ~ 2^112 using NFS.

For DSA and sometimes for DH, people use primes p with a generator g
of smaller prime order q, eg q ~ 2^256 here.  This speeds up the operation
at the cost of lower brute-force resistance.  This would reduce the brute
force costs to

* ~ 2^256 using straightforward brute force
* ~ 2^128 using collision-based brute force
* but still ~ 2^112 using NFS

This is generally seen as acceptable, because the cost estimates for rho
attacks are much more certain than for NFS, and are still at an acceptable
level.  Since the security is determined mainly by the best attack, this
doesn’t lower the security.  (Unless NFS at that scale is harder than
projected, but in that case the security is still fine.)

Likewise, your attack slightly speeds up straightforward brute force, but
not (as far as you’ve shown) collision-based brute force or NFS.  So it
doesn’t affect the overall security of DH / DSA.



However, primes of a special form *can* reduce security against the NFS.
But these aren’t primes that specifically begin or end with a lot of 1s, but
rather primes that can be expressed as a low or medium-degree polynomial
with small coefficients.  For example, p = 2^2048 - 1557 would be a poor
choice, because it can be written as a small polynomial, eg

p = x^32 - 1557 with x = 2^64.

I’m not an expert on NFS, so I’m not sure exactly how much security this
knocks off.  Asymptotically you lose about 20% of the bits, (eg 2^112 ->
2^89, which is still out of reach of academics but maybe not large / govt
organizations, especially because most of the work can be amortized
across many discrete logs) but concretely this might be quite different.



Cheers,
— Another Mike

> On Oct 16, 2020, at 3:22 AM, Michael D'Errico <[e-mail]> wrote:
> 
> 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
>> 
>> 
> 
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg