When it comes to cryptography algorithms the topic of bruteforcing them appears often, however is rarely dealt with in a satisfying way. Usually such a discussion will start with someone asking “Why not just bruteforce it?” and end with someone stating “It is not possible, it would take too long”. Occasionally someone will chip in with “Why not randomly guess it? You might get lucky”. So one day I decided to find out if it is possible, and if not, to at least get an idea of just how long “too long” is.

I chose the AES algorithm to try bruteforcing since I wanted to discover the key used to decrypt Xbox360 xex files, and this was before the Xbox360 was exploited. It should be noted that one of the requirements for a good crypto is that it should not be able to be broken by brute force. AES has been chosen as *the *standard encryption algorithm, used by the US government and approved by the NSA, so it can definitely be considered a good crypto.

AES can use keys of size 128, 192 and 256bits. The longer the key (the larger the number of bits) the stronger protection it provides. The AES implementation I was up against used 128bit keys. So I was trying to brute force the weakest form of AES. Every bit in the key can be either a 0 or a 1 which means there are 2 possible values for every bit. A 128 bit key then has 2^{128} possible key values. That is 2 to the power of 128, or 2 multiplied by itself 128 times. Just how large this number is will be explained in more detail below.

The next step was to write the program to perform the bruteforcing. I had a small amount of encrypted data and the decrypted equivalent. The bruteforcer program continually attempts to decrypt the encrypted data using different key values. If the result is the same as the decrypted data I knew, then the correct key had been found. Once completed, the bruteforcer program was able to test 2 million possible keys every second! This seemed to me to be a huge amount of keys being tested, so surely it would only be a matter of time before it found the correct key.

Before I wrote the bruteforcer program I had no idea how many keys would be able to be bruteforce tested in a second. Now that I had an actual figure I could let my bruteforcer run while I did some math to work out how long before I would have my key.

The maximum number of seconds it would take to find the key:

2^{128}keys ÷ 2,000,000 keys/second = 1.7e+32 seconds

For those not fluent in “calculator speak” 1.7e+32 means 1.7 x 10^{32}, which means you move the decimal point to the right 32 times. So then the number is 17 followed by 31 zeros. This seems like a lot of seconds, but it is hard to gauge time in large numbers of seconds. So for the benefit of the humans here, lets use years instead of seconds for our measurements of time.

First we need to work out how many seconds there are in a year. We will approximate to simplify the math:

365 days x 24 hours x 60 minutes x 60 seconds = 31,536,000 seconds in a year

Now we can work out how many keys the bruteforcer can test in a year:

2,000,000 keys/second x 31,536,000 seconds = 63,072,000,000,000 keys/year

Finally we can work out the maximum number of years it would take to find our key:

2^{128}keys ÷ 63,072,000,000,000 keys/year = 5,395,141,535,403,007,094,485,264 years

Now we actually get a number that is small enough to to display on the calculator without requiring “calculator speak” Another way of writing these numbers is:

5,395,141,535,403,007,094 million years 5,395,141,535,403,007 billion years

Being that the current age of the universe is estimated to be 15 billion years old I think it is fair to say that it is impossible to work out an AES key by bruteforce.

But what if…?

But what if you were to optimise your bruteforcer? And what about increases in computing power every year? What if you created a distributed bruteforcer program that everyone around the world can run? What if you were to randomly guess keys instead of trying all keys incrementally?

Assuming I could optimise my bruteforcer to be 1,000,000 times faster, and that computers suddenly became 1,000 times more powerful and that every single person in the world (7,000,000,000) owned one of these new computers then:

5,395,141,535,403,007,094,485,264 years ÷ (1,000,000 x 1,000 x 7,000,000,000)

= 770734 years

Or if it were to use random guesses, then every year that passes there would be a 1 in 770734 chance that someone somewhere guessed the right number.

Great Post.

This should be the main `goto` post each time someone asks the question.

\Why not just brute force it\. Especially when talking about AES

Lets just hope those quantum computers arrive soon

great stiff but again nothing i did not know but hopefully it will cut dowon on some of noobie questions, and yes i do reallies there people just staring in this for them i say good goodluck guys

