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

Michael D'Errico <mike-list@pobox.com> Wed, 21 October 2020 15:31 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 4736B3A0C45 for <cfrg@ietfa.amsl.com>; Wed, 21 Oct 2020 08:31:02 -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=mp2H7mGr; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=pqUnDsBb
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 89TQtzX5Ck-X for <cfrg@ietfa.amsl.com>; Wed, 21 Oct 2020 08:30:59 -0700 (PDT)
Received: from out2-smtp.messagingengine.com (out2-smtp.messagingengine.com [66.111.4.26]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B757C3A0BBE for <cfrg@irtf.org>; Wed, 21 Oct 2020 08:30:59 -0700 (PDT)
Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id CD9BA5C0264 for <cfrg@irtf.org>; Wed, 21 Oct 2020 11:30:58 -0400 (EDT)
Received: from imap21 ([10.202.2.71]) by compute4.internal (MEProxy); Wed, 21 Oct 2020 11:30:58 -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=tnO1G SxsRBjabnSqoPafYKu84RwvbekPwGlfwXZKueQ=; b=mp2H7mGrzO/+3eYk1NVae 5hMzJbUGiMZAjgTsjq5c1XBYjLPoXOKSLwpp6ERYYm1sptClQrOLDv0W936C5KR5 v6qEoLbH2/UrulaJwA9sWl7oJkBOpH/gbYxXqME+vhiUPMGFW1DXVchRA6uZrkzl uUGsU8IXcl5Ung+Tt2N9KpzFjWRfkELRNj2mmKlfkrCfc1nz3WksLkH98MdKsrUy q3aJ2jb4cG5d1T6WZixRE22Nz5VIBlC7uJ7mtzDYpNYxaJTTSkb9FaGOKsZBoxre nQr5K4fhbgbVGOeQLnCKAFe/97B3MYz7VeJD+Tl8um1sRlAL2Odmmj6os8oDymgM 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=tnO1GSxsRBjabnSqoPafYKu84RwvbekPwGlfwXZKu eQ=; b=pqUnDsBbVZodjYuVG/RIQjUOKQ0Zu5Hm2OStcoElpv/zGk1YjSx0Rbm2G bmtwoBxazKswJNnIsKRO6+6D/PmsNYyjpYGy+iLSUs0GrHLOXgvy4LAAvc1HPwKb 9UHdm7ebkienJVvx8PUGno14xpROZ0+YZEZxTXh/ou21boJN2HZCtIpr2Soxjfoq oSpEJXD+d59U5KjLboT6JRtp8RTFivR8kpwQCDBDzkzXdOa+lps0MpCSlSjbuhSx fufsRqJBAwYMjBZ4DJUg5J2QNsGnBqwiPOUCb9+oCqqU0OrgPOwp65xSEqj7C4rp 3esafuV1XGMiMLzVLtDrSDesxwWzg==
X-ME-Sender: <xms:MlSQX0rF4YjZSSmV7fmyftgZCBrT4X_728i7fUKpAf1wlDK5OhKirA> <xme:MlSQX6qYj3Orw1gN6XZaTDs8au5JC9ljgb5u1VQ6svYfD0bYdFaVO9aJ5ONC-8ZbE 0ZlNXfLcBT8EaLkzg>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedujedrjeehgdeltdcutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecunecujfgurhepofgfggfkjghffffhvffutgfgsehtqh ertderreejnecuhfhrohhmpedfofhitghhrggvlhcuffdkgfhrrhhitghofdcuoehmihhk vgdqlhhishhtsehpohgsohigrdgtohhmqeenucggtffrrghtthgvrhhnpeegleetfeeiie ejueegvdekgfejieejffevieejkeekkeelhfeiheevjedtueegieenucffohhmrghinhep rghlphgvrhhtrhhonhdrtghomhdrrghrnecuvehluhhsthgvrhfuihiivgeptdenucfrrg hrrghmpehmrghilhhfrhhomhepmhhikhgvqdhlihhsthesphhosghogidrtghomh
X-ME-Proxy: <xmx:MlSQX5MUZVeGClVptjHVAEjCCCPZaPPZ47KffUSkKlaalU8h8_f7Fw> <xmx:MlSQX75A7by8qTsURYL1eoiMbtoouossuBEzWeJUAfeZQ9JThw1zIg> <xmx:MlSQXz4Jm0hMAV0fkSYU8pj9lhzQx9xkXGEjBPG-sc2xwxkjxKqigw> <xmx:MlSQX1HPpeTrKTuneV92tOcJ1d54oHiwSv3ctniWW0JRV_bKlQWb-Q>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id 8E4DF66006F; Wed, 21 Oct 2020 11:30:47 -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: <81ebf7c4-7529-4693-85c9-edc3ece508a6@www.fastmail.com>
In-Reply-To: <1ed370e4-8a09-4a41-bf15-22d8e61bef6e@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>
Date: Wed, 21 Oct 2020 11:30: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/rCLEPDYWstc_AJ1sEC5Bq8FCgs8>
Subject: [Cfrg] =?utf-8?q?Your_Secret_is_Too_Short_=28was=3A_Is_Diffie-He?= =?utf-8?q?llman_Better_Than_We_Think=3F=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: Wed, 21 Oct 2020 15:31:02 -0000

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