[Cfrg] Is Diffie-Hellman Better Than We Think? (was: Ideal Diffie-Hellman Primes)

Michael D'Errico <mike-list@pobox.com> Tue, 20 October 2020 16:51 UTC

Return-Path: <mike-list@pobox.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id E50F73A0C01 for <cfrg@ietfa.amsl.com>; Tue, 20 Oct 2020 09:51:48 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level:
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=pobox.com header.b=iMubwTuv; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=UWxWQ2AX
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 5BWQGyvIPj48 for <cfrg@ietfa.amsl.com>; Tue, 20 Oct 2020 09:51:46 -0700 (PDT)
Received: from wout3-smtp.messagingengine.com (wout3-smtp.messagingengine.com [64.147.123.19]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id BA61E3A1170 for <cfrg@irtf.org>; Tue, 20 Oct 2020 09:51:46 -0700 (PDT)
Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.west.internal (Postfix) with ESMTP id 47CD86B8 for <cfrg@irtf.org>; Tue, 20 Oct 2020 12:51:45 -0400 (EDT)
Received: from imap21 ([10.202.2.71]) by compute4.internal (MEProxy); Tue, 20 Oct 2020 12:51:45 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pobox.com; h= mime-version:message-id:in-reply-to:references:date:from:to :subject:content-type:content-transfer-encoding; s=fm1; bh=5OtnP n35fZkJmHsVJ3cuNieU8rJn9mVBj3cExeETm1I=; b=iMubwTuvjkdYgSBTYwSmb E8rCtqSwwea/aS1qrgvXqngvXX7o1Cq11KFYB8U67r0COZkAOqwoVjMU4QUMuMXM chvxYdlwxUXm0wiIhogXONfKL19w/KaiTnWl4t2VbNYWQWs7wnhrTNo4a+E3ibYc R96TZDI01PR/uHc1eBcb2D+RpK8v34EItEFls94/van21ICKlVES4RnbVLkOFJnR D85GoYFvP+jKkTniZdcxmdiZkpiS8Mh97E9MabcKd1X/IbC67B815mJgeZmxtirj uHNyGcQIfgk9qo/PQCcqnrAwfsYuy9dEvMguK/OZfxj2uO6Xpt+k2CVPVepehZLI A==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender :x-sasl-enc; s=fm1; bh=5OtnPn35fZkJmHsVJ3cuNieU8rJn9mVBj3cExeETm 1I=; b=UWxWQ2AX6ICaTtTGsYk3K2DaDbsqk6N9Tvw6P7TUANEzJoeIetSs/sGxN ixT3zdhJoY1lFUXRkdKF+i3dqKHL22QPPM322IHXdIvYqXh0GYqXY5g9NLQlB/oU UdzZoCnySvnkMPxj7sgykwWVXFb8QCXvEJbwina/WsQyct1rHX4OSDHiC41/Tynu bjmzSj+0qgtqmGUrX1OH/2LF1rTbMSeUPWf0kkOr44Jih/2WdVawOI7FK00MAIzF SsKddXF1lid1R6VtNDTW8Vf7ce03zMp9zYL+o9F2vJQP6ka7EoUogT4aq/5prLP7 56C/LPa8K8tQbAXBRRdZ1sRg4AUgQ==
X-ME-Sender: <xms:oBWPX3F1G9PKeHyv2Tq081_-NQygrrhNs7gd9pZRI3mwdCMdxkQKxQ> <xme:oBWPX0WjVhiANFJhFOcFuHrBmoeVl2C83yjM9pP4I4mHQNjkshZdc4PNXA2wvWFl4 SPlXLYtaoCp-VD7vg>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedujedrjeefgddutdegucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpefofgggkfgjfhffhffvufgtgfesth hqredtreerjeenucfhrhhomhepfdfoihgthhgrvghlucffkdfgrhhrihgtohdfuceomhhi khgvqdhlihhsthesphhosghogidrtghomheqnecuggftrfgrthhtvghrnhepgeelteefie eijeeugedvkefgjeeijeffveeijeekkeeklefhieehveejtdeugeeinecuffhomhgrihhn pegrlhhpvghrthhrohhnrdgtohhmrdgrrhenucevlhhushhtvghrufhiiigvpedtnecurf grrhgrmhepmhgrihhlfhhrohhmpehmihhkvgdqlhhishhtsehpohgsohigrdgtohhm
X-ME-Proxy: <xmx:oBWPX5Laj4TehBZ3VaFNz1A1hLwMUClHTKtKBoGC07rjKdSYVR_A2Q> <xmx:oBWPX1GoGg9bHAZGOHQpOUM1dKEd4BD12OBHT-INfSE-W0To4tGQIw> <xmx:oBWPX9U0ggbSVkr8LJv0FVo7uwasStgvjyu6GQshZxASDvEEqVBjYA> <xmx:oBWPX1i9IPluyVCeobGaVGUSSOM1LA0vRIHG8USIvMSsZ7zeDodMPw>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id EC565660069; Tue, 20 Oct 2020 12:51:34 -0400 (EDT)
X-Mailer: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.3.0-502-gfef6c88-fm-20201019.001-gfef6c888
Mime-Version: 1.0
Message-Id: <1ed370e4-8a09-4a41-bf15-22d8e61bef6e@www.fastmail.com>
In-Reply-To: <bc77f256-2fc6-48c1-9a7a-60ec6caaa55d@www.fastmail.com>
References: <07090aa6-1bd1-4a37-810d-6cd95a6f1e7c@www.fastmail.com> <ACF3D521-99D7-4A46-A3E6-2865FE53A816@gmail.com> <19672d78-77de-4744-b9d8-470a18dc3ac0@www.fastmail.com> <770E332F-B404-45C8-898B-BAD69A9B75A0@shiftleft.org> <cc5b03ef-01d0-44a3-9030-1faa99107425@www.fastmail.com> <3c63be30-5c09-42b0-a0a4-18190ef5d548@www.fastmail.com> <bc77f256-2fc6-48c1-9a7a-60ec6caaa55d@www.fastmail.com>
Date: Tue, 20 Oct 2020 12:50:17 -0400
From: "Michael D'Errico" <mike-list@pobox.com>
To: cfrg@irtf.org
Content-Type: text/plain;charset=utf-8
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/RFq0nz1lf03lBoXWnK1K8vOxPpw>
Subject: [Cfrg] =?utf-8?q?Is_Diffie-Hellman_Better_Than_We_Think=3F_=28wa?= =?utf-8?q?s=3A_Ideal_Diffie-Hellman_Primes=29?=
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 20 Oct 2020 16:51:49 -0000

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