[curves] Curves for pairings

Ray Dillinger bear at sonic.net
Thu Sep 29 12:16:40 PDT 2016

On 09/29/2016 02:38 AM, Michael Scott wrote:

> Here is another take on a possible response to the new estimates..
> There is an asteroid called "Quantum Computing" heading straight for
> "Planet Crypto". We know more or less exactly what damage it will do. And
> from what I have been hearing it is expected to hit around the year 2030.
> Now if you look at papers estimating key sizes that we would need, often
> they were based on extrapolations of current technologies beyond 2050. Well
> that's all pretty pointless now. So why beat ourselves up between now and
> the asteroid strike? As of now 80 bits of (AES equivalent) security has
> still not been broken, and may still be fine in 2030!

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.

If you're not interested in symmetric-key cryptography that's all you
need to know.  If you want to know some general facts about post-quantum
symmetric crypto, and a few very specific facts about AES with keys
longer than 128 bits, then keep reading.

Always keep in mind that for both public-key and symmetric algorithms,
the crypto code in an application is almost never the weakest security
link unless the algorithm is proprietary or original to the program's
authors.  To make the crypto strong enough has become very easy. To make
breaking it the easiest way to break security remains very hard.

That said: In the case of quantum computers, symmetric-key cryptography
is generally, regardless of algorithm, expected to "lose" about half its
key length for purposes of calculating security due to Grover's Algorithm.

80 bits of symmetric-cipher security in a post-quantum world is
therefore expected to be equal in work factor to 40 bits of security in
the pre-quantum world.  IE, terribly easy to break.

Current recommendations for long term security in symmetric ciphers use
128 bit keys.  But that's long term in the absence of Quantum Computers.
 Those who consider Quantum Computers to be likely are extending that to
256 bit keys.

However, AES has been shown to have poor key schedules for keys larger
than 128 bits, and is not recommended at larger key sizes.  AES-256 for
example is theoretically less secure than AES-128 if a related-key
attack can be used.

While there are no realistically conceivable scenarios where the
related-key attack could be practically applied, attacks only get
better, never worse, and Quantum Computers are more likely to speed that
process up than slow it down.  So why use something where a known attack
exists when things not subject to any equivalent attack are available?

Finally according to the Snowden Files there is an attack on AES using
something called the "Kendall Tau Rank Correlation Coefficient" which
the NSA considered likely to be possible but had not yet successfully
developed at the time of the Snowden leaks.  I don't know anything about
it, and fear the unknown.

Summary:  Don't build systems with AES keys larger than 128 bits.  For
equivalent post-quantum security overengineering, (and this really is
overengineering) build software using some other symmetric cipher with a
256 bit key.

"The More You Know...."


PS. "... cryptography is like a nice solid security door.  It looks
nice, it makes owners feel secure, and it discourages stupid burglars.
But responsible builders, and smart burglars, should notice when it's
installed in a wood framed building with big glass windows."

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

More information about the Curves mailing list