### Re: [Cfrg] Weak Diffie-Hellman Primes

Dan Brown <danibrown@blackberry.com> Mon, 12 October 2020 18:22 UTC

Return-Path: <danibrown@blackberry.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 6948F3A15FE
for <cfrg@ietfa.amsl.com>; Mon, 12 Oct 2020 11:22:46 -0700 (PDT)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -3.298

X-Spam-Level:

X-Spam-Status: No, score=-3.298 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-1.2, DKIM_SIGNED=0.1,
DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1,
HTML_MESSAGE=0.001, SPF_HELO_NONE=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=blackberry.com

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 cq9kmz5g5Q35 for <cfrg@ietfa.amsl.com>;
Mon, 12 Oct 2020 11:22:44 -0700 (PDT)

Received: from smtp-pc10.blackberry.com (smtp-pc10.blackberry.com
[74.82.81.42])
(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id D19913A15FB
for <cfrg@irtf.org>; Mon, 12 Oct 2020 11:22:42 -0700 (PDT)

Received: from pps.filterd (mhs400cnc.rim.net [127.0.0.1])
by mhs400cnc.rim.net (8.16.0.42/8.16.0.42) with SMTP id 09CIMf6d135973;
Mon, 12 Oct 2020 14:22:41 -0400

DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=blackberry.com;
h=from : to :
subject : date : message-id : references : in-reply-to : content-type :
mime-version; s=corp19; bh=Vjfm4Ads9T4wRjsunBNpNG2eiMtmF6OncDMxzipUo58=;
b=QolzGtacI8uVeNkBAkqLzEV41CRayh93ySQ/Pw44xgE2mtCLAbRUZaQP/W8HIBtD3LRB
vW+UsJjxCqDlvDlVBaCQ3r1Qi1/F3doUj+sXofE9h6EyUzjn07V3uQvf5Suvl/D5CQbt
0DlwLiiTWPPRLdfaZUxxct4ZAkRH6sj2T4PtG48K/Z+nc+qYuGIdFMx8DAErtlw9rOSb
bNrgl/PX0+Cuu4n/UK+4LOU+gTpToS89/USsXAEUygQdK1VVTR1ErooIzAHU1r8vkU1E
+b64ghvif3kw3f1MwWQ8EXr9EA0CWoMtNulJuEiW9WZObaJlONg0sbc+EeVdebBRD4Rk SA==

Received: from xch214cnc.rim.net (xch214cnc.rim.net [10.3.27.119])
by mhs400cnc.rim.net with ESMTP id 3439qg4cgx-1
(version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT);
Mon, 12 Oct 2020 14:22:40 -0400

Received: from XCH210YKF.rim.net (10.2.27.110) by XCH214CNC.rim.net
(10.3.27.119) with Microsoft SMTP Server (version=TLS1_2,
cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2044.4; Mon, 12 Oct
2020 14:22:40 -0400

Received: from XCH210YKF.rim.net ([fe80::ac8d:3541:704c:478a]) by
XCH210YKF.rim.net ([fe80::ac8d:3541:704c:478a%5]) with mapi id
15.01.2044.006; Mon, 12 Oct 2020 14:22:40 -0400

From: Dan Brown <danibrown@blackberry.com>

To: "mike-list@pobox.com" <mike-list@pobox.com>, "cfrg@irtf.org"
<cfrg@irtf.org>

Thread-Topic: [Cfrg] Weak Diffie-Hellman Primes

Thread-Index: AQHWn1D34pYtvany5EGirh9LlmK08amUSrQp

Date: Mon, 12 Oct 2020 18:22:40 +0000

Message-ID: <da998077e86749298c5e158c322c06fa@blackberry.com>

References: <0a24076e-3227-405c-84d4-26d82b5ff783@www.fastmail.com>

In-Reply-To: <0a24076e-3227-405c-84d4-26d82b5ff783@www.fastmail.com>

Accept-Language: en-US

Content-Language: en-US

X-MS-Has-Attach:

X-MS-TNEF-Correlator:

Content-Type: multipart/alternative;
boundary="_000_da998077e86749298c5e158c322c06fablackberrycom_"

MIME-Version: 1.0

X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.235, 18.0.687
definitions=2020-10-12_15:2020-10-12,
2020-10-12 signatures=0

Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/KdtgWhMQ-83qbmp8ceFLvwNVUYg>

Subject: Re: [Cfrg] 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: Mon, 12 Oct 2020 18:22:46 -0000

Hi Mike and CFRG list, Not sure where to draw line between false alarms and well-intentioned concerns, since these can intersect, so I tried to understand Mike's DLP attack strategy ... Somehow he aims to find bits, the 2^j, in the quotient of 2^X over P. But there are nearly X/2 such bits, so finding them all would cost as much as exhaustive search. (C.f. Polar rho method, taking sqrt(X) steps.) Likely misunderstood the proposed method, but am at least trying. Sent with BlackBerry Work (www.blackberry.com) ________________________________ 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://urldefense.proofpoint.com/v2/url?u=https-3A__www.irtf.org_mailman_listinfo_cfrg&d=DwICAg&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q-lhj0sp26wE&r=qkpbVDRj7zlSRVql-UonsW647lYqnsrbXizKI6MgkEw&m=tZVPiwvPHNhVOmq07mAv6dmVDQlZzwq_f8amSXXto_E&s=NyJBFGx6gbKbkDE1W9v4dZEZXff-kNCuzGyswktikEk&e= ---------------------------------------------------------------------- This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

- [Cfrg] Weak Diffie-Hellman Primes Michael D'Errico
- Re: [Cfrg] Weak Diffie-Hellman Primes Dan Brown
- Re: [Cfrg] Weak Diffie-Hellman Primes Michael D'Errico
- Re: [Cfrg] Weak Diffie-Hellman Primes Michael D'Errico
- Re: [Cfrg] Weak Diffie-Hellman Primes Anna Johnston
- Re: [Cfrg] Weak Diffie-Hellman Primes Michael D'Errico
- Re: [Cfrg] Weak Diffie-Hellman Primes Mike Hamburg
- [Cfrg] Inadequate Definition of "Safe Prime" ? (w… Michael D'Errico
- Re: [Cfrg] Inadequate Definition of "Safe Prime" … Michael D'Errico
- [Cfrg] Ideal Diffie-Hellman Primes (was: Inadequa… Michael D'Errico
- [Cfrg] Is Diffie-Hellman Better Than We Think? (w… Michael D'Errico
- Re: [Cfrg] Is Diffie-Hellman Better Than We Think… Christopher Patton
- [Cfrg] Your Secret is Too Short (was: Is Diffie-H… Michael D'Errico
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Mike Hamburg
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Dan Brown
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Andrey Jivsov
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Ian Goldberg
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Dan Brown
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Andrey Jivsov
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Andrey Jivsov
- Re: [Cfrg] Your Secret is Too Short (was: Is Diff… Ian Goldberg
- [Cfrg] New Type of Math Object Discovered? (was: … Michael D'Errico