11
$\begingroup$

I have a program where computing SHA-1 is the bottleneck. This is using OpenSSL 1.0.0e on a 2.6Ghz 16-core Opteron where I get about 325MiB/s throughput. (SHA1 here is via Andy Polyakov's x86-64 assembly implementation using SSSE3.)

If I need to go faster, what makes most sense?

  • Use multiple cores
  • Use another implementation that's faster than default OpenSSL's
  • Buy a CUDA-based video card and leverage it
  • Buy a commercial hardware accelerator

I assume multiple cores won't help me because of overhead. I don't know much about CUDA other than it seems a popular choice for SHA-1 brute forcing, but unsure if it will help when I have to hash a large file. And I haven't had much luck looking for dedicated hardware accelerators (though I'm just starting to look).

Improve this question
$\endgroup$
12
  • $\begingroup$ Do you have a given protocol to implement, or can you change the protocol to make it faster (i.e. better parallelizable)? $\endgroup$
    – Paŭlo Ebermann
    Commented Sep 20, 2011 at 16:52
  • 1
    $\begingroup$ What is the size of the data in each hash? Are there several hashes running in parallel? How big is the typical data chunk passed for hashing? $\endgroup$
    – fgrieu ♦
    Commented Sep 20, 2011 at 16:57
  • 2
    $\begingroup$ Tree hashing is the way to go if you have large amounts of data and multiple cores available. $\endgroup$
    – Paŭlo Ebermann
    Commented Sep 20, 2011 at 17:08
  • 1
    $\begingroup$ @fgrieu: I'm hashing 128KiB at a time via SHA_Update (OpenSSL) in a tight read loop. I need a hash for the entire file, so I cannot run hash invocations in parallel (since SHA1 needs the previous chaining value to start computing the next). $\endgroup$
    – Fixee
    Commented Sep 20, 2011 at 17:23
  • 1
    $\begingroup$ Paŭlo Ebermann is right: tree hashing will let you leverage all your cores. You only need two levels. Define a chunk size (say 128kiB). Hash each chunk of the file with SHA-1; this will take most of the time, and (for a file over 2MiB) can be parallelized over the 16 cores. Then hash the hashes (in the order of the corresponding chunks in the file) with SHA-1. The final result is not, or course, the same as SHA-1 of the whole file, but this hash is demonstrably at least as secure. Your bottleneck might become moving the file data to the cores. $\endgroup$
    – fgrieu ♦
    Commented Sep 20, 2011 at 20:47

3 Answers 3

Reset to default
9
$\begingroup$

325 MB/s is already good, i.e. you will not get much more with another implementation. Also, SHA-1 is a sequential algorithm, so multiple cores or a GPU will not help you. Specialized hardware is probably your best bet to make SHA-1 faster.

(Also, if SHA-1 is the bottleneck then you are able to move data around faster than that, which is impressive; usually, network or hard disk bandwidth is the bottleneck, not hashing.)

If you can change the protocol, you could switch to another, faster hash function. I suggest RadioGatún[64]; there is an optimized implementation (in C) in sphlib. It is faster than SHA-1 (more than 660 MB/s on an Intel Core2 clocked at 2.4 GHz). RadioGatún[64] is not actively supported anymore but it did receive some public analysis, and it should not be weaker than SHA-1 anyway.

To benefit from multiple cores, you can use tree hashing, as @Paŭlo suggests. It is not that easy to get right (I mean, if you still want security) so I would advise using a hash function for which a tree hashing mode has already been detailed by competent cryptographer. This points to Skein, a current candidate for the upcoming SHA-3 standard. The "tree mode" is not part of "the Skein for SHA-3" so it was not thoroughly investigated, but at least it was designed by generally smart people who know their trade; and Skein itself is still a "recent design"; but it is still better than SHA-1, which has known weaknesses.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thomas: the authors of the paper I cite in my answer claim that a GPU does help. But they talk about "SSL flows" so perhaps they are inducing parallelism this way?! $\endgroup$
    – Fixee
    Commented Sep 20, 2011 at 21:30
  • 1
    $\begingroup$ In an SSL server, you are serving many independent (parallel) clients simultaneously...there's plenty of coarse-grained parallelism to explore there. Not sure whether that is your case. Note that you can also explore SIMD (XMM, soon YMM) registers to perform 4 (resp. 8)-way SHA-1, along with multiple cores/GPU. $\endgroup$
    – Samuel Neves
    Commented Sep 21, 2011 at 0:07
  • $\begingroup$ @Samuel: I'm processing a single incoming stream arriving at 5Gbps from the network and I'm currently bottlenecked by SHA-1 at 2.6Gbps; you're right that SIMD is useful: the XMM and YMM registers are part of the SSE(1-4) instructions which are already used in the OpenSSL code. $\endgroup$
    – Fixee
    Commented Sep 21, 2011 at 3:09
