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.