32
$\begingroup$

I had heard that although it's easy to implement message digest functions like MD5, SHA-1, SHA-256 etc. in CUDA (or any other GPU platform), it is impossible to implement bcrypt there.

bcrypt is different from these hash functions, in that Blowfish is a block cipher, and in order to produce a one way hash a "feed back" is used.

I am not too familiar with the GPU platforms. Does anyone know if bcrypt can be ported to a GPU and if not, why?

$\endgroup$
1
  • 10
    $\begingroup$ For a moment I misread "Cuda" as "Cuba" and thought this was an encryption import problem. $\endgroup$
    – Joe Z.
    Jan 27, 2013 at 21:32

2 Answers 2

34
$\begingroup$

It is not impossible, only harder to implement efficiently. This is because of RAM. In a GPU, you have a number of cores which can do 32-bit operations. They will run at one operation per cycle and per core, as long as they operate on their respective registers. RAM access, however, is more troublesome. Each group of cores has access to a small amount of shared RAM, and all cores can read and write the GPU main RAM, but there are access restrictions: not all cores can read from or write to RAM simultaneously (constraints are stricter for main RAM).

Now bcrypt is a variant of the Blowfish key scheduling, which is defined over a table (a few kilobytes) which is constantly accessed and modified throughout the algorithm. Due to the size of the table, each core will have to store it in the GPU main RAM, and they will compete for usage of the memory bus. So bcrypt will run -- but not with full parallelism. At any time, most cores will be stalled, waiting for the memory bus to become free. This comes from the type of elementary operation bcrypt consists in, not from the fact that bcrypt is derived from the key schedule of a block cipher.

For SHA-1 or SHA-256, computation entirely consists in 32-bit operations on a handful of registers, so a password cracker will run without doing any memory access at all, and full parallelism is easily achieved (I did it on my GeForce 9800 GTX+, and I got about 98% of the theoretical maximum speed with a straightforward unrolled SHA-1 implementation).

For details on the programming model in CUDA, have a look at the CUDA C Programming Guide. Also, the author of bcrypt now proposes scrypt (edit: actually that's not the same person; the author of scrypt is Colin Percival, while bcrypt has been designed by Niels Provos and David Mazières), which is even heavier on the memory accesses, exactly so that implementation is hard on GPU and FPGA.

$\endgroup$
12
  • 1
    $\begingroup$ scrypt is really cool! What do you think of using memory-hard algorithms for key derivation and password storage? If I am not mistaken PBKDF2 is operation-hard and is there for is optimal for cracking with a GPU or FPGA. $\endgroup$
    – Rook
    Aug 13, 2011 at 7:37
  • 1
    $\begingroup$ So a special purpose hardware implementation with its own 4 KB of (fast) memory per core would be good for bcrypt, wouldn't it? (Not for scrypt, of course.) $\endgroup$ Aug 13, 2011 at 15:57
  • $\begingroup$ @Rook: what we want is a password processing algorithm which is as slow as possible for the attacker, and as fast as possible for the "honest user". So it makes sense to optimize it for what the honest user will use, and that's a PC (or similar) with a general purpose CPU which is quite good at accessing lots of RAM. So yes, memory-hard algorithms are a good idea -- until one of your target systems is a memory-constrained embedded system, of course. $\endgroup$ Aug 13, 2011 at 16:06
  • 3
    $\begingroup$ @Paulo: yes, special purpose hardware with fast embedded RAM blocks should be efficient for bcrypt. Newer FPGA (e.g. the Virtex 5 from Xilinx) have such RAM blocks; it is a reason why Percival thought that bcrypt was not memory-hard enough, and thus designed scrypt. $\endgroup$ Aug 13, 2011 at 16:08
  • $\begingroup$ When you say " Each group of cores has access to a small amount of shared RAM" how much RAM are we actually talking about? Amounts less than the typical processor's L2 cache? $\endgroup$ Oct 11, 2011 at 17:58
3
$\begingroup$

bcrypt has now been implemented for both GPUs and for FPGAs. See Bcrypt password cracking extremely slow? Not if you are using hundreds of FPGAs!.

The GPU implementation described there is just barely faster than the CPU implementation. But the FPGA implementation is much more cost-effective, and takes over an order of magnitude less power. But so far it only seems to run on discontinued FPGA boards.

In particular, first they compare two systems each costing on the order of a thousand dollars: a CPU (AMD EPYC 7401P - 24 core, 3.0 GHz), with a high-end GPU (Nvida RTX-2080Ti). Both are pretty slow for bcrypt using work factor 12 (2^12 hashes), e.g. 197 vs 219 hashes/sec.

But the FPGA implementation (using open source code from Jack the Ripper) can do about a thousand work-factor-12 hashes/sec on a single ZTEX 1.15y board, using just 3-5% of the power.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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