0
$\begingroup$

It's well-known that computing lots of hash functions (like SHA1) in parallel involves the use of GPUs in most cases. However, when doing something serially, such as computing sha1(sha1(sha1(...sha1(x)))) parallelism would not seem to be that useful.

I ran into this very problem recently, and I started running a program on my Mac laptop using python, at about 270k hashes/sec. Moving to a C implementation, I was able to get 750k hashes/sec. And strangely, using VirtualBox with Kali and the same C implementation, about 1.3m hashes/sec.

(There is some discussion one can find online regarding why a Linux version of SHA1 code might be faster than a Mac OS version, even when the former is through a virtualization layer, but this is beyond the scope of my question.)

Question: If I want to compute SHA1 as fast as possible and parallelism is not helpful, what's the fastest way to do it? I suppose the answer involves special hardware? Or buying a desktop with a good CPU and overclocking?

$\endgroup$
1
  • $\begingroup$ Depending on the number of iterations and the type of input, there's supposedly an optimization that ASICs can use involving extremely fast and compact approximate adders that deterministically fail on certain input. I believe some bitcoin ASICs do this as an optimization. If the number of iterations is particularly high though, it would greatly reduce the accuracy since a single approximate adder being fed input it cannot handle would taint the rest of the computation. $\endgroup$
    – forest
    Jun 28 '18 at 2:44
5
$\begingroup$

There is no known mathematical trick to compute iterates of SHA-1. Getting high throughput in software involves:

  • Use of parallelism if at all possible; that is, if starting from multiple points. Depending on why one computes iterates of SHA-1 that is possible, or not.

  • Specializing the code to compute the hash of a 20-byte message obtained as as hash, removing endianness conversion and padding in the main iteration. That is, to compute an $n$-iterate of a message per SHA-1:
    • hash the message per normal SHA-1;
    • convert the (bytestring) result to 5 native-endian 32-bit words, yielding the current iterate;
    • repeat $n-1$ times:
      • perform a single SHA-1 round, starting from the SHA-1 Initialization Vector 0x67452301 0xEFCDAB89 0x98BADCFE 0x10325476 0xC3D2E1F0, hashing the 16-word block consisting of the 5 words of the current iterate, 9 zero words, the word 0x000000A0 (for 160 bits), and a zero word; yielding the new value of the current iterate, manipulating 32-bit (or wider) quantities only;
    • convert the current iterate to (bytestring) result.

  • Coding and micro-optimizing carefully, perhaps in assembly. That a 73% throughput increase was achievable merely by changing compiler is telling that this counts. Among techniques likely to help:
    • Fully unroll the 80 rounds
    • Take advantage of constant words in IV and 16-word block hashed
    • (b&c)|((~b)&d) is ((b^c)&d)^c and that might help (or not) for rounds 0..19
    • (b&c)|(c&d)|(d&b) is ((d|b)&c)|(d&b) and typically helps for rounds 40..59
    • Schedule and choose what goes into what register wisely.

Update: on selected CPUs, there are special instructions; see this Intel whitepaper and reference code.


For the ultimate in speed, there's FPGA; an ASIC would be even faster, but wasteful.

$\endgroup$
2
$\begingroup$

Why would you say parallelism isn't relevant. When iterating hash functions we can't parallalize a single chain but we can calculate multiple chains in parallel. We can use CPU threads, GPU threads, SIMD or bitslicing to achieve this parallelism. In most scenarios you do not want to build one very very long chain.

If you really need just a single chain you will want a powerfull CPU, which CPU is tricky as there could be various optimization which take advantage of various procrssor specific. In general Intel provide the best single thread performance. Overclocking will help, for a given CPU your hashinh speed will scale very near linearly with clock speed.

$\endgroup$
3
  • $\begingroup$ I want to compute the length of the tail and loop of a rho starting at a specific point and iterating on SHA1(). I am currently using Brent's algorithm (en.wikipedia.org/wiki/Cycle_detection) but looking for ways to go faster in the hash-function eval step. Suppose I start at point '000...0' and iterate SHA1() looking for a cycle... how can parallelism help? $\endgroup$
    – Fixee
    Jun 27 '18 at 6:09
  • $\begingroup$ If you are looking for the length of a cylce from a single point I'm afraid you are indeed out of luck, not only regarding parallelism but even worse, the cycle length is expected to be 2^80 so I don't consider this viable. $\endgroup$
    – Meir Maor
    Jun 27 '18 at 6:19
  • $\begingroup$ I'm doing cycle detection on a prefix of the SHA1() digest that is within reach. Suppose I'm looking at just the first half of the digest and iterating on that. Then the expected cycle-length is $2^{40}\cdot\sqrt{\pi/8}$ which is doable but will take a while $\endgroup$
    – Fixee
    Jun 27 '18 at 6:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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