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

Dan Brown <danibrown@blackberry.com> Wed, 21 October 2020 22:15 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 B4EF83A09D8 for <cfrg@ietfa.amsl.com>; Wed, 21 Oct 2020 15:15:00 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.1
X-Spam-Level:
X-Spam-Status: No, score=-2.1 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, 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 VmBxfT7JQfhd for <cfrg@ietfa.amsl.com>; Wed, 21 Oct 2020 15:14:58 -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 A2AF63A097F for <cfrg@irtf.org>; Wed, 21 Oct 2020 15:14:57 -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 09LMEtkc045202; Wed, 21 Oct 2020 18:14:55 -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=abXHh9dsmY10qnbSi78W8OUevAFlx1kwUybY76JMBu0=; b=XAg8K9mB1wBvvQxJ7DyZboe48RFrnGz5cwrx+NG7U9FN3izey9DK1OL08WzWuGcOc2lF +CPyKteIyc9FBcY5Z0OMxR1ahHdpgBEUu12A4wO59kn3atQ4ysDtEivMowT1Z5soah7F wWO1OpCiMtQVMNZ7dzeomctdJU0fa+TECiSdTTyA99UWqWeXUuKJxKHrf2g7JqaE+fHM 9iZ66j4IBJpErfmKn1uTAwfbhHuP0rczskshzyJoLhL49uYQjK7S3V1NbR5XhLur3ez4 U5NkKJExUR5q3wlkP3QQYK+BxTE7gugWUbiiD7xBOYnsIPLVOJhgWYi7NBPhhOyH3aDb GA==
Received: from xch213ykf.rim.net (xch213ykf.rim.net [10.2.27.113]) by mhs400cnc.rim.net with ESMTP id 347wcg1vq2-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT); Wed, 21 Oct 2020 18:14:55 -0400
Received: from XCH210YKF.rim.net (10.2.27.110) by XCH213YKF.rim.net (10.2.27.113) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2044.4; Wed, 21 Oct 2020 18:14:54 -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; Wed, 21 Oct 2020 18:14:54 -0400
From: Dan Brown <danibrown@blackberry.com>
To: Michael D'Errico <mike-list@pobox.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: [Cfrg] Your Secret is Too Short (was: Is Diffie-Hellman Better Than We Think?)
Thread-Index: AQHWp79KSq/UlnO3l0Gf3imnI00W56miiyQg
Date: Wed, 21 Oct 2020 22:14:54 +0000
Message-ID: <34e8fff30c8a4316a1bd64dede8c958c@blackberry.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>
In-Reply-To: <81ebf7c4-7529-4693-85c9-edc3ece508a6@www.fastmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [100.64.197.123]
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=2.16.840.1.101.3.4.2.1; boundary="----=_NextPart_000_005E_01D6A7D6.12B43C10"
MIME-Version: 1.0
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.235, 18.0.737 definitions=2020-10-21_13:2020-10-20, 2020-10-21 signatures=0
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/ftbUI94nxs5p8YU6qVwSHlu3__I>
Subject: Re: [Cfrg] Your Secret is Too Short (was: Is Diffie-Hellman Better Than We Think?)
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 22:15:01 -0000

> From: Cfrg <cfrg-bounces@irtf.org> On Behalf Of Michael D'Errico
>
> 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.

Yes, but that's already well-known.  Doubling the number of bits avoids 
various square-root time attacks such as Shank's baby-step-giant-step and 
Pollard rho/lambda attacks (e.g. kangaroo). E.g. 256 bit keys for 128-bit 
security.

> 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.

Is your "attack" generic enough to work against composite N?  If so, then 
consider the next speculative argument.

Any given P should divide a composite number N with M trailing one bits, e.g. 
N = P(-1/P mod 2^M), right?  Finding a discrete log mod N allows finding them 
mod P, by reducing the logs mod P-1.

Of course, N is larger, so logs mod N should naturally take little longer than 
in mod P, but is it by a factor log2(M)?

Well, if the key sizes are fixed at K bits, then exhaustive search or Pollard 
rho-type attacks (respectively) should take the same number of mod P or mod N 
operations, 2^K or 2^(K/2) (respectively).  The runtime factor in modular 
arithmetic (between N vs P) is something like 1+log2(M)/log2(N), which seems 
smaller than log2(M).  So, if generic, then your attack should affect all P 
almost equally, right?

> This translates to a loss of log2(M) bits of security of the secret.
As already explained so well by Mike H., brute force attacks do not define the 
security of Diffie--Hellman, because there are better attacks.  Even your 
hypothetical sped-up exhaustive search would still be slower than Pollard rho 
variants or number field sieve (unless the keys have <=2log2(M) bits).

You do not claim to speed up Pollard rho or NFS, right?

If so, the best attacks are unchanged (AFAICT), and thus security is 
unchanged, right?

> 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.)

It gives 32 bits of security, due to Shank's baby-step giant-step algorithm, 
which takes about 2^32 operations mod P, noticeably less than 2^58 ops.


----------------------------------------------------------------------
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.