Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

It is common knowledge that password cracking attempts can greatly benefit from specialized hardware such as large clusters of GPUs or FPGAs.

Are there any implementations of the commonly recommended password hashing algorithms (PBKDF2/bcrypt) for common or popular programming languages and/or frameworks such as .NET that offloads the password hashing portion of the authentication process to specialized hardware such as GPUs or FPGAs?

If there isn't such an existing library, are there any good reasons why they do not exist?

share|improve this question
1  
Off-the-cuff comment with no research: have you looked at the oclHashcat source code? They may well have an implementation that you can "borrow". –  Polynomial Jun 28 '13 at 14:03
    
^ +1 I know they recently added support for bcrypt as well –  Lucas Kauffman Jun 28 '13 at 14:10
    
@Polynomial Well, I can do that but I think most people would prefer to use an existing implementation actually meant for authentication in the form of a convenient library if at all possible. :) –  Terry Chia Jun 28 '13 at 14:13
    
I saw a DEFCON talk about FPGAs where one of the uses they had it at was MD5 hash cracking. –  medivh Jun 28 '13 at 21:31

3 Answers 3

up vote 2 down vote accepted

As @Rook points out, most of the advantage of specialized hardware such as GPU is through parallelization. A single GPU core, by itself, is quite feeble; it is clocked at a frequency lower than that of the main CPU, and it will compute only one operation per clock cycle (at best, and with high latency). However, a GPU includes hundreds of cores all dancing simultaneously.

Now, it so happens that usual password hashing functions are inherently sequential. See for instance PBKDF2: each output chunk is computed as the end result of a sequence of Ui values, where Ui+1 is obtained by processing Ui with a PRF (normally HMAC). This cannot be made parallel. If you want to compute a single PBKDF2 instance on a GPU, then it will use only one core on that GPU, and this will be very slow. Indeed, a typical GPU core can launch one instruction per clock cycles, but the result will be available only ten or twenty cycles later, so the GPU is used at its full power only if it has thousands of tasks to run in parallel.

The attacker benefits from GPU because, by definition, the attacker has a lot of potential passwords to try. So he can use parallel computing to its full power; brute forcing of passwords is an embarrassingly parallel problem. Indeed, since each GPU core The defender, on the other hand, does not have a lot of hashing to do: only one per incoming client at a time. We could imagine a very busy server with, at any time, hundreds of clients trying to open a session, and that might be amenable to optimization with a GPU, but this is not very realistic.


So, there is no ready-to-use implementation of an authentication framework which offloads the PBKDF2 or bcrypt cost to a GPU because it would not work. In the context of authenticating incoming clients (the defender's situation), the best hardware to use is the CPU, not a GPU.

That being said, this is really because PBKDF2 and bcrypt (and also scrypt and most other functions of the same kind) are sequential. One could design password hashing functions which can be made parallel. As an illustration, imagine a slow password hashing function designed like this:

  • Password is pw, salt is s.
  • For i = 1 to 10000, define Vi = PBKDF2(pw||i, s).
  • Final hash value is SHA-256(V1 || V2 || ... || V10000).

In the case of that function, the bulk of the computational effort is the ten thousands of PBKDF2 instances, and these can be optimized with a GPU, even if you have only a single password to hash.

(Caution: the function above is presented only as a speculative illustration. Don't believe that it is secure ! This has not undergone any kind of review by lots of trained cryptographers during several years.)

There is an ongoing competition for defining new password hashing primitives, in the same spirit as the AES, SHA-3 or eSTREAM efforts. If you have some nifty ideas about defining a password hashing function amenable to parallelism, then, by all means, consider submitting a candidate.

share|improve this answer
    
Just an afterthought - is there any specialized hardware that could potentially be used to accelerate slow hash functions, maybe something similar to Bitcoin miners? Or it's just not worth it and investing into more CPUs/cores would yield better bang for the buck? I'm specifically thinking here of bcrypt/scrypt functions. Cheers! –  TildalWave Jun 28 '13 at 18:00
1  
For the serious attackers against bcrypt, FPGA are best (well, ASIC are even better, but you first test the design on FPGA). Good FPGA have embedded RAM blocks, which allow for fast parallel bcrypt implementations. But the initial investment is rather high (it takes some time to build and integrate a working FGPA implementation) so mere amateurs prefer to use CPU or GPU. For scrypt, a plain old CPU in a PC is supposed to be the best architecture (that's the point of scrypt, really). –  Tom Leek Jun 28 '13 at 18:45

The benefit of computing hash functions with an FPGA or GPU is that they are heavily parallel, such parallelization is not required for most authentication systems. Further more memory intense hash functions, such as bcrypt and scrypt, remove parallelization advantage that FPGAs and GPUs have over CPUs.

It is possible to implement such a feature, however it would be counter productive. The point of using bcrypt, and other key stretching algorithms, is to remove the computational advantage provided by a heavily parallelized computational resource such as a FPGA or GPU.

Related: Why can't one impermanent bcrypt in Cuda?

share|improve this answer
    
Why is it counter productive? bcrypt can be computed rather efficiently with FPGAs. PBKDF2 can be computed efficiently with GPUs. An attacker is going to be using such specialized hardware anyway. Why can't someone use the same hardware to increase the number of rounds each password is hashed to make things much more difficult...? –  Terry Chia Jun 28 '13 at 15:38
    
@Terry Chia There is a very very good reason for this. Perhaps you should read the link at the bottom of my post more carefully and read my update. –  Rook Jun 28 '13 at 16:19
    
+1 but I don't get the downvote :O –  TildalWave Jun 28 '13 at 17:52

Have a look at bitcoin mining code -- their whole process is based on calculating SHA-256 hashes, and I know that there exists not only GPU implementations, but also FPGAs and now even ASICs appearing.

An ASIC-based device available today for $1300 can blow through about 66,300,000,000 SHA-256 hashes per second. An ATI/AMD 7970 video card can do about 687,000,000 hashes per second.

share|improve this answer

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.