41
$\begingroup$

I know that Graphics cards are faster at solving algorithms like SHA-256 because of the many builtin processors, but are there Algorithms that take actually longer on a Graphics card than on a modern consumer CPU (Amd/intel)?

$\endgroup$
  • 2
    $\begingroup$ AES possibly, if the CPU has an AES accelerator. Same for the random number generator, but that's more an issue of entropy. $\endgroup$ – Maarten Bodewes Oct 1 '17 at 20:17
  • 10
    $\begingroup$ Actually, just about any problem where parallelism doesn't help; an individual process on a GPU is considerably slower than a CPU; hence if having multiple GPUs doesn't speed things up, the CPU will be naturally faster... $\endgroup$ – poncho Oct 1 '17 at 20:21
  • $\begingroup$ see scicomp.stackexchange.com/questions/943/… $\endgroup$ – gusto2 Oct 1 '17 at 20:45
  • 2
    $\begingroup$ It's generally accepted that to make things difficult for GPUs, memory intensive algorithms are the way to go due to memory limitations on GPU based devices. Have a read about scrypt: en.wikipedia.org/wiki/Scrypt $\endgroup$ – Daniel Lane Oct 2 '17 at 16:46
  • $\begingroup$ @poncho To expand on this: Even if there are many parallel parts that could in theory be executed at the same time, GPUs have a hard time with diverging control flows. Due to the way they work, they would have to linearize the execution of each different branch which could result in a total linearization (as if there was only one thread) of all execution. So if you have an algorithm with many branches where both outcomes are about equally likely... It isn't as bad as it sounds above, because the architecture has developed but it will lead to a significant slowdown. $\endgroup$ – Nobody Oct 3 '17 at 8:49
65
$\begingroup$

This specific situation is a central part of the analysis of password hashing functions. Indeed, for hashing a password, we want a function which is:

  1. slow in a tunable way;

  2. such that the most cost-effective hardware for evaluating many instances of the function is the hardware that the expected defender will use, i.e. a "normal PC".

"Cost" here means actual money. For the attacker, it does not matter whether he will need 10, 100 or 1000 units of whatever hardware he'll use; only the total cost will be necessary. It can be argued that with modern hardware, in particular GPU, the majority of the budget for crunching passwords will be spent on electrical power, not on purchasing the hardware. Therefore, it makes sense to define the cost of the function with regards to the energy consumed by its computation, on both general-purpose CPU, and various GPU.

The bcrypt password hashing function appears to be indeed such a function, that is more expensive (energy-wise) to compute on a GPU than on a CPU. The bcrypt feature that makes it so is that it is organized around an internal 4 kB array of data which is continuously read and modified in a way which is not amenable to shortcuts, and at pseudorandom addresses. GPU are not well-equipped for that; if you try to implement bcrypt on a GPU, you will experience considerable contention for data access, and most of the GPU cores will be stalled at any time (and such a stalled core still consumes power).

The Password Hashing Competition was organized to define new functions that fulfill a larger goal, namely to not only be more CPU-friendly than GPU-friendly, but also to "hold the line" to some extent when facing attackers with FPGA or custom ASIC. The main tool used by most candidates was again RAM, but more of it; the underlying assumption is that modern PC (servers, desktop systems...) contain a thoroughly optimized memory bus that cannot be operated at a substantially lower cost by custom hardware. It is unclear how far that assumption holds.

One of the PHC candidates, called Makwa (which I designed), did not use RAM but modular arithmetics. This is not expected to fare well against FPGA and ASIC, but, for GPU, it appears to behave well: according to my analysis, costs on CPU and GPU appear to be roughly on par for a 2048-bit modulus, and larger moduli benefit the CPU more than the GPU.

To sum up, both bcrypt and Makwa seem to be valid answers to your question, and they do so through quite different means.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ On the other hand, an FPGA may have a few hundred independent 4k memories. $\endgroup$ – user253751 Oct 2 '17 at 23:31
  • 3
    $\begingroup$ Yes, that's the reason why most PHC candidates included options to use a lot more RAM (megabytes, if not gigabytes). The 4 kB buffer is good against GPU, not against FPGA. $\endgroup$ – Thomas Pornin Oct 3 '17 at 12:58
