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:

0000
0001
0002
...
9999

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:

4a7d1ed414474e4033ac29ccb8653d9b:0000
25bbdcd06c32d477f7fa1c3e4a91b032:0001
fcd04e26e900e94b9ed6dd604fed2b64:0002
...
fa246d0262c3925617b0c72bb20eeb1d:9999

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

26 Followers

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