[ISN] Rainbow warriors crack password hashes

[InfoSec News]

http://www.theregister.co.uk/2005/11/10/password_hashes/

By Robert Lemos
SecurityFocus
10th November 2005 

A trio of entrepreneurial hackers hope to do for the business of
password cracking what Google did for search and, in the process, may
remove the last vestiges of security from many password systems.

Over the past two years, three security enthusiasts from the United
States and Europe set a host of computers to the task of creating
eleven enormous tables of data that can be used to look up common
passwords. The tables - totaling 500GB - form the core data of a
technique known as rainbow cracking, which uses vast dictionaries of
data to let anyone reverse the process of creating hashes - the
statistically unique codes that, among other duties, are used to
obfuscate a user's password.

Last week, the trio went public with their service. Called
RainbowCrack Online, the site allows anyone to pay a subscription fee
and submit password hashes for cracking.

"Usually people think that a complex, but short, password is very
secure, something like $FT%_3^," said Travis, one of the founders of
RainbowCrack Online, who asked that his last name not be used.  
"However, you will find that our tables handle that password quite
easily."

While security professionals have questions whether a business can be
created by offering access to rainbow tables, the endeavor does
highlight the weaknesses in security of password-only authentication.  
History has shown that password systems are imminently breakable.

In August, a group of Chinese researchers found further breaks in a
common hash function, the Secure Hash Algorithm or SHA-1, used by the
U.S. government. In September, researchers from the University of
California at Berkeley published a paper that demonstrated that the
sound of a person typing can reveal the content, including passwords.  
Those technical breaks do not even account for the human factor:  
People tend to pick simple passwords and disclose them frequently. In
fact, many viruses and worms have successfully spread by trying to log
into administrator accounts using a small list of common passwords.

Because of the problems, the U.S. government is requiring that banks
move towards two-factor authentication, where the typical password
security is augmented by a biometric or a physical security device.  
Some security researchers maintain that even adding a second type of
security check is not enough.

The latest attack focuses on the hash functions used to verify
passwords. Because operating systems cannot keep a copy of the
password on the disk without weakening system security, the software
instead saves a statistically unique code generated from the pasword.  
While the code, or hash, is computationally easy to create, reversing
the process to recover the password is nearly impossible, given a
correctly implemented hash function.

Rainbow tables side step the difficulty in cracking a single password
by instead creating a large data set of hashes from nearly every
possible password. To break a password, the attacker merely looks up
the hash to find the password that produces that code.

"Creating the tables takes much more time than cracking a single hash,
but then you can use the tables over and over again," said Philippe
Oechslin, CEO of Swiss information-technology firm Objectif Sécurité
and the inventor of rainbow tables. "The advantage of rainbow tables
is that once you have the tables it is faster than a brute force
(attack) and it needs less memory than a full dictionary (attack) of
the function."

The theory behind rainbow tables extends research by Martin Hellman
and Ronald Rivest done in the early 1980s on the performance
trade-offs between processing time and the memory needed for
cryptoanalysis. In a paper published in 2003, Oechlin refined the
techniques and showed the attack could reduce the time to attack 99.9
per cent of Microsoft's LanMan password scheme to 13.6 seconds from
101 seconds. Further refinements have reduced the number of false
positives produced by the system.

"This is something that you are never supposed to be able to do with
(a good implementation of) crypto - generate every single possible
combination," said Dan Moniz, a member of the Shmoo group, a coalition
of security researchers and the manager of the groups own rainbow
table project.

RainbowCrack Online will offer 11 tables covering six different hash
algorithms, including LanMan, MD5, MySQL 323, and SHA-1. Offering the
tables in an online service is not about helping attackers, but about
helping system administrators secure their systems, said
RainbowCrack's Travis.

"Attackers already have tables like these, (so) RainbowCrack serves as
a tool to judge what is and what is not a secure password policy," he
said.

Making money with rainbow tables is not a new idea. A handful of
efforts have been started and then stalled. Zhu Shuanglei, who created
the open-source tool that RainbowCrack Online uses to generate its
tables, has generated a 64GB LanMan table and advertises it for sale
for $400. The Shmoo group created its own rainbow table to crack
Microsoft's LanManager tables that offered them for free through
BitTorrent, and at the DEF CON hacking convention, Shmoo's Moniz saw
several versions of the LanManager tables for sale. People with free
computer time would calculate the tables hoping to make a little
money, he said.

The experience has Shmoo's Moniz questioning whether there will be
demand for a service like RainbowCrack Online. Bruce Schneier, a
well-known cryptographer and chief technology officer of network
monitoring service Counterpane Internet Security, agrees.

"There could be a criminal business in it," he said. "But I don't see
the legitimate business demand for rainbow tables."

To some extent, RainbowCrack Online applies Google's business model to
cracking encryption. Like Google, RainbowCrack Online give web access
to a large database of information. Both services go through a lot of
effort and a lot of memory to give users a quick answer to a query.  
And both services could be reproduced, barring patent hurdles.

Yet, while searching the web has obvious utility, the usefulness of
rainbow tables is questionable, because good programming can make the
tables require several magnitudes more memory, rendering the technique
essentially useless. Specifically, adding several unpredictable bytes
at the beginning of a password before hashing, a technique known as
salt, can add several orders of magnitude of complexity to any
cryptanalysis of the result.

"Remember that rainbow tables only work for inferior functions that
use no salt or initialization vector," Objectif Sécurité's Oechslin
said. "If programmers were more careful, there would be no market for
a rainbow Google."

RainbowCrack Online's founders disagree. The lion's share of
cryptographic hash functions are not well implemented and thus could
be broken with their tables quite easily, RainbowCrack's Travis said.

Counterpane's Schneier agrees.

"All we have is anecdotal evidence about development practices, but I
would agree that a lot of systems are weak," Schneier said. "The
biggest problems that we as cryptographers have to face is bad
implementations."

For such insecure password implementations, rainbow-table services may
be the sign that it's time to reconsider security.

Copyright © 2005, SecurityFocus