Bitcoin Forum

Given ASICs have near zero resale value in the event of a bitcoin collapse.

Could someone technical explain; How different is Bitcoin mining to SHA cracking and how much more would it cost to fab such a dual use device ?

Albeit small, I see no end in demand for SHA-1 & 2 cracking, be it for legit password recovery services or evil hacking of encrypted assets.
If the cost is marginally higher (30%) it could significantly reduce the investment risk.

Certainly it would be possible with some trivial design changes to support both - but the only cracking application it would have is with SHA256, and nothing else at all.

Since a bitcoin hash is one SHA256 piped into another SHA256, you would just need to provide a way to get info into and out from the middle of that 2-step process.

Wondering ,,, Since BFL isn't specifying anything about Bitcoin mining in their ASICs press release, is it safe to assume it can also do something else too ? like cracking ?

 ::)

I suspect it would be convertible, but they probably don't want to publicize that fact - more negative press is the last thing both Bitcoin and BFL need right now. I can just see the headlines:

"Shady Bitcoin Company Launches New Units, Hackers Reverse Engineer Them and Hack <Insert Major Website Here>'s Password Database"

"Password Theft - The Future of Bitcoin Mining?"

"Bitcoin - The Virtual Currency it Appears to Be OR The Largest Hacking Operation the World Has Ever Seen?"

Correct me if I'm wrong, but this can't happen with their ASICs. Password cracking works backwards from hashing, right?


The general idea of mining is to run thru a SHA256 hash twice. They take x and turn it into y like this:

y = (SHA256 (SHA-256 (x)))


This is assuming their ASIC does both steps at once. Their ASIC may only do one hash at a time, but it would still look like this:

z = (SHA256 (x))
y = (SHA256 (z))

For password cracking, you would need some way to go from an already encrypted password that's only gone through one SHA256 encryption (z, in the example above), and un-encrypt it into x. It was my impression that this sort of password cracking works backwards from bitmining. The ASIC could be use to encrypt passwords, but there would be no use for something that fast.

Bitmining: x --> SHA256 --> z --> SHA256 --> y
Password: x --> SHA256 --> z
Cracking: z --> CRACK --> x


Does that make sense? Anyone more knowledgeable care to point out any blatantly obvious holes in my reasoning?

Bandwidth would be a problem.

Bitcoin miners use very little bandwidth because they hash the same header 4 billion times (one with a different nonce).

If BFL Single (800 MH/s) was performing password cracking 1.6 billions passwords per second to supply raw blocks (which would be the most compatible w/ Bitcoin algorithm) would require 1.6 * 1000^3 * 512 bytes * 8 bits / byte = 6.4 terrabits per second.  (or ~ 50x bandwidth of 16 lane PCIe 3.0 adapter).  Now that is a BFL Single (65nm FPGA).  If an ASIC can acheive up to 200x higher performance you are looking at bandwidth requirements of ~ 1 pbs (petabit per second).

Bitcoin only uses a small amount of bandwidth because it works like this

block header sent to miner
hash block header w/ nonce 0
hash block header w/ nonce 1
....
hash block header w/ nonce 4294967295
new block header sent to miner

That doesn't apply to password cracking.  You likely "could" design a chip which did both but the compromises would mean it would be a less than optimal bitcoin miner.   The need for single pass mining, lower throughput, and higher bandwidth design would mean it hash higher cost, higher energy consumption and produces less hashes.  I doubt anyone will do that.  SHA-256 cracking is pretty niche so the "dual use" likely isn't worth more than the loss of performance costs.

Someone more knowledgeable than I am will probably chime in here, but they don't crack passwords like this. For cracking, you have the hash of the password. You then take your password guess, hash it, then compare that hash to the value you have. Rinse and repeat several trillion times.

Bold added for emphasis ;)

I'm not too up on my cryptology and password hacking, so I would not be surprised if you are right!

This is correct, in the case we're referring to. (Certain methods more efficient than guessing and checking are usable with some hashing algorithms, but not SHA256 to my knowledge)

Since raw passwords are never (should never be) stored on the server, when a user signs up, their password is hashed at least once and hopefully salted (though not as frequently as they should be) before being put in a database. Through various methods irrelevant to this discussion, a hacker can gain access to that database and consequentially the hashed passwords.

