Re: [Cfrg] revised requirements for new curves

Andrey Jivsov <crypto@brainhub.org> Mon, 15 September 2014 05:36 UTC

Return-Path: <crypto@brainhub.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 E0E881A065F for <cfrg@ietfa.amsl.com>; Sun, 14 Sep 2014 22:36:05 -0700 (PDT)
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, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, 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 XmPIkbsLweLC for <cfrg@ietfa.amsl.com>; Sun, 14 Sep 2014 22:36:04 -0700 (PDT)
Received: from resqmta-ch2-10v.sys.comcast.net (resqmta-ch2-10v.sys.comcast.net [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 ietfa.amsl.com (Postfix) with ESMTPS id 5ABDE1A065A for <cfrg@irtf.org>; Sun, 14 Sep 2014 22:36:04 -0700 (PDT)
Received: from omta20.westchester.pa.mail.comcast.net ([76.96.62.71]) by resqmta-ch2-10v.sys.comcast.net with comcast id rHa91o0011YDfWL01Hc3vJ; Mon, 15 Sep 2014 05:36:03 +0000
Received: from [192.168.1.2] ([71.202.164.227]) by omta20.westchester.pa.mail.comcast.net with comcast id rHc21o00T4uhcbK3gHc2Ff; Mon, 15 Sep 2014 05:36:03 +0000
Message-ID: <54167AC2.1030307@brainhub.org>
Date: Sun, 14 Sep 2014 22:36:02 -0700
From: Andrey Jivsov <crypto@brainhub.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.7.0
MIME-Version: 1.0
To: cfrg@irtf.org
References: <CAMfhd9UaJtcaRurEOtN289ribT7ZH6OUB55or+T1NN6U8jv9Rw@mail.gmail.com> <CAMm+LwhATMG9Pco-Bt1n-rgr3vEmgFKbpbvA0f9V9fW9t36UVw@mail.gmail.com>
In-Reply-To: <CAMm+LwhATMG9Pco-Bt1n-rgr3vEmgFKbpbvA0f9V9fW9t36UVw@mail.gmail.com>
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=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==
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/oN5hw2vKhnWqWGSBgv_5G-NdI6k
Subject: Re: [Cfrg] revised requirements for new curves
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: 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 <agl@imperialviolet.org> 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
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>