Rainbow Tables (probably) aren’t what you think — Part 1: Precomputed Hash Chains

Rainbow Attack by TheeWeguy

Rainbow Tables != Lookup Tables

Many people use “rainbow table” to refer to “a lookup table of password hashes”, but in reality a rainbow table is a far more complex, and more interesting technology. This article will discuss the problem with lookup tables, and how rainbow tables solve it. We’ll be focusing on a scenario where we want to crack any md5 hash of a 4 digit password, meaning our search space looks like so:


Lookup Tables Explained

Lookup tables are probably what you thought rainbow tables are, and are what most people mean when they say “rainbow table”. A lookup table is an extremely simple data structure. All it does is store both the hash and the corresponding password in a massive list. For example, by hashing the candidate list and storing the hash, we arrive at the following list:


Precomputed Hash Chains

The predecessor of rainbow tables, precomputed hash chains allow us to store far less on disk, at the expense of greater computing power requirements at “lookup” time.

0000 -> 4a7d1ed414474e4033ac29ccb8653d9b
4a7d1ed414474e4033ac29ccb8653d9b -> 4515



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


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