Re: [TLS] 4492bis table 1

Tanja Lange <tanja@hyperelliptic.org> Wed, 22 July 2015 09:44 UTC

Return-Path: <tanja@hyperelliptic.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 78A781A1A98 for <tls@ietfa.amsl.com>; Wed, 22 Jul 2015 02:44:21 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 2.094
X-Spam-Level: **
X-Spam-Status: No, score=2.094 tagged_above=-999 required=5 tests=[BAYES_20=-0.001, HELO_EQ_NL=0.55, HOST_EQ_NL=1.545] 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 NdhpZZ9lTtyk for <tls@ietfa.amsl.com>; Wed, 22 Jul 2015 02:44:20 -0700 (PDT)
Received: from calvin.win.tue.nl (calvin.win.tue.nl [131.155.70.11]) by ietfa.amsl.com (Postfix) with SMTP id 8099C1A1A58 for <tls@ietf.org>; Wed, 22 Jul 2015 02:44:19 -0700 (PDT)
Received: (qmail 26385 invoked from network); 22 Jul 2015 09:44:39 -0000
Received: from unknown (HELO hyperelliptic.org) (131.155.71.33) by calvin.win.tue.nl with SMTP; 22 Jul 2015 09:44:39 -0000
Received: (qmail 14992 invoked by uid 1000); 22 Jul 2015 09:44:05 -0000
Date: Wed, 22 Jul 2015 11:44:05 +0200
From: Tanja Lange <tanja@hyperelliptic.org>
To: Martin Thomson <martin.thomson@gmail.com>
Message-ID: <20150722094405.GD12152@cph.win.tue.nl>
References: <CABkgnnVq7xFUMwMpc=n4d_cWCgAbcJOpG=OfiCxPmLChFLj_nQ@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <CABkgnnVq7xFUMwMpc=n4d_cWCgAbcJOpG=OfiCxPmLChFLj_nQ@mail.gmail.com>
User-Agent: Mutt/1.5.11
Archived-At: <http://mailarchive.ietf.org/arch/msg/tls/pnw7ONVpEubfo-OfS7FNAGj14CE>
Cc: "tls@ietf.org" <tls@ietf.org>
Subject: Re: [TLS] 4492bis table 1
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: <https://mailarchive.ietf.org/arch/browse/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: Wed, 22 Jul 2015 09:44:21 -0000

> Is table 1 correct?
> 
>                      +-----------+-----+------------+
>                      | Symmetric | ECC | DH/DSA/RSA |
>                      +-----------+-----+------------+
>                      |     80    | 163 |    1024    |
>                      |    112    | 233 |    2048    |
>                      |    128    | 283 |    3072    |
>                      |    192    | 409 |    7680    |
>                      |    256    | 571 |   15360    |
>                      +-----------+-----+------------+
> 
> Aren't we dropping 571?  Can we use values that match up.
> 
> Or, drop the table.
> 
>From all research I know the ECC numbers are larger than they should
be.

Breaking ECC (good curve etc.) with size ~2^n takes 2^{n/2} point
additions. Breaking a cipher with m bits takes about 2^m cipher 
evaluations; usually some parts can be omitted. The difference for
cryptographic sizes between one EC operation and a symmetric operation
is somewhere around 2^3 to 2^5 depending on size.

When attacking multiple symmetric keys at once security reduces faster
than for ECC keys (k keys give factor k speedup for symmetric while
giving a factor sqrt(k) speedup for ECC).

In summary symmetric m corresponds to ECC with somewhat _less than_ 2m.

The numbers listed in that table match up with NIST's Koblitz
curves; the sizes were chosen because for those Koblitz curves of
nearly prime order exist -- this is a rare property for Koblitz
curves -- and not because that bit size is needed for other 
reasons.

There are several proposals for matching key sizes, see
	http://www.keylength.com/
for an overview. 

I would go with

                      +-----------+-------+------------+
                      | Symmetric | ECC   | DH/DSA/RSA |
                      +-----------+-------+------------+
                      |     80    | >=158 |    1024    |
                      |    112    | >=221 |    2048    |
                      |    128    | >=252 |    3072    |
                      |    192    | >=379 |    7680    |
                      |    256    | >=506 |   15360    |
                      +-----------+--------+------------+

where the number in the ECC column refers to the bitlength of
the prime order of the subgroup. This does not take into 
account that symmetric and DH are more weakened by multi-target
attacks.

I wouldn't haggle over a bit or two, but the previous table was
certainly not reflective of ECC strength given all we know.

All the best
	Tanja