Hashing passwords for storage, or using similar cryptographic functions to generate cypto keys from passwords, was problematic for a long time. Hashing functions were first created to be computationally efficient and so attacking them meant that it was quite easy to reproduce them. This led to functions that took significant computational effort. Typical of these was PBKDF2 (Password-Based Key Derivation Function 2). Implementations of PBKDF2 have used many thousands of iterations of the function to compute their results meaning that an attackers ability to employ brute force was severely impaired.
However, research just issued shows that it is possible to precompute certain elements of the PBKDF2 function and hence avoid up to 50% of the CPU intensive operations. This represents a significant dent in the protection afforded by PBKDF2.
We've known for some time that PBKDF2 had some limitations. Whilst it is possible to use an increasingly large number of iterations to ensure that the algorithm takes up arbitrarily large amounts of computing time, the limited amount of resources required for each iteration means that ASICS and GPUs can be employed for relatively cheap brute force attacks.
The original weaknesses have meant that algorithms such as bcrypt are seen as better solutions, although it is still possible to mount brute force attacks as demonstrated by a monster GPU based systems presented at the Password 12 conference.
More modern functions such as scrypt are more resistant to ASIC and GPU based brute force attacks but the state of the art is still evolving.
This latest research reminds us all that even relatively modern password and key derivation functions can be subjected to brute force attacks. Doubtless work will continue to emerge that shows how to optimise such attacks. Will we have learned to improve over the original hash functions, it is important that we don't assume the job is finished. Like painting the Fourth Bridge, the job never really finishes despite what we might think.
