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

Dan Brown <danibrown@blackberry.com> Thu, 22 October 2020 02:24 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 F15033A0475 for <cfrg@ietfa.amsl.com>; Wed, 21 Oct 2020 19:24:49 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.099
X-Spam-Level:
X-Spam-Status: No, score=-2.099 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, 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 L-7r9lcgz1Ar for <cfrg@ietfa.amsl.com>; Wed, 21 Oct 2020 19:24:45 -0700 (PDT)
Received: from smtp-pg11.blackberry.com (smtp-pg11.blackberry.com [68.171.242.227]) (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 4CB523A05A6 for <cfrg@irtf.org>; Wed, 21 Oct 2020 19:24:43 -0700 (PDT)
Received: from pps.filterd (mhs401ykf.rim.net [127.0.0.1]) by mhs401ykf.rim.net (8.16.0.42/8.16.0.42) with SMTP id 09M2GeQY015944; Wed, 21 Oct 2020 22:24:40 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=blackberry.com; h=from : to : cc : subject : date : message-id : references : in-reply-to : content-type : mime-version; s=corp19; bh=Rq35XjxBpJygnW/a2tASnl8NVBrhROFXXcNzxufqagU=; b=IWU71WFXuUtHd72ATio5qsUsNg+/2MhOiAv6UcRuqTwsVHAXbZN4WLq9NtvTe7G9S9mA XCJqwU/GI7QuHXzxiz2voBUgucgu0MJPsGmN6lVu5sgfSMncwW1vk5OCBgCAJBqDpI3T kntfNr1beN5T5izybjhaPyJ1O09Wu6Q73bKOKgDpkiaUjDk6jsD3jXlGTHy0ff2ZZ96s 3W0El91TTDVe/cX0eHbT+9LgKhGqPPegHdupLmkaYJz9Mj/4p4gWhWLOQkzPJJqksF11 k1CLDQz4GNTP1f10LyCNZpZW9mSijGDC9s/YF5sJwwWklmOakYUi6VZDL0ykZS9G/dsA Tg==
Received: from xch211cnc.rim.net (xch211cnc.rim.net [10.3.27.116]) by mhs401ykf.rim.net with ESMTP id 347uv725qh-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT); Wed, 21 Oct 2020 22:24:40 -0400
Received: from XCH210YKF.rim.net (10.2.27.110) by XCH211CNC.rim.net (10.3.27.116) 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 22:24:39 -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 22:24:39 -0400
From: Dan Brown <danibrown@blackberry.com>
To: "crypto@brainhub.org" <crypto@brainhub.org>, "mike@shiftleft.org" <mike@shiftleft.org>
CC: "mike-list@pobox.com" <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/UlnO3l0Gf3imnI00W56miwQKAgABVoID//87b3w==
Date: Thu, 22 Oct 2020 02:24:39 +0000
Message-ID: <86cffbc9a65547d48a4dc4a254ab68fd@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> <F372A9D6-3B48-4967-8D3B-53B328F332D9@shiftleft.org>, <CAKUk3btW4xfRyuyuZYE9qzdB42qSCqBXJBVoLaY3EJiO_cBUOA@mail.gmail.com>
In-Reply-To: <CAKUk3btW4xfRyuyuZYE9qzdB42qSCqBXJBVoLaY3EJiO_cBUOA@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
Content-Type: multipart/alternative; boundary="_000_86cffbc9a65547d48a4dc4a254ab68fdblackberrycom_"
MIME-Version: 1.0
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.235, 18.0.737 definitions=2020-10-22_01:2020-10-20, 2020-10-22 signatures=0
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/jZ0nB2o7B3qiJhxhWefi6AcgS_M>
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: Thu, 22 Oct 2020 02:24:50 -0000

​in the case of ECC, See
https://eprint.iacr.org/2015/605
For recent work in this area.

Sent with BlackBerry Work (www.blackberry.com)
________________________________
From: Andrey Jivsov <crypto@brainhub.org>
Sent: Oct 21, 2020 9:21 PM
To: Mike Hamburg <mike@shiftleft.org>
Cc: Michael D'Errico <mike-list@pobox.com>om>; IRTF CFRG <cfrg@irtf.org>
Subject: Re: [Cfrg] Your Secret is Too Short (was: Is Diffie-Hellman Better Than We Think?)

Is the Pollar-Rho algorithm able to take advantage of the exponent size that is about the size of the security parameter?

Let's consider ECDLP for P-256 or Curve25519. Does private x for public Q=xG need to be ~256 bits? I would appreciate pointers on how does Pollard-Rho can take advantage of x~2^128 for P-256 of Curve25519.

( I know that e.g. NIST documents recommend a private key to be as you Mike wrote, e.g. 256 bits for P-256)

Thank you.

On Wed, Oct 21, 2020 at 1:14 PM Mike Hamburg <mike@shiftleft.org<mailto:mike@shiftleft.org>> wrote:
Hello again Mike,

In general, secrets for discrete log systems have to be at least
twice the security level, due to collision-based attacks such as
Pollard rho, baby-step-giant-step, etc.

This is also why P-1 must be divisible by a prime that’s at least
2*lambda bits, where lambda is the desired security level.
Otherwise the Pohlig-Hellman attack breaks the system.

Cheers,
— Mike
...

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