Written by DrPres:
On October 16th, 2013 Google unveiled it’s nifty new artificial intelligence quantum computer, and around the same time Konloch and I were discussing a way to share information without worrying about the prying eyes of third parties. We discussed a method which would use an asynchronous public key exchange to create a secure channel to pass files that had been encrypted with a synchronous method (i.e. AES). I suggested the use of AES-128, noting that AES-256 would require the extra Oracle security libraries. In addition I told Konloch that the amount of raw computing power required to brute-force AES-128 would be astronomical. Not satisfied, Konloch asked that I explain exactly how long it would take. Here’s the rundown of our conversation:
Imagine we have an arbitrary key of an arbitrary bit length, how long does it take for us to bruteforce this key assuming we can only attempt 1 key per second? If our key has a bit length of one, in order to attempt all possible keys we would need to test two keys: 0 and 1. If our key has bit length of two it takes four seconds to test all possible keys: 00, 01, 11, and 10. If we have a key of bit length 3, it will take us 8 seconds to test all possible keys. By induction we have that it takes 2 ^ n seconds to attempt all possible keys. However, since on average we will only have to attempt half of all possible keys, it will take half of the time 2 ^ (n) / 2 which is equal to 2 ^ (n – 1). In this case, a 128 bit key takes approximately 340282366920938463463374607431768211456 seconds to brute force the key. It is unlikely, however, that anyone attempting to bruteforce the keys will be attempting only 1 key per second. The fastest supercomputer ever recorded showed a processing power of 10.51 pentaflops, which is 10.51 x 10 ^ 15 floating point operations per second. Now it would take much more than a single floating point operation to test the combination, in this case a very generous estimate would be 1000 operations. In this case, we can attempt 10.51 ^ 12 ( 10510000000000) keys per second on the fastest supercomputer in the world. Using this supercomputer to bruteforce a 128 bit key would take approximately 3237700922178291755 seconds. That’s 102,948,874,458.76 years.
So it’s unlikely that AES-128 will ever be broken by current technology. Quantum computing, however, changes this rule. Grover’s algorithm allows us to search an unsorted database of N unsorted entries in the square root of N operations. So a quantum computer makes the effective number of entries of AES-128 2 ^ 64 rather than 2 ^128. This means the time required to bruteforce the same file is now a very plausible .055 years (about 20 days). AES-256, however, will still remain at an effective 2 ^ 128 possible combinations which we have shown to be much more than adequate for the foreseeable future.
There is a possibility that AES is vulnerable to more complex cryptanalytic attacks. Researchers from Microsoft and K.U.Leuven provided a partial crack to AES in August of 2011. The so-called Biclique cryptanalysis technique presents the greatest known risk to AES yet. The technique reduces the computational complexity of AES-256 from 2 ^ 256 to a startling 2 ^ 254.4. This reduction in complexity presents no real-world significance though, and given the high computational complexity of the attack, it is unlikely to be used outside of academia. That being said, it is plausible that more comprehensive cryptanalytic techniques will surface in coming years that will threaten the security of AES-256. For now, however, upgrading from AES-128 to AES-256, if you haven’t already done so, should be more than adequate.
This article will be my first in a series of mathematics and cryptography related posts on this site. Next week’s article will focus on typical public-key exchange algorithms and their relative security.