[Cfrg] New Type of Math Object Discovered? (was: Your Secret is Too Short)

Michael D'Errico <mike-list@pobox.com> Tue, 27 October 2020 02:19 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 9113E3A1226 for <cfrg@ietfa.amsl.com>; Mon, 26 Oct 2020 19:19:29 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.101
X-Spam-Level:
X-Spam-Status: No, score=-2.101 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_H2=-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=LZZQ0sxL; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=W8VN3Dw8
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 ALtQZ-gFbdAj for <cfrg@ietfa.amsl.com>; Mon, 26 Oct 2020 19:19:26 -0700 (PDT)
Received: from wout5-smtp.messagingengine.com (wout5-smtp.messagingengine.com [64.147.123.21]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C96933A1231 for <cfrg@irtf.org>; Mon, 26 Oct 2020 19:19:26 -0700 (PDT)
Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.west.internal (Postfix) with ESMTP id ABDEC95B for <cfrg@irtf.org>; Mon, 26 Oct 2020 22:19:24 -0400 (EDT)
Received: from imap21 ([10.202.2.71]) by compute4.internal (MEProxy); Mon, 26 Oct 2020 22:19:24 -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=fEOL1 6IE2zuUnqdrz2ffE9KOkmJLJjIvBB8mgHaMqqU=; b=LZZQ0sxLMCGoD+WeFw6mq 6xbHoQw76etLM5rBFNVYieEIFfz26NsI9AetOthAwPvo9amXktV+KwZ5waSA436L vKxJi+WmVV7+dU3WwJ+Z3jzjGvUAYQNSgtqcRGo2paollY1CfENTkqtx6ewv1Dsg QOh4/x9JtHPerZfd88zmqC3fVTLGcSqbmos2PobjviglaQ8lu9PNlgvto4STJd+j B2REbxznauVIF3baOF/O3h0dsaXvucPDhHVWbz2NjUYywXnG7FEQ/3HihQXdyxwt Wj7veBLORPK8TxXU01KMv0cmGP3bsD+4obmKoKsgPqXi2oxMiRjh+qqd02MZfgS4 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=fEOL16IE2zuUnqdrz2ffE9KOkmJLJjIvBB8mgHaMq qU=; b=W8VN3Dw8Mhqdf9RGsuTQ37iMXsPwL7KUppjDsf8qAgLhsma2CvMCP/v7t QDgp8gB4oA7wOK6bw61K8uyUtOJjhjQ97O6ZvvKJx4Ep4C3HOfLlYZPkVRgrf4uB 7X4Sr8i+qDoX9s3iQlb8vTODP/yG8WSfF+jNMkm89wDMZOBLh45Juf6eoxCRLO4v Kd63o5WwzIreXJFf9AUqlbnWA5AAkpjKA4Jr0YCzPTYpS4G8ngTPrE41q4M6F9zf 2MrbM3L2nqs4aYhUlE0cyx58svIvyEb+NcAKXEqocI8/7U8VjAWr4uApdWzaRJB9 KfyTVqetmiYOQr3n9eQrl0xHVQuyA==
X-ME-Sender: <xms:q4OXX-N0HsD7MAAT650G9k91wDo6cBOG57DKd0gbRcZZHT3lmZp31g> <xme:q4OXX8_SNQ2m5UAJrHld8_o-c2XGMU4hXw3K96fTVB3SjxFjA1AzkO3_V35iPVPnZ cVDsBnamIMEnlYIXg>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedujedrkeekgdegvdcutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecunecujfgurhepofgfggfkjghffffhvffutgfgsehtqh ertderreejnecuhfhrohhmpedfofhitghhrggvlhcuffdkgfhrrhhitghofdcuoehmihhk vgdqlhhishhtsehpohgsohigrdgtohhmqeenucggtffrrghtthgvrhhnpeegleetfeeiie ejueegvdekgfejieejffevieejkeekkeelhfeiheevjedtueegieenucffohhmrghinhep rghlphgvrhhtrhhonhdrtghomhdrrghrnecuvehluhhsthgvrhfuihiivgeptdenucfrrg hrrghmpehmrghilhhfrhhomhepmhhikhgvqdhlihhsthesphhosghogidrtghomh
X-ME-Proxy: <xmx:q4OXX1QUhcthRijlLAxcMc1rIojkOAEt3XqjuCT7fCP_6v-aDpiJ5Q> <xmx:q4OXX-uLQBL_TAMnvV5V6VySGIUYHWu9lyTaTrpjax3M0OlwqkOfhw> <xmx:q4OXX2d5GMatBBHDRkhI9NKEZQwBx4hXX2P8L5X1daEuKrDupiphZA> <xmx:rIOXXwp5pRxEGDKEuzeHrf6UK9E8_PU6Ote0-Ld2qTzQa5fXQKg1wQ>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id D1565660069; Mon, 26 Oct 2020 22:19:13 -0400 (EDT)
X-Mailer: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.3.0-529-g69105b1-fm-20201021.003-g69105b13
Mime-Version: 1.0
Message-Id: <2e71d7c0-1df5-4291-8f19-98247b874ae5@www.fastmail.com>
In-Reply-To: <81ebf7c4-7529-4693-85c9-edc3ece508a6@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> <1ed370e4-8a09-4a41-bf15-22d8e61bef6e@www.fastmail.com> <81ebf7c4-7529-4693-85c9-edc3ece508a6@www.fastmail.com>
Date: Mon, 26 Oct 2020 22:16:38 -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/1LeoyYycv24z5SwJ68H0uXbQdT8>
Subject: [Cfrg] New Type of Math Object Discovered? (was: Your Secret is Too Short)
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, 27 Oct 2020 02:19:30 -0000

Hi Again,

I may have discovered a new type of math object
while trying to find a prime according to my
previous message (which may not be possible).

For lack of a better term, I call them "prefix
primes" which have this weird property:

  If P is prime, P is also a prefix prime
  if you can remove any number of trailing
  bits and add 1 to yield another prefix
  prime multiplied by a power of 2.

I didn't expect to find many examples of this
but there are lots of them!  Here's one set
where the prefix prime generator is 157:

  PP{157}: 157 313 2503 20023 160183
           1281463 164027263 335927834623
           42998762831743

The binary expansion of these numbers
illustrates the idea behind a prefix prime:

  10011101
  100111001
  100111000111
  100111000110111
  100111000110110111
  100111000110110110111
  1001110001101101101101111111
  100111000110110110110111111011111111111
  1001110001101101101101111110111111111101111111

The generator should be a prime ending with
bits 01 [the prime is congruent to 1 (mod 4)].
To find the "next" prime in the set, flip the
final one bit to zero and append as many bits
with value one until you find another prime.
Repeat the process to find the next one, etc.

I was hoping to find a prefix prime Q with
generator W, where P=2*Q+1 is also prime.  I
don't know if this is possible, but I didn't
find one in a few hours of trying.

Maybe these prefix primes are just a curiosity
and not actually useful for anything, but I
thought some of you might find them interesting.

Mike


On Wed, Oct 21, 2020, at 11:30, Michael D'Errico 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