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

Andrey Jivsov <crypto@brainhub.org> Thu, 22 October 2020 01:20 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 937E73A0EF2 for <cfrg@ietfa.amsl.com>; Wed, 21 Oct 2020 18:20:50 -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 l_CQTlIO4bqh for <cfrg@ietfa.amsl.com>; Wed, 21 Oct 2020 18:20:48 -0700 (PDT)
Received: from mail-lf1-f47.google.com (mail-lf1-f47.google.com [209.85.167.47]) (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 5586D3A0EF1 for <cfrg@irtf.org>; Wed, 21 Oct 2020 18:20:47 -0700 (PDT)
Received: by mail-lf1-f47.google.com with SMTP id c141so109701lfg.5 for <cfrg@irtf.org>; Wed, 21 Oct 2020 18:20:47 -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=e0X5W/VjBoywqqEzCLM0kDqO587tCrf11CtYmMfKeUE=; b=AcKADBkDKU8z+KhcXl08FllMpllHGCtFLO8k0ZqO+Vw+FpCfspi6EonM+VV3k0UAVK jHvXCHOmx239vu+ebd6jneKHecrZRwjws+vY2U+q6OHrM8Er+xCPy+I+90FLUnG8VNbU 9+Yw0Fh07kpZuWmuQpldNoBpZNfZMv5p0GovX7SjikOXPMdUa5kLzneqkNIhi8Rfwf/x lAXw/ezVIm45eryEdv5GQgwc3rdRM55W1abr44IHOrbBKfQn15kk21FR2HmqYdeaqIqZ mnyOEu6YM3eHBZLI208yTeCA5rMkI+xykudx/h0walPZNiotuRE4TaStHfdQpcU79+JZ txsQ==
X-Gm-Message-State: AOAM532uTWwmqJNUSrHGOiROe/iF/ShlqUerbtkdm1vLJA1IZ6IHgOpn EviI1joh5DI6lt25chdSOg7oREyg2bWtyOoIPaGcVA==
X-Google-Smtp-Source: ABdhPJxTOOYje8XUBkTcwOzphWquqtVWtkrgrPy5IMf6fA3YeyAAvZUmMWuHBY7liTsbYlErDRBzGmUDh54wdb+UM2I=
X-Received: by 2002:a05:6512:3490:: with SMTP id v16mr6088lfr.61.1603329645977; Wed, 21 Oct 2020 18:20:45 -0700 (PDT)
MIME-Version: 1.0
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>
In-Reply-To: <F372A9D6-3B48-4967-8D3B-53B328F332D9@shiftleft.org>
From: Andrey Jivsov <crypto@brainhub.org>
Date: Wed, 21 Oct 2020 18:20:33 -0700
Message-ID: <CAKUk3btW4xfRyuyuZYE9qzdB42qSCqBXJBVoLaY3EJiO_cBUOA@mail.gmail.com>
To: Mike Hamburg <mike@shiftleft.org>
Cc: "Michael D'Errico" <mike-list@pobox.com>, IRTF CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="00000000000001b48505b23846d0"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/YeqU9Is_V06tQuZazroV_Ks6I5k>
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 01:20:51 -0000

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