Rainbow table definition
A rainbow table is a large, precomputed table designed to cache the output of cryptographic hash functions to decrypt hashed passwords into plaintext. Rainbow tables were invented by IT expert Philippe Oechslin, who published a paper on his work in 2003. The method itself is based on research from the early 1980s by Martin Hellman and Ronald Rivest that explored the performance trade-offs between processing time and the memory needed for cryptanalysis. “Rainbow” refers to the colors used within a table to represent different reduction functions and steps. These create a colorful rainbow with a corresponding number of iterations.
How do rainbow tables work?
For security reasons organizations have, for several years, typically stored users’ passwords using hashes. Hashing algorithms disguise passwords and make them unviewable to anyone without inverting the hash function. This can technically be achieved via brute-force attacks, but as the set of possible password outcomes grows, it becomes more and more infeasible to use this method.
Rainbow tables greatly reduce the complexity in cracking large numbers of passwords through a pre-generated data set of password hashes. Vast numbers of hashed passwords can be run through this data set and, following several stages of reduction by which hashes are split into smaller components, computed and linked to words and letters to reveal whole passwords in plaintext.
Rainbow table creator Oechslin tells CSO: “Rainbow tables allow you to reduce the effort of cracking a password by using large amounts of memory. You organize the passwords in chains, and only store the first and last element of each chain. The tables only contain a fraction of the passwords (i.e., one in 100,000) and they allow you to crack all passwords with only a fraction of the effort. The larger you make the table, by keeping a larger fraction of passwords, the faster the cracking is. This is why it is called a trade-off.” Over the years, rainbow tables have proved most effective against the popular but particularly weak password hashing algorithm LAN Manager hash, used in the earlier days of Windows.
Rainbow tables have typically been of interest to those on both sides of the law. For ethical security researchers, they’ve provided a means to check the effectiveness of password security standards. For threat actors, they’ve made it easier to crack passwords for malicious gain, testing what they can access with the passwords since most people (at least to some degree) reuse passwords across accounts.
Rainbow table attacks and prevention
Preventing rainbow table attacks is straightforward, explains Javvad Malik, security awareness advocate at KnowBe4. “It requires adding a salt (an extra random value) to every hashed password,” he says. “If an attacker only has the rainbow table but not the salt, it’s not enough and they won’t be able to match the password without that added bit of randomness. It’s like taking a fingerprint for authentication and then stamping a random shape over the top of it—and you need both for a perfect match.”
While pretty much all companies today salt hashed passwords by default, “you’re always going to find some developer that’s made an app or something which may use a really poor password hashing mechanism,” Malik explains. Likewise, an organization could still be using an outdated password hashing algorithm. Either of these two things could potentially make a company vulnerable to a rainbow table attack.
There’s also the possibility of attackers who lack newer or vastly more effective password cracking methods opting to use the more traditional rainbow table approach to see what they can find. After all, rainbow tables still work well for decrypting short keys, for example to crack GSM A5/1 encryption, points out cryptographer JP Aumasson.
Rainbow tables vs. modern password cracking
From a modern password cracking threat perspective though, rainbow tables are mostly obsolete, and that’s not only due to the previously mentioned commonality of password salting that makes them ineffective. They have also long since been replaced by more advanced, powerful practices less hampered by limitations. “Rainbow tables rarely provide value compared to optimized GPU-based cracking, because they are very specific to a given password hash and password type, and they’re slow to generate,” JP Aumasson explains.
Oechslin agrees, adding that more modern password cracking techniques have driven rainbow tables into almost complete obscurity over the last 10 years or so. “They are redundant except for very specific cases. When GPU became an alternative way to crack passwords, this tremendously increased the speed at which hashes can be cracked,” he says.
Jeremi Gosney, founder and CEO of distributed password cracking company Terahash, concurs. “Modern password cracking is highly dynamic, and requires agility, flexibility, and scalability. Rainbow tables are static, rigid, and not at all scalable—they are the antithesis of modern password cracking. Even if you don’t have the horsepower of GPUs, employing modern techniques will still net you a far higher hash yield than rainbow tables will.” Probabilistic candidate generation, rules, hybrid attacks, and now even machine learning candidate generation are far superior to rainbow tables, he says.
Perhaps the most relevant aspect of rainbow tables today is their use in education and training, with many universities and security qualifications still covering them, Malik points out. “It’s useful to understand, in the full picture, what security needs to be aware of when it comes to passwords. They are also a good example of how security has improved over time and teach us what we can do about other threat vectors.”
Copyright © 2021 IDG Communications, Inc.
