Windows passwords cracked in seconds

Swiss researchers released a paper on Tuesday outlining a way to speed the cracking of alphanumeric Windows passwords, reducing the time to break such codes to an average of 13.6 seconds, from 1 minute 41 seconds.

The method involves using large lookup tables to match encoded passwords to the original text entered by a pereson, thus speeding the calculations required to break the codes. Called a time-memory trade-off, the situation means that an attacker with an abundance of computer memory can reduce the time it takes to break a secret code.

The results highlight a fact about which many security researchers have worried: Microsoft's manner for encoding passwords has certain weaknesses that make such techniques particularly effective, Philippe Oechslin, a senior research assistant and lecturer at the Cryptography and Security Laboratory of the Swiss Federal Institute of Technology in Lausanne (EPFL), wrote in an e-mail to CNET News.com.

"Windows passwords are not very good," he wrote. "The problem with Windows passwords is that they do not include any random information."

Oechslin outlined a way to take advantage of that lack of randomness on Tuesday when he published a paper and a Web demonstration of the technique. The research builds on previous work showing that encryption algorithms can be sped up with the help of large lookup tables. Increasing the size of the lookup tables reduces the amount of time, on average, that it takes to search for a password.

The researcher used a 1.4GB lookup table and a single computer with an AMD 2500+ processor and 1.5GB RAM to offer people a way to test the process online.

Oechslin said he hadn't notified Microsoft of the issue before publishing his paper. He said his research has been more about creating efficient time-memory trade-offs, not about breaking Microsoft passwords.

"This is not a new vulnerability," he said. "It is only the first time that it has been worked in so much detail. Microsoft passwords are just a nice example to demonstrate the theoretical results."

Microsoft has used two encoding schemes, also known as hashing functions, to encrypt passwords. The first, known as LANManager or LANMan, was used by Windows 3.1, 95, 98, Me and early NT systems to secure passwords that were used to connect to early Windows networks.

The LANMan scheme has several weaknesses, including converting all characters to uppercase, splitting passwords into 7-byte chunks, and not using an additional random element known as "salt." While the more recent NTHash fixes the first two weaknesses, it still does not use a random number to make the hashes more unique.

The result: The same password encoded on two Windows machines will always be the same. That means that a password cracker can create a large lookup table and break passwords on any Windows computer. Unix, Linux and the Mac OS X, however, add a 12-bit salt to the calculation, making any brute force attempt to break the encryption take 4,096 times longer or require 4,096 times more memory.

While an attacker would need administrator rights to a system to grab the file that contains the password hashes, the file is still valuable, said David Dittrich, a senior security researcher at University of Washington.

"The object is to use rights you have gained on one resource to break into other systems," he said. "If you have broken into a server and you have a hash, you can escalate your privilege and slowly move your way through the network. If you can get your hands on the hash, then game over."

Users can protect themselves against the attack by adding non-alphanumeric characters to a password. Including other symbols besides alphanumeric characters adds complexity to the process of breaking passwords and that means the cracker needs more time or more memory or both.

Oechslin, for example, has created a new version of his program using 20GB of lookup tables that can break passwords made of numbers, letters and 16 other characters in an average of 30 seconds for large batches of passwords.

"To make things more complex, we could have generated a set of data half as big (10GB), which would (have broken) the same passwords faster, but we would have spent multiple times the amount of work calculating this data," he wrote. "So there is another trade-off, namely between precalculation time and memory or cracking time."