The 1 trillion figure is only after factoring in that you would need multiple false positives to trigger the feature. It's not descriptive of the actual false positive rate of the hashing itself.
In practical terms, that's still not very many. GPUs can do 2 GH/s for a simple hashing function. Your 44 bit password can be cracked in 4 hours by a single GPU, or in minutes by a cluster.
A large KDF helps, but damages user experience and again starts to become fragile if your threat model includes ASICs (a $3m expense or so for an attacker. That's a practical sum for many applications).
To put things in perspective, a CPU can do about 2^20 hashes per second. A $3m ASIC cluster (made entirely from scratch) can do about 2^52 hashes per second. It's obscenely asymmetric.
For high security accounts, you really want like 64 bits of entropy in your password plus a KDF, or you want 80 bits without a KDF.
KDFs have another major problem. If you forget a word in your password, and you also have a KDF, you have to fight your own KDF to discover that last word. You don't want that barrier.
edit: was off by a factor of 1000 in my ASIC math. $3m in ASICs can do about 2^52 hashes per second, not 2^42
Hashing hardware capability is typically measured in trillions per second (TH/s) so the math might be better using trillion instead of billion. As I understand it, the rental cost of 1 PH/s (which I think is one-thousand-trillion?) is about $10/hour. From that I think you could work out an actual cost to generate a collision!
To put things into perspective, let the Bitcoin network hashrate (double SHA256 per second) = B and the number of SHA1 hashes calculated in shattered = G.
B = 3,116,899,000,000,000,000
G = 9,223,372,036,854,775,808
Every three seconds the Bitcoin mining network brute-forces the same amount of hashes as Google did to perform this attack. Of course, the brute-force approach will always take longer than a strategic approach; this comment is only meant to put into perspective the sheer number of hashes calculated.
> The time needed for a homogeneous cluster to produce the collision would then have been of 114 K20-years, 95 K40-years or 71 K80-years
If I'm reading that correctly, 852 (71 * 12) K80 cards gets that down to a month, which sounds well within the reach of NSA et al.
Even getting it down to a day (71 * 12 * 30=25,560 cards) seems feasible. Assuming $10k per card ($5k launch price + doubled to account for supporting hardware), the upfront investment is around $0.25 billion, a figure that sounds plausible given, e.g., that the Utah data centre is budgeted at around $2 billion.
Edit: formatting fix. Also, this is of course assuming custom hardware designed for a specific hash function isn't employed.
Yeah, botched my numbers, sorry. I saw that the hash rate of the current Bitcoin network went up to 2^93 hashes per year, and then I managed to pretend 2^128/2^93 = 35, instead of 2^35.
With your numbers if humanity dedicated all its energy to brute forcing a 128/bit key for a year it would have a ~0.1% chance of finding it. I guess that's a pretty good argument that no one is going to even try it in the foreseeable future.
Right now the bitcoin network is calculating at about 500 GHash/second. Only 1 hash is needed to process an entire batch of transactions (a block). Well, technically it is 2 SHA hashes that are needed per block. So 499,999,999,998 of the hashes calculated in the next second will be wasted.
It gets worse. That is 500 GHash per second. Over the approximately 10 minutes between blocks, only two of those 300,000,000,000,000 hashes that were calculated will actually be used even.
Of course, there is a reason for this. Hashing to obtain a relatively unique result is called a "proof of work" and is the method that Bitcoin uses to ensure that the amount of currency issued occurs only at the levels specified in the source code. http://en.bitcoin.it/wiki/Proof_of_work So far, that method has been the only one found so far that works as the transaction processing system for a decentralized payment network.
Does it? At 50M TH/s (https://www.blockchain.com/en/charts/hash-rate) that's 10^8 TH/s, or 10^8.10^12 = 10^20 hashes per second. There's less than 10^5 seconds so surely that's only 10^25 per day. If I've messed up each of these numbers by an order of magnitude, that would leave it still well under 10^30.
Given the rate required for this its not a reasonable assumption. It's like saying Amazon sees sha256 collisions between S3 buckets. Just doesn't happen in practice.
With 8 characters, which is way below all recommendations and using only alphanumeric + the simple special chars on the keyboard you're looking at over 7 * 10^14 possibilities.
If you could do 100 million hashes per second (that seems to be possible with hardware looking at crypto stuff), the way I understand the setup you're still up against the 100100 iterations in the key derivation algorithm. So that's 7 * 10^19 hash calculations.
Even with the hardware to do 100 million hashes per second you're looking at nearly 23,000 years.
Let's hope you get a hit at 50% of the space (the expected average case). That's 11500 machine years with beefy GPU accelerated machine. So to bring this to a usable 5 years (and that's already pushing the expiration date of any creditcard you may find in the stolen vault) you'd need 2300 gpu accelerated machines running 24x7.
In AWS terms, with reserved discounts and everything you're going to spend roughly 60 million dollars cracking one vault.
100% bogus? I'm not sure what bad/incorrect statistics you are referring to since it's relatively straight forward to find.
The current target hash is "0x000000000000022FBE0000000000000000000000000000000000000000000000"
This means that to solve a block, you must find a SHA-256 hash of that block's transactions + nonce that hash to a value equal or below that target. Since the output of a SHA-256 hash is essentially random, the probability of finding a nonce that evaluates to hash at or below that target is roughly [target]/[possible sha256 outputs] or 3.51e60/2^256, or 3.034e-17. On average, that means it takes 1/3e-17 or 3.3e16 hashes per block. To calculate average hashes per second of the network, we look at number of blocks solved in the last x unit of time (if you want a 24 hour average, take the number of blocks in the past 24 hours). As of the time of this post, 170 blocks have been solved in those 24 hours. This implies an expected 24*3.3e16 or 8e17 hashes have been computed. Divide by 86400 (seconds in a day) and you get 9.26e12, or 9.26 TH/s. The site reports 6.5 TH/s, presumably because it uses a longer window than 24 hours (probably 7 days).
Just because it's a statistical average instead of the exact rate doesn't mean it's 100% bogus. If you want, you can use fairly standard statistical models to find an acceptable error margin.
Small note, but 3,000 trillion is 3 quadrillion, not 3 quintillion. Which is their total, over a significant amount of time.
The bitcoin network does over 3 quintillion (>3,000,000 trillion) hashes a second. So even if they were doing a significantly harder to compute hash -- they're still only a very small part of the computational power the bitcoin network is using.
So it's probably already more effective to attack wallets than join a mining pool.
Ed: Estimate of numbers --
Assuming that their hashrate was over 3 months (article says nearly a year, but they're also scaling), they had about 300 million hashes per second. Bitcoin had 3 million trillion hashes per second over the same period. So you're talking 1 to 10 billion in raw hashrate, and even with a generous challenge factor, bitcoin is using millions of times more compute power.
There were about 150 thousand bitcoins mined over that period, so 1 in 10 billion of that is 0.000015BTC.
Since they hit 3 in use accounts with the same compute effort, they almost certainly made more BTC attacking wallets with collisions.
Ed2: How much parasitic hashing --
If you figure the average active wallet has between 1 and 5 BTC (very high variance), and the wallet hash takes about 100x as long (over estimate), they made 3-15BTC vs 0.015BTC by attacking the network versus mining, or about 200-1000x as much.
Since colliders are themselves unlikely to collide (and thus competition doesn't starve out colliders), the system will only stabilize if 99%+ of miners drop out of the pool or the difficulty in finding a collision raises 1000x.
Given the sunk costs in dedicated mining rigs and that new hashes would be breaking, it seems like parasitic hashing will continue to be an issue.
On the plus side, only a one-in-a-million chance it wipes one of your accounts.
(Of course, a fluke collision with a high value account might create other problems.)
The numbers are: 9 petahashes/second (entire Bitcoin network [FTA]), and 20 petaflops/second (IBM Sequoia [1]). If you equate a SHA-2 hash with a floating point op, the ratio is 0.45, not 4,500.
>even the next generation of ASIC mining hardware (which will continue the exponential growth of worldwide hashing power) would require hundred or thousands of years (I don't know the specifics and can't be bothered to find the numbers with specificity), on average, to find a specific hash.
It would take much longer than that.
The current hashing power of the entire Bitcoin network is ~5 PH/s. If we assume it will increase 200x over the next generation of ASICs (this is unlikely), it will still only be ~1 EH/s. That's 1e18 hashes per second, or 3e25 hashes per year. Finding an input that hashes to a specific 2^256 bit hash would take, on average, 2e51 years. The universe is only 14e9 years old.
reply