Original URL: http://www.theregister.co.uk/2005/11/10/password_hashes/
Rainbow warriors crack password hashes
By Robert Lemos, SecurityFocus (tips at securityfocus.com)
Published Thursday 10th November 2005 15:42 GMT

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.
Click Here

Last week, the trio went public with their service. Called RainbowCrack
Online (http://www.rainbowcrack-online.com/), 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 (http://www.securityfocus.com/news/11292), 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
(http://www.securityfocus.com/news/11318), including passwords. Those
technical breaks do not even account for the human factor: People tend to
pick simple passwords (http://news.com.com/2009-1001_3-916719.html) and
disclose them frequently (http://www.securityfocus.com/news/11101). In fact,
many viruses and worms have successfully spread by trying to log into
administrator accounts using a small list of common passwords
(http://www.securityfocus.com/news/3003).

Because of the problems, the U.S. government is requiring that banks move
towards two-factor authentication
(http://www.securityfocus.com/columnists/363), 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 (http://www.securityfocus.com/news/10694).

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é
(http://www.objectif-securite.ch/) 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 (http://lasecwww.epfl.ch/~oechslin/projects/ophcrack/),
Oechlin refined the techniques and showed the attack could reduce the time
to attack 99.9 per cent of Microsoft's LanMan password scheme
(http://online.securityfocus.com/infocus/1319) 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
(http://www.antsight.com/zsl/rainbowcrack/). The Shmoo group created its own
rainbow table to crack Microsoft's LanManager tables
(http://www.microsoft.com/technet/community/columns/secmgmt/default.mspx)
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 (http://www.securityfocus.com/)



You are a subscribed member of the infowarrior list. Visit
www.infowarrior.org for list information or to unsubscribe. This message
may be redistributed freely in its entirety. Any and all copyrights
appearing in list messages are maintained by their respective owners.

Reply via email to