This article fits in: Techniques for countering security software.
Really? AES-256 can not be brute forced and that is a fact and security products use it all the time. But look what happens when I run this small POC to crypt and then try to brute force a secret message
crypted with AES-256:
Original message is = My Secret Message!
Random password generated to encrypt the message = UWVVSGDADGSZIEXUGAGXXUKDYVHTDETP
Crypted message using AES-256 = mKOfC5GktNPVmR2kf/kfOGOVrG3bk9xsNqn+BjsF9r8=
Press any key to start brute forcing...
Testing password = MYJFWQBCUHVJQERMZCRSWOYFXNFIZZIQ
Testing password = YRRAKUPPRYCPYRZVOLQISHUWUWJSSEZJ
Testing password = KJZUYXDCOOJVGDHFDVPYPBQNSFNCLJPD
Testing password = XCGPNASPLEQAOQPPSFPOLVLEPOQMEOFW
Testing password = JUOJBDGCHVXGWCXZHPOEIOHVNYUWXTWP
Testing password = WMWDPHUPELEMFPEIWZNUEICMKHYGPYMI
Testing password = IFEYDKJCBCKRNBMSLJNKBBYDIQBQIDDB
Testing password = VXMSSNXPYSRXVOUCBTMAXVUUFZFABITU
Testing password = HPUNGQLCUIYDDACMQDLQUPPLCJIJUOJN
Testing password = TIBHUUAPRZFILNKVFNKGRILCASMTNTAH
Testing password = GAJCIXOCOPMOTZRFUWKWNCGSXBQDFYQA
Testing password = STRWXACPLGTUBLZPJGJMKWCJVLTNYDHT
Testing password = FLZRLERCIWZAJYHZYQICGPYASUXXRIXM
Testing password = RDHLZHFPEMGFSKPJNAISDJTRQDBHKNNF
Testing password = DWOGNKTCBDNLAXXSCKHHZCPINMERDSEY
Testing password = QOWACNIPYTURIJECRUGXWWKZLWIBWXUS
Testing password = CGEUQRWCVKBWQWMMGEGNSQGQIFMLOCLL
Testing password = PZMPEULPSAICYIUWVOFDPJCHFOPUHHBE
Testing password = BRUJTXZBOROIGVCFKXETLDXYDYTEAMRX
...many tests omitted to save space...
Testing password = TBMIFPOOSZEJTCQXCAVBRYYMAIITYCND
Testing password = GTUCTTCBPQLPBPXHRKUROSUDXRMDRHDW
Testing password = SLCXHWQOMGSUJBFRGUUHKLPTVAPNKMUP
Testing password = FEKRWZFBJXZARONBVETXHFLKSKTXDRKI
Testing password = RWSLKCTOGNGGAAVLKOSMDZHBQTXHVWBC
Testing password = DOZGYGHBCDNLINDUZXSCASCSNCAROBRV
Testing password = QHHAMJWOZUTRQZKEOHRSWMYJLLEAHGHO
Testing password = CZPVBMKBWKAXYMSODRQITGUAIVIKALYH
Testing password = PSXPPPZOTBHDGYAYSBPYPZPRGELUTQOA
Testing password = BKFKDTNBPROIOLIHHLPOMTLIDNPELVFT
Testing password = OCNERWBOMIVOWXQRWVOEJMGZAXSOEAVM
Testing password = AVUZGZQBJYCUEKXBMFNUFGCQYGWYXFLG
Testing password = MNCTUDEOGOIZNWFLBPNKCAYHVPAIQKCZ
Testing password = ZFKOIGSBDFPFVJNUQZMAYTTYTYDSJPSS
Testing password = LYSIXJHOZVWLDVVEFILQVNPOQIHCCUJL
Testing password = YQACLMVAWMDQLIDOUSLGRHKFORLLUAZE
Testing password = KJHXZQJNTCKWTUKYJCKWOAGWLAOVNFPX
Testing password = WBPRNTYAQSRCBHSHYMJMKUCNJKSFGKGR
Testing password = JTXMCWMNNJXIJTARNWICHNXEGTWPZPWK
Testing password = VMFGQAAAJZENSFIBCGIRDHTVDCZZSUND
Testing password = IENBEDPNGQLTASQLRQHHABOMBLDJKZDW
Testing password = UWVVSGDADGSZIEXUGAGXXUKDYVHTDETP
Random password initially generated = UWVVSGDADGSZIEXUGAGXXUKDYVHTDETP
Match found in 00:00:00.3239570 seconds. The password is = UWVVSGDADGSZIEXUGAGXXUKDYVHTDETP
The original message is = My Secret Message!
The brute forced message is = My Secret Message!
Press any key to close...
Took less than one second to brute force AES-256. If you want to know why, keep reading...
Let's first examine the facts. What would it take to brute force AES-256. To brute force it, you need to check 2^255 keys which would represent half of the possible combinations in a 256bit password. By checking that
amount of keys you would be covering half of the possibilities and therefore you would have a chance of 50% to guess the right password. A high-end PC can check 2^26 passwords per second. A year contains 31,557,600
seconds. In a year you would be able to test 2,117.8 trillion keys. By dividing 2^255/2,117.8 trillion you get how many years are needed to brute force AES-256, and its
27,337,893,038,406,611,194,430,009,974,922,940,323,611,067,429,756,962,487,493,203 years which is the same as 27 trillion trillion trillion trillion trillion years. If you have access to more computing power then
calculations are different but lead to the same conclusion:
Computing power Average time to crack using exhaustive search
High-end PC 27,337,893,038,406,611,194,430,009,974,922,940,323,611,067,429,756,962,487,493,203 years.
27 trillion trillion trillion trillion trillion years
Fastest supercomputer 27,337,893,038,406,611,194,430,009,974,922,940,323,611,067,429,756,962,487 years.
27,337,893 trillion trillion trillion trillion years
2 billion high-end PCs 13,668,946,519,203,305,597,215,004,987,461,470,161,805,533,714,878,481 years
13,689 trillion trillion trillion trillion years
Age of the universe 15,000,000,000 years
15 billion years
As you can corroborate in the table, its simply not possible. So then how come I did it? If you look at the code (look at end of the article), I am using standard Microsoft Libraries. So what went wrong?
The answer is, I purposely created a poor implementation of AES-256. You would be surprise on how many times security products have flaws in their implementation of these libraries.
On purpose, I used a weak random password generator. The password generator only produces uppercase letters, so instead of having to check 2^255 keys, I only have to check 2^26 possible keys. If I add
lowercase letters then it would be 2^52 keys and if I add numbers still I would be in the range of 2^62 keys. A proper password would have to be created in such a way that all of the 32 bytes could have their
full range of possible values and this of course includes non printable characters. However, in many situations, developers chose to allow only printable characters for their passwords because its easy for the
costumer to type them when requested. If you check on public implementations of AES-256, you won't see much of a difference in a large number of the instances, in regard to the errors I have shown here.
But there is even more to this story, if you run the POC you will notice that it only checks a fraction of the 2^26 possible keys. This means there is a second flaw in the algorithm, one that is worst than
the first one. The random password is also not really random although, again, uses Random Class provided by Microsoft. The problem on using this is that Random Class also is not adequate for the purpose
of creating passwords suitable to be used by AES-256 because the Random Class is seeded using the PC Clock, and the PC clock is predictable. What I have done is simply test every possible seed value
from the PC Clock moving backwards. The clock can only go one way and its forward, so by moving the clock value backward one unit at a time and knowing that Random results are always the same if the seed is the same
then I can guess the password even faster.
Lets see the code:
Unsafe password generator:
Finally, another aspect to keep the algorithm strong is to use a different or even random nonce (iv) for each communication. In this way the attacker has to calculate the password and also the nonce for every key check.
If the password is not long enough, it can be hashed to reach a safe length, in fact, the password is more strong if you add two additional characters than if you triplicate the number of possible values of each one of
the existing characters.
In conclusion, AES-256 is safe if implemented right. There are several sources of errors during its implementation that can be exploited in certain situations to the advantage on an attacker, specially in relation to the
proper selection of a secure password but not only limited to it.
Source code attached.
Really? AES-256 can not be brute forced and that is a fact and security products use it all the time. But look what happens when I run this small POC to crypt and then try to brute force a secret message
crypted with AES-256:
Original message is = My Secret Message!
Random password generated to encrypt the message = UWVVSGDADGSZIEXUGAGXXUKDYVHTDETP
Crypted message using AES-256 = mKOfC5GktNPVmR2kf/kfOGOVrG3bk9xsNqn+BjsF9r8=
Press any key to start brute forcing...
Testing password = MYJFWQBCUHVJQERMZCRSWOYFXNFIZZIQ
Testing password = YRRAKUPPRYCPYRZVOLQISHUWUWJSSEZJ
Testing password = KJZUYXDCOOJVGDHFDVPYPBQNSFNCLJPD
Testing password = XCGPNASPLEQAOQPPSFPOLVLEPOQMEOFW
Testing password = JUOJBDGCHVXGWCXZHPOEIOHVNYUWXTWP
Testing password = WMWDPHUPELEMFPEIWZNUEICMKHYGPYMI
Testing password = IFEYDKJCBCKRNBMSLJNKBBYDIQBQIDDB
Testing password = VXMSSNXPYSRXVOUCBTMAXVUUFZFABITU
Testing password = HPUNGQLCUIYDDACMQDLQUPPLCJIJUOJN
Testing password = TIBHUUAPRZFILNKVFNKGRILCASMTNTAH
Testing password = GAJCIXOCOPMOTZRFUWKWNCGSXBQDFYQA
Testing password = STRWXACPLGTUBLZPJGJMKWCJVLTNYDHT
Testing password = FLZRLERCIWZAJYHZYQICGPYASUXXRIXM
Testing password = RDHLZHFPEMGFSKPJNAISDJTRQDBHKNNF
Testing password = DWOGNKTCBDNLAXXSCKHHZCPINMERDSEY
Testing password = QOWACNIPYTURIJECRUGXWWKZLWIBWXUS
Testing password = CGEUQRWCVKBWQWMMGEGNSQGQIFMLOCLL
Testing password = PZMPEULPSAICYIUWVOFDPJCHFOPUHHBE
Testing password = BRUJTXZBOROIGVCFKXETLDXYDYTEAMRX
...many tests omitted to save space...
Testing password = TBMIFPOOSZEJTCQXCAVBRYYMAIITYCND
Testing password = GTUCTTCBPQLPBPXHRKUROSUDXRMDRHDW
Testing password = SLCXHWQOMGSUJBFRGUUHKLPTVAPNKMUP
Testing password = FEKRWZFBJXZARONBVETXHFLKSKTXDRKI
Testing password = RWSLKCTOGNGGAAVLKOSMDZHBQTXHVWBC
Testing password = DOZGYGHBCDNLINDUZXSCASCSNCAROBRV
Testing password = QHHAMJWOZUTRQZKEOHRSWMYJLLEAHGHO
Testing password = CZPVBMKBWKAXYMSODRQITGUAIVIKALYH
Testing password = PSXPPPZOTBHDGYAYSBPYPZPRGELUTQOA
Testing password = BKFKDTNBPROIOLIHHLPOMTLIDNPELVFT
Testing password = OCNERWBOMIVOWXQRWVOEJMGZAXSOEAVM
Testing password = AVUZGZQBJYCUEKXBMFNUFGCQYGWYXFLG
Testing password = MNCTUDEOGOIZNWFLBPNKCAYHVPAIQKCZ
Testing password = ZFKOIGSBDFPFVJNUQZMAYTTYTYDSJPSS
Testing password = LYSIXJHOZVWLDVVEFILQVNPOQIHCCUJL
Testing password = YQACLMVAWMDQLIDOUSLGRHKFORLLUAZE
Testing password = KJHXZQJNTCKWTUKYJCKWOAGWLAOVNFPX
Testing password = WBPRNTYAQSRCBHSHYMJMKUCNJKSFGKGR
Testing password = JTXMCWMNNJXIJTARNWICHNXEGTWPZPWK
Testing password = VMFGQAAAJZENSFIBCGIRDHTVDCZZSUND
Testing password = IENBEDPNGQLTASQLRQHHABOMBLDJKZDW
Testing password = UWVVSGDADGSZIEXUGAGXXUKDYVHTDETP
Random password initially generated = UWVVSGDADGSZIEXUGAGXXUKDYVHTDETP
Match found in 00:00:00.3239570 seconds. The password is = UWVVSGDADGSZIEXUGAGXXUKDYVHTDETP
The original message is = My Secret Message!
The brute forced message is = My Secret Message!
Press any key to close...
Took less than one second to brute force AES-256. If you want to know why, keep reading...
Let's first examine the facts. What would it take to brute force AES-256. To brute force it, you need to check 2^255 keys which would represent half of the possible combinations in a 256bit password. By checking that
amount of keys you would be covering half of the possibilities and therefore you would have a chance of 50% to guess the right password. A high-end PC can check 2^26 passwords per second. A year contains 31,557,600
seconds. In a year you would be able to test 2,117.8 trillion keys. By dividing 2^255/2,117.8 trillion you get how many years are needed to brute force AES-256, and its
27,337,893,038,406,611,194,430,009,974,922,940,323,611,067,429,756,962,487,493,203 years which is the same as 27 trillion trillion trillion trillion trillion years. If you have access to more computing power then
calculations are different but lead to the same conclusion:
Computing power Average time to crack using exhaustive search
High-end PC 27,337,893,038,406,611,194,430,009,974,922,940,323,611,067,429,756,962,487,493,203 years.
27 trillion trillion trillion trillion trillion years
Fastest supercomputer 27,337,893,038,406,611,194,430,009,974,922,940,323,611,067,429,756,962,487 years.
27,337,893 trillion trillion trillion trillion years
2 billion high-end PCs 13,668,946,519,203,305,597,215,004,987,461,470,161,805,533,714,878,481 years
13,689 trillion trillion trillion trillion years
Age of the universe 15,000,000,000 years
15 billion years
As you can corroborate in the table, its simply not possible. So then how come I did it? If you look at the code (look at end of the article), I am using standard Microsoft Libraries. So what went wrong?
The answer is, I purposely created a poor implementation of AES-256. You would be surprise on how many times security products have flaws in their implementation of these libraries.
On purpose, I used a weak random password generator. The password generator only produces uppercase letters, so instead of having to check 2^255 keys, I only have to check 2^26 possible keys. If I add
lowercase letters then it would be 2^52 keys and if I add numbers still I would be in the range of 2^62 keys. A proper password would have to be created in such a way that all of the 32 bytes could have their
full range of possible values and this of course includes non printable characters. However, in many situations, developers chose to allow only printable characters for their passwords because its easy for the
costumer to type them when requested. If you check on public implementations of AES-256, you won't see much of a difference in a large number of the instances, in regard to the errors I have shown here.
But there is even more to this story, if you run the POC you will notice that it only checks a fraction of the 2^26 possible keys. This means there is a second flaw in the algorithm, one that is worst than
the first one. The random password is also not really random although, again, uses Random Class provided by Microsoft. The problem on using this is that Random Class also is not adequate for the purpose
of creating passwords suitable to be used by AES-256 because the Random Class is seeded using the PC Clock, and the PC clock is predictable. What I have done is simply test every possible seed value
from the PC Clock moving backwards. The clock can only go one way and its forward, so by moving the clock value backward one unit at a time and knowing that Random results are always the same if the seed is the same
then I can guess the password even faster.
Lets see the code:
Код:
using System;
using System.Diagnostics;
using System.Text;
namespace BreakAES256
{
class Program
{
public static string Secret = "My Secret Message!"; // Secret message to be crypted and later brute forced
static void Main()
{
var randomPassword = RandomStringGenerator.RandomString(32, Environment.TickCount); // Get a random string and use the PC clock as seed to introduce the flaw
Console.WriteLine("Original message is = " + Secret);
Console.WriteLine("Random password generated to encrypt the message = " + randomPassword);
var crypted = AesCryptoService.Encrypt(Secret, Encoding.ASCII.GetBytes(randomPassword), new byte[]{1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4 }); // Crypt the message
Console.WriteLine("Crypted message using AES-256 = " + Convert.ToBase64String(crypted) + "\r\n\r\n" + "Press any key to start brute forcing..."); // Show the crypted message
Console.ReadKey();
Stopwatch watch = new Stopwatch(); // Measure how long will it take to brute force
watch.Start();
for (int i = Environment.TickCount; i > 0; i--) // Check the PC clock in a backward fashion
{
var randomPassword1 = RandomStringGenerator.RandomString(32, i); // Get a password to test
var decrypted = AesCryptoService.Decrypt(crypted, Encoding.ASCII.GetBytes(randomPassword1), new byte[]{1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4 }); // Try to decode the password
Console.WriteLine("Testing password = " + randomPassword1); // Print password being tested
if (decrypted == Secret) // Check if we got a match
{
watch.Stop(); // Stop the clock - a match was found
Console.WriteLine("\r\nRandom password initially generated = " + randomPassword); // Show results
Console.WriteLine($"Match found in {watch.Elapsed} seconds. The password is = " + randomPassword1);
Console.WriteLine("\r\nThe original message is = " + Secret);
Console.WriteLine("The brute forced message is = " + decrypted);
Console.WriteLine("\r\nPress any key to close...");
Console.ReadKey();
return;
}
}
Console.WriteLine("No Match found...");
Console.ReadKey();
}
}
}Unsafe password generator:
Код:
using System;
using System.Text;
namespace BreakAES256
{
internal class RandomStringGenerator
{
public static string RandomString(int size, int seed, bool lowerCase = false)
{
var random = new Random(seed); // We seed it with the PC clock on purpose
var builder = new StringBuilder(size);
var offset = lowerCase ? 'a' : 'A';
const int lettersOffset = 26; // Only 26 possible letters
for (var i = 0; i < size; i++)
{
var @char = (char)random.Next(offset, offset + lettersOffset);
builder.Append(@char);
}
return lowerCase ? builder.ToString().ToLower() : builder.ToString();
}
}
}Finally, another aspect to keep the algorithm strong is to use a different or even random nonce (iv) for each communication. In this way the attacker has to calculate the password and also the nonce for every key check.
If the password is not long enough, it can be hashed to reach a safe length, in fact, the password is more strong if you add two additional characters than if you triplicate the number of possible values of each one of
the existing characters.
In conclusion, AES-256 is safe if implemented right. There are several sources of errors during its implementation that can be exploited in certain situations to the advantage on an attacker, specially in relation to the
proper selection of a secure password but not only limited to it.
Source code attached.
