How secure is AES against brute force attacks?
21 comments
In the world of embedded and computer security, one of the often debated topics is whether 128-bit symmetric key, used for AES (Advanced Encryption Standard) is computationally secure against brute-force attack. Governments and businesses place a great deal of faith in the belief that AES is so secure that its security key can never be broken, despite some of the inherent flaws in AES.
This article describes the strength of the cryptographic system against brute force attacks with different key sizes and the time it takes to successfully mount a brute force attack factoring future advancements in processing speeds.
Any cryptographic algorithm requires multi-bit key to encrypt the data as shown in Figure 1.
The key length used in the encryption determines the practical feasibility of performing a brute-force attack, with longer keys exponentially more difficult to crack than shorter ones.
Brute-force attack involves systematically checking all possible key combinations until the correct key is found and is one way to attack when it is not possible to take advantage of other weaknesses in an encryption system.
Here is an example of a brute force attack on a 4-bit key:
As shown, it will take a maximum 16 rounds to check every possible key combination starting with "0000." Given sufficient time, a brute force attack is capable of cracking any known algorithm.
The following table just shows the possible number of key combinations with respect to key size:
Notice the exponential increase in possible combinations as the key size increases. "DES" is part of a symmetric cryptographic algorithm with a key size of 56 bits that has been cracked in the past using brute force attack.
There is also a physical argument that a 128-bit symmetric key is computationally secure against brute-force attack. Just consider the following:
Faster supercomputer (as per Wikipedia): 10.51 Pentaflops = 10.51 x 10^{15} Flops [Flops = Floating point operations per second]
No. of Flops required per combination check: 1000 (very optimistic but just assume for now)
No. of combination checks per second = (10.51 x 10^{15}) / 1000 = 10.51 x 10^{12}
No. of seconds in one Year = 365 x 24 x 60 x 60 = 31536000
No. of Years to crack AES with 128-bit Key = (3.4 x 10^{38}) / [(10.51 x 10^{12}) x 31536000]
= (0.323 x 10^{26})/31536000
= 1.02 x 10^{18}
= 1 billion billion years
As shown above, even with a supercomputer, it would take 1 billion billion years to crack the 128-bit AES key using brute force attack. This is more than the age of the universe (13.75 billion years). If one were to assume that a computing system existed that could recover a DES key in a second, it would still take that same machine approximately 149 trillion years to crack a 128-bit AES key.
There are more interesting examples. The following snippet is a snapshot of one the technical papers from Seagate titled "128-bit versus 256-bit AES encryption" to explain why 128-bit AES is sufficient to meet future needs.
If you assume:
Then the earth's population can crack one encryption key in 77,000,000,000,000,000,000,000,000 years! |
The bottom line is that if AES could be compromised, the world would come to a standstill. The difference between cracking the AES-128 algorithm and AES-256 algorithm is considered minimal. Whatever breakthrough might crack 128-bit will probably also crack 256-bit.
In the end, AES has never been cracked yet and is safe against any brute force attacks contrary to belief and arguments. However, the key size used for encryption should always be large enough that it could not be cracked by modern computers despite considering advancements in processor speeds based on Moore's law.
About the author
Mohit Arora (mohit.arora@freescale.com) is a Sr. Systems engineer and Security Architect at Freescale Semiconductor. He is responsible for product and architecture definition for 32-bit industrial and general-purpose parts. "Embedded Security" is one of his main expertise and focus areas and he also leads the Security IP Asset team in AISG (Automotive Industrial and Solution Group). He holds more than 35 publications and is also the author of the book "The Art of Hardware Architecture."
For more articles like this and others related to designing for the embedded Internet, visit Embedded Internet Designline and/or subscribe to the biweekly Embedded Internet newsletter (free registration).
Author
spw1 2/22/2016 12:00:13 PM
I guess what I'm pointing out is a slight flaw in the calculation/logic that seems to assume a brute force attack must calculate all possible outcomes prior to determining which was the correct one. Granted, It would still come out to about half a billion billion years (on average), which is still essentially "unbreakable"...
Author
bdoud 3/20/2015 1:09:15 PM
Author
Navelpluis 3/20/2015 1:03:59 PM
Now you might think: "Yes, but Enigma had vulnerabilities", that's right. But each crypto system is designed by humans, so each crypto system is weak in a certain way. While trying to crack systems you have to think equally: Think as a software design engineer. So, let me suggest that by choosing large keys, they are often formed by primes. Well, with a -for example- 128 bit key, let us first test THE LARGEST PRIMES and I will ensure you that you will find the key faster than you think. This is what the 'capable bodies' would do (and probably will do). My thoughts are that this is the way you have to think while working with crypto. So -at least- use a 1024 bit key or even larger. The rest smaller than this already has been lost, it is not safe anymore.
Another annoying thing that most people forget is the following: Key exchange is one thing, but data exchange is another. Most people fuzz about key exchange and how safe this must be. Most fantastic procedures are designed for that. But then... , to be followed by a laughable data exchange format to be cracked by seconds (with some statistics only). Then you don't even *need* the key. Please consider this as well.
The best way to encipher data is with the Vernam principle. Only problem is that your key has to be as large as your message, and you have to distribute your key in a safe way. During the cold war the Washington-Moscow hotline worked with this principle. It contained the Siemens M190 mixer machine with a couple of TELEX machines. Look at the cryptomuseum dot com webpages and search for M190. This website will be an eye-opener for you and it is also good to learn about the history. Vernam is the way to go, anywaym have fun !
Author
sansik 7/14/2014 8:32:55 AM
Author
shutterspeed 2/3/2014 1:17:01 PM
Rather, IMO, the weakness comes in the randomization of the initialization vector. We've already heard how NSA underminds the Dual_EC_DRBG. :)
Author
phpexp1 11/13/2013 6:14:43 AM
Author
David.L.Fleischer 5/22/2013 3:35:13 PM
Author
David Brown 5/21/2013 8:39:40 PM
Author
David Brown 5/21/2013 7:14:34 PM
Author
David Brown 5/21/2013 7:12:50 PM