Print this page

In the news...

03/10/13

Economics of GPU password recovery


Posted by: gat3way in fun



This is my first post in English and I hope you'd put up with my poor command of it :)

Normally, I would write about the latest hashkill developments, new features, technical and crypto-related mumbo jumbo and stuff. This post is going to be different, more practical in a way.

Perhaps some of you have seen my GPU estimations table for hashkill (which to be honest desperately needs an update). I started it a long time ago when hashkill was still capable of attacking just a couple of "fast" hash algorithms (including bitcoin and SL3 which are not supported anymore). I borrowed the idea from Ivan Golubev. I believe both estimation tables are prepared more or less the same way - by gathering statistics about ALU operations and extrapolating based on shader cores, core clocks and some minor perks related to different architectures. While this works for simple "fast" algorithms which are 100% ALU-bound, it gets much more complicated to do the same calculations for "slow" and more complex algorithms which may involve branch divergence and use of shared memory. This is one of the reasons I haven't updated it yet for more algorithms.

I got bored today (still too exhausted after the "ASOT 600" party here in Sofia to do any coding) so I decided to play with drawing some ugly diagrams and doing some tests. My idea was to evaluate GPU password recovery of "slow" hash algorithms from practical and economical standpoint. For my tests, I used an AMD Radeon HD7970 GPU. So here are the results (and a pile of ugly diagrams).

Most people don't have a good idea about the cryptography employed by different products. Actually, most people do believe password recovery works by bruteforcing the keyspace until the password is found. While this approach might guarantee successful attack result (depending on charset), it is not practical with "slow" algorithms. In fact it might not be practical even with "fast" ones such as MD5. The keyspace might be enormous (in fact, "keyspace" is not the correct term, but I guess "password space" sounds...strange). For example, bruteforcing a 20-character password (md5) out of the alpha-numeric space would take about 83 million years when run on a cluster of 1 million 7970 GPUs - which is completely impractical. Well, it gets much worse for slow hashes where bruteforcing even 10-character alpha-numeric password may get equally impractical.

In fact good wordlists expanded with clever rules is the only practical approach for "slow" algorithms right now and this would not change soon. We are exploiting the fact that human passwords generally have low entropy. Thus, stronger passwords are likely out of reach.

Anyway let's finally move to the colorful graphs :) Keep in mind that the speeds were achieved using the most intensive settings and rules that were able to take advantage of the GPU offloading for candidate generation in hashkill (which rules take advantage of GPU offload is an interesting question that I would probably try to answer in details in a different post).

First, let's see how the things are going with password recovery of protected archives. On the Y axis we have the attack speed (the higher, the better):


This diagram is rather...skewed by the ZIP (old) algorithm which should better be put in the "fast" category I believe. OK let's remove it and see how it goes:

Hm still what about DMG (10.8)? OK, removing ZIP (AES) as well:


Now that's better. We can get a better impression of the scale - cracking DMG produced by MacOSX Mountain Lion (10.8) is orders of magnitude slower than cracking ZIP passwords :) In fact, it is close to being impractical to crack, unless we either know something part of the password or we are armed with a huge cluster with thousands of GPUs and we can pay the enormous running costs :)

Jeremiah Grossman was lucky recovering his DMG password, he knew part of it though.



Let's move on to the document formats:


Again, diagram is skewed by the PDF (R5) results. As you know, PDF has several revisions to the password protection and encryption algorithms. PDF R5 uses just a simple SHA256. hashkill's results are in fact quite bad as this algorithm could have been accelerated at least 9x faster. This implementation flaw should be fixed soon. Well, at least the diagram is not completely dominated by PDF R5 yet :) Let's remove the faster algos and see how it would look like though:


You can see the huge gap between PDF R6 and PDF R5. With revision 6, Adobe basically made GPU recovery pointless by introducing a lot of branch divergence and moving to a memory-bound algorithm. In fact, the CPU implementation is often faster than the GPU one even when running on a 7970 :) Another thing that is worth mentioning is that OpenOffice uses Blowfish as a symmetric cipher (newer versions use AES). Blowfish is an anti-GPU algorithm and needs to be performed on CPU. Thus results may vary depending on your CPU.



Let's move on to cracking Full Disk Encryption. Currently, hashkill supports just TrueCrypt and LUKS. Below is the diagram:


It gets funny here. As you can see, we have two entries for TrueCrypt - one when using the default settings, and the other when trying all the possible algorithms. This is better explained in this document. In real life though, you may never be sure whether the default settings were used when creating the volume.

Now let's move to my recent obsession - password managers:

Yet again, the graph is dominated, this time by the Mozilla cracking speed. Mozilla is rather insecure password manager as compared to most other solutions in terms of password cracking. OK - let's remove it and see how the diagram would look like:

Update (11 March 2013): Rosen Penev wrote that recently, LastPass increased the iterations count tenfold. That would make it the harder to crack among the software listed above, at about 90K c/s.

Update (12 March 2013): Data was wrong for both KeePassX and KeePass2. Diagram was also corrected for LastPass' increased iterations count.

We got somewhat more balanced diagram this time. KeePass2 is much faster to crack as compared to the opensource KeePassX that uses the old database format, which is funny at least to me.

OK let's have a look at the diagram about system passwords now:

OK we know NTLM is a "fast" algo so that was expected. Let's remove it and OSX ones and see how it looks like:


Hm, the diagram still skewed by the cracking speed of MD5Crypt. Let's remove it as well:

