Feeds

Rainbow warriors crack password hashes

Is it safe? Nope

The Power of One eBook: Top reasons to choose HP BladeSystem

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

The Power of One eBook: Top reasons to choose HP BladeSystem

More from The Register

next story
HIDDEN packet sniffer spy tech in MILLIONS of iPhones, iPads – expert
Don't panic though – Apple's backdoor is not wide open to all, guru tells us
BMW's ConnectedDrive falls over, bosses blame upgrade snafu
Traffic flows up 20% as motorway middle lanes miraculously unclog
LibreSSL RNG bug fix: What's all the forking fuss about, ask devs
Blow to bit-spitter 'tis but a flesh wound, claim team
Mozilla fixes CRITICAL security holes in Firefox, urges v31 upgrade
Misc memory hazards 'could be exploited' - and guess what, one's a Javascript vuln
Putin: Crack Tor for me and I'll make you a MILLIONAIRE
Russian Interior Ministry offers big pile o' roubles for busting pro-privacy browser
Manic malware Mayhem spreads through Linux, FreeBSD web servers
And how Google could cripple infection rate in a second
Don't look, Snowden: Security biz chases Tails with zero-day flaws alert
Exodus vows not to sell secrets of whistleblower's favorite OS
Researcher sat on critical IE bugs for THREE YEARS
VUPEN waited for Pwn2Own cash while IE's sandbox leaked
prev story

Whitepapers

Top three mobile application threats
Prevent sensitive data leakage over insecure channels or stolen mobile devices.
Implementing global e-invoicing with guaranteed legal certainty
Explaining the role local tax compliance plays in successful supply chain management and e-business and how leading global brands are addressing this.
Top 8 considerations to enable and simplify mobility
In this whitepaper learn how to successfully add mobile capabilities simply and cost effectively.
Application security programs and practises
Follow a few strategies and your organization can gain the full benefits of open source and the cloud without compromising the security of your applications.
The Essential Guide to IT Transformation
ServiceNow discusses three IT transformations that can help CIO's automate IT services to transform IT and the enterprise.