Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
