Editing Talk:Bruteforcing

== Bruteforcing AES encrypted data ==
<div style="border-width: 1px; border-style:dashed; border-color:#000000; padding: 10px; background-color:#FFFFFF; color:#000000; ">Posted on May 8, 2009 by xorloser @ http://www.xorloser.com/?p=93

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<sup>128</sup> 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<sup>128</sup> keys ÷ 2,000,000 keys/second = 1.7e+32 seconds

For those not fluent in “calculator speak” 1.7e+32 means 1.7 x 1032, 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<sup>128</sup> 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.
</div>

=== Key sizes ===
{| class="wikitable sortable"
|-
! bits !! style="text-align:left" | No of keys
|-
| 1 || 2
|-
| 2 || 4
|-
| 4 || 16
|-
| 8 || 256
|-
| 16 || 65536
|-
| 32 || 4294967296
|-
| 48 || 281474976710656
|-
| 64 || 18446744073709551616
|-
| 80 || 1208925819614629174706176
|-
| 96 || 79228162514264337593543950336
|-
| 112 || 5192296858534827628530496329220096
|-
| 128 || 340282366920938463463374607431768211456
|-
| 144 || 22300745198530623141535718272648361505980416
|-
| 160 || 1461501637330902918203684832716283019655932542976
|-
| 176 || 95780971304118053647396689196894323976171195136475136
|-
| 192 || 6277101735386680763835789423207666416102355444464034512896
|-
| 208 || 411376139330301510538742295639337626245683966408394965837152256
|-
| 224 || 26959946667150639794667015087019630673637144422540572481103610249216
|-
| 240 || 1766847064778384329583297500742918515827483896875618958121606201292619776
|-
| 256 || 115792089237316195423570985008687907853269984665640564039457584007913129639936
|-
| 272 || 7588550360256754183279148073529370729071901715047420004889892225542594864082845696
|-
| 288 || 497323236409786642155382248146820840100456150797347717440463976893159497012533375533056
|-
| 304 || 32592575621351777380295131014550050576823494298654980010178247189670100796213387298934358016
|-
| 320 || 2135987035920910082395021706169552114602704522356652769947041607822219725780640550022962086936576
|-
| 336 || 139984046386112763159840142535527767382602843577165595931249318810236991948760059086304843329475444736
|-
| 352 || 9173994463960286046443283581208347763186259956673124494950355357547691504353939232280074212440502746218496
|-
| 368 || 601226901190101306339707032778070279008174732520529886901066488712245510429339761526706943586500787976175353856
|-
| 384 || 39402006196394479212279040100143613805079739270465446667948293404245721771497210611414266254884915640806627990306816
|-
| 400 || 2582249878086908589655919172003011874329705792829223512830659356540647622016841194629645353280137831435903171972747493376
|-
| 416 || 169230328010303641331690318856389386196071598838855992136870091590247882556495704531248437872567112920983350278405979725889536
|-
| 432 || 11090678776483259438313656736572334813745748301503266300681918322458485231222502492159897624416558312389564843845614287315896631296
|-
| 448 || 726838724295606890549323807888004534353641360687318060281490199180639288113397923326191050713763565560762521606266177933534601628614656
|-
| 464 || 47634102635436893179040485073748265163400240214004076398607741693502376385799646303105256699577209032590132615988260237052123652332890095616
|-
| 480 || 3121748550315992231381597229793166305748598142664971150859156959625371738819765620120306103063491971159826931121406622895447975679288285306290176
|-
| 496 || 204586912993508866875824356051724947013540127877691549342705710506008362275292159680204380770369009821930417757972504438076078534117837065833032974336
|-
| 512 || 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096
|-
| 768 || 1552518092300708935148979488462502555256886017116696611139052038026050952686376886330878408828646477950487730697131073206171580044114814391444287275041181139204454976020849905550265285631598444825262999193716468750892846853816057856
|-
| 1024 || 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216
|-
| 1280 || 20815864389328798163850480654728171077230524494533409610638224700807216119346720596024478883464648369684843227908562015582767132496646929816279813211354641525848259018778440691546366699323167100945918841095379622423387354295096957733925002768876520583464697770622321657076833170056511209332449663781837603694136444406281042053396870977465916057756101739472373801429441421111406337458176
|-
| 1536 || 2410312426921032588580116606028314112912093247945688951359675039065257391591803200669085024107346049663448766280888004787862416978794958324969612987890774651455213339381625224770782077917681499676845543137387820057597345857904599109461387122099507964997815641342300677629473355281617428411794163967785870370368969109221591943054232011562758450080579587850900993714892283476646631181515063804873375182260506246992837898705971012525843324401232986857004760339316736
|-
| 1792 || 279095111627852376407822673918065072905887935345660252615989519488029661278604994789701101367875859521849524793382568057369148405837577299984720398976429790087982805274893437406788716103454867635208144157749912668657006085226160261808841484862703257771979713923863820038729637520989894984676774385364934677289947762340313157123529922421738738162392233756507666339799675257002539356619747080176786496732679854783185583233878234270370065954615221443190595445898747930123678952192875629172092437548194134594886873249778512829119416327938768896
|-
| 2048 || 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656
|-
|}

=== Pseudorandom Period sizes ===

{| class="wikitable sortable"
|-
! bits !! style="text-align:left" | Period
|-
| 32 || Xorshift [http://www.jstatsoft.org/v08/i14/paper PDF] (period 2<sup>32</sup>−1)
|-
| 64 || Xorshift [http://www.jstatsoft.org/v08/i14/paper PDF] (period 2<sup>64</sup>−1)
|-
| 96 || Xorshift [http://www.jstatsoft.org/v08/i14/paper PDF] (period 2<sup>96</sup>−1)
|-
| 128 || Xorshift [http://www.jstatsoft.org/v08/i14/paper PDF] (period 2<sup>128</sup>-1)
|-
| 160 || Xorshift [http://www.jstatsoft.org/v08/i14/paper PDF] (period 2<sup>160</sup>-1)
|-
| 192 || Xorshift [http://www.jstatsoft.org/v08/i14/paper PDF] (period 2<sup>192</sup>−1)
|-
| 250 || Mother-Of-All pseudorandom number generator algorithm [ftp://ftp.forth.org/pub/C/mother.c]
|-
| 19937 || Mersenne Twister pseudorandom number generator algorithm (period 2<sup>19937</sup>-1 ≈ 4.3 × 10<sup>6001</sup>)
|-
|}