Timeline for Accelerating SHA-1
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 10, 2019 at 10:57 | answer | added | user10496 | timeline score: 1 | |
| Jun 15, 2016 at 12:30 | history | edited | otus | CC BY-SA 3.0 |
add relevant tags
|
| Sep 27, 2011 at 6:25 | comment | added | fgrieu♦ | @Fixee: you can separate to some degree the cost of hashing and the cost of bringing the data to the caches, by benchmarking hashing repeatedly the same block of constant data. By varying that block size (say as powers of 2), you'll find that up to a thresold the throughput (in MiB hashed per second) grows with the block size, then drops rather abruptly, because cache misses come into play. The best block size in practice is probably markedly below that threshold. | |
| Sep 22, 2011 at 22:01 | history | tweeted | twitter.com/#!/StackCrypto/status/116995678038786048 | ||
| Sep 22, 2011 at 17:28 | comment | added | Thomas Pornin | @Fixee: it really depends on the hash function, the target architecture, the fine details of the cache management algorithm, the way the implementation works, and whatever else runs on the machine. From experience I have been, on average, happier with 8 kB buffers than with bigger or smaller buffers; which is why I suggest trying it out. | |
| Sep 22, 2011 at 16:37 | comment | added | Fixee | @fgrieu: Is there a way to see if I'm having cache misses and how much they're costing me? | |
| Sep 22, 2011 at 16:35 | comment | added | Fixee | @Thomas: reducing my buffer results in no difference in runtime; I'm not sure why you think L1 cache matters here since we process data exactly once (I'm running SHA1 over an 8GiB file). | |
| Sep 22, 2011 at 16:33 | vote | accept | Fixee | ||
| Sep 21, 2011 at 13:46 | comment | added | fgrieu♦ | @Fixee: as pointed by Thomas Pornin, hitting cache, rather than memory, is critical. That's a separate optimization from tree hashing (which is here to put multiple CPUs to good use). It is possible to hash a big chunk (much larger than caches) on one CPU with no cache miss between acquiring a buffer and hashing it; one needs to divide a chunk into suitably sized buffers, and hash a buffer while the next is brought in. If I/O must be sequential, you need to interleave the buffers into the chunks on different CPUs, and then the interleave factor (number of CPUs) affects the final result. Hairy. | |
| Sep 20, 2011 at 21:26 | answer | added | Fixee | timeline score: 4 | |
| Sep 20, 2011 at 20:51 | comment | added | Thomas Pornin | @Fixee: you may want to shrink the buffer a bit, down to, say, 8 or 16 kB. So that the buffer stays in L1 cache. Cache misses are the real performance killer. | |
| Sep 20, 2011 at 20:50 | answer | added | Thomas Pornin | timeline score: 9 | |
| Sep 20, 2011 at 20:47 | comment | added | fgrieu♦ | 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. | |
| Sep 20, 2011 at 17:23 | comment | added | Fixee | @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). | |
| Sep 20, 2011 at 17:08 | comment | added | Paŭlo Ebermann | Tree hashing is the way to go if you have large amounts of data and multiple cores available. | |
| Sep 20, 2011 at 16:57 | comment | added | fgrieu♦ | 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? | |
| Sep 20, 2011 at 16:56 | comment | added | Fixee | I have some latitude with the protocol... you're thinking to hash separately on multiple cores? | |
| Sep 20, 2011 at 16:52 | comment | added | Paŭlo Ebermann | Do you have a given protocol to implement, or can you change the protocol to make it faster (i.e. better parallelizable)? | |
| Sep 20, 2011 at 16:30 | history | asked | Fixee | CC BY-SA 3.0 |