4
$\begingroup$

For free software-based solutions on an x86_64, OpenSSL is the best around. Intel's IPP is purported to be 20% faster, and it's software-only, but it's not free (about 200USD, or 80USD for the academic version) and you have to fill out a form saying you're not from N. Korea, etc.

There are hardware accelerators in the form of SSL cards/chips, but are somewhat pricy. Although SHA-1 is fundamentally serial (ie, you need the chaining value of the prior block before you can compute the chaining value for the next block), there is instruction-level parallelism (which is what is exploited by the SSSE3-based software implementations in OpenSSL and IPP). CUDA-based implementations can be quite fast compared to IPP. See the recent paper in NSDI, for example.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Do you also find the link software.intel.com/en-us/articles/… ? OpenSSL uses this improvement starting with Version 1.0.1, as far as I understood. So you should consider updating to a newer version of OpenSSL. $\endgroup$
    – j.p.
    Commented Sep 21, 2011 at 6:53
  • $\begingroup$ @jug: I did find that link, which is what led me to updating to the latest OpenSSL. Unfortunately, it was no faster. $\endgroup$
    – Fixee
    Commented Sep 21, 2011 at 17:11
  • $\begingroup$ Too bad. As currently Intel processors are quite a bit faster than AMD processors when processing only one thread, you might consider them (even a dual-core) as an alternative in case a hardware solution is too expensive and the change of protocols discussed in the comments to your question can't be done. $\endgroup$
    – j.p.
    Commented Sep 22, 2011 at 7:42
  • $\begingroup$ @jug: I've never heard this before (that Intel is quite a bit faster on a single core)... can you point me at a reference for this? I'd like to see if switching hardware would help. $\endgroup$
    – Fixee
    Commented Sep 22, 2011 at 16:27
  • 1
    $\begingroup$ Sorry, I have to correct myself. I just found benchmark results that show that for the SHA1 AMD and Intel platforms have the same speed when running at the same clock speed. My info came mostly from reading regularly a German computer magazine [c't](www.ct.de). Periodically they benchmark current CPUs and write articles describing their design. Most times it's about smaller systems than yours (PCs), but they also write about bigger systems (>=4 CPUs) where AMD is still able to compete. Lately Intel was far ahead in most tests, but apparently not in SHA1. $\endgroup$
    – j.p.
    Commented Sep 23, 2011 at 8:36
1
$\begingroup$

I have a program where computing SHA-1 is the bottleneck... If I need to go faster, what makes most sense?

I believe your are using OpenSSL's sha1-586.pl written by Andy Polyakov. Andy's code is likely running around 6.0 or 7.0 cycles per byte.

Since about mid-2014 you can buy an Intel Goldmont or Goldmont+ machine, like here. SHA-1 runs around 2.8 cycles per byte. I believe the latest AMD Ryzens include SHA-1 instructions, but I don't have one and don't know the benchmark results.

Since about 2012 you can buy an ARM Aarch64 board that has crypto extensions. SHA-1 runs around 2.5 cycles per byte on Cortex A-53's, which is the lower-end ARMv8 machine. The higher-end Cortex A-57's will probably perform a little better, around 1.5 to 2.0 cycles per byte.

You might also be interested in SHA Intrinsics on GitHub. It provides reference implementations for SHA using x86, Aarch64 and PowerPC intrinsics. Andy's ASM will run faster, but the intrinsics are a little easier to use since you don't have to do the Cryptogams SHA port.

Improve this answer
$\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.