Latest GPU proves to be excellent password cracking tool

October 31, 2007

ElcomSoft, a software company headquartered in Moscow, has filed a patent for using a GPU (Graphics Processing Unit) to crack passwords. The company has demonstrated that by using a high-end NVIDIA-based GeForce 8800 Ultra video card (about $620), they are able to increase their password cracking prowess by a factor of up to 25. This means that whereas it might have taken 1 year previously to brute-force crack a password, the exact same machine with a 8800 Ultra could be able to do it in slightly more than 2 weeks.1

Take for example an eight-character long login password for Windows Vista composed of uppercase and lowercase alphabetic characters. In such a case there would be about 55 trillion (52 to the eighth power) possible passwords to consider. Windows Vista uses NTLM hashing by default, so using a modern dual-core PC you could test up to 10,000,000 passwords per second, and perform a complete analysis in about two months. If one were to take advantage of the GPU with ElcomSoft's new technology, the process would take only three to five days, depending upon the CPU and GPU.2 (Note however that adding extra characters to a password exponentially increases the amount of time required to crack it through brute-force. At 10 characters it would take 23 years to try all combinations against the password above - and on average half of that amount of time to crack it. At 12 characters this would increase dramatically to approximately 62,000 years).

This advancement was made possible thanks in part to NVIDIA's Compute Unified Device Architecture (CUDA) technology, which allows for high-performance tasks to be outsourced to the graphics card. In particular, tasks that can be highly parallelized (such as brute force password cracking) are especially suitable for modern graphics cards like NVIDIA's GeForce 8800 Ultra, with its 128 stream processors.3 Until recently, a graphic cards' GPUs could not be used for applications such as password recovery. Older graphics chips could only perform floating-point calculations, and most cryptography algorithms require fixed-point mathematics. Today's chips can process fixed-point calculations, and with as much as 1.5 GB of onboard video memory and up to 128 processing units, these powerful GPU chips are much more effective than CPUs in performing many of these calculations.2 Furthermore, modern day link technology such as NVIDIA's SLI allows for up to four graphic cards to be linked together on a single PC in order to increase its computing capacity up to 6 teraflops, according to NVIDIA.4

It is the parallel computing architecture of a GPU that provides this speed increase. NVIDIA spokesman Andrew Humber describes the process using the analogy of searching for words in a book. "A [normal computer processor] would read the book, starting at page 1 and finishing at page 500," he says. "A GPU would take the book, tear it into a 100,000 pieces, and read all of those pieces at the same time."5

At the time of writing, ElcomSoft's Distributed Password Recovery program can currently be used to crack passwords from the following formats:6

* Microsoft Word/Excel/PowerPoint 2007 (.DOCX, .XLSX, .PPTX) (password recovery - "open" password only)
* Microsoft Word/Excel/PowerPoint XP/2003 (.DOC, .XLS, .PPT) (password recovery - "open" password only)
* Microsoft Word/Excel 97/2000 (.DOC, .XLS) (password recovery - "open" password only)
* Microsoft Word/Excel 97/2000 (.DOC, .XLS) (guaranteed decryption)
* Microsoft Money (password recovery)
* Microsoft OneNote (password recovery)
* PGP zip archives (.PGP) (password recovery)
* PGP secret key rings (.SKR) (passphrase recovery)
* PGP disks with conventional encryption (.PGD) (password recovery)
* PGP self-decrypting archives (.EXE) (password recovery)
* PGP whole disk encryption (password recovery)
* Personal Information Exchange certificates - PKCS #12 (.PFX, .P12) (password recovery)
* Adobe Acrobat PDF with 128-bit encryption ("user" and "owner" password recovery)
* Adobe Acrobat PDF with 40-bit encryption ("user" and "owner" password recovery)
* Adobe Acrobat PDF with 40-bit encryption (guaranteed decryption)
* Windows NT/2000/XP/2003/Vista logon passwords (LM/NTLM) (password recovery)
* Windows SYSKEY startup passwords (password recovery)
* Windows DCC (Domain Cached Credentials) passwords (password recovery)
* Intuit Quicken (.QDF) (password recovery)
* Lotus Notes ID files (password recovery)
* MD5 hashes (plaintext recovery)

ElcomSoft state that it took three months for them to develop the code to take advantage of a GPU, and the company plans to introduce the feature into some of its password cracking products over time.5

"ElcomSoft's revelations are likely to send shock waves through the IT security world, as it shows that powerful off-the-shelf kit can be now used for advanced hacking procedures. If ever there was a wake-up call to companies of the need to encrypt their data, this is it," says Calum Macleod of Cyber-Ark Software, an information security company.7 If anything, this demonstrates once again that short passwords cannot be relied upon for security.

1. "Password cracking, the new use for high speed GPUs", TG Daily, October 24, 2007

2. "ElcomSoft Files Patent for Revolutionary Technique to Recover Lost Passwords Quickly", Elcomsoft, October 31, 2007

3. "GeForce 8 cracks passwords", heise Security, October 23, 2007

4. "The Most Extreme HD Gaming Experience is Here", NVIDIA, October 31, 2007

5. "Password-cracking chip causes security concerns", New Scientist, October 24, 2007

6. "Elcomsoft Distributed Password Recovery", Elcomsoft, October 31, 2007

7. "Cyber-Ark warns manufacturers to encrypt data after nVidia revelations", Manufacturing Computer Solutions, October 29, 2007