Password cracking, mining, and GPUs

http://erratasec.blogspot.com/2011/06/password-cracking-mining-and-gpus.html

by d0ne • 15 years ago

84 25 15 years ago

erratasec.blogspot.com

andrewcooke2• 15 years ago

very nice point about exponential growth and diminishing returns. also, i didn't realise that 9 characters was the inflection point (are they overestimating slightly the rate?)

biturd• 15 years ago

This may help answer your question about the inflection point: http://www.baekdal.com/tips/password-security-usability

It is a bit old, but not so old that you can't determine what a good length is. More importantly, it is not always about the length, where something like "alpine fun" (two common words) may take a couple months, but just adding in "this is fun" (three common words) gains you thousands of years in time.

Before reading, I was under the impression that without a password manager, it has become impossible to secure passwords by memory as GPU's became more powerful. My impression was that "random", alpha-numeric, plus non-alpha-numeric characters, and, of great length would be needed.

This article leads me to believe otherwise, and that something like "this#is#my#password" should be sufficiently uncompromisable for some time to come. It is also highly rememberable to me.

There was a youtube video linked, I believe from HN, apx. 3 weeks ago, that showed a demo of GPU password cracking that was a bit more illustrative than this article, and more current. Unfortunately, I can't seem to locate it.

andrewcooke2• 15 years ago

1 - the article linked here on hn gives 9 characters as the current practical limit for brute force hacking with a 100 values per character (upper + lower + symbol). the link you gave calls 6 characters "safe for life" when using alphanumeric + symbols. while exactly what symbols are included is significant, there's clearly a major discrepancy (i guess that the problem is two-fold: your link is woefully out of date and the link here is over-estimating rates on gpus).

2 - also, using more words is, in the context of the article you linked to, related to dictionary attacks. and again your article is pretty poor since it's giving an example with very common words which implies that a very small dictionary would be needed. i would not call "this is fun" a safe password.

3 - the article you link to is again misleading in that it completely ignores password helpers and puts too much emphasis on local restrictions like reducing login rates. it seems like it was written before both the web (we are seeing lists of passwords being stolen - that makes "restricting retries" completely irrelevant) and gpus were common. i would not use it as a reliable source of advice.

bonzoesc2• 15 years ago

> Before reading, I was under the impression that without a password manager, it has become impossible to secure passwords by memory as GPU's became more powerful. My impression was that "random", alpha-numeric, plus non-alpha-numeric characters, and, of great length would be needed.

Remember that the article is about today's state-of-the-art. Next year, cracking algorithms might be better, GPUs will certainly be better, EC2 spot instances might be cheaper, and dictionary guessing algorithms will be smarter. A 50-character random password loaded with symbols, digits, and letters is good in the face of that.

dkokelley3• 15 years ago

I really wonder how dictionary attacks will progress as word frequency and distribution is studied. "this is fun" has 11 characters, which has 310^15 possible lower-case combinations, and (using the 500,000 word dictionary), has 1.2510^17 combinations, an order of magnitude more. But, assuming a smart hash cracker, the size of the dictionary could be shrunk considerably. I believe most people use approximately 10,000 common English words (not including proper nouns or fictional words). 'this', 'is', and 'fun' would all show up under that scheme. Using a 10,000 word dictionary, there are only 1*10^12 combinations. Much less secure than an 11 character random password. A smarter cracker could apply sentence structure rules to skip odd, fragmented sentences (ie. "dog foot with happy").

Also, the article failed to mention the risks of compromised password databases. Sure, the attacker could just gain access to the actual files he or she wants while bypassing the login step, but the list of username/email and password credentials are a major threat to users. Most users only have a handful of passwords, and an attacker could leverage the one they know to find the ones they don't. Password managers are necessary for this reason, to provide unique passwords to each protected site. If password managers become wide spread, then why not let them remember arbitrarily long and complex passwords. It can't hurt, right?

StavrosK• 15 years ago

Quite an informative article. I considered building one of these rigs, but I'm only a hobbier, far from the hobbiest.

mcantelon• 15 years ago

Macbook Pro at 17 MH/s is a poor value compared to a $1K gaming notebook that comes with an 5870M (~150 MH/s according to mining hardware comparison)... there are also units with other, possibly faster, GPUs:

http://ncix.com/products/index.php?minorcatid=1323&submi...

