Re: [Cfrg] Your Secret is Too Short (was: Is Diffie-Hellman Better Than We Think?)

[Mike Hamburg <[e-mail]>]

Hello again Mike,

In general, secrets for discrete log systems have to be at least
twice the security level, due to collision-based attacks such as
Pollard rho, baby-step-giant-step, etc.

This is also why P-1 must be divisible by a prime that’s at least
2*lambda bits, where lambda is the desired security level.
Otherwise the Pohlig-Hellman attack breaks the system.

Cheers,
— Mike

> On Oct 21, 2020, at 4:30 PM, Michael D'Errico <[e-mail]> wrote:
> 
> Hello,
> 
> If the length of your Diffie-Hellman secret
> exponent is on the order of the number of bits
> of security you are trying to achieve, then
> it's too short.  [Below I propose a way to
> make a better choice for the prime P used in
> the Diffie-Hellman exchange, which may make it
> easier to determine the strength of D-H.]
> 
> The prime P will end with at least 2 ones in
> the least significant bits (if it's a safe
> prime) and all of the published parameters in
> [MODP] and [FFDHE] have primes with at least
> 64 trailing bits of 1.
> 
> If you count the number of trailing one bits
> and call this M, then brute force finding the
> secret takes 1/M the time you would expect.
> A custom device can be built to unwind the
> modular exponentiation M steps at a time.
> 
> For details, please refer to the conversation
> below, starting with the first message all the
> way at the bottom.
> 
> This translates to a loss of log2(M) bits of
> security of the secret.
> 
> As an example, if you have a requirement that
> your secret exponent X can not be determined
> in 2^64 operations and assume you can just
> generate a random 64-bit number to use as the
> Diffie-Hellman exponent, and if you are using
> any of the published MODP or FFDHE parameters,
> then your secret is actually only giving you
> about 58 bits of security.  (This revised
> estimate may be optimistic.)
> 
> All of the trailing 1 bits show up as factors
> of 2 in the number (P+1), which is why I got
> interested in factoring these numbers (see
> below for a list of the factors of all of the
> MODP and FFDHE primes plus one).
> 
> I don't know how factors other than 2 affect
> the security, so it seems best to avoid them.
> 
> Here's a proposed way to avoid any factors of
> (P+1) which aren't 2:
> 
>  - Choose a prime W of sufficient length
>    ending with bits 01 (W mod 4 is 1)
> 
>  - Append a whole lot of 1 bits to the
>    end of (W-1) and call this P
> 
>  - Ensure P and (P-1)/2 are both prime
> 
> Would P be roughly twice as long as W at the
> minimum?
> 
> Does P perform better than expected w.r.t. all
> of the known Diffie-Hellman attacks on primes
> on the order of the length of W? (P is only
> effectively as long as W, right?)
> 
> Do we actually know that P isn't effectively
> even shorter than W?
> 
> Mike
> 
> [MODP]:  RFC 2409 and RFC 3526
> [FFDHE]: RFC 7919
> 
> 
> On Tue, Oct 20, 2020, at 12:50, Michael D'Errico wrote:
>> Hi again,
>> 
>> My theory is that vanilla modular-exponentiation
>> Diffie-Hellman is not as bad as currently thought
>> and maybe the Number Field Sieve achieves its
>> impressive results when the prime is "bad", where
>> bad means that P+1 has lots of (small) factors.
>> 
>> It was pointed out to me that the largest prime
>> satisfying [1], [2], and [3] in my previous
>> message is 11, but that [3] could be replaced by:
>> 
>>    [3'] (P+1)/12 is prime
>> 
>> Does anybody have access to a Number Field Sieve
>> program who can do the following experiment?
>> 
>>  - Choose a prime P such that (P-1)/2 and
>>    (P+1)/12 are also prime
>> 
>>  - [Added bonus for long string of 1's in
>>    the top bits? (*)]
>> 
>>  - Determine equivalent security bits for
>>    the prime P
>> 
>> Maybe a 64-bit prime would have 30 or so bits
>> of security?
>> 
>> Mike
>> 
>> (*) All of the published primes have sixty-four
>> 1's in the top bits -- is this done for the
>> reason that Diffie-Hellman fails if the secret
>> X is greater than P?
>> 
>> [I also corrected the factorizations below; there
>> were two missing large factors.]
>> 
>> 
>> On Sun, Oct 18, 2020, at 10:04, Michael D'Errico wrote:
>>> 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, Michael D'Errico 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 *
>>>>             500905890761075075179[a] * {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 *
>>>>             233140623089477581[b] * {1807}
>>>> 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....)
>>>> 
>>>> [a] This factor was accidentally omitted when I
>>>>    composed my original message
>>>> 
>>>> [b] I didn't wait long enough to find this factor
>>>>    but someone else did (via private email)
>>>> 
>>>> 
>>>>> 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 Fri, Oct 16, 2020, at 03:22, Michael D'Errico 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 Thu, Oct 15, 2020, at 09:15, Michael D'Errico 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
>>>>>>>>> 
>>>>>>>>> 
>>>>>>>>> On Sat, Oct 10, 2020, at 18:01, Michael D'Errico wrote:
>>>>>>>>>> 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