Date: Thu, 5 Apr 2012 16:44:01 +0400 From: Solar Designer <solar@...nwall.com> To: john-dev@...ts.openwall.com Subject: Re: fast hashes on GPU myrice - On Thu, Apr 05, 2012 at 04:19:49PM +0800, myrice wrote: > Yes, I using a much larger max_keys_per_crypt. ( 128*KEYS_PER_CRYPT, > THREADS: 512, BLOCK: 32, sm_13) > On GTX580, Before: > Benchmarking: Mac OS X 10.7+ salted SHA-512 [CUDA]... DONE > Many salts: 70254K c/s real, 70964K c/s virtual > Only one salt: 27262K c/s real, 27262K c/s virtual > > After: > Benchmarking: Mac OS X 10.7+ salted SHA-512 [CUDA]... DONE > Many salts: 72673K c/s real, 72673K c/s virtual > Only one salt: 27439K c/s real, 27698K c/s virtual The only change was an increase of max_keys_per_crypt by a factor of 128, correct? > Enlarge either MAX_KEYS_PER_CRYPT or BLOCK size will reduce the > performance. Are you saying that increasing these values _further_ (beyond 128x) reduces performance? If so, the reason is probably that the keys no longer fit into the same cache level on the CPU. This is also why the salts trick discussed before does have potential for a little bit of speedup (with a lower max_keys_per_crypt then, to fit in a smaller and faster CPU cache) compared to an increased max_keys_per_crypt. Similarly, the reduced work set size on GPU (N passwords + M salts instead of N*M passwords for comparable total processing time per call) may allow for the use of a faster memory type on GPU. So the salts trick is worth revisiting once you feel you're done with easier optimizations. > I think it is a lot of data transfer that takes time. Of course transferring more data takes more time, but this is irrelevant to the slowdown with larger (too large) max_keys_per_crypt because the relative data transfer sizes per password hashed remain the same. I've provided my guess as to the actual cause of the slowdown above. What are you planning to do next, for XSHA512 or/and for other aspects of the fast hashes project? Here are some possible sub-tasks: 1. Work with magnum to get your code written so far into magnum-jumbo. (I strongly recommend that you take care of this first.) 2. Try to optimize XSHA512 further by optimizing the SHA-512 stuff in it (e.g., get rid of the init/update/final functions). 3. Try to optimize XSHA512 further by storing/caching the salts in GPU as discussed. 4. Try to optimize XSHA512 further by storing/caching the loaded hashes in GPU, so that you can merge cmp_all()'s on-GPU code into crypt_all()'s and avoid the call to GPU in cmp_all(). With very large max_keys_per_crypt this won't matter (the calls are infrequent anyway), but this change may result in the optimal max_keys_per_crypt value becoming a little bit lower (you'll need to re-tune it), which may improve CPU cache usage (resulting in a little bit of speedup). 5. Try to support longer passwords without a significant slowdown when the actual passwords being tested happen to be short. Right now, we have to decrease PLAINTEXT_LENGTH to achieve decent speed for the single-salt case, but this is a nasty limitation for actual use of such a build of John (another build needs to be used when testing of longer passwords is desired). There are ways to keep the data transfers to GPU smaller most of the time while allowing for longer passwords in the rare cases when those are present. 6. For correctness, implement computation of bytes 9-64 of the hash value in cmp_exact(). You'll keep BINARY_SIZE at 8, but in the rare cases when the 8 bytes match and cmp_exact() is called, you re-decode the ASCII string, compute the full 512-bit hash value, and compare these two 512-bit values. You may perform this computation on CPU (just use OpenSSL calls). 7. Proceed to implement XSHA (similar to XSHA512, but based on SHA-1). Since these hashes are a lot faster to compute on GPU, they will highlight the various bottlenecks much better (and will make the need for dealing with those more pressing). (By the way, XSHA should be added to your proposed GSoC timeline.) 8. Implement XSHA512 (and then XSHA) in OpenCL as well. Try it on AMD GPUs. This may also highlight the bottlenecks better (if run on a card like 7970, which should be about 3x faster than GTX 580 at SHA-1). (Yes, it is desirable that you get a fast AMD card as well.) 9. Since XSHA512 and XSHA use only a single instance of SHA-512 or SHA-1, it should be possible to reverse the last few rounds of the computation (perform the reverse in binary() on CPU when loading the hashes). Then you have fewer rounds to compute at runtime (on GPU). (BTW, this optimization will apply to CPU-only implementations as well, so we'll need it there as well, but we'll have to move away from OpenSSL's to our own code for SHA-512 and SHA-1 first. If you show how many rounds may be reversed and how in your GPU code, someone else on our team may do it for CPU, or vice versa.) Of course, there will be many more sub-tasks (for the summer if we proceed to work under a summer program), but the above are some that I think you can work on now. How does this sound to you? Thanks, Alexander
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.