As for Bitcoin mining being profitable, the difficulty level is going up quite quickly so the days of quickly recouping your hardware costs seem to be waning.

epiphany47• 15 years ago

Random thought: If the bitcoin currency fails, would people turn their bitcoin mining rigs into hash cracking rigs? I wonder if it's more economical to be mining bitcoin or to crack hashes.

bonzoesc2• 15 years ago

Once the Mt. Gox password database leaked, there was a little bit of commentary about how the community had a lot of password-cracking power on tap.

kayoone2• 15 years ago

Mining bitcoins and selling them will soon be not profitable anymore. It was just some weeks ago but since that time loads of people started mining and now the difficulty of the mining algorithm goes up every 7-10days effectivly cutting profits in half. I you buy a mining rig now you will probably never be able to pay it off as electricity costs will eat up all profits before August of this year. Of course the value of Bitcoins could raise dramatically to make it profitable again, but if and when that happens remains to be seen.

ars• 15 years ago

> Of course the value of Bitcoins could raise dramatically to make it profitable again

If the value didn't go up people would stop mining. If people stopped mining the difficulty level would go down.

So basically the value of bitcoins will always stabilize at the cost of electricity for the most efficient rig.

But the efficiency of rigs changes constantly, but that is offset by the difficulty changing. So I'm not quite sure how the balance will stay longterm.

But in the short term the value is pegged to the cost of energy.

ohashi• 15 years ago

Well, to take it one step further, price differences in electricity costs could play a role too. Also people subsidizing electrical costs from various sources (office for example).

noahc• 15 years ago

So theoretically, being in the midwest with super cheap electricity, I should always be able to make money because my cost of power is about three times cheaper than a place like California?

caf2• 15 years ago

It's not the value of bitcoins that stabilises but the difficulty of producing bitcoins (measured in average number of trial hashes per BTC). Given:

D = difficulty (HASH/BTC)

E = marginal efficiency (HASH/kWH)

V = value of bitcoins (USD/BTC)

C = cost of electricity (USD/kWH)

then in equlibrium, the difficulty will be equal such that the electricity you can purchase with a generated bitcoin will just balance out the electricity required to produce it (neglecting depreciation of equipment, time value of money etc..):

D ~= (E * V) / C

So this predicts that equilibrium difficulty will increase when marginal mining efficiency increases (ie. more power-efficient GPUs are available), when the value of bitcoins increases, and when the price of electricity decreases.

(Note that there is no guarantee that the system will reach equilibrium - the relatively long time lag taken for the difficulty to adjust in the protocol may mean it doesn't).

It is also notable that you can rearrange to solve for `V`, allowing you to determine an estimate of the underlying theoretical value of bitcoins based on the current difficulty level, the efficiency of the best GPU now available, and the price of electricity.

kayoone2• 15 years ago

i dont totally agree since there are people that get electricity for free and others who are just in it for the fun. Think of folding@home or seti@home which both were very popular without ANY financial incentive thus i reckon mining will be on the edge of profitability but more on the unprofitable side. Adding to that that in germany for example i pay .3USD per kWh so i am out of the game much sooner than others.

lwat2• 15 years ago

From what I heard on http://reddit.com/r/bitcoin the latest difficulty increase have now made bitcoin mining more expensive than the electricity required, and some home miners are now stopping production.

dkokelley3• 15 years ago

...decreasing the supply of new bitcoins, leaving more on the table for the remaining miners (with the most efficient setups). Really the primary variable is the acceptance of the BTC as currency, which influences the exchange rate. Everything else would seem to be in a nice equilibrium.

maximilian• 15 years ago

> Smart sysadmins "salt" the passwords, which requires cracking.

As has been mentioned previously on HN, smart sysadmins use bcrypt making the entire password cracking exercise nearly impossible.

dkokelley3• 15 years ago

New conspiracy theory:

Bitcoin was created as a secret government project to inexpensively wage cyber warfare. Thousands of hopeful BTC prospectors invest in ever-increasingly efficient hash-cracking rigs, creating a sleeping botnet of cyber-soldiers. When the time comes, the government takes control of these machines (possibly silently). Instead of cracking bitcoin blocks, they are now all cracking nuclear launch codes of enemy states. That's a movie I would see.

Password cracking, mining, and GPUs

Related Stories