Optimize our OpenCL PBKDF2-HMAC-SHA512 code

[kholia]

Our current speed,

$ ../run/john --format=PBKDF2-HMAC-SHA512-opencl --test 
Device 0: GeForce GTX 1050 Ti
Benchmarking: PBKDF2-HMAC-SHA512-opencl, GRUB2 / OS X 10.8+ [PBKDF2-SHA512 OpenCL]
Speed for cost 1 (iteration count) of 1000
Raw:	72817 c/s real, 72817 c/s virtual, GPU util: 100%

Hashcat's speed,

$ ./hashcat --optimized-kernel-enable -b -m 12100 -w 4
hashcat (v5.1.0-39-gdbbba1fb) starting in benchmark mode...

Hashmode: 12100 - PBKDF2-HMAC-SHA512 (Iterations: 999)
Speed.#1.........:   130.8 kH/s (330.53ms) @ Accel:128 Loops:124 Thr:512 Vec:1

It seems that our OpenCL PBKDF2-HMAC-SHA1 stuff is solid but our PBKDF2-HMAC-SHA512-opencl stuff isn't the best.

Hopefully, I am comparing comparable things here.

@magnumripper This will require your help.

[magnumripper]

I had a look, it's just as optimized as the other ones. However, SHA-512 is 64-bit while all current GPUs are 32-bit. So the compiler has to make 32-bit code for all 64-bit ops, making it half as fast - best case. I recall Atom mentioned he found a nice trick to make SHA-512 significantly faster but that was before they went open source so I have no idea what it was. Perhaps we should study their kernels!

[kholia]

In pure dictionary mode, hashcat's speeds is around 97,000 c/s.

[solardiz]

As I recall, our sha512crypt-opencl is actually on par or even slightly faster than hashcat's equivalent as of the last time I tested. I think the optimizations to 64-bit rotate that I introduced a couple(?) of years ago are on par with whatever alternative hashcat had. We need to re-do this comparison at sha512crypt-opencl on both the Titan X Maxwell and @kholia's 1050 Ti, as well as possibly on other GPUs, and be also comparing speeds at PBKDF2-HMAC-SHA512-opencl at the same time. Also compare actual cracking runs with same-length mask mode for both tools (can choose length 7 try match hashcat's banchmark mode's test vector).

[magnumripper]

the optimizations to 64-bit rotate that I introduced a couple(?) of years ago

What optimizations was that? I only see this, specific for AMD (the one actually used now is slightly more complicated to work around some AMD bug when n is a multiple of 8):

#define ror64(x, n)      ((n) < 32 ? \
	(amd_bitalign((uint)((x) >> 32), (uint)(x), (uint)(n)) | \
		((ulong)amd_bitalign((uint)(x), (uint)((x) >> 32), (uint)(n)) << 32)) \
	: \
	(amd_bitalign((uint)(x), (uint)((x) >> 32), (uint)(n) - 32) | \
		((ulong)amd_bitalign((uint)((x) >> 32), (uint)(x), (uint)(n) - 32) << 32)))

[magnumripper]

the one actually used now is slightly more complicated to work around some AMD bug when n is a multiple of 8

Apparently that workaround is only used in some formats. Since we don't seem to see any bug I'm going to remove it. There are rotates with multiples of 8 in SHA-512.

[solardiz]

Hmm, yes - it was probably only this one for AMD. As I recall, we determined that on NVIDIA the funnel shift instructions are used for rotate() by the compiler, so no tricks in our code are needed. (We only had to use inline asm for them on NVIDIA in md5crypt, where the uses are trickier than for a rotate.)

As to removing the workaround for multiples of 8, I'd find john-dev postings where we discussed it first. It might still be relevant. I hear you regarding us not using it consistently anyway, though.

[magnumripper]

I'm pretty sure there were no john-dev postings, I recall I added it because Atom mentioned it somewhere (and was referring to ancient drivers IIRC). So I actually never saw the bug and since the other formats (eg. Claudio's) haven't had the problem I'm pretty sure we're OK without it.

[solardiz]

There were john-dev postings, see this and the rest of that thread:

https://www.openwall.com/lists/john-dev/2015/10/19/2

The thread also mentions PBKDF2-HMAC-SHA512-opencl being unexpectedly slower than sha512crypt-opencl (perhaps in terms of SHA-512s per second).

Also see #1840.

[magnumripper]

Oh, right. Well, we'll see if we hit a problem somewhere - then perhaps we can re-apply the workaround selectively.

[magnumripper]

My Macbook's AMD is faster with JtR (not even using bitalign at all) than with hashcat:

Device 2: AMD Radeon Pro 560 Compute Engine
Benchmarking: PBKDF2-HMAC-SHA512-opencl, GRUB2 / OS X 10.8+ [PBKDF2-SHA512 OpenCL]... DONE
Speed for cost 1 (iteration count) of 1000
Raw:	30624 c/s real, 3276K c/s virtual

* Device #3: AMD Radeon Pro 560 Compute Engine, 1024/4096 MB allocatable, 16MCU
Speed.#3.........:    25759 H/s (70.61ms) @ Accel:32 Loops:15 Thr:256 Vec:1

[magnumripper]

Super's Titan X (with banned-old driver so using --force) is much faster with hashcat though:

Hashmode: 12100 - PBKDF2-HMAC-SHA512 (Iterations: 999)

Speed.#7.........:   302.9 kH/s (58.22ms) @ Accel:64 Loops:31 Thr:384 Vec:1

Device 6: GeForce GTX TITAN X
Benchmarking: PBKDF2-HMAC-SHA512-opencl, GRUB2 / OS X 10.8+ [PBKDF2-SHA512 OpenCL]... DONE
Speed for cost 1 (iteration count) of 1000
Raw:    177124 c/s real, 175542 c/s virtual, GPU util: 99%

I can see they do a few things using 32-bit halves but nothing revolutionary or that I think should matter much (perhaps it does though, but that would be extremely poor compiler/optimizer performance by the runtime). The main functions, Maj, Ch and sigmas, are standard stuff. I have no idea why they are so much faster, it almost looks like we do a lot of redundant work somewhere, by mistake. But that should show up on my Macbook's AMD as well.

[magnumripper]

Latest hashcat & jumbo

hashcat (v5.1.0-797-g5a1d929) starting in benchmark mode...
* Device #1: gfx900, 4048/8176 MB allocatable, 64MCU
* Device #4: GeForce GTX 1080, 2029/8119 MB allocatable, 20MCU
Hashmode: 12100 - PBKDF2-HMAC-SHA512 (Iterations: 999)

Speed.#1.........:   352.0 kH/s (86.10ms) @ Accel:128 Loops:62 Thr:64 Vec:1
Speed.#4.........:   341.8 kH/s (52.37ms) @ Accel:256 Loops:124 Thr:32 Vec:1

Device 1: gfx900 [Radeon RX Vega]
Benchmarking: PBKDF2-HMAC-SHA512-opencl, GRUB2 / OS X 10.8+ [PBKDF2-SHA512 OpenCL]... DONE
Speed for cost 1 (iteration count) of 1000
Raw:    324435 c/s real, 8192K c/s virtual

Device 4: GeForce GTX 1080
Benchmarking: PBKDF2-HMAC-SHA512-opencl, GRUB2 / OS X 10.8+ [PBKDF2-SHA512 OpenCL]... DONE
Speed for cost 1 (iteration count) of 1000
Raw:    254015 c/s real, 254015 c/s virtual, GPU util: 100%