As you can see, there are huge differences among system passwords hash algos' cracking speed. hashkill still doesn't support OSX Mountain Lion hashes - and they are expected to be slower to crack even as compared to BCrypt.

Update (11 March 2013): Solar Designer pointed out that both BCrypt and OSX Mountain Lion's password hashing algorithms have variable cost parameter and it is not correct to compare them both. The graph above assumes BCrypt uses the $2а$05$ cost parameter (32 iterations).


But where does the WPA-PSK cracking speed stand? Let's see:


Well not so bad, much better than RAR for example :)


As you might have already noticed, the title of the post was about the economics of GPU password recovery and yet nothing was mentioned about economics and money. Of course you can easily do some quick calculations about the cost to try a wordlist of say 1 billion candidate passwords. Here is an example diagram, the cost (in EUR) to try a 10 billion candidates wordlist using 4x7970s (the lower the better from attacker's perspective, the higher - the better for energy distribution companies). Assuming price per KWh is 0.1 EUR (which is more or less valid for Bulgaria, might be much more expensive or cheaper depending on where you live. It also takes into consideration just the direct energy costs, however you might have other costs related to cooling for example.


As you can see, it could be relatively expensive to try even 10 billion candidates in an attempt to crack a linux system password.


So that's all for now. Hope you liked the ugly diagrams :)





Comments:


  • March 11, 2013, 2:06 pm - TekTengu

    Your english was pretty good. I imagine even with a lot of practical work, I would have struggled to have done as good of job in your native language.

    On a secondary note, I think the graphics took a bit to understand. They were backwards to what I would have thought they were at first glance and had to read what you wrote (fully and carefully) to understand them. We have a saying here (in America) that graphics should be "idiot proof" and should not require words (other than maybe the caption).

    So if brute forcing without some ancillary knowledge is still so costly why are we claiming things like wireless security has been broken? I know there are some easy breaks to wireless, but properly configured enterprise wireless configurations should require cracking the password.

  • March 11, 2013, 7:28 pm - Alberto

    Could you try also with 7-zip and Opera's master password?

  • March 11, 2013, 7:52 pm - Hroi

    Nice post - I just want to suggest logarithmic scaling of the y-axis.

  • March 11, 2013, 8:39 pm - gat3way

    @TekTengu: thanks. I am not a business/presentation person and so my diagrams are appalling :) Hopefully I'd improve that some day.

    As far as WPA-PSK security is concerned, I don't think it's broken. It's just as secure as the passphrase used. A strong passphrase (though it's hard to give a definition of that) makes it impractical to crack. What is referred to as "Enterprise mode" is a different thing, though certain protocols are vulnerable to offline attacks in case an attacker is able to intercept the traffic (and that could be much harder as compared to the preshared key mode).

    @Alberto: 7zip and Opera are not yet supported by hashkill (the GPU cracking software I am developing), thus I cannot provide any exact figures at the moment. I don't even know what algorithm Opera uses. As far as 7zip is concerned, it should be somewhat 3 to 4 times slower as compared to rar - it uses sha256 rather than sha1 with twice the iterations count.

    @Hroi, I was considering that but dropped it as 1:1 would...better illustrate cracking speed differences, at least I thought so. Then again this decision was probably wrong, I just noticed the post at reddit where someone posted the xkcd link eheh :)

  • March 12, 2013, 12:37 am - Qu

    Keepass2 has a config to let you change the number of iterations to slow attacks. Default is very quick, settings have a button to make it 1 second of CPU time.

  • March 12, 2013, 3:48 am - Josh

    Outstanding article, great command of English. Better than most college students' writing in the US.

  • March 13, 2013, 4:05 am - murica

    Post up a pastebin of the raw data. I'll make them charts work right for biz users.

  • March 13, 2013, 9:47 pm - !ntel

    Thanks for the article. Very good explained!

  • March 13, 2013, 10:05 pm - gat3way

    @Qu: you're right (also my data was wrong for both KeePassX/KeePass2, the speed is slower, I corrected the diagram).

    @Josh: thanks :)

    @murica: I can do that when I have more spare time. How can I reach you (mail I guess)?

  • March 14, 2013, 10:03 am - rembrandt

    Hi gat3way,

    You see do like english blog-posts :-D
    Nobody exspects weekly blog posts but it's a lot easier to understand compared to the output of google-translate. And you might reach more users. :)

    But I would wish to write a critic.
    The topic is "Economics"...

    So what card provides the best average rate for the money?
    You might consider to take the total cost of ownership into the statistics. Energy cost is one thing but if I pay 400EUR for one single card compared to a lightly slower model wich cost me 250 I can afford to spend like 40EUR more for energy a year and still would crack passwords more cost effective. *just a quick idea of what could get considered if we talk about economics*

    Related to WPA-Enterprise: It is vuln. with some protocols.
    You can disconnect a client and then sniff the trffic. It should not be more difficult then WPA-PSK (to get the handshake). The security of WPA-PSK belongs to use used protocols and modes from my point of view.

    Overall: Interesting article :)

  • March 17, 2013, 9:08 pm - hl2run

    Hello, what about 1Password for Mac, Windows and the browser plugins?

    Thanks

  • March 18, 2013, 1:13 pm - бацето

    nice one, everyone loves statistics :D, само на първата графика ми се виждат много нули на у оста, няма ли да е по-четливо в K,M,G или научно 10^3,10^6. Поздрави за якия пост.


Add A Comment

This is a captcha-picture. It is used to prevent mass-access by robots. (see: www.captcha.net)
Code in the picture:
Your Name(*):
Comment(*):