On October 25, 2007, Elcomsoft Co Ltd. in Moscow, Russia filed for a US patent on a reportedly new password recovery method that makes use of a video card's graphics processing unit (GPU). Elcomsoft credits the February 2007 release of the NVIDIA CUDA C-Compiler and developer's kit for providing the necessary low-level GPU access they needed to make this cryptographic advancement. The newest NVIDIA GPUs act as multiprocessors that utilize shared memory, cache, and multiple registers. The newest graphics cards utilize fixed point calculations, relatively massive amounts of memory, and multiple processing units. They differ significantly from a computer's central processing unit (CPU) in terms of their cryptanalytic processing capabilities and Elcomsoft claims to have leveraged newer GPU architectures to improve brute force password cracking by a factor of 25.
Statistics from Elcomsoft state that the new method can be used to exhaustively crack an eight character pseudo-random password on Windows Vista in approximately three to five days using a combination of CPU- and GPU-based hardware. This requires a cycle of about 55 trillion password possibilities when brute force testing Windows Vista NTLM hashes. In comparison, a conventional exhaustive attack using CPU hardware only may take months to complete.
Patenting GPU-based cryptographic calculation techniques is not without its share of controversy. Steven Bellovin recently pointed out on the Metzdowd cryptography list that similar ideas were presented as far back as 2004/2005 in "Remotely Keyed Cryptographics: Secure Remote Display Access Using (Mostly) Untrusted Hardware" by Debra L. Cook, Ricardo Baratto, and Angelos D. Keromytis. In this paper Columbia University research scientists discuss whether it is possible to confine a minimally trusted computing base to GPU hardware and propose core concepts and feasibility of GPU-based decryption. Most fascinating is the fact that they concede that their methods can not be fully implemented due to the current (2004/2005) limitations in GPU APIs (see CUDA release in February 2007).
Regardless of any developing patent controversies, dramatically improved password recovery techniques that leverage onboard parallel processing GPU architectures are a fascinating cryptographic development. It will be interesting to watch for the GPU-based crypto products that Elcomsoft pushes to market and whether we are forced to strengthen our enterprise password infrastructures as a result.
ElcomSoft Files Patent for Revolutionary Technique to Recover Lost Passwords Quickly http://www.elcomsoft.com/EDPR/gpu_en.pdf
Remotely Keyed Cryptographics Secure Remote Display Access Using (Mostly) Untrusted Hardware http://www1.cs.columbia.edu/~angelos/Papers/2005/rkey_icics.pdf
Password-cracking chip causes security concerns
NVIDIA CUDA Revolutionary GPU Computing