AES vs Brute Force assisted with Moore's law

AES-256 has a few known attacks that are more efficient than an exhaustive search (brute force) due to weakness in AES-256 key schedule algorithm. As a result, Bruce Schneier, the Michael Jordan of cryptographers, has recommended that new applications use AES-128 instead of AES-256.

In practicality, an encryption algorithm's useful life is a lot shorter than its theoretical life due to the development of new mathematical attacks and computational speed doubling roughly every other year. In fact, DES was the standard symmetric encryption algorithm in the 90's before Moore's law made DES obsolete in 1998 when a $250,000 computer cracked a DES cipher in 56 hours.

I wanted to understand how theoretical advances in computational power based on Moore's law would impact the time needed to crack AES-128. Surprisingly, I had some difficulty locating literature on the subject.

I found an EE Times article which computed the amount of time needed to crack AES-128 using the world's fastest supercomputer. In short, their conclusion was that it would take 1.02E18 (about 1 billion billion) years to crack AES-128 if the only option was to use exhaustive search using the world's fastest supercomputer. They computed this number(1.02E18) by dividing the possible number of keys by combinations checks per year. Assumptions used were that the fastest supercomputer currently is 10.51 X 10^15 flops, and it takes 1000 flops to check each key.

Equation 1: Shows it will take 1.02 X 10^18 years to break AES-128 if we use the world's fastest computer today to attempt an exhaustive search of all keys  

The number 31536000 in equation 1 is the number of seconds in a year. Note, upgrading the supercomputer to account for advances in technology over time was not accounted for in their calculations.

Figure 1: It takes One Billion Billion(1.02x10^15) years to crack AES-128?


What I did was modify some of the formulas above used by the EE Times article to account for Moore's law.

Here are some of the basic number assumptions I started out with:

1. World's fastest Supercomputer in 2014 - 33.86 PFlops (33E10^15 flops)
2. Moore's Law Speed - Processing power doubles every 2 years 
3. Numbers of flops needed to test each key combination -1000

Let's leave aside the discussion of Moore's law sustainability for the remainder of this post. I'll leave that discussion to professional physicists. Additionally, if you disagree with any of my assumptions, change them in the spreadsheet I used to do my calculations and try your own assumptions!

Here are the results for AES-128:

Year	Years needed to crack
2025	5000 Trillion Years
2050	850 Billion years
2075	148 Million years
2100	25,618 years
2114	200 years
2129	1 year

Table 1: Shows how long an exhaustive search will take to crack AES-128 if we only used the fastest supercomputer of the day (and not upgrade it each year).

The second row in Table 1 should be read as the following, if we used the fastest supercomputer that would be available in the year 2050 to exhaustive search for keys, it would still take 850 billion years to crack AES-128. The last row of Table 1 shows that we would need to time travel to the year 2129 to use their fastest supercomputer available so that we could crack AES-128 via exhaustive search in about one year. Although the year 2129 is still 115 years away, 115 years is still significantly smaller than 1 billion billion years which is commonly quoted as the amount of time needed to crack AES-128. With that said, 115 years is practically good enough for nearly all applications.

In addition to the assumptions listed above, I've made some other hidden assumptions which are probably untrue. Here are a few:

1. Amount of money spent to buy the world's fastest supercomputer will be the same each year (accounting for inflation). This is likely to underestimate the computational power of the future.
2. The world's fastest computer today is actually listed correctly on Wikipedia. I suspect the NSA or another government body has a faster supercomputer or crypto cracker elsewhere.
3. Moore's law will be sustainable for centuries to come.
4. ASICS are not being used (really bad assumption, just ask Bitcoin miners).
5. I've ignored all discussion and math of Quantum computers and recent/expected advances in distributed computers (Botnets). 

So what does the chart look like for AES-256:

Year	Years needed to crack
2050	2.93E50 years
2100	8.72E42 years
2200	7.74E27
2300	6.8 Trillion years
2350	204,942 years
2385	1 year

Table 2: Shows how long an exhaustive search will take to crack AES-256 if we only used the fastest supercomputer of the day(and not upgrade it each year).

In reading Table 2, this means that by the year 2385, AES-256 will become computationally insecure for exhaustive search. Given that Bruce Schneier has recommended that new applications use AES-128, this probably means that a professional cryptographer like Bruce suspects that AES-256 keys can be retrieved faster than an exhaustive search of AES-128.

Conclusion:
Under various assumptions, AES-128 will be computationally insecure around the year 2129 against brute force attacks. This is really not a problem today for nearly all applications given the distance we need to cover by the year 2129. The majority of computing power gains needed to break AES will occur only a few years prior to the year of break. To put things in perspective, the fastest supercomputer today has roughly 3x10^-18 of the computing power it will have by the year 2129.

With that said, if some of the assumptions prove to be totally false, the years needed to crack could potentially reduce significantly.

Fair Disclosure:

In fair disclosure, I am not a mathematician or a professional cryptographer. If you find something wrong with my math in this article, please let me know in the comments below! And don't forget to check out the spreadsheet if you want to test out your own assumptions.

---

Shikhir Singh currently works at BlackBerry where he works as a mobile developer. He has previously worked at Lockheed Martin, and Sun Microsystems. You can follow Shikhir on twitter at @shikhirsingh