Re: [Cfrg] revised requirements for new curves

Andrey Jivsov <> Mon, 15 September 2014 05:36 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id E0E881A065F for <>; Sun, 14 Sep 2014 22:36:05 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id XmPIkbsLweLC for <>; Sun, 14 Sep 2014 22:36:04 -0700 (PDT)
Received: from ( [IPv6:2001:558:fe21:29:69:252:207:42]) (using TLSv1 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 5ABDE1A065A for <>; Sun, 14 Sep 2014 22:36:04 -0700 (PDT)
Received: from ([]) by with comcast id rHa91o0011YDfWL01Hc3vJ; Mon, 15 Sep 2014 05:36:03 +0000
Received: from [] ([]) by with comcast id rHc21o00T4uhcbK3gHc2Ff; Mon, 15 Sep 2014 05:36:03 +0000
Message-ID: <>
Date: Sun, 14 Sep 2014 22:36:02 -0700
From: Andrey Jivsov <>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.7.0
MIME-Version: 1.0
References: <> <>
In-Reply-To: <>
Content-Type: text/plain; charset="ISO-8859-1"; format="flowed"
Content-Transfer-Encoding: 7bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=q20140121; t=1410759363; bh=QS0ayain3Qb6EnLZVVK0Me92CVmn49QhuvPlJe+JpKI=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=VGJA+eCas7g/Gjlt8MTP5ICiLqLE8HdCT6J1xej3m1wIwS+6HVMbBJ36O5rr8C4B7 Zbr7zzgJObiJjnnHt8RJfLA8Azh6EeuwXnw5LX9ajr8Yq3C8qTG9DCdYilT/J90uPr oyMaEQ0r7NM/goJw5/RfCkPUt30GYsqm8g6vFox7n2yUAr54qKKgjHaXNpEf6Hra3Z rFc8TpQE5jeHwx6iITrQE2tpvhWBiiz0xB/aQQCbGqu4jDUKGykF3/xwuSXEtC9Wvm 0Ejy8lXOLS5ZQ2n+UJSpZTYgUPt3OftG0J290U/9b/SsKScQeF6iABQYhBaKZU9VLl ASPqn7OmGAaiQ==
Subject: Re: [Cfrg] revised requirements for new curves
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 15 Sep 2014 05:36:06 -0000

On 09/14/2014 07:22 AM, Phillip Hallam-Baker wrote:
> On Tue, Sep 9, 2014 at 4:23 PM, Adam Langley <> wrote:
>> Although flexibility should be eliminated where possible, we believe
>> that forgoing sensible optimisations because of a fear that someone
>> might know a magic attack on a subset of curves and might be guiding
>> the selection them that would be a mistake. We are not looking for a
>> replacement for P-256 because we seriously worry that the NSA
>> backdoored it.
> Well maybe not. BUT one of the main advantages of moving to new curves
> is that the deployment of ECC has been gradual and incremental and has
> taken an enormous amount of time. And one of the main points to a flag
> day is not just burning the old ones, it is getting everyone to buy
> and hang the new.
>> We're looking for a replacement because we think that
>> we can get something much faster and simpler.
> Case in point here, can anyone who has these facts at their disposal
> tell us what sort of leverage random curves are believed to provide
> over primes close to a power of 2.
> The issue here is cryptographic leverage. I am prepared to do more
> work to increase the work factor for the attacker. But should I pick
> (say) a fast curve with 256 bits or a slower curve with 192 bits?
> If the two curves give exactly the same work factor or take exactly as
> long with different security, then the comparison is easy. But things
> rarely turn out so simple, chances are that the fast but bigger curve
> turns out to be a little bit slower and a bit more secure than the
> smaller one... oops.
> The basis for comparison is a little tricky...
> If I am doing RSA 2048 then I an doing four times the work of RSA 1028

As can be seen with timing of openssl speed rsa1024/rsa2048/2048, the 
factor is ~7.5 (e.g. in op.sec: 5940.2/791.2/111.8)

 > But if I am doing a symmetric cipher then 256 bits is more likely to
 > take about double 128

This is exactly 40% more work with AES in bulk encryption (10 rounds 
v.s. 14, not counting 1 XOR as a round).

> Oh and RSA 2048 does not give anywhere close to the square of the work
> factor of RSA1024 (i.e. double the bits). In fact that is one of the
> main reasons we have to look beyond RSA.

RSA 2048 and DH 2048 are on the margin of standard security at 110 bits, 
as considered by NIST. There is a measurable penalty for stronger 
security if one were to do the upgrade with RSA/DH/DSA.

1024 EDH in TLS is common today and still the default in OpenSSL.

> But if we plot the points on graphs of defender effort vs attacker
> work factor and look at the curves we can probably see quite easily
> what we are buying with the different approaches.
> _______________________________________________
> Cfrg mailing list