this remindes me of a story were the german police ask a mate of mine if it was possible to crack pgp oh how i laghthed.

so there you go gys now you have the same knolage as me and others now go and read bruces work.

I’ll leave a quote by bruce to that pefetic idorcacy idium

“if you got nothing to hide, you have nothing to worry about”

* “If I’m not doing anything wrong, then you have no cause to watch me.”

* “Because the government gets to define what’s wrong, and they keep changing the definition.”

* “Because you might do something wrong with my information.”

Piece guys

cheers

back to looking at screens of hex

I think you have years backwards.

You said:

5,395,141,535,403,007,094 million years

5,395,141,535,403,007 billion years

Don’t you mean

5,395,141,535,403,007,094 billion years

5,395,141,535,403,007 million years

No it is correct, a billion is a 1,000 times a million. So to convert from million to billion you divide by 1,000. At least when talking about a “short scale” billion.

Who the hell decided to take a quantity used for measurement and provide multiple different definitions of the amount. Such as two versions of how much a billion is? Or multiple versions of how much a ton/tonne is, or even how much a quart is? wtf ppl?

“Who the hell decided to take a quantity used for measurement and provide multiple different definitions of the amount.”

hehe, the Americans.

They still have trouble using the universally accepted Metric System.

Fantastic article Xor!!

I have few questions.

You speaking about “increases in computing power every year” and “became 1,000 times more powerful”

Are you refers to x86 CPU or GPU “CUDA” power?

Another thing, you mention a program that everyone around the world can use, I hope you mean something like BOINC “http://boinc.berkeley.edu”. right?

One more thing, did you (or someone else) thought about electric power consumption? That’s just unreal.

The suggestions I made were not based on anything other than extreme possible values. For example I do not predict computing powers actually becoming 1000x more powerful, nor do I expect every single person in the world to suddenly own such computing power.

The point I was making is that even if the most extreme limits of progress were made, then bruteforcing of AES is still not a feasible option.

Today I came across a project to write an AES brute forcer optimsed for the PS3. The project itself is nicely done, however even with a PS3 optimised implementation it only performed 10 times faster the brute forcer I tried on PC. This is a nice real world example that an increase in CPU power is not going to make AES bruteforcable any time soon

The link to this project is:

http://www.kennethroe.com/WWW/PS3Crypto.html

If it’s not too far OT…

If RSA functions uses only prime numbers (or, if I am informed correctly Mersenne primes) …would it be trivial to crack RSA if one had a list of primes …furthermore, where can I find this list for free

A good asymmetric crypto algorithm, such as RSA, is based on a mathematical process that is very difficult or impossible to reverse.

In the case of RSA it relies on the fact that it is much easier to multiple two large prime numbers together to get a result than it is to take the result and work out what the original two prime numbers were.

As an example use the two prime numbers 11 and 17.

You can work out the product easily: 11 x 17 = 187

However if start with 187 and need to work out its prime factors it requires a bit of work. Since 187 is quite small you can still work out the factors without too much trouble, however the prime numbers used in RSA are very very large, so working out their factors is very tricky.

Read up on “factoring prime numbers” for the more in depth version

As for a list of primes, not only would the list be too big to store, there is also no standard pattern or formula for calculating what the next prime number is. It basically comes down to checking all possible factors to determine if a number is a prime or not. This is part of the complexity of dealing with primes as doing so for a very large number takes a lot of computation power.

There was a recent interesting RSA key crack for the TI-83 operating system:

http://www.mail-archive.com/cryptography@metzdowd.com/msg10781.html

For RSA-512, it’s at the point where it is now reasonable to brute-force the key. For anything higher, you’re still out of luck.

So what is the size of the key for the Beatles Rockband?

let me rephrase that

If one had the encrypted message & the decrypted message of readable text like “Hello”, could one alter the encrypted message without having the key so when the message was decrypted by the original key owner the message would read “GoodBye”

Regards

Impact

Nice Link Jim Paris

