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

Ian Goldberg <iang@uwaterloo.ca> Fri, 23 October 2020 02:29 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 61F4E3A10D7 for <cfrg@ietfa.amsl.com>; Thu, 22 Oct 2020 19:29:56 -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 9CLrhOhmSGsB for <cfrg@ietfa.amsl.com>; Thu, 22 Oct 2020 19:29:54 -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 B26AE3A10D6 for <cfrg@irtf.org>; Thu, 22 Oct 2020 19:29:54 -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 09N2TnU4004250 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO); Thu, 22 Oct 2020 22:29:52 -0400
DKIM-Filter: OpenDKIM Filter v2.11.0 minos.uwaterloo.ca 09N2TnU4004250
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=uwaterloo.ca; s=default; t=1603420192; bh=F6Ft3PeMLBsBvXBxu+RP5sEwmJ1amjMTKu7DlBC5RKI=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=Oi+gPoZBgW2YSIonSEAmTEqmI8OOnnNyWW9OLmVBSPQNDBsKeRYXR7Hzdba/Z5ZYD Z6/EzPVGTBDdT47KWq1sGyVJLkBN/Pf/LHVwxM78FfTWob64E7h0JEKYpPD7hsZAdu MieAkZD0Reys3SEYqlbVAYKU5q9w5PqyqY7q+mjM=
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 73A895FC0047; Thu, 22 Oct 2020 22:29:49 -0400 (EDT)
Received: from iang by yoink with local (Exim 4.90_1) (envelope-from <iang@uwaterloo.ca>) id 1kVmpw-0002rA-R4; Thu, 22 Oct 2020 22:29:48 -0400
Date: Thu, 22 Oct 2020 22:29:48 -0400
From: Ian Goldberg <iang@uwaterloo.ca>
To: Andrey Jivsov <crypto@brainhub.org>
Cc: IRTF CFRG <cfrg@irtf.org>
Message-ID: <20201023022948.GL16060@yoink.cs.uwaterloo.ca>
References: <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> <CAKUk3btJ9e77umCMQatSQ_G7GFKpVPuk3xRgxkT3tM0CO2Mbmg@mail.gmail.com> <CAKUk3btYb38GH3s6v+z1L40_gQmfGKX13_0c5++U8fg=qaoSAg@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <CAKUk3btYb38GH3s6v+z1L40_gQmfGKX13_0c5++U8fg=qaoSAg@mail.gmail.com>
User-Agent: Mutt/1.9.4 (2018-02-28)
X-UUID: bcbad85b-295c-4654-bfa8-56aa0570fd9a
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/tVl1rJ8Uc558cuh4lwM6YAlvdQI>
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: Fri, 23 Oct 2020 02:29:56 -0000

On Thu, Oct 22, 2020 at 07:15:33PM -0700, Andrey Jivsov wrote:
> Thanks to an anonymous reply, I see this
> https://eprint.iacr.org/2010/615.pdf, sec. 2, which is a good description
> of the enhanced algorithm that takes advantage of a short exponent (The
> Gaudry-Schost Algorithm). It's similar to Pollard-Rho algorithm, but its
> not the the same, and the link below is not an accurate description of this
> algorithm. In particular, this later algorithm is structured to contain the
> "walk" within the small set corresponding to small exponents, which doesn't
> happen with the Pollar-Rho algorithm.

Pollard rho indeed doesn't take advantage of short exponents; we were
talking about Pollard lambda (aka kangaroo), which is a different
algorithm that does.

> Looks like a private key expanded from 128 bits into 256 is needed as a
> mitigation e.g. if you must use a 128-bit secret with e.g. P-256.

And you have to be at least a little bit careful when you do the
expansion.  Trivial things like padding with a constant, etc., don't
help.
-- 
Ian Goldberg
Canada Research Chair in Privacy Enhancing Technologies
Professor, Cheriton School of Computer Science
University of Waterloo