Re: [Cfrg] draft-irtf-cfrg-curves-07

Michael Hamburg <mike@shiftleft.org> Fri, 04 September 2015 00:58 UTC

Return-Path: <mike@shiftleft.org>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 89A0F1A8739 for <cfrg@ietfa.amsl.com>; Thu, 3 Sep 2015 17:58:58 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 4.255
X-Spam-Level: ****
X-Spam-Status: No, score=4.255 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=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 x8MiLYUPsR_a for <cfrg@ietfa.amsl.com>; Thu, 3 Sep 2015 17:58:57 -0700 (PDT)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net [199.116.74.168]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B72531A0018 for <cfrg@irtf.org>; Thu, 3 Sep 2015 17:58:55 -0700 (PDT)
Received: from [10.184.148.249] (unknown [209.36.6.242]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id CEF28F210A; Thu, 3 Sep 2015 17:51:00 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1441327861; bh=IOurLAr3+Td9k1MSANzuOS3dNSTkNdNQncQc+Vvi+Nk=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=O+D4T801WI6DmyaWEKzsWqUlkbeVvcLKbsqDFuL149BAK9zL4mPtxWPWTsDk6Rxfc BgMFi352uh5BnzNmFVBNk3Yz/yZI08tYlI5QcrwArdRszlO9kvD6D8Yo/24mG/s3L4 v0eLeDtyW94Zv7YhRNFDk+wdfiA6r9Z9gUXZfsKQ=
Content-Type: text/plain; charset="utf-8"
Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2104\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <CAMfhd9UW8w4dv79xRxxYLRnugjin6g2B0CD2KQJv2bVMxdNAdg@mail.gmail.com>
Date: Thu, 03 Sep 2015 17:58:55 -0700
Content-Transfer-Encoding: quoted-printable
Message-Id: <B7A5417C-78EC-455D-8374-FAB0EBB1A544@shiftleft.org>
References: <CY1PR0301MB119540063747E1C326904D59956B0@CY1PR0301MB1195.namprd03.prod.outlook.com> <CAMfhd9UW8w4dv79xRxxYLRnugjin6g2B0CD2KQJv2bVMxdNAdg@mail.gmail.com>
To: Adam Langley <agl@imperialviolet.org>
X-Mailer: Apple Mail (2.2104)
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/9Xv47t7J--HszFVUyUzgBcwDMC0>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>, Ronald Harvey <ron.harvey@freescale.com>
Subject: Re: [Cfrg] draft-irtf-cfrg-curves-07
X-BeenThere: cfrg@mail.ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.mail.ietf.org>
List-Unsubscribe: <https://mail.ietf.org/mailman/options/cfrg>, <mailto:cfrg-request@mail.ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@mail.ietf.org>
List-Help: <mailto:cfrg-request@mail.ietf.org?subject=help>
List-Subscribe: <https://mail.ietf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@mail.ietf.org?subject=subscribe>
X-List-Received-Date: Fri, 04 Sep 2015 00:58:58 -0000

> On Aug 31, 2015, at 6:10 PM, Adam Langley <agl@imperialviolet.org> wrote:
> 
> On Mon, Aug 31, 2015 at 4:39 PM, Ronald Harvey <ron.harvey@freescale.com> wrote:
>> In Section 5.1, the second input u-coordinate for each of "X25519" and
>> "X448" are, to my computations, not on the curve. These are the values
>> beginning e5210f1278 and 0fbcc2f993cd56d, respectively.  I believe
>> that this makes 'any valid implementation' unable to compute the
>> answer, as only implementations which use an x-only algorithm could
>> possibly find the expected new u.  If it was intentional, then it
>> should probably be noted that these are limited in scope.
> 
> X25519 and X448, as defined, are functions from (byte[32], byte[32])
> to byte[32] (or byte[56] for X448). As such, they are defined for all
> inputs.
> 
> Although it is the case that one only expects points on a curve to be
> generated and transmitted etc, partial implementations present at
> least a fingerprinting issue. Since all the field functions can be
> shared, and the Montgomery ladder is small, I think the assumption is
> that implementations will use it. You can certainly still reuse
> generator tables in Edwards form for calculating multiples of the base
> point without any issues.

I think this could go either way.  It’s kind of painful to ban implementations which
reject small torsion points and/or points on the twist, because that’s a natural
thing to do.  Also, AFAIK an honest party cannot complete an ECDH key exchange
with a party that sends a twist point, unless either that point is a 4-torsion point or
the honest party’s secret key is compromised.  Still, that’s a little bit of fingerprinting.

On the other hand, it is nice to lock down a specification like this completely, and
the ladder code isn’t very big.

Out of curiosity, how is this specified for RSA?  Are implementations required to
accept any (N,e)?  What if one or both are even?

>> When using other than x-only ladder for doing ECDH on these curves, is
>> there a recommended procedure for running the (twisted) Edwards point
>> multiply when starting from an 'invalid' u?  Most square root
>> procedures will fail to return an answer when y^2 is not square.
> 
> (Completely shooting from the hip: the twist of curve25519 will also
> be bi-rationally equivalent to a twisted Edwards curve. Some of the
> Edwards formulas don't depend on d and so you might be able to compute
> on that curve with the same formulae. Still, that seems more complex
> and worse than using the ladder.)

Yes, though the formulas which don’t depend on d aren’t complete.  Also,
you will need to check whether the point is on the curve or the twist to carry
out a different isomorphism in each case.

>> Regarding the Monte Carlo tests, it seems likely that a k which gets
>> turned into a u will not always be on the curve, thus making it
>> impossible also to use the tests with an Edwards (or other x-y)
>> implementation.  Perhaps both k and u should be the result of the
>> function after each iteration, ensuring a valid u as input; or k could
>> be computed from the new u, e.g.
> 
> Are the "Monte Carlo" tests the iterated ones? If so, then I think it
> might actually work out (by accident). The initial values are on the
> curve and thus so will the outputs of the function be. So I think that
> all the values will be on the curve? (Those tests were intended to
> shake out any arithmetic errors in implementations rather than
> anything else.)

This sounds right to me.

> Cheers
> 
> AGL
> 
> -- 
> Adam Langley agl@imperialviolet.org https://www.imperialviolet.org
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@mail.ietf.org
> https://mail.ietf.org/mailman/listinfo/cfrg