6
$\begingroup$

Even if a small part of the encryption algorithm can be parallelized e.g 10% and the speedup of this part of the algorithm that benefits from GPU is 20fold then GPU version will appear 10% faster than the CPU version.

Mind that a good implementation on GPU will take advantage from both worlds (CPU+GPU).

So it will be very strange for someone to build a GPU only solver.

A good place to start your search would be a memory hard implementation. The most popular is scrypt. It is designed to be far more secure against hardware brute-force attacks than alternative functions such as PBKDF2 or bcrypt. Also the winner of Password Hashing Competition (PHC) is Argon2.

PBKDF2 has one weakness (# of iterations) which makes brute-force attacks using application-specific integrated circuits or graphics processing units relatively cheap. The bcrypt key derivation function requires a larger amount of RAM (but still not tunable separately, i. e. fixed for a given amount of CPU time) and is slightly stronger against such attacks.

So the main advice is to go for Scrypt or Argon2i (better vs all other).

Argon2 was designed to be resistant against brute-force attacks using specialized hardware, such as GPUs, ASICs, or FPGAs. In July 2015, it was announced as the winner of the Password Hashing Competition.

Didnt last long to see a good implementation. Here is a GPU POC for Argon2.

Performance ✓

The CUDA implementation can reach about 40-60 GiB/s (divide by time cost * memory cost * 1024 B to get hashes per second) on an NVIDIA Tesla K20X. For comparison, a fast Intel Xeon processor can only reach about 10 GiB/s.

So I dont think there is an algorithm that can run slower on GPU if the solver implementation is programmed using common sense.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Those GPU numbers for Argon2 are in fact not evidently discouraging. Even though the question here is formulated as "algorithms slower on GPU than CPU," the point of memory-hard functions like Argon2 is to limit the specialized adversary's advantage. If the GPU can calculate Argon2 only 4-6 times as fast as the CPU, that's not bad at all—particularly considering that this GPU costs $3,500 USD. $\endgroup$ – Luis Casillas Oct 3 '17 at 22:14
  • 2
    $\begingroup$ I think that GTX1080 has almost the same performance and is affordable $\endgroup$ – Panos Kal. Oct 4 '17 at 2:32
1
$\begingroup$

A common approach, taken by Ethereum, for instance, is to use algorithms that are memory hard.

While GPU may contain thousands of processors, the amount of memory available does not increase in the same proportion. If the algorithm is such that the memory is absolutely required, this restricts the number of cores that could run efficiently in parallel.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Reading the FAQ does not quite support this. Ether mining does need a lot of RAM, but the intention seems to be to protect small miners by making ASICs and FPGAs inefficient. They claim GPUs work well, and the memory requirements are just low enough to make it practical. $\endgroup$ – James Hollis Oct 3 '17 at 20:48
0
$\begingroup$

GPUs have slower clock rates than CPUs, but many more threads with the restriction that large groups of threads need to execute the same code.

So an algorithm that is supposed to run faster on a CPU will have linear data dependencies so the GPU can run only a single thread (and all other threads execute NOPs) and use only one lane in the vector — then the lower clock rate takes effect.

You can also further pessimize GPU performance by making the arithmetic operations data dependent. GPU compilers will then try to generate speculative execution for all operations, followed by a SELECT instruction to use only the result from the winning branch.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ How would your "introduce linear data dependencies" approach work? Brute-forcing password hashes works by letting each core hash a different password. By the very nature of this approach there are no data dependencies between cores, no matter which hash function is used. $\endgroup$ – Dreamer Oct 2 '17 at 12:31
  • 2
    $\begingroup$ @Dreamer The question is still very generic. Although it mentions a hash says nowhere that the answer is about brute forcing passwords. Take for instance (AES-)CBC, which is data dependent. That's an algorithm that would almost certainly be faster on a CPU if the fastest implementations are compared. AES-CBC cannot be paralleled for a single message. $\endgroup$ – Maarten Bodewes Oct 2 '17 at 17:20
  • $\begingroup$ That would be AES-CBC encryption of course, sorry about this followup, but the distinction with decryption must be made. $\endgroup$ – Maarten Bodewes Oct 3 '17 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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