Re: [TLS] On Curve25519 and other possibilities (e.g. ietf256p, ietf384p, ietf521p,

Andrey Jivsov <crypto@brainhub.org> Sat, 28 June 2014 20:06 UTC

Return-Path: <crypto@brainhub.org>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 249451A0417 for <tls@ietfa.amsl.com>; Sat, 28 Jun 2014 13:06:23 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.399
X-Spam-Level:
X-Spam-Status: No, score=0.399 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, MANGLED_OFF=2.3, 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 77MgRC5_E4dM for <tls@ietfa.amsl.com>; Sat, 28 Jun 2014 13:06:21 -0700 (PDT)
Received: from qmta07.emeryville.ca.mail.comcast.net (qmta07.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:43:76:96:30:64]) by ietfa.amsl.com (Postfix) with ESMTP id BED221A0031 for <tls@ietf.org>; Sat, 28 Jun 2014 13:06:21 -0700 (PDT)
Received: from omta13.emeryville.ca.mail.comcast.net ([76.96.30.52]) by qmta07.emeryville.ca.mail.comcast.net with comcast id Kvth1o00817UAYkA7w6M8M; Sat, 28 Jun 2014 20:06:21 +0000
Received: from [192.168.1.145] ([71.202.164.227]) by omta13.emeryville.ca.mail.comcast.net with comcast id Kw6L1o00C4uhcbK8Zw6LNd; Sat, 28 Jun 2014 20:06:21 +0000
Message-ID: <53AF203C.10902@brainhub.org>
Date: Sat, 28 Jun 2014 13:06:20 -0700
From: Andrey Jivsov <crypto@brainhub.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
MIME-Version: 1.0
To: tls@ietf.org
References: <53AEF428.3010302@cs.bris.ac.uk>
In-Reply-To: <53AEF428.3010302@cs.bris.ac.uk>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20140121; t=1403985981; bh=K7mzsQF/xGr20xM9eLOWtEnDZbLnf73OhtA1g2KVXMg=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=fv2QJi5lNUs0xnft60RR2xNL5xC5DSCn7mGtX0LyCVzQlbpu1AFkWuynPiiIXqZDo 40pB4n4Q2kXx43ar/JjiyAaHu/+ORZfzy5mSCA05Mm/YS1QkOePABU9vo2CLHGTPb/ +0uM6dCcleEqVBekF0iV6GS3+dr1fhwHV3CeBIUBEUrXUIN//TROEf2jtj0UjvlhSG r7CNJoZR8Z5H5QtbpPgCPRO7ReBIjjmBoEa8RqN9l2x6K6BIzSAPUT4YOnDnL83ANL XJ9DSbOQAz3Be4mLZqg+Sk5dz1BvmII2WdpKmvB1ZPZgbJnS4XyZSJfiKf2znahymi 24MK6RErePvBg==
Archived-At: http://mailarchive.ietf.org/arch/msg/tls/G9xVNQqmsSDOH4FU-GLa0RaO7K8
Subject: Re: [TLS] On Curve25519 and other possibilities (e.g. ietf256p, ietf384p, ietf521p,
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/tls/>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Sat, 28 Jun 2014 20:06:23 -0000

On 06/28/2014 09:58 AM, Nigel Smart wrote:
> Hi
>
>> One way to attempt to unify the diverse world of ECC curves is to focus
>> on the underlying field, as opposed the curve itself. Consider Fp
>> operations with p=2^255-19 or p=2^256-189. In other words, for
>> n={256,384,512}, chose the closest C: p=2^n-C is a prime and make this p
>> "MUST". People who demand random primes will have to play along and
>> accept less "randomness" in their curves.
>
> Alas there could be some issues with primes close to powers of two.
> See our recent side channel attacks on EC-DSA with the Eurovision
> titles on ePrint "Just a Little Bit" etc. Such a p forces the
> group order to also be close to a power of two (by Hasse's Theorem).
>
> Whilst these papers show there are problems with the NIST choices
> in this respect, the above choices of p would be even worse.
>
> So unifying in this respect would be a bad idea IMHO.
>
> Nigel

The paper https://eprint.iacr.org/2014/434.pdf describes a technique to 
recover the bits of a secret intermediate value used in the ECDSA 
algorithm. These bits are in the high half of the large integer. This 
improved method works when EC order is close to 2^n, which is the case 
with F(p): p=2^n-C due to the relationship between the two per Hasse 
theorem.

A random p will have high half of its bits random, and this will deny 
such an enhanced side-channel attack. A generalized pseudo-mersenne 
prime should help as well.

The exploited side channel in the paper is provided by the ECDSA 
algorithm, through the ECC field scalar multiplication. In other words, 
we are not talking about a side channel in an implementation of an F(p) 
being exploited.

IMO fixing the p will help with high-quality implementations of F(p).

What this p is, is the question to answer based on pros and cons. p that 
allows faster operations is inevitably less secure because the 
Pollard-rho on the ECC is faster with such a p. A safest p cannot save 
an ECC implementation from side-channel bugs.