So I have an implementation where by we have an $8$-byte random input (entirely random, not user defined) which we hash with $\text{SHA256}$. The hash is shared with many parties to the point that we consider it is effectively public, so we are concerned with potential attacks to reverse the hash.

With this input, there are $1.8 \times 10^{19}$ hashes.

So my calculations for brute-force feasibility are done taking into account reported hash rates of bitcoin mining rigs and ASICs from:

https://en.bitcoin.it/wiki/Mining_hardware_comparison Current best $7,722,000$ MHash/s would take 27 days ($\frac{1.8 \times 10^{19}}{7722000000000 \times 60 \times 60 \times 24}$).

https://en.bitcoin.it/wiki/Non-specialized_hardware_comparison Current best $2,568$ MHash/s would take 227 years ($\frac{1.8 \times 10^{19}}{2568000000 \times 60 \times 60 \times 24 \times 365}$).

Also, I'm assuming that since bitcoin mining is $\text{SHA256}(\text{SHA256}(x))$, that either the times above could be roughly halved, or in the case of an ASIC which may not be flexible enough to do single hashing, a brute force attempt would simply target $\text{SHA256}(target_{hash})$ instead?

As for calculating the rainbow tables, I'm guessing at the basic level, each record would be $40$ bytes ($8$ byte input + $32$ byte hash), leading to $1.8 \times 10^{19} \times (8 + 32) = 7.2 \times 10^{20}$ bytes $= 720,000,000$ terabytes

I've made a number of brain farts in getting to these numbers, so I'm not entirely confident in their accuracy, and whilst I've read many articles on the related topics, my concern is that they all seem to target password cracking, and therefore don't assume that $8$ bytes input is actually $8$ bytes of entropy, especially since they often promote dictionary attacks.

Please can anybody confirm the accuracy of the above numbers and whether my methods are sound?

TL;DR: 64-bit entropy is nowhere near enough against a serious attacker.

Yes, you have calculated the worst case correctly.
Your second calculation isn't about rainbow tables, but about a full hash table.

Now for "how long can you stop a serious attacker" if you hash a fully random 8 byte string with SHA-256. If the attacker has enough money, they can design their own ASICs for this or ask nicely at companies like AntMiner to produce such ASICs. So assuming you pay a little more, you can probably get 1GHash/s for 1000 USD (AntMiner's S7 is at 4.7THash/s for 575USD + energy, network,... at the moment). So to break the hash using one miner (with 1THash/s), you need 213 days, whereas if you buy 427 of them, you can break the hash in at most half a day and expect to break it in a quarter of a day on average and at this point you wouldn't even be egligible to the highest discount they offer (at 500 pieces and more).

Rainbow tables should allow for quick breaks of the security and normally reduce the storage required to $2^{2n/3}$ and the computational requirements to $2^{2n/3}$ per look-up or more generally, given $2^m$ storage, the lookup time will be around $2^{2(n-m)}$.
If you want to defend against rainbow tables, salts are inevitable, because you need a full rainbow table per unique salt, which is computationally and storage-wise intense. As for the efficiency of rainbow tables, you need a full pass over the complete space (all $2^{64}$ values) to build the table. For the original (first) publication of rainbow tables, see "Making a Faster Cryptanalytic Time-Memory Trade-Off" by Oechslin (PDF)

  • Thanks for the advice and pointer on rainbow tables. After reading up on them, they definitely seem like the sweet spot I should be concerned about. How did you come to 213 days however? If I substitute 4.7Th/s in for 7.7Th/s as per OP, I'm getting 45 days. – DanH Apr 1 '16 at 14:51
  • Also, is there any calculation to understand the rainbow table time-space trade off, and what sort of space saving that would lead to? I believe salting totally takes rainbow tables out of the game though right? – DanH Apr 1 '16 at 14:56

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.