I’ll just point out for those who don’t know it that the *common* size for an RSA key seems to be 2048 bits when used in commercial applications such as in the Xbox360. Also note that while a 2048 bit key is four times the size of a 512 bit key, it takes a lot longer than 4 times as long to “break” it. It takes 2 ^ (2048-512) times as long to break it (is using a brute force method to break it). This is approx 2.4 x 10^462 as long!

Impactops

No, for AES that is not possible except by trying by brute force which would theoretically take as long as it would to find the key.

Using Winhex, write a message in plain text and encrypt it with the AES encryption option within winhex with what ever key size of your choosing

Save the unencrypted & encrypted version of the text & send them to me & i’ll send you an altered encrypted message

You disappoint me Xorloser,

http://www.winhex.com/winhex/manual.pdf

This explains the AES mode of encryption used in winhex as stated in page 91(87).AES in CTR mode has an inherent weakness as describe in the article below dated 2003

http://everything2.com/title/CTR

I discovered this weakness prior to comming across these articles & not knowing what mode of AES was used by winhex after being told it cannot be done then answering my questions with a question.AES has many modes it can be configured in, refering to it in general terms is naive.

I believe that the signature on sector16 of the xbox360 can be exploited using this method

AES CTR mode is not used by the Xbox360. It is a special mode that has it’s uses when used correctly. AES CTR creates a stream of “random” data that is generated from the key, this stream is then XORed with the data being encrypted by this mode. So all of the usual “xor tricks” apply to this mode, these tricks are all common knowledge.

What sector 16 do you refer to?

Symmetric encryption should not be used as protection as once the key is found the protection is lost. On the Xbox360 anything important is signed using asymmetric RSA encryption and keys. So no the Xbox360 cannot be exploited in this way.

Then why didn’t you state this from the beginning when i ask you?

I did not think about AES in the broader terms of all of its possible modes. There are a few different ways to use AES which all build on top of the general AES encrypt/decrypt function. The *normal* modes of using it for encryption are ECB and CBC which are what the Xbox360 use.

The PS3 does make use of AES CTR mode for some of its encryption, however it also checks the validity of the data using asymmetric crypto in the form of elliptic curve cryptography (ECC). So at best you might be able to decrypt the encrypted data, but not replace it with your own such as altering a “hello” string to be a “goodbye” string.

In the case of the XBox 360 games, we can narrow the field considerably by using data from the game discs and from RAM dumps while the game is running as dictionaries for our decrypter. I have no idea what this would do to your math but a hybrid brute force would seem more likely than random brute force.

Nerd42 I suggest you read my “cryptography for dummies” post to get a bit of background info on how crypto systems work.

Basically any symmetric algorithm, which AES is, uses the same key to decrypt as it does to encrypt. This means that the key must be present in the Xbox360 so that it can decrypt the AES encrypted data. If the key is present it means it can be retrieved, and in fact all Xbox360 keys have been retrieved since the initial exploit years ago.

Asymmetric crypto algorithms use a different key to encrypt than they do to decrypt. This means that while the Xbox360 contains the keys required to decrypt asymmetrically encrypted data, it does not contain the key to encrypt it. This is the basis of “signing” files as you hear about when running signed or unsigned code.

So in summary we can get the keys required to decrypt data, but cannot get the keys required to sign data which is required to make your own applications run on an unmodified system.

And why not 4 AMD istanbul combined with 4 ati HD 5970 ?

The above post explained that if you had

seven billionmachines running 2 million keys per second, you’re looking at up to 5,395,141,535,403,007,094,485,264 years to decrypt it. Even if your AMD/ATI combination is 1,000,000 times as fast, that’s still over several trillion years – and that’s still with 7,000,000,000 of these machines running nonstop.So no, using top-of-the-line CPUs and GPUs to speed up aren’t going to help, unless someone invents a CPU several trillion times faster than what we have now.

Cold-FX: The end of the post allows for computers that are 1000 times faster than current. Using 4 AMDs and 4 gfx cards is not even going to reach this 1000 time improvement.

I think I shoulded have ended with a simmary stating that it is not doable.

HyperHacker: Exactly.

“Asymmetric crypto algorithms use a different key to encrypt than they do to decrypt. This means that while the Xbox360 contains the keys required to decrypt asymmetrically encrypted data, it does not contain the key to encrypt it. This is the basis of “signing” files as you hear about when running signed or unsigned code.

