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

Andrey Jivsov <crypto@brainhub.org> Thu, 22 October 2020 22:13 UTC

Return-Path: <andrey@brainhub.org>
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 3CBA73A0AC7 for <cfrg@ietfa.amsl.com>; Thu, 22 Oct 2020 15:13:01 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
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 x-p3NtHIfNsX for <cfrg@ietfa.amsl.com>; Thu, 22 Oct 2020 15:12:58 -0700 (PDT)
Received: from mail-lj1-f172.google.com (mail-lj1-f172.google.com [209.85.208.172]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 7E7F93A09E7 for <cfrg@irtf.org>; Thu, 22 Oct 2020 15:12:52 -0700 (PDT)
Received: by mail-lj1-f172.google.com with SMTP id a5so3600770ljj.11 for <cfrg@irtf.org>; Thu, 22 Oct 2020 15:12:52 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=3MbKsHDLYsztMMAhLriudy4mwZOiaJAZir+D+VaP0NU=; b=BOHkQ7F1CS6KWewzwLUS6KUSc6peFhiyfP8oF3B+Ed6YGR06nACydP8Ft6+3QYIRKe DK348ssuPrVpSwLeUJN3tZXcsS/PTE3kZerPT1l8hh7FfCDVDSG4EjR7LDpo1CdzflBt Mcbrnxy1dVHO2wnRbzbEy0jEbkVuaC4ydJESeJhKxV7yIDnpqakYW56XXYwH11ZnaN7w TKhjkPkZY+9XAjhLNKhcff3RwX98zY/xt6TEecZEhsni+SuGx5IDiOmt3sZh6lf6sdQg d39wXZ9Z7P5S9OVdoBvSiX/Ke4HqOAtvILGSQtNAR9Bjf4iUn3oS9/RnyAONAgU64keW Wfxw==
X-Gm-Message-State: AOAM5308cVQm1YlAkl9j+WXDp4WJEwN5fSej8SXm9XrCvEaXogwj4fwV g8vU7Vy6v2170komX29VBAlxK45xe63shILUjql5XtrHUx/AqtMmps4=
X-Google-Smtp-Source: ABdhPJxE3gkyopNrS8Yb+7BF+BxaaPC7OtGGcqvlwnBYRhGGtgGMqu0LX8S/tCrb0ZjYIcAMhvo9yb8ebRzI+d7Rshc=
X-Received: by 2002:a2e:9948:: with SMTP id r8mr1888305ljj.175.1603404771016; Thu, 22 Oct 2020 15:12:51 -0700 (PDT)
MIME-Version: 1.0
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> <20201022021543.GR16060@yoink.cs.uwaterloo.ca>
In-Reply-To: <20201022021543.GR16060@yoink.cs.uwaterloo.ca>
From: Andrey Jivsov <crypto@brainhub.org>
Date: Thu, 22 Oct 2020 15:12:39 -0700
Message-ID: <CAKUk3btJ9e77umCMQatSQ_G7GFKpVPuk3xRgxkT3tM0CO2Mbmg@mail.gmail.com>
To: Ian Goldberg <iang@uwaterloo.ca>
Cc: IRTF CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="000000000000ced91505b249c34f"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/nNNq3Kj1wi5kxNUnzU1f-W1Pa6I>
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 22:13:02 -0000

Hm, this was my original question. When the generator is in a large
subgroup/group, I don't see how the algorithm on Wikipedia page benefits
from the limited range of the secret exponent.

I can further enhance my question by saying that instead of using x in
[1,sqrt(group_order)] the secrets are derived with a KDF(128-bit key, x),
where KDF's output is 256 bits (mod group order), so that they are
unpredictable values. However, I don't even see why this is needed.

It seems that the page is written for a small 128-bit subgroup (for a
256-bit curve).

On Wed, Oct 21, 2020 at 7:15 PM Ian Goldberg <iang@uwaterloo.ca> wrote:

> 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
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>