Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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).

share|improve this question
    
Do you have a given protocol to implement, or can you change the protocol to make it faster (i.e. better parallelizable)? –  Paŭlo Ebermann Sep 20 '11 at 16:52
    
I have some latitude with the protocol... you're thinking to hash separately on multiple cores? –  Fixee Sep 20 '11 at 16:56
1  
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? –  fgrieu Sep 20 '11 at 16:57
1  
Tree hashing is the way to go if you have large amounts of data and multiple cores available. –  Paŭlo Ebermann Sep 20 '11 at 17:08
    
@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). –  Fixee Sep 20 '11 at 17:23
show 7 more comments

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
    
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?! –  Fixee Sep 20 '11 at 21:30
    
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. –  Samuel Neves Sep 21 '11 at 0:07
    
@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. –  Fixee Sep 21 '11 at 3:09
add comment

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.

Note: Although the rules allow it, I am in general opposed to people answering their own questions. I did so anyway here because 3-4 hours of web searches turned up answers that I thought were useful and seem to complement information already offered. I did not know any of this when I asked my question.

share|improve this answer
1  
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. –  j.p. Sep 21 '11 at 6:53
    
@jug: I did find that link, which is what led me to updating to the latest OpenSSL. Unfortunately, it was no faster. –  Fixee Sep 21 '11 at 17:11
    
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. –  j.p. Sep 22 '11 at 7:42
    
@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. –  Fixee Sep 22 '11 at 16:27
    
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. –  j.p. Sep 23 '11 at 8:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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