So in summary we can get the keys required to decrypt data, but cannot get the keys required to sign data which is required to make your own applications run on an unmodified system.”

Ah, well I was just interested in getting the Rock Band DLC audio data out. I think my RAM dump theory

Perhaps you should consider re-evaluating some of what you’ve said here in the light of the fact that the PS3’s been hacked and today somebody figured out how to get around some of the DRM’d components in the XBox 360 http://arstechnica.com/security/news/2010/02/infineon-drmencryption-chip-succumbs-to-physical-attack.ars?utm_source=rss&utm_medium=rss&utm_campaign=rss

Also, why do I not see Moore’s Law taken into account in this post?

Oops I’m missing the rest of my sentence. I meant to say, “I think my RAM dump theory might have a chance at helping with that.”

“Who the hell decided to take a quantity used for measurement and provide multiple different definitions of the amount.”

According to that wiki that you link, it would be the French.

“hehe, the Americans.

They still have trouble using the universally accepted Metric System.”

My god, tell me about it. I was born an citizen of the US and I frequently regret it. I don’t know why “we” can’t just switch and be done with it. “We” have tried a few times, but the morons just refuse to forget about that damned english system. However, it is not “universally” accepted. Burma and Liberia also use the accursed english system.

One (probably ignorant) question, as you stated that the keys will be tested randomly instead of sequential, does it favour the finding of the key?

I mean, being random, the first tested key could be the correct one rigth? How does it being sequential or random affects the chance of finding it?

Thanks for the article, very informative for decryption legos!

I very much doubt that “randomising” the selection would affect the chances of finding the key.

For example, say we’re trying to find a number between 1 and 100. If we start at 1 and work our way up (1, 2, 3, etc.), it could well take 100 guesses to find it. But if we’re randomly guessing (42, 64, 11, etc.), then there’s every chance it could still take 100 guesses to find it. In each case, the chance of the next attempt being the right number is still 1%.

Now, factor in that when you’re “randomly guessing”, you’re going to have to either risk guessing the same values twice or waste processing power checking to make sure that you haven’t already guessed that value (Which would require logging every value you’ve tested thus far, taking up more and more memory and taking longer and longer to check each time), in the end the wasted resources would just slow you down.

Having said that, I very much doubt the key will be the first or last value (0 or 100, in our example) so if you REALLY wanted to attempt to bruteforce it, perhaps the best way would be to pick a random starting point and count up from there. But then, you’re pretty much fighting with the same odds as when you play the lottery, anyway.

Pingback: XBOX 360: x360 CPU Key Finder *SOURCE* - ModControl.Com - GermanysNr1MultiConsoleSceneSource

I am aware that bruteforcing AES is not a great idea.

However, I am pretty sure that the Rock Band .ark files that you manged to decipher were encrypted through AES.

I was just curious through what process you went through to decipher the unknown file formats in Rock Band.

(I’m pretty sure you did not bruteforce it.)

Unenrypted file formats you can often work out by looking at various different files of the same format in a hex editor.

Encrypted files require disassembling the program that uses them to see how it decrypts them. It is much more than just AES to decrypt rockband songs

Given Moore’s Law and the constant increase in computing speed, you’re only looking out about 22 years, in the worst case, for a 1000x increase in speed. 42 for a million times increase. Rather than call it 700000-some years to bruteforce AES-128, it’s more like it will be a century or so until AES-128 is so easy to crack that a cell phone can do it. You have to factor in the rate of computational improvements to get a real and proper estimate.

‘course, by the time a century has passed, we’ll probably have surpassed Moore’s Law, and AES will be a 16K-bit encryption. And someone like you will be posting on the hypernet about how it won’t be bruteforced, and someone like me will be talking about how in the future it will be easy to break.

Pingback: Brute Force Decrypter?, Can someone make one? - Page 3 - PSX PS2 PS3 Scene Hacking Modchip & Jailbreak Community

Why not just aquire the signing software from Microsoft by means of hacking or social engineering? Seems more likley than brute forcing.