### [Cfrg] Review of draft-ladd-safecurves

Ilari Liusvaara <ilari.liusvaara@elisanet.fi> Thu, 16 January 2014 12:30 UTC

Return-Path: <ilari.liusvaara@elisanet.fi>

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 C796D1AE32E for <cfrg@ietfa.amsl.com>;
Thu, 16 Jan 2014 04:30:56 -0800 (PST)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -1.901

X-Spam-Level:

X-Spam-Status: No,
score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9,
RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=ham

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 3I7mre2IFp1r for
<cfrg@ietfa.amsl.com>; Thu, 16 Jan 2014 04:30:54 -0800 (PST)

Received: from emh01.mail.saunalahti.fi (emh01.mail.saunalahti.fi
[62.142.5.107]) by ietfa.amsl.com (Postfix) with ESMTP id 9656E1AE32B for
<cfrg@irtf.org>; Thu, 16 Jan 2014 04:30:53 -0800 (PST)

Received: from LK-Perkele-VII (a88-112-44-140.elisa-laajakaista.fi
[88.112.44.140]) by emh01.mail.saunalahti.fi (Postfix) with ESMTP id
7AFC9900BD; Thu, 16 Jan 2014 14:30:40 +0200 (EET)

Date: Thu, 16 Jan 2014 14:30:40 +0200

From: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>

To: cfrg@irtf.org

Message-ID: <20140116123040.GA30096@LK-Perkele-VII>

MIME-Version: 1.0

Content-Type: text/plain; charset=utf-8

Content-Disposition: inline

User-Agent: Mutt/1.5.21 (2010-09-15)

Sender: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>

Subject: [Cfrg] Review of draft-ladd-safecurves

X-BeenThere: cfrg@irtf.org

X-Mailman-Version: 2.1.15

Precedence: list

List-Id: Crypto Forum Research Group <cfrg.irtf.org>

List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>,
<mailto:cfrg-request@irtf.org?subject=unsubscribe>

List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>

List-Post: <mailto:cfrg@irtf.org>

List-Help: <mailto:cfrg-request@irtf.org?subject=help>

List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>,
<mailto:cfrg-request@irtf.org?subject=subscribe>

X-List-Received-Date: Thu, 16 Jan 2014 12:30:57 -0000

Version: 743d3597a045fc6dd08b412d148d3f1a1e4cfd55 Date: Wed Jan 15 17:26:58 2014 -0800 > Let p be a prime number. There is a unique field with p elements. > Its elements can be represented as the set of integers {0, 1, ... p}. Should that be {0, 1, ... p-1} ? > To compute the additive inverse of a, one can compute (p-1)*a, and again > take the remainder. Won't p-a followed by remainder work? > The remainder of this standard defines abelian groups in which for > a fixed basepoint (denoted p), distinguishing between (g, [a]p, [b]p, [ab]p) > with a, b picked uniformly at random from nonnegative integers less then > the order, and (g, [a]g, [b]g, [c]g), is hard without spending prohibitive > amounts of time. The time required is the square root of the order of g. What's c? I presume uniform random nonnegative integer less that the order? > On Montgomery curves, curves of the form y^2=x^3+a*x^2+x, the typical > technique is to work over the Kummer variety instead, i.e. drop y > coordinates for use in Diffie-Hellman. Let (X_1,Z_1), (X_2,Z_2), > (X_3,Z_3) be coordinates such that X_1/Z_1, X_2/Z_2, X_3/Z_3 are the x > coordinates of P, Q, and P+Q respectively. Then the equations Is it P+Q or P-Q? Also, reading the markup, the formulas below seem to use X1, Z1, etc... when the above text talks of X_1, Z_1, etc... > gives X_4/Z_4 as the x coordinate of [2]Q, and X_5/Z_5 as the x > coordinate of P+[2]Q where a24=(a+2)/4. If in calculating [n](X, Z), > Z of the result is zero, this indicates that [n](X,Z) is the point > at infinity, and so the result has x-coordinate 0. P+[2]Q... The text below has P_1+P_0 appear in it? How those fit together? > 1: Intilize P_0=[1,0], and P_1=[x_P,1] > 2: Iterate over the bits of n from most to least significant > 2.1: If the bit is 0, let P_1=P_1+P_0, P_0=2P_0 > 2.2: If the bit is 1, let P_0=P_1+P_0, P_1=2P_1 > 3: Write [x_f, z_f]=P_0 > 4: If z_f is 0, return 0. Otherwise return x_f/z_f. This section looked messed up in -03 HTML version. Can't easily tell if you have done anything to it that would fix the formatting in output. Also, if one computes x_f/z_f as x_f*z_f^(p-2) mod p, then if z_f=0, that produces 0 anyway. > On (twisted) Edwards curves, curves of the form a*x^2+y^2=1+d*x^2y^2, > a complete addition formula, which works for doubling as well, is > given by representing points in projective coordinates. The formula > for adding (X_1, Y_1, Z_1) to (X_2, Y_2, Z_2) is then Then the formulas below have the X1 vs. X_1 thing. Also, should doubling formula be given? Yes, straightforward substitution works, but produces suboptimal algorithm without some manipulation. > The Montgomery ladder algorithm from above will work with this addition > and doubling, taking care to represent points as triples, and check that > points lie on the curve going into and out of the routine. To convert In what situations that check for points going out can fail. I know two: - Buggy implementation - Fault attack. Others? > Each curve is given by an equation and a basepoint, together with the > order of the point and the cofactor. One thing that could be useful would be listing low-order points (since none of these curves has more than 8). Checking for those is needed in some protocols. I think explicit comparisions are much faster than multiplying 2 or 3 times and checking the result. > Let (x,y) be a point on E(GF_p), where E is an Edwards curve or > twisted Edwards curve. Let l=floor[log(p)/log(256)]+1. A point is > represented as l bytes, l representing in big-endian radix 256 the > minimal representative of [y] modulo p, and the top bit of the top > byte set to equal the low bit of x. Because we have always ensured > that there is extra room in l than is strictly required to represent > y, we have room for the top bit to be set. So the intention is that the top byte is always 0x00 or 0x80 for all curves here, not just E448-Goldilocks (which is the only Edwards curve here with bitlength multiple of 8)? > Point encoding is clear in both cases. To decode a point on an Edwards > curve with parameter d, one takes the y value and computes the > valuex^2, then takes the square root. Methods for taking the square > root are sadly highly prime-dependent, but [COHEN] contains a large > number of options. Perhaps add a note that if one relies on point decompression to check the validity of input point, one has to check that the square root actually exists. Many square root algorithms produce "interesting" results if one tries to blindly take square roots that don't exist. And using those "interesting" results might be much worse for security than just enabling twist attack... -Ilari

- [Cfrg] Review of draft-ladd-safecurves Ilari Liusvaara