6
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ I think you are right on the consequence of bitcoitn mining using SHA256d, which performs SHA-256, then SHA-256 on the result. Also, the expected effort is to hash only $2^{63}$ values, and it's customary to quoted the expected attack time. $\endgroup$
    – fgrieu
    Nov 13, 2020 at 12:01

2 Answers 2

5
$\begingroup$

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)

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – DanH
    Apr 1, 2016 at 14:51
  • $\begingroup$ 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? $\endgroup$
    – DanH
    Apr 1, 2016 at 14:56
0
$\begingroup$
  1. Mining ASIC's is not suitable for SHA256 brute-force/rainbow tables, they fixed by initial silicon design only for bitcoin double-sha256 mining. They drop 10^9 non-suitable hashes internally (even dropping not finished rounds), just to provide 1 per fix matching criteria
  • hash should start from 0x0000000000xxx the only suitable solution for final block
  • mining ASIC's also has very poor slow speed bus link for external communications, in most cases i2c - its absolutely enough for mining, but just downloading 1s of mining ASIC's work in case of brute-force will takes days-weeks even at 4x100Gbps interfaces

ASIC's are fast, but if you would like to redesign then, add more memory, PCI-e bus - this will require more complex design, PCIe/RAM IP cost a lot of $$$ - this will make ASIC's for bruteforce in 100-1000x more high cost device and in most cases doesn't worth it.

just forget about using AntMiner, Cannnan, Bitfury, custom device design take year+ & will cost x millions$ per uniq design. as option you may ask IC design studio's like Innosilicon, price will be higher - terms will be longer 1.5-2+ years, still require xx millions of investments, but this may works.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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