Subject: [TLS] 4492bis table 1

From: Martin Thomson <[email-masked]>
Date: Wed, 22 Jul 2015 01:36:00 -0700

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: Peter Yee <[email-masked]>
Date: Wed, 22 Jul 2015 01:56:35 -0700

The current recommendations in NIST SP 800-57 Part 1, Table 2 suggest that
256-bit symmetric strength is matched by ECC strength of 512+ bits.  All
of the ECC sizes given in Table 2 are slightly different than given below,
and most are given as ranges, not single values.

http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57_part1_rev3_gener
al.pdf  (see page 64)

			-Peter

On 7/22/15, 1:36 AM, "TLS on behalf of Martin Thomson"
<[email-masked] on behalf of [email-masked]> wrote:

>_______________________________________________
>TLS mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/tls
>

---

From: Tanja Lange <[email-masked]>
Date: Wed, 22 Jul 2015 11:44:05 +0200

>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