Hopefully the server uses a good hashing algorithm such as bcrypt (multi-layered salted SHA256/512 isn't as good, but is usually sufficient). In this case, the hacker can't do much of anything with the database, as it is inefficient to brute force and impossible to reverse-hash.

However, in a startling number of cases (the MtGox hack for example), passwords are not well-hashed and salted, and are stored in a hashing algorithm such as SHA256, SHA1, or (heaven forbid) MD5 that is efficient. (read: hashes can be calculated quickly)

The hacker then proceeds to find a hash he/she wishes to crack and then attempts to brute force it by hashing standard alphanumeric strings until he finds the one giving the hash he has obtained. He can then use that string (which should be the user's password, except in rare cases) in order to log in to the website and wreak havoc.

Now, for some math. In the 95 character ASCII printable keyspace (usually around the number of different characters allowed in a password), checking every possible password up to 8 characters would take around 6.6 e+15 tries. While that seems like a lot, a 1 TH/s (1 e+12 hashes/sec) unit could process all of those in under two hours. (this is hypothetical, I'm not accounting for bandwidth limitations and the like)

Sorry, that was a bit long winded. Hopefully it's at least moderately understandable.

Now the scary thing, watch the curve as you go to 9, 10 and 11+ characters.

passwords should be 9+ characters, as that would take years for the average person to crack it with average equipment.

edit-

http://4.bp.blogspot.com/-7MwMdlW5nc8/TgKUqjs3ipI/AAAAAAAAAX8/80Fr4_RI85A/s1600/chart_1.png

this is what I was referring to

No offense, but that's a completely useless (and actually deceptive) graph.  The scale on the y axis is really poorly chosen.

The difference between each line is 2.5E19...

1,000,000,000,000,000,000,000
750,000,000,000,000,000,000
500,000,000,000,000,000,000
250,000,000,000,000,000,000
0

That look better?

The graph is 100^x, in case you're wondering

You should not use a linear scale but a logarithmic scale

1. It's not my graph

2. Who uses logarithms for portraying time.  # hashes directly correlates with time.  # hashes is the independent variable.

That's not the issue. For something like that you should use a log scale. I could take the exact same function and make these graphs.
http://i47.tinypic.com/2wgy70o.png
Why use 9+, look at how it shoots up at 8!

http://i45.tinypic.com/i2vqcl.jpg

doesn't portray much of a point, does it?

http://k32.kn3.net/1D9E27922.png

Too bad you only live < 110 years

Actually, I think it shows the point very clearly. Difficulty is an exponential function of password length. It's the other graphs that aren't clear.

Congrats, you've passed algebra.  To some it looks like a straight line.  To some it is a straight line.  Keeping things is prospect to something you can relate to, shows the magnitude of the situation.  ie time.

There's a more fundamental problem than choice of scale in those graphs - using current hardware speeds to predict times to crack of years or more is meaningless; hardware speed increases exponentially.

More characters in a password will certainly help, but you'd be surprised how high a percentage of users use 8 character or less passwords. Remember, we're not discussing how to secure your account - we're discussing the potential power and implications of the use of ASICs for SHA256 cracking.

I figured in 100 million hashes per second. following moores law, we can make the hashing power double every two years to see what kind of impact that makes on it.  I'll do it when I get to work.

Edit: takes a ton of loops.  Too lazy to do it in excel.

pieppiep is right, these graphs (not yours, I get it) should use a logarithmic scale.

The point of a graph is not to wow the audience by showing an impressive exponential curve, it is to document data. Linear scales don't document anything when the data points vary by orders of magnitude.

We have hashed password: z
We need to know the password: x
Solution: Just calculate y = SHA256(z). Then use ASIC to search for x when we already know y

A) Hashing an already hashed password does nothing for us. How is an ASIC (that only does hashes) gonna find a twice hashed password?

B) This discussion has already run its course, and been answered. I was corrected 2 posts down:

Granted BFL ASICs can't be used to crack password but I'm pretty sure a more complex ASICs could be used for both.

The hash has to be compared a list of wanted password hashes instead of the required difficulty mask.

I wish someone could come-up with an estimate of the difference in gates and bandwidth required for the simplest of dual uses.

We don't know that their ASICs cannot be used cracking passwords. We know how theoretically one would do it with double-SHA256 devices but we are not sure how the BFL ASIC will be created (features, programmability, etc).

What do you think regarding the possibility of a bitcoin collapse?

||bit

The point was that if the ASIC operates by hashing twice internally, then you simply hash the hashed password from the DB and then spin through the combinations looking for the twice hash. So, the basic answer here is that, yes, these devices can be used to crack SHA256 passwords that have been either hashed one or twice. And most 8 character passwords will be cracked in a reasonable time.

Did you think that through?

So ASIC goes input -> SHA256 ->SHA 256 and can do a large number per second.

However you only have the stored password which is single hashed.  Your solution is to hash it again.  Ok so on your slow non-ASIC you are going to single hash the hashed pasword and compare it to the double hash output of the ASIC?

So more work and it is no faster than simply using your non-ASIC to single hash the plain text. :)

Well, if you are trying to brute-force 2-pass SHA256, SHA256 is the same no matter where you do it... so you could just hash the password again to get the SHA256*2 of the password... Like password = myPassword
String temp = SHA256(MYPASSWORD)
Now temp is equal to 76549b827ec46e705fd03831813fa52172338f0dfcbd711ed44b81a96dac51c6
If we have a machine that hashes twice, then we could just do this:
temp = SHA256(temp), and then with our two-time hasher look for the value that makes temp. It's half as efficient, but if you can't pull out the hash halfway through the ASIC process, this would still work. Not trying to promote password cracking, but that seems to make sense to me...

Edit: didn't see that previous post about this, sorry lol

To clarify, the SC processor does not support password recovery use.  This is intentional due to export control considerations.

Yes, I thought it through. You only have to hash the hashed password once on your CPU to get the comparator. Then you run the 15 exohashes on the ASIC to find the match.

Not with an ASIC, not even for sha256(sha256(password))-type hashes, not even for the simplest single-hash case as opposed to the hashlist scenario which is much more complicated. Bitcoin mining is different as compared to hash cracking, inputs follow a certain pattern. It doesn't have to worry about candidate generation, full-length hash comparisons and more complex cases involving comparisons against lists of hashes where hash bitmaps or similar technique needs to be employed for early rejects in order to reduce the SLOW host-device transfers.

Sorry, you can't profit on mining ASICs in case something generally f***s up.

 

Bandwidth ? the low amount of memory required for the hash to be checked can fit easily on-board, (512bk for ~16 000 hashes ?)

I'm no expert but there is certainly a way to reuse the hashing blocks for cracking, even if that mean adding 10x to the cost of hardware.
(If someone see the chance of bitcoin to succeed at 10% that'll be worth it for him.)

Of course it is possible to design a dual-purpose (SHA256 cracking/mining) chip, it would very likely mean larger die size and more layers thus higher NRE costs and higher end-product costs.

End result being customers paying more to get the same hashrate. There isn't that much demand for SHA256 cracking actually, in fact sha256 is not widely used, thus it is highly unlikely you'd ever pay off your ASIC miner in case bitcoin collapses simply because demand is low. A better idea would be to create a dual-use chip that can perform custom number of PBKDF2 iterations, it can then be easily reused by software to crack different stuff (WPA-PSK, ZIP 3.x, protected OpenOffice docs, FileVault, encrypted IOS/blackberry backups, etc). Problem being PBKDF2-SHA1 is so radically different as compared to SHA256 that you'd be much better off selling two different boards together.

Overall though fast ASICs are not quite useful for hash cracking unless you are a three-letter agency that can afford producing lots of different designs. Also unlike bitcoin mining, it is not all about speed, cleverly exploiting low password entropy by reducing keyspace in some way, generally works better (otherwise cracking passwords of length >=10  would be extremely uncommon). Simple bruteforce attacks are dumb and generally it's much more practical to write some good wordlist mangling rules as compared to bruteforcing. Even statistical attacks like ones based on markov models are generally much better than bruteforcing. Yet markov attacks require good input models and rule mangling requires much more skill as compared to bitcoin mining.

You forgot paperweight.  ;D

I realize I'm replying here about 9 months after the last post... but I think I may have something to add. I was under the impression (since I last looked into the password cracking topic about 15 years ago), that back then the latest preferred method was to use "rainbow tables". As I recall, this is basically a huge file that contains confirmed hashes that correspond to specific passwords. With this table, the cracking software no longer needs to brute force each hash - the rainbow tables file is the output of huge brute force attempts. Thus, the cracking of passwords is now reduced to taking the hash of a password file, looking it up like a database search against the same hash already recorded in the rainbow tables file, and spitting out the clear text password in a split second, thus no brute forcing is involved at all - because that work was already done ONCE to create the rainbow-table file.

My point being, I don't think there's any point at all in creating an ASIC to brute force crack passwords, because rainbow tables already have all the brute force work reduced to one (or more) huge file(s).  I believe there are online projects where hacke....er... people are creating multi-terabyte sized rainbow table files that contain every possible hash variation of X length passwords. If anything, a custom ASIC could be used to create these rainbow tables much faster than normal PCs or GPUs; but to provide real-time password cracking services, probably doesn't make that much sense (I think). So with rainbow tables, I think the speed of finding the password in a hash becomes more about I/O - how fast can the hash/password finder application dig through multi-terabyte files to match the hash you are looking for? In theory, if the rainbow tables are like indexed databases, even multi-terabyte files should yield a password recovery in a few seconds.

Comments?

Rainbow table are only useful when used against well known algorithms on unsalted hashes. (MD5)

For example WPA keys are generated with 4096 SHA1 iteration of the password + SSID as salt.
A specific rainbow table can be made for SSID "Linksys" but is completely useless against a "Router058" SSID.

Storing and indexing of rainbow tables is often much more costly than the generation and comparing process.

Can you point where on the ammunition list is named a password cracking system or equipment? I'm very curious about that!