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

Michael D'Errico <mike-list@pobox.com> Sat, 17 October 2020 18:34 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 AFEAA3A13C6 for <cfrg@ietfa.amsl.com>; Sat, 17 Oct 2020 11:34:28 -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_H4=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=P37j6QwE; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=m9d9sIQh
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 nybnf9kW9Uvn for <cfrg@ietfa.amsl.com>; Sat, 17 Oct 2020 11:34:26 -0700 (PDT)
Received: from wout1-smtp.messagingengine.com (wout1-smtp.messagingengine.com [64.147.123.24]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 377083A13C2 for <cfrg@irtf.org>; Sat, 17 Oct 2020 11:34:25 -0700 (PDT)
Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.west.internal (Postfix) with ESMTP id C5A17ABD for <cfrg@irtf.org>; Sat, 17 Oct 2020 14:34:23 -0400 (EDT)
Received: from imap21 ([10.202.2.71]) by compute4.internal (MEProxy); Sat, 17 Oct 2020 14:34:23 -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=sG9C/ 9c+D81cQapBUu6mB89Rh/K/fswTo7f1WMXtTf8=; b=P37j6QwENjy7+uZbwrmrB i90yqJQMjJeK/UEHK2QnOBMeGepGef4NPN22064O1wjECG4q/uYYx1/aTEMQA6Y5 +ANoZbTQNrWYlpM8cFuctfRs42G1aWRTeNWSW0r6OthifUx1uXUX3LU8q7lc9caw TccIJKLX81WEEOwtvSDC8usu0RN5OE67XXupPkbjGeakH+hUiQFnsKEKxciMijU8 JuFogIvyf2fpll7qAA3ktxjkOumVAhi0Yj9iNy5aMMnGmKD7cii6yMz6ktw3NSBc 8qeNMEXPuFbkMIebsXB0OaOpM8nqRX1boEeoobm/es2VIQNNAqheIHR+adVBj03X w==
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=sG9C/9c+D81cQapBUu6mB89Rh/K/fswTo7f1WMXtT f8=; b=m9d9sIQhBu7Tr5cJ4j0nfbZ7hEjVlNwJTfTib857GoeQLenFw9np49RuZ b2/Xn/qPwZ4n4L6JYQJQgYwthbJlzkmFGqFhEGQyO90dor/V/joxXfB8LJ+VzoPV LPnIwXxFKlDl8mIBHFAwiXLFaWn3yp1E/6+D3Uw/F6FDpYLCKs8C/V1PPsLb4Rby 9NGncaoHFRKbG3txwuJGoWST2ZqFriN8WGrTjgbgGTCwlJZwv8Vr8SRsnXWxm047 ACATmUbl1LUmqcAh5BsVg2CSnIADYNKFaYaJTVOb2aR5OfxYsvy7w4UsbGnLUqN4 ZHIPQN+960eONBvtme3HWOT46sg8Q==
X-ME-Sender: <xms:LjmLX6mklrE78xIAfumagoah5md0iO6L11vbbeXUhtN3oVXJbbfNnw> <xme:LjmLXx0O1pYwnoJpx1L0scEK4bADVBugc4aNqyGKGO6aIpFZr_ZMSV1KKwq2UYlMX 5eVmD6PsLvkr0_4Dw>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedujedrieejgdduvdejucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpefofgggkfgjfhffhffvufgtgfesth hqredtreerjeenucfhrhhomhepfdfoihgthhgrvghlucffkdfgrhhrihgtohdfuceomhhi khgvqdhlihhsthesphhosghogidrtghomheqnecuggftrfgrthhtvghrnhepgeelteefie eijeeugedvkefgjeeijeffveeijeekkeeklefhieehveejtdeugeeinecuffhomhgrihhn pegrlhhpvghrthhrohhnrdgtohhmrdgrrhenucevlhhushhtvghrufhiiigvpedtnecurf grrhgrmhepmhgrihhlfhhrohhmpehmihhkvgdqlhhishhtsehpohgsohigrdgtohhm
X-ME-Proxy: <xmx:LjmLX4po7qkE5HYVBgtlL9subGhmcmU2NL3Id1gsE7gDwOFyBeEs8Q> <xmx:LjmLX-nqidyv6nuBoCpH--m7kx14Ibr4eIr2kV9c4W6uZCzdl3TGJQ> <xmx:LjmLX40f1qh3rKGXo5JpOFt-4tmyIPc_Dr3Pi8rvFDfd8Ry5pdnx2Q> <xmx:LzmLX5CbbcTezlkoflmrAi23fGTwjrwuggDNq90WCtSZKDH7WMaOjw>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id BD0DA660069; Sat, 17 Oct 2020 14:34:12 -0400 (EDT)
X-Mailer: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.3.0-489-gf39678d-fm-20201011.001-gf39678d0
Mime-Version: 1.0
Message-Id: <3c63be30-5c09-42b0-a0a4-18190ef5d548@www.fastmail.com>
In-Reply-To: <cc5b03ef-01d0-44a3-9030-1faa99107425@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>
Date: Sat, 17 Oct 2020 14:34:01 -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/23mi7C5wEJpmlXU29_q5fchuz0k>
Subject: Re: [Cfrg] =?utf-8?q?Inadequate_Definition_of_=22Safe_Prime=22_=3F_?= =?utf-8?q?=28was=3A_Weak_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: Sat, 17 Oct 2020 18:34:29 -0000

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 <mike-list@pobox.com> 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 <mike-list@pobox.com> 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 <mike-list@pobox.com>
>>>>>> Sent: Oct 10, 2020 6:01 PM
>>>>>> To: cfrg@irtf.org
>>>>>> 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