Dual use ASICs, Mining and Cracking

[mrb]

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.

[nguoinhaque]

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?

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

[crazyates]

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?

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:

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.

[Transisto]

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:

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.

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.

[abeaulieu]

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:

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.

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

[||bit]

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

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

||bit

[Fjordbit]

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

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.

[DeathAndTaxes]

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

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.

[Vorksholk]

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

[BFL]

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

[Fjordbit]

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

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.

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.

[gat3way]

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.

 

[Transisto]

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

[gat3way]

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.

[tatsuchan]

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.

You forgot paperweight. 

[digitalmagus]

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?

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.

[Transisto]

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

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.

[pietrod21]

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

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