[curves] Curves for pairings

[Ray Dillinger]

On 10/04/2016 09:40 AM, Nicolai wrote:
> On Thu, Sep 29, 2016 at 12:16:40PM -0700, Ray Dillinger wrote:
>> Post-Quantum security recommendations for symmetric ciphers (the keys to
>> which are the material that are most of what public-key algorithms are
>> used to encrypt) recommend 256-bit keys and recommend NOT using AES-256
>> in particular.
> 
> Hi Ray,
> 
> Do you have a citation for this claim?  I have a counter-citation:
> 
> Section 2, "Symmetric Encryption" recommends AES-256 and Salsa20 with
> a 256-bit key:
> 
> https://pqcrypto.eu.org/docs/initial-recommendations.pdf
> 
> Though it's not an ECC issue, and maybe I misunderstood what you wrote.
> 
> Nicolai

It's known (though maybe not well-known) that AES has key
schedule problems over 128 bits.

https://en.wikipedia.org/wiki/Advanced_Encryption_Standard

mentions in passing that there's a related-key attack on AES-256
with a complexity on the order 2^99.5.  Which doesn't work on
AES-128. So, oddly, yes there is one known attack vs which
AES-256 is weaker than AES-128.  This doesn't apply to any
other attack on AES ever discovered, and all other attacks
have been pretty trivial. (they add up to maybe 2 or three
bits now?  Maybe not even that much?)

Here's the first of two IACR papers about it.

http://eprint.iacr.org/2009/317

The other one (which identifies a vanishingly small class of
keys for which the attack is only on the order 2^45) is in
the CRYPTO 2009 printed journal.

Being able to use this "attack" almost requires you to be able to
choose your opponent's keys, which makes it NEARLY useless.

The odds are deeply against anyone being able to actually use a
related-key attack in practice without being able to use a
"chosen-key attack" ("chosen key attack" is a joke, like DOUBLE
encrypting with ROT13 for more security).  Especially since the
work factor is still on the 2^99 level, well beyond current
capabilities.

But - in my opinion - if you're going to use 196 or 256 bit keys,
there should be *NO* attack that has less than 2^~194 or 2^~254
complexity.  Attacks always get better not worse, and I'm not
sure whether some extremely clever person with quantum computers
will be able to leverage such a "nearly useless" attack in a
surprising way.

So I don't really care if pqcrypto.eu.org recommends it. I don't.
Especially in a post-quantum-computer universe, if that comes
to pass.

All that said, there is absolutely nothing wrong with AES-128
as far as anybody's been able to tell, and as far as we can
tell the larger versions deliver fully in every OTHER way. I
do still recommend AES-128 if you want symmetric ciphers with
128-bit keys.


				Bear

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 801 bytes
Desc: OpenPGP digital signature
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20161004/d6965a89/attachment.sig>