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

Michael D'Errico <mike-list@pobox.com> Fri, 16 October 2020 19:55 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 316573A0AA4 for <cfrg@ietfa.amsl.com>; Fri, 16 Oct 2020 12:55:20 -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=U83UvgY+; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=iJGWT0fd
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 GeNJG8c8L2Zm for <cfrg@ietfa.amsl.com>; Fri, 16 Oct 2020 12:55:18 -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 291203A0AA3 for <cfrg@irtf.org>; Fri, 16 Oct 2020 12:55:18 -0700 (PDT)
Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.west.internal (Postfix) with ESMTP id 37D7AF83 for <cfrg@irtf.org>; Fri, 16 Oct 2020 15:55:17 -0400 (EDT)
Received: from imap21 ([10.202.2.71]) by compute4.internal (MEProxy); Fri, 16 Oct 2020 15:55:17 -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=gGfv1 lEioBGJx3sO0nWju4wwYuF52OZJLwv/O6r7+bU=; b=U83UvgY+ioCSivKXC0n8t gNPL9OqHBz+BpyNH5zCEHjnAbveNfTeBRo5ftTTfb6aa7xp1wx+fiTAtUaATKwru MUpK7tMvS0ZBvoIxxjacDPGz81TPg0h6fo4gs4ungaT5fIRZroRCu54cD7v/vN0D iew6YYGhTNg2WDGt4OlVvNQv5Tf8giQBdsv+tzR4S5pFoC9XUZBHndIrtYBc9xyG HPkMCrRMqsYzlXavB67299fnhvujP4utIAwjWjSchXd7cXnoBYzymD9zLALLBXWJ c6dzU2qRcVWWzdcTCR1a3IqKI8e8f9pkhXRQCSPW3fdtvk1MFLKJ2XhYCAYQfYcW g==
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=gGfv1lEioBGJx3sO0nWju4wwYuF52OZJLwv/O6r7+ bU=; b=iJGWT0fdzhevx4syeDkRfoYhXzvIb7BPv5Hzr8cV3aFkK9SB2BYs5ImZZ QHLLGZC+ZhLs+K0wTTBCul9+AwoPljFI+lwVlajRwYxM4iRgI/yqRfgHdeHKy1NC TFyRrNykFxavfNBICv/nHrVxRyKrGSauwTNMtkL5O6I6nMkmiFlaQMKjzPY+14sz nQUiPZ8bhjmAcBhkjoo7xb4WghO4Cj0QpYUOUvTF92smQvVu/H9px3IIiuc7yLxa L79nHNqw/ZCVsnHLG8cJoXCmYoQDT0Mths/GOBjFtX7FB8GYylUqIJKFBIX42CCk cGVje2p/4Y/b1MQQLh11RA9TCXzbg==
X-ME-Sender: <xms:pPqJX-LtCQh8gnGQ-Pj0OBqa-BwNj77Obt36M9OGCPm8rTxVWsq40g> <xme:pPqJX2JxQejker_g0xeXczrtzUGS5BGnGFvc3FvKh2Ug4Uyj_jKkOlcD-ZCuiyyMz SfaRR371XCdE04t1A>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedujedrieehgddugeefucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpefofgggkfgjfhffhffvufgtgfesth hqredtreerjeenucfhrhhomhepfdfoihgthhgrvghlucffkdfgrhhrihgtohdfuceomhhi khgvqdhlihhsthesphhosghogidrtghomheqnecuggftrfgrthhtvghrnhepfeefiedule fhteeifeehieffudehteektdetteejkeeukedutdfgveehgeevffetnecuffhomhgrihhn pehirhhtfhdrohhrghenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrih hlfhhrohhmpehmihhkvgdqlhhishhtsehpohgsohigrdgtohhm
X-ME-Proxy: <xmx:pPqJX-uqcyk_Bv9wxCawc7eFzGwYwvxZRXy9mPIJ7N5XGeBvPh3flg> <xmx:pPqJXzZUVjHezoGD8px3-Zt69g27IlmgJEwp5QGqxWj4tMKXl_tOgQ> <xmx:pPqJX1YjdkMDfV9kKHb8HleK7GU7q5fwz_CheLKBswbTp8lrxUc7zA> <xmx:pPqJX-lyAYDyvQFg1u4wLYyZhbxEqCyqLdpXBAZ-EwIbiUMOeNOp9w>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id 255C7660069; Fri, 16 Oct 2020 15:55:07 -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: <cc5b03ef-01d0-44a3-9030-1faa99107425@www.fastmail.com>
In-Reply-To: <770E332F-B404-45C8-898B-BAD69A9B75A0@shiftleft.org>
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>
Date: Fri, 16 Oct 2020 15:53:36 -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/PSKR9CeDiQkanBfL6zKYxceEtGU>
Subject: [Cfrg] Inadequate Definition of "Safe Prime" ? (was: Weak Diffie-Hellman Primes)
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: Fri, 16 Oct 2020 19:55:20 -0000

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,
> > 
> > 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 <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
> >>> 
> >>> _______________________________________________
> >>> Cfrg mailing list
> >>> Cfrg@irtf.org
> >>> https://www.irtf.org/mailman/listinfo/cfrg
> >> 
> >> 
> > 
> > _______________________________________________
> > Cfrg mailing list
> > Cfrg@irtf.org
> > https://www.irtf.org/mailman/listinfo/cfrg
> 
>