Rainbow Tables (probably) aren’t what you think — Part 2: Probability, Efficiency, and Chain Collisions

Probability & Efficiency

Try this experiment: roll a dice repeatedly, with the goal of rolling each possibility at least once. On the first roll, the chance of a “collision” (rolling something you’ve already rolled before, therefore wasting that roll) is zero. The next roll will have a 1 in 6 chance of colliding, since you might roll the same number as before. After 5 numbers have been discovered, you’re likely to need several attempts before discovering the final number, since you only have a 1 in 6 chance every time you roll.

Chain Collisions

Remember that one requirement for a hash chain is that it’s deterministic, because we need to be able to reproduce the chain from scratch. However, this creates a problem if a hash from one chain collides with one in another. Consider the following example:

Rainbow Tables

This is where the innovation of rainbow tables comes in. With a rainbow table we add a second parameter to our reduce function, as a sort of “salt”, which changes depending on our position in the chain. Just like before, the reduce function is still deterministic, it just takes one extra piece of information.

  • Insecure password hashes are capable of being cracked with pretty reasonable speed on modern cracking rigs (You can do a full 8 character NTLM crack in less than a day on an RTX 3090, and you can crack thousands of hashes simultaneously, all without storing TeraBytes of Data)
  • Rainbow Tables are still heavily constrained by modern hardware. Most people don’t have TeraBytes of storage available, and you still need to do the equivalent of several brute-forces to generate the rainbow table in the first place. The best rainbow tables publicly available only go up to 8 characters for a full character set, and 10 characters for a lower-case only character set (which is useless with modern complexity rules).
  • Brute-force attacks aren’t that effective anymore. Back when most services and users had very short passwords, the ability to crack any 8 character password resulted in excellent results. However, due to the popularity of password policies with complexity rules, most users pick passwords longer than 8 characters. The most commonly cracked passwords these days are similar to “Password123” or “Summer@2021”, which are far longer than 8 characters. In fact, the average password length is over 9 characters, for which an 8 character brute-force will do no good.
  • Wordlist attacks with manipulation rules are far more effective at getting actual user-picked passwords. Real users don’t randomly generate passwords (with the exception of security-minded folks, who know better than to generate only 8 characters). Real users pick one or two words, then add a few extra numbers and symbols to satisfy the complexity requirements. An attack with a massive wordlist and ruleset (weakpass2a with OneRule is my go-to for NTLM, which an RTX 3090 can crunch in a couple hours) gets approximately 60% of real user passwords.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Ryan Sheasby

Ryan Sheasby

26 Followers

Information Security Engineer, Passionate about AppSec, algorithms, Go, and ZFS, among lots of other things.