[Cfrg] Ideal Diffie-Hellman Primes (was: Inadequate Definition of "Safe Prime" ?)

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

Good morning,

Perhaps there is an "ideal" Diffie-Hellman prime
with the following characteristics:

    [1] P is prime
    [2] (P-1)/2 is prime
    [3] (P+1)/4 is prime

Is it possible to generate such a number (in a
reasonable amount of time)?  (You'd be able to
skip any numbers where P mod 8 isn't 3.)

In addition, I notice that all of the published
Diffie-Hellman primes in [MODP] and [FFDHE] have
their 64 most significant bits set to 1.

Is this to make it unlikely for the secret X to
be randomly chosen greater than P (when
calculating 2^X mod P)?

Does Diffie-Hellman fail if you choose a secret
X larger than P?  Do clients and servers check?

Mike

[MODP]:  RFC 2409 and RFC 3526
[FFDHE]: RFC 7919


On Sat, Oct 17, 2020, at 14:34, I wrote:
> Hi,
> 
> I went to the trouble of computing the factors [*]
> of (P+1)/2^64 for all of the "MODP" primes in RFCs
> 2409 and 3526, and the "FFDHE" primes in RFC 7919,
> so I thought it would be good to share the results.
> 
> The final factor(s) are not shown but are assumed
> to be prime or very large since the factoring
> program never finished:
> 
> 
>   modp-0768: 3 * 5 * 58502243 * {183-digits}
> 
>   modp-1024: 2 * 3^3 * 7 * 61 * 755333 *
>              903210511397 * {267}
> 
>   modp-1536: 2^3 * 3^2 * 5 * 7 * 59 * 773 *
>              10111 * 713941 * 116114161 * {418}
> 
>   modp-2048: 3 * 5 * {597}
>  ffdhe-2048: 2^3 * 3^3 * 5 * 101 * 46559 *
>              95651 * {583}
> 
>   modp-3072: 3 * 13 * 2129 * 5572027361377 * {888}
>  ffdhe-3072: 2^3 * 3 * 173 * {902}
> 
>   modp-4096: 2 * 3 * 3067 * {1210}
>  ffdhe-4096: 3^3 * 5^2 * 5683 * 853854997 * {1199}
> 
>   modp-6144: 3 * 19 * 137 * 211 * {1825}
>  ffdhe-6144: 2 × 3 × 41 × 9533 × 2417897 * {1818}
> 
>   modp-8192: 2^5 * 3^3 * 5 * 7^2 * 17 * 277 * {2438}
>  ffdhe-8192: 3 * 937 * 140611 * {2439}
> 
> 
> Are there any conclusions to be drawn from this?
> 
> Maybe that modp-2048 is "better" than ffdhe-2048,
> but ffdhe-8192 is better than modp-8192?
> 
> Is modp-1536 a really bad choice for a prime?
> 
> Mike
> 
> 
> [*] I used: https://www.alpertron.com.ar/ECM.HTM
>     (hopefully I didn't make any mistakes....)
> 
> 
>> Hello,
>> 
>> I think that the current definition of a "safe prime"
>> for use in Diffie-Hellman may be inadequate and
>> could require more than just:
>> 
>>     [1] P is prime
>>     [2] (P-1)/2 is also prime
>> 
>> Maybe you also want:
>> 
>>     [3] (P+1) is square-free
>> 
>> This postulate follows from the discussion quoted
>> below.  I've found that all of the Diffie-Helman primes
>> published in RFC's 2409, 3526, and 7919 allow you
>> to brute-force compute a secret 32 times faster than
>> you would expect just looking at the number of bits.
>> 
>> The prime numbers all have the property that (P+1)
>> is divisible by 2^64.  This follows from the fact that
>> the lower sixty-four bits are all ones.  I don't know
>> if any additional problem arises by having the top
>> 64 bits also equal to 1.
>> 
>> These primes are (assumedly) safe according to the
>> current definition ([1] and [2] above), but perhaps
>> effectively 64 or more bits shorter than advertised.
>> 
>> This could mean that the number field sieve would
>> also be faster (the 2048-bit primes could act like
>> 1984-bit primes), but I have not tried to determine
>> this myself.
>> 
>> It may be really difficult to find primes satisfying [1],
>> [2], and [3], so there'd maybe be a trade-off where
>> you'd allow a few square factors....
>> 
>> This is not my field of expertise, so I apologize if
>> anyone feels I'm wasting their time.
>> 
>> Mike
>> 
>> 
>> On Fri, Oct 16, 2020, at 09:07, Mike Hamburg wrote:
>>> 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,
>>>> 
>>>> [...]
>>>> 
>>>> 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 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