Re: [TLS] 4492bis table 1

[Tanja Lange <[e-mail]>]

> 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