Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
2  
For a moment I misread "Cuda" as "Cuba" and thought this was an encryption import problem. –  Joe Z. Jan 27 '13 at 21:32
add comment

1 Answer 1

up vote 18 down vote accepted

It is not impossible, only harder. 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.

share|improve this answer
1  
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. –  Rook Aug 13 '11 at 7:37
1  
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.) –  Paŭlo Ebermann Aug 13 '11 at 15:57
    
@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. –  Thomas Pornin Aug 13 '11 at 16:06
2  
@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. –  Thomas Pornin Aug 13 '11 at 16:08
    
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? –  David Perry Oct 11 '11 at 17:58
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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