How secure is AES against brute force attacks?

By Mohit Arora, Sr. Systems Engineer & Security Architect, Freescale Semiconductor 05.07.2012 15

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.

Figure 1: Multi-bit key to encrypt data using cryptographic algorithm

The key lengthused 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 keycombinations 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:

Figure 2: Brute Force attack on 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:

Figure 3: Key combinations versus 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¹⁵ 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¹⁵ ) / 1000 = 10.51 x 10¹²

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³⁸ ) / [(10.51 x 10¹² ) x 31536000]
                = (0.323 x 10²⁶ )/31536000
                = 1.02 x 10¹⁸
                = 1 billion billion years

Figure 4: Time to crack Cryptographic Key versus Key size

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:

Every person on the planet owns 10 computers.
There are 7 billion people on the planet.
Each of these computers can test 1 billion key combinations per second.
On average, you can crack the key after testing 50% of the possibilities.

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 () 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).

Something of Interest: Vision AI developer kit combines AI and ML to push deep neural network models out to the intelligent edge

15 comments

Post Comment

David1965 2013-05-05 13:31:53

I have written an encryption/decryption system which uses Blowfish to generate the DES keys of which there are 4x blocks also I am using AES 256 as the filling to this DES sandwich algorithm which also uses cipher block chaining so would this be a better solution and resistant to hacking.

David1965 2013-05-05 13:37:05

Sorry to have forgotten to add this the way the system would work is to start with DES being used 4 times on the four input blocks then those four input blocks are fed into AES256 and finally into 4 OUTPUT blocks via the DES to complete one cycle of encryption also the system can be used in reverse.

USInnovate 2013-05-20 15:53:25

Thanks for the great article on data security based on brute force attacks. I am looking at quantum algorithms and the use of quantum computers (D-Wave from Canada). My sense is that quantum is the biggest threat to data security in the medium term. In the short term attacks based on side channel leakage and active attacks are the main problem.

Sparky_Watt 2013-05-20 22:11:35

People who talk about this stuff often ignore 3 factors that make any code more secure. I was reminded of this by the speed comment.
- Symmetric encryption is usually used to securely open a conversation. The initial part of the conversation trades information that is then used to encrypt the rest of the conversation with a much simpler asymmetric encryption.
- Because it is primarily a conversation opener, you can say that you have to have 100 msec between attempts. At this point the power of your computer doesn't matter. You can only try 10 times per second no matter how fast your computer is.
- The response to the last one is that they don't have to retry. They can try repeatedly to decrypt the same recorded message. However, that only works if they have a way to assess that they have successfully decrypted it. Information exchanges as given above can be in the form of a chain of completely random numbers with no encrypted checksum. That makes it impossible to know if you have cracked it without cracking the whole bloody conversation. What I am saying is that the messages can be designed in such a way that the code breaker has no way of knowing when he got it right. It does him no good to guess the correct key if he doesn't know he got it.

elektryk321 2013-05-21 15:41:53

According to current research on cryptoanalisys strenght of AES-256 is comparable with bruteforce key size about 220-bits. So there is no sense to use pure bruteforce. Of course 2^220 is still very big number, but future technics may still lower number. Beside of that, there are additional tricks that could be used against particular AES implementation (in hardware or software), that may lead to recovering the value of the key. This is the most current problem.

David Brown 2013-05-21 19:12:50

The energy argument is a good point. There are theoretical limits to information storage density, and to the minimum amount of energy for calculations.

As far as I know, the theoretical minimum energy for switching one line is kT, where k is the Boltzmann constant and T is the temperature (in K). That's 4e-21 J at room temperature. If we assume that testing an n-bit key takes 1000n switches (an absurdly low estimate), then it takes 5e-16 J per test, and thus 1.75e23 J total to do a brute-force crack of a 128-bit key.

The earth's current energy consumption is about 150 PWh per year, or 5.4e17 J per year.

That means it would take 300000 years to power the calculation to break the 128-bit key, assuming the same power generation of the earth, assuming absolute theoretical minimal switching energies, and assuming ridiculously small numbers of switches per test.

Call me naive, but I don't think the NSA has a secret AES-128 cracking lab...

David Brown 2013-05-21 19:14:33

I made a mistake in my calculations - the theoretical minimum switching energy is kT.ln(2). So it would only take 200000 years to power the calculations!

David Brown 2013-05-21 20:39:39

It is correct that there are ways to reduce the keyspace you need to search - and that future research may reduce this a little more. And it may turn out that in the future, there will be a breakthrough that reduces the search keyspace significantly - but there is no indication of that at the moment.

So even with 128-bit AES, the cheapest and most reliable way to break the key is to use one of the two traditional methods - the three B's technique (bribery, burglary, blackmail) or rubber hose cryptoanalysis. And it looks likely to remain that way for a long time yet.

David.L.Fleischer 2013-05-22 15:35:12

Pentaflops? Good one.

phpexp1 2013-11-13 06:14:43

There is an online demo for AES encryption and decryption

shutterspeed 2014-02-03 13:17:01

I believe AES weakness is not in the Symmetric algorithm itself.

Rather, IMO, the weakness comes in the randomization of the initialization vector. We've already heard how NSA underminds the Dual_EC_DRBG. :)

sansik 2014-07-14 08:32:55

The cryptographic algorithms used in Advanced Encryption Standards are more secure due to 128-bit symmetric keys, if someone sets a password containing both letters and symbols it is very hard for any hacker to find out the code. I use a 128 bit key size password on our workflow management systems and I am sure no one will break it, for a better security I use a random password generator that maximizes the security of the password.

Navelpluis 2015-03-20 13:03:59

You are right. Allow me to add a couple of things: Please try to learn from history. Enigma had about 2^76 possibilities. Much more than single DES (!). In a way as users we are always behind: All we use can be broken, exept for 1 method...

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 !

bdoud 2015-03-20 13:09:15

@Sparky: You have the Symmetric and Asymmetric (Public Key) parts switched. The Public Key algorithms are used to perform the authentication and key handshake, and then the symmetric algorithms such as AES or 3DES are used to encrypt the conversation. The author was only disussing the cracking of AES here, and with a brute force approach there would be no need to attack the Public Key handshake (although of course that's another attack vector that could be used!) Regardless, your concluding point at the end is valid regarding the cracker's need to know something about what properly decoded plaintext "should" look like. But in almost all cases, that is quite reasonable since the wrong decryption key yields statistically random jibberish and the correct key yields something that stands out as being non-random (regardless of what the payload actually is). Sure, the paranoid can obscure their plaintext in a really good way by performing another encryption layer, but then of course your workload has doubled to protect the traffic!

spw1 2016-02-22 12:00:13

This may be just a "nit", but isn't that 1 billion billion years the time required to evaluate ALL possible keys?

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"...

How secure is AES against brute force attacks?

Share this:

Leave a Reply Cancel reply