Tala Blog

Crypto Armageddon: NSA says current asymmetric key algorithms are susceptible to quantum computing attacks in the near future with no alternatives.

Rajesh Kanungo - Nov 7, 2017 10:19:00 AM

Crypto Armageddon: In lay-person's terms, the underpinnings of our internet security are going to get yanked out from underneath us. 
Advances in quantum computing will render today's cryptographic methods obsolete. What then?
The February 2016  Scientific American has a wonderful article on it.

The NSA started (QUIETLY) advising some US departments in August to stop using ECC-256 and to move to ECC-384 or higher.  They claimed that quantum computing attacks using Shor’s algorithm made ECC very susceptible to attacks.  They have now made the announcement public:


The blogosphere is filled with comments by many cryptographers claiming that the quantum computing attack story is just a cover for some other serious vulnerability.  Bruce Schneier also made the statement in 2013 that he no longer trusts the magical constants in Suite B.

Neal Koblitz and Alfred Menezes called it a “A Riddle Wrapped in an Engima”.  See: http://eprint.iacr.org/2015/1018.pdf.  For those who don’t know, Neal Koblitz is one of the two independent inventors of ECC.

Whatever the real reason, the NSA is telling people to start moving.  We don't know where to yet.  Will it be lattice based, multi-variate, or something else?

For those of us who work on devices that are going to be out in the field (think IoT), this is a special headache.  

In order to upgrade your algorithms, you have to upgrade both your software and your keys.

Upgrading the software and re-keying a device Over The Air using a broken algorithm is not a good idea.  Most of the energy limited devices don't even have a good random number generator.  Doing a good Diffie-Hellman key exchange will be extremely hard; the IoT device has to generate its own secret ...

One of the curious side effects of the short-term recommendation from NSA is that we should move to ECC-384 and ECC-512 is that we should also drop AES-128 and move to AES-256 at least.

Current research indicates that AES-256 is weaker than AES-128 but consumes 40% more power.  For energy limited devices (think IoT), this has a big impact.

AES-128 and AES-256 use the same block size of input data (16 bytes) but different key lengths and different number or rounds.  A round in standard crypto is the process of substitution and obfuscation.  AES uses  rounds of substitution and permutation.  Each round uses a different part of the key.  AES-128 and AES-256 both produce the same sized outputs (16 bytes).  The selection of which parts of the key to use for each round is called a key-schedule.   

The current cryptographic attacks have the following complexities:

AES-128 requires 2**128 complexity (exhaustive search) 

AES-192 requires 2**176 complexity.  This is more than that for AES-128 but still less than what we thought it would be.

AES-256 requires 2**119 complexity.  THIS IS LOWER than AES-128.  There is no reason to use AES-256 which is 40* slower.

Fundamentally, just based on crypto strength, AES-256 is WEAKER than AES-128.  The crypto is still harder to crack than currently possible but I’d have expected a 40% increase in power consumption should give me better crypto, not worse.  These are just theoretical attacks, however.

Furthermore, the paper shows that there are many ways to attack AES-256 using related key attacks with a reduced number of rounds.  The attacks seem extremely feasible.  Note that related keys are rare.

From their paper:

Here is the weakness:“The key schedules of AES-128 and AES-192 are slightly different, since they have to apply more mixing operations to the shorter key in order to produce the slightly smaller number of subkeys for the various rounds. This small difference in the key schedules plays a major role in making AES-256 more vulnerable to our attacks, in spite of its longer key and supposedly higher security. For more details about all aspects of the design of AES, we refer the reader to [6].”

The Title:

Key Recovery Attacks of Practical Complexity on AES Variants With Up To 10 Rounds Alex Biryukov1 , Orr Dunkelman2 , Nathan Keller3 , Dmitry Khovratovich1 , and Adi Shamir4 1 University of Luxembourg, Luxembourg 2 Ecole Normale Sup´erieure, ´ 45 rue d’Ulm, 75230 Paris, France. 3 Einstein Institute of Mathematics, Hebrew University. Jerusalem 91904, Israel 4 Computer Science department The Weizmann Institute Rehovot 76100, Israel Abstract.

 The Abstract:

AES is the best known and most widely used block cipher. Its three versions (AES- 128, AES-192, and AES-256) differ in their key sizes (128 bits, 192 bits and 256 bits) and in their number of rounds (10, 12, and 14, respectively). In the case of AES-128, there is no known attack which is faster than the 2**128 complexity of exhaustive search. However, AES-192 and AES-256 were recently shown to be breakable by attacks which require 2**176 and 2**119 time, respectively. While these complexities are much faster than exhaustive search, they are completely non-practical, and do not seem to pose any real threat to the security of AES-based systems. In this paper we describe several attacks which can break with practical complexity variants of AES-256 whose number of rounds are comparable to that of AES-128. One of our attacks uses only two related keys and 2**39 time to recover the complete 256-bit key of a 9-round version of AES-256 (the best previous attack on this variant required 4 related keys and 2**120 time). Another attack can break a 10 round version of AES-256 in 2**45 time, but it uses a stronger type of related subkey attack (the best previous attack on this variant required 64 related keys and 2**172 time). While neither AES-128 nor AES-256 can be directly broken by these attacks, the fact that their hybrid (which combines the smaller number of rounds from AES-128 along with the larger key size from AES-256) can be broken with such a low complexity raises serious concern about the remaining safety margin offered by the AES family of cryptosystems.

Next Post

Simple ECC implementations and a Simple Approach to Side Channel Attacks