On October 25, 2007, Elcomsoft Co Ltd. inMoscow, Russia filed for a US patent on a reportedly new passwordrecovery method that makes use of a video card's graphics processingunit (GPU). Elcomsoft credits the February 2007 release of the NVIDIACUDA C-Compiler and developer's kit for providing the necessarylow-level GPU access they needed to make this cryptographicadvancement. The newest NVIDIA GPUs act as multiprocessors that utilizeshared memory, cache, and multiple registers. The newest graphics cardsutilize fixed point calculations, relatively massive amounts of memory,and multiple processing units. They differ significantly from acomputer's central processing unit (CPU) in terms of theircryptanalytic processing capabilities and Elcomsoft claims to haveleveraged newer GPU architectures to improve brute force passwordcracking by a factor of 25.
Statistics from Elcomsoft state that the new method can be used toexhaustively crack an eight character pseudo-random password on WindowsVista in approximately three to five days using a combination of CPU-and GPU-based hardware. This requires a cycle of about 55 trillionpassword possibilities when brute force testing Windows Vista NTLMhashes. In comparison, a conventional exhaustive attack using CPUhardware only may take months to complete.
Patenting GPU-based cryptographic calculation techniques is notwithout its share of controversy. Steven Bellovin recently pointed outon the Metzdowd cryptography list that similar ideas were presented asfar back as 2004/2005 in "Remotely Keyed Cryptographics: Secure RemoteDisplay Access Using (Mostly) Untrusted Hardware" by Debra L. Cook,Ricardo Baratto, and Angelos D. Keromytis. In this paper ColumbiaUniversity research scientists discuss whether it is possible toconfine a minimally trusted computing base to GPU hardware and proposecore concepts and feasibility of GPU-based decryption. Most fascinatingis the fact that they concede that their methods can not be fullyimplemented due to the current (2004/2005) limitations in GPU APIs (seeCUDA release in February 2007).
Regardless of any developing patent controversies, dramaticallyimproved password recovery techniques that leverage onboard parallelprocessing GPU architectures are a fascinating cryptographicdevelopment. It will be interesting to watch for the GPU-based cryptoproducts that Elcomsoft pushes to market and whether we are forced tostrengthen our enterprise password infrastructures as a result.
References:
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
http://technology.newscientist.com/article.ns?id=dn12825
NVIDIA CUDA Revolutionary GPU Computing
http://developer.nvidia.com/object/cuda.html