Bug#476441: Please revist this choice. AES128 vs AES256 (for gnutls)

[Robert de Bath]

On Fri, 21 Mar 2014, Daniel Kahn Gillmor wrote:

> [re: GnuTLS default ciphers]
>
> On 03/21/2014 06:15 AM, Robert de Bath wrote:
>> I notice that the distribution of RSA key sizes distributed with Debian
>> has changed.
>>
>> The 2048 bit keys are still the most common but 20% of the keys are now
>> 4096 bit with only 12% still being 1024 bit. (The 4k and 1k keys have
>> basically changed places)
>
> which keys are you talking about here?  where are these numbers from?
I ran the one line script in this "bug report" against a current Debian
testing install.

$ for i in /etc/ssl/certs/*; do certtool -i < $i; done|grep 'bits'|sort|uniq -c

The Modulus lines are:
      76                 Modulus (bits 1024):
     424                 Modulus (bits 2048):
     136                 Modulus (bits 4096):

> Here is a modern report from ENISA, which includes a survey of a bunch
> of other literature:
>
> http://www.enisa.europa.eu/activities/identity-and-trust/library/deliverables/algorithms-key-sizes-and-parameters-report
>
> in this report, AES-128 is considered roughly equivalent to RSA-3Kbit;
> to be equivalent to AES-256, an RSA key would need to be ~15Kbit.
> 4Kbit RSA is not a "large margin" more than AES-128 by these metrics.
Very interesting, there is (not really unexpectedly) a very large spread in
these results. The estimates are changing over time mostly in the same
direction; but I really would be dubious about seeing a trend here.

By the exact numbers of the most recent reports the strength of AES-128
is lower than RSA 4K but the error bands here seem to be so large that
this is by no means certain.

>> As the RSA key is usually the
>> "headline" strength indicator for the algorithms other keysizes IMO should
>> equal or exceed this value; AES-128 appears not to for 4k RSA keys.
>
> I agree that it's slightly below, but i think it's in the same ballpark
> -- if we're balancing crypto, it's roughly balanced.  If anything, i'd
> argue that the default RSA key generation size (2432-bit RSA, which is
> ~112-bit equivalent) should be raised to match AES-128, e.g. certtool
> --sec-param high --generate-privkey.
Yes, from the estimates above that may be a good idea. A 4K key would
be overkill, but 3K as in their 'Future' suggestions might be right.
What's more as this is often used once per connection (not per byte)
your power/heat budget note isn't as applicable.

> Please cite your sources explicitly.  Google does not return the same
> answers for everyone, or over time.
Sorry, on rechecking this seems to be the "drop dead" date for 3DES;
I though 3DES was already dead ... oh well.

> I agree we need to be conservative about our default algorithm choices,
> but i don't think a move to AES-256 by default is the the right place to
> push right now.
I now agree, though I still believe that AES-128 is probably 'substantially'
weaker than RSA 4K, but this is by no means certain and I have no reason to
believe that the additional strength is in any way necessary.

Thank you for reply on the current state of this 'bug' and the link to the
updated research report.


-- 
Rob.                          (Robert de Bath <robert$ @ debath.co.uk>)
                                              <http://www.debath.co.uk/>