How long will it take to Brute Force AES?

 How long will it take to brute force a given encrypted text if encrypted with 256 bit AES?

As of April 3, 2013 Using modern cryptanalysis to break AES-256 bit encryption by guessing the key used on a given block of data using the Biclique Cryptanalysis method as developed by Andrey, Bogdanov, Dmitry Khovratovich, and Christian Rechberge [i] will require a minimum of 2^254 operations for a data-space of  2^40 Bits (128 Gigabytes). 

Processor	Operations Per Second	Number of Operations	Time in Years  (@ 100% Success)
Xeon E5-4650	1.4969 x 10 ^ 13	2^254	6.12818 x 10 ^ 55
I7 3970 XM	1.2969 x 10 ^13	2^254	7.07323 x 10 ^ 55
AMD 7970 (GPGPU)	3.584 x 10 ^ 15	2^254	2.55951 x 10 ^ 53
Titan (Oak Ridge National Labs) Current Top 500 King.	1.759 x 10 ^ 18	2^254	5.2150 x 10 ^ 50

Again, this is a perfect scenario; given a sample size of  2^40 bits ; 128 Gigabytes encrypted with the same 128 bit symmetric key. 

The world’s fastest computer would take 5.215 x 10 ^ 50 (That's 50 zeros) years at 100% accuracy; the research stipulates that the best hit / miss scenario is 63% accuracy so we may infer that the best case would actually be far longer than that. Bogdanov stated the following in an interview:

"To put this into perspective: on a trillion machines, that each could test a billion keys per second, it would take more than two billion years to recover an AES-128  bit key"[ii]

If we take Moore’s Law into account assuming that Titan’s number of operations will double every twelve months.

Number of Years = Number of Operations Required / Maximum Operations Available * Efficiency

A good method used to ball park would be to assume that every year the "Maximum Operations Available" for a given computing system will double.

Multibillion Dollar Super computers will be capable of brute forcing using AES using Bogdanov et. al. method using a single operation in 1.6457091 x 10 ^58 years; assuming 100% efficiency.

That’s 1,645,709,100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 Years.

 

Current scientific estimates state that our sun will become a red giant; expand due to lack of Hydrogen for fusion and consume all inner planetary bodies including the earth in 7.59 billion years. Current estimates put the sun at 4.5 billion years of age which means around 3.09 Billion (3,090,000,000,000) years are left before this event occurs give or take a millienia. 

This analysis only covers the most recently published method to brute force AES; Side Channel Analysis, and other such methods that use attacks on the implementation of the algorithm such as improper key storage, memory management or the failure of security controls on a given system are excluded from discussions here and this is a purely theoretical discussion; we are not considering the platform or implementation of AES on a computer. 

These estimates are based on the idea that the current environment remains unchanged: That is of course unless someone builds a quantum computer capable of executing Shor’s, Grover’s or similar quantum factorization and search algorithms (greater than 1000 entangled q-bits) or if there is some kind of rapid change in Moore’s Law; such as inexpensive atomic replication and manufacture of complex systems such as the Drexler revolution, or the Kurtzwiel's singularity occurs where systems become self aware and more intelligent than humanity and become better at designing chips than we are this timeline is likely to remain somewhat constant.

IBM has already demonstrated the implementation of Shor’s algorithm with 7-qbits[iv], in 2001. Although the key requirement for Quantum systems is the sheer number of Q-bits required; the evolution of these systems is far more complex than the traditional computing systems as developed with transistors on silicon using VLSI and their associated developmental challenges. 

 The estimates for number of q-bits vary but somewhere between 512 and 1000 would be needed to break AES or RSA in a timely way; ie; before the sun explodes. And their development faces both real world theoretical problems in physics and practical engineering difficulties such as environmental isolation that are associated with said physics problems. Good examples of quantum machines include atom smashers built under mountains for CERN between Switzerland and France; they are under mountains for a reason; there's little to no background radiation there. 

As stated by Schneier[iii]  attacks against cryptosystems always get better, not worse; D-Wave systems is making massive inroads (more like major highways) into discrete optimization problems using quantum computing and their board has announced that soon they will have more computing power than that which is available in this universe according to Rose’s Law; limited by their computing architecture to said optimization problems; various scholars and industry pundits do not fear this event but openly admit the risk it maintains to their cryptosystems which include RSA and AES; the only issue bieng when will a company or organization produce a system like D-wave's only using Shor's or Grover's algorithms;

 

In a quantum machine environmental background radiation is similar to electrical or RF based noise in a traditional electrical machine; Ever notice how your personal radio may hum next to a fluorescent light? The only difference being the requirement for a kilometer of hard stone to prevent interference vs. the use of a grounded metal box, isolated power supply and exterior antenna.   

A cryptosystem is considered broken when a method exists to solve for a key that is more efficient than the existing brute force method using known ciphertexts and cryptanalysis. Even broken crypto systems often remain useful due to the time and effort required to search for a given key. 

Easy ways to defeat this and future attacks include developing and using cryptosystems that are lattice based and do not  make use of the discrete logarithm or large prime problems.

References;

---

[i] Bogdanov, Andrey; Khovartovich, Dmitry; Rechberge, Christian (Univesity Luven, Microsoft Resarch, France Telecom, 2011) Biclique Cryptanalysis of the Full AES [PDF Document] Available Online: http://research.microsoft.com/en-us/projects/cryptanalysis/aesbc.pdf  (Accessed on April 2^nd 2013)

 [ii] Neil, Dave (The Inquirer, August 17^th 2011) AES encryption is cracked [World Wide Web] Available Online: http://www.theinquirer.net/inquirer/news/2102435/aes-encryption-cracked (Accessed on April 3rd 2013)

[iii]Schneier, Bruce (August 8^th 2011) New Attack on AES [World Wide Web] Available Online: http://www.schneier.com/blog/archives/2011/08/new_attack_on_a_1.html (Accessed on April 3rd 2013) 

 [iv]N.a. (IBM, 2001)  IBM's Test-Tube Quantum Computer Makes History [World Wide Web] Available Online: http://www-03.ibm.com/press/us/en/pressrelease/965.wss (Accessed on April 4th 2013)