[Cfrg] Comparing ECC curves

Phillip Hallam-Baker <phill@hallambaker.com> Wed, 23 July 2014 22:28 UTC

Return-Path: <hallam@gmail.com>
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 8D5981A0322 for <cfrg@ietfa.amsl.com>; Wed, 23 Jul 2014 15:28:06 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.278
X-Spam-Level:
X-Spam-Status: No, score=-1.278 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FM_FORGED_GMAIL=0.622, FREEMAIL_FROM=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 8QbqROfmufDX for <cfrg@ietfa.amsl.com>; Wed, 23 Jul 2014 15:28:05 -0700 (PDT)
Received: from mail-we0-x22d.google.com (mail-we0-x22d.google.com [IPv6:2a00:1450:400c:c03::22d]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 6DD5E1B297C for <Cfrg@irtf.org>; Wed, 23 Jul 2014 15:28:05 -0700 (PDT)
Received: by mail-we0-f173.google.com with SMTP id q58so1867960wes.18 for <Cfrg@irtf.org>; Wed, 23 Jul 2014 15:28:04 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:date:message-id:subject:from:to:content-type; bh=Cvj3L6793UwN6ws/GYKeI0lAPXmonA/WhiS/ZdBSRPg=; b=Jn2c2X+SK1ovzKXqGRm9etFW77awb/PvT5EY/9wUZEO5rQPDeYhsQTC4TcA1sc0Bs/ 95jKW4JYIU0nyug8UF5tj6nR7SJPaaKHJZn2+6pb6bpDqWUw5HQRRIJFxQdN00ZHPSV3 FEXeO8RDEevivDHeLddD+j+Q00nCv1BwmkladK/uVqgcC8CzUp+KTxm0mGpWD+llooBL igdlte0XjwDX0/OPgXrCPi/p+RcWUbsr424EoBM0/LMCBB8x4Fdg3t3y59cbutMoM0NX WwYYzVUf6E7spHw5u8cdSw2JL0/5PM+1pgDhbSXhmyDz4G/qjzEyOOvG4Kca2gipMKf9 PH5w==
MIME-Version: 1.0
X-Received: by 10.194.71.12 with SMTP id q12mr6167571wju.5.1406154483881; Wed, 23 Jul 2014 15:28:03 -0700 (PDT)
Sender: hallam@gmail.com
Received: by 10.194.123.167 with HTTP; Wed, 23 Jul 2014 15:28:03 -0700 (PDT)
Date: Wed, 23 Jul 2014 18:28:03 -0400
X-Google-Sender-Auth: fiF3MBvn-kGp8J7_GLP4QDRY3KE
Message-ID: <CAMm+Lwj9EPJ9v92xrkM1ceAbkWYe22fpOOBObUbUJjkk8X0dng@mail.gmail.com>
From: Phillip Hallam-Baker <phill@hallambaker.com>
To: Cfrg@irtf.org
Content-Type: text/plain; charset=UTF-8
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/ZoJ2dzZ0IvkySjFxd_1q7n57u4M
Subject: [Cfrg] Comparing ECC 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: Wed, 23 Jul 2014 22:28:06 -0000

Thanks to all the presenters, some thoughts on comparing like with like:

1) How do we compare algorithm A taking X cycles and offering a work
factor 2^Y with algorithm B taking 2X cycles and offering a work
factor 2^(Y+Z)?

My answer here is that I am interested in the yield ratio i.e.
[attacker work factor] / [defender effort]. so having the defender do
twice as much work to get an improvement of one bit is not a win.

We can define an exclusion rule: B, is definitely not going to be
interesting as an alternative to A if Z >= 1. Doubling the work factor
is not a win if I have to do twice as much work.

But that still leaves open the question of how much defender effort it
is worth to increase the difficulty by a factor of two.


2) Should the security levels be maximums or minimums?

Looking through the Microsoft presentation I see that they have chosen
work factors of 128, 192 and 256 bits. This is reasonable of course
but maybe not the best way to compare like with like. Because the real
limitations here are the machine resources which nowadays come in
units of 64 bits.

What I am really interested in is how much security you can provide
for an n*64 bits wide datapath. I do not want to have to mess about
with a129 bits to achieve 128 bits security. If someone can do the
math significantly faster then I'll take 127 bits. But I certainly
don't want to go below 120 bits unless the advantages were phenomenal.


3) Do we need to consider 2^192 work factor?

I can't see any case where I am interested in a work factor of 2^192.
Either I am willing to make some concession to performance or I want
it gold plated and 2^256. I would quite like to see the 2^192 work
factor nuked.

The only reason for going above 2^128 is that I don't trust the
algorithm. Its not about increasing the work factor by 2^64, its about
increasing the safety margin in the case of a cryptanalytic attack. I
have seen attacks that reduce the work factor to the root of the
intended one (i.e. 2^n becomes 2^(n/2)). I can't think of a better one
that has been discovered offhand (most are not that good of course).
So 2^256 makes me feel like I am sufficiently protected against
algorithm compromise while 2^192 is kinda marginal.