Talk:Bruteforcing

Bruteforcing AES encrypted data

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¹²⁸ 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:

2128 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³², 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:

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

Key sizes

bits	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

bits	Period
32	Xorshift PDF (period 232−1)
64	Xorshift PDF (period 264−1)
96	Xorshift PDF (period 296−1)
128	Xorshift PDF (period 2128-1)
160	Xorshift PDF (period 2160-1)
192	Xorshift PDF (period 2192−1)
250	Mother-Of-All pseudorandom number generator algorithm [1]
19937	Mersenne Twister pseudorandom number generator algorithm (period 219937-1 ≈ 4.3 × 106001)