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

Ian Goldberg <iang@uwaterloo.ca> Thu, 22 October 2020 02:15 UTC

Return-Path: <iang@uwaterloo.ca>
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 80DBB3A00E5 for <cfrg@ietfa.amsl.com>; Wed, 21 Oct 2020 19:15:51 -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, 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 (1024-bit key) header.d=uwaterloo.ca
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 3DAKUrQL9yg8 for <cfrg@ietfa.amsl.com>; Wed, 21 Oct 2020 19:15:49 -0700 (PDT)
Received: from minos.uwaterloo.ca (minos.uwaterloo.ca [129.97.128.78]) (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 4DC0E3A00E3 for <cfrg@irtf.org>; Wed, 21 Oct 2020 19:15:48 -0700 (PDT)
Received: from mail.paip.net (whisk.cs.uwaterloo.ca [198.96.155.11]) (authenticated bits=0) by minos.uwaterloo.ca (8.14.4/8.14.4) with ESMTP id 09M2FiD4025843 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO); Wed, 21 Oct 2020 22:15:46 -0400
DKIM-Filter: OpenDKIM Filter v2.11.0 minos.uwaterloo.ca 09M2FiD4025843
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=uwaterloo.ca; s=default; t=1603332946; bh=pln2gGESuf//ZsHD1RQfCaZR1Fjn0GsvF0MyQ5EOcR4=; h=Date:From:To:Subject:References:In-Reply-To:From; b=4PlYe0VxO/LoB8R1+Z5/JUePQVLoFkrjuMlw0q78qSS22nS7zANkHEfmnXq4CYkk2 rLCs16Hj5MyKfzMXphyocL2nZwRqDwpfVzEiUN65Cx8oH9qa84NAdZy0HK0hmztqpv AgJA1ZqGOdRj8yDXe00NUm6ua97EMSoSy6vi5g40=
Received: from yoink (brandeis.paip.net [66.38.236.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.paip.net (Postfix) with ESMTPSA id DC0C55FC0047; Wed, 21 Oct 2020 22:15:43 -0400 (EDT)
Received: from iang by yoink with local (Exim 4.90_1) (envelope-from <iang@uwaterloo.ca>) id 1kVQ8l-0002fs-Aj; Wed, 21 Oct 2020 22:15:43 -0400
Date: Wed, 21 Oct 2020 22:15:43 -0400
From: Ian Goldberg <iang@uwaterloo.ca>
To: cfrg@irtf.org
Message-ID: <20201022021543.GR16060@yoink.cs.uwaterloo.ca>
References: <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>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <CAKUk3btW4xfRyuyuZYE9qzdB42qSCqBXJBVoLaY3EJiO_cBUOA@mail.gmail.com>
User-Agent: Mutt/1.9.4 (2018-02-28)
X-UUID: 8b69aa87-59aa-41a5-99f0-86eeaa01a38e
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/ZeckqAEtjit11qqympNF1xt5X_c>
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:15:52 -0000

On Wed, Oct 21, 2020 at 06:20:33PM -0700, Andrey Jivsov wrote:
> 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.

If you choose x ~ 2^128 and Q=xG, Pollard's kangaroo (aka Pollard's
lambda) algorithm can break that in ~2^64 time.

https://en.wikipedia.org/wiki/Pollard%27s_kangaroo_algorithm

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

As well it should.  Is there a standard that suggests choosing a 128-bit x?

-- 
Ian Goldberg
Canada Research Chair in Privacy Enhancing Technologies
Professor, Cheriton School of Computer Science
University of Waterloo