Why do look up tables speed things up compared to brute force?

Question

I'm currently reading up on lookup tables and efficiency. In my uni script it says the following:

For Brute Force:

• Preparation time: $O(1)$

• Disk space requirement: $O(1)$

• Time required to crack the password: $O(2^n)$

Full lookup table:

• Preparation time: $O(2^n)$

• Disk space requirement: $O(2^n)$

• Time required to crack the password: $O(1)$

I'm not sure I'm understanding this correctly.

As far as I understand, for Brute Force:

$O(1)$ is the time required to look up the password in my table of all possible passwords. The disk space requirement is simply as large as needed for a list of all possible passwords, so $O(1)$ as well

My questions:

Why is the time needed to crack the password $O(2^n)$? How is it determined?

It seems I don't understand the concept of a lookup table either. As far as I see, a lookup table will simply hash the full list of possible passwords (so required disk space is larger) but what then? Why is the cracking of the password per se faster?

I think I'm missing something crucial here. Any help will be appreciated.

Answer 1

Suppose you have an $n$-bit key. Suppose further you have some reliable predicate $P(k,m)$ which decides whether a key $k$ is the key you are looking for given the reference $m$. Furthermore, suppose you have a "successor" function $F$, that takes a key and returns you the "next" key so that eventually all keys are traversed.

Now what a brute-force attack does is, given $m$, it takes a starting key $k$, evaluates $P(k,m)$ if it returns false, sets $k\gets F(k)$. This will take $\mathcal O(2^n)$ evaluations of $P$ and $F$. Assuming both can be computed in $\mathcal O(1)$ the entire calculation takes $\mathcal O(2^n)$.

Now for the look-up table. For this you simply start at some key $k$, and store the $m$ such that $P(k,m)$ yields true as a pair $(m,k)$ in a giant array (or hashmap). Now you repeat this with $F(k)$. When you then get a concrete $m$, you simply look it up in the table and find the corresponding $k$. For hashmaps and continuous arrays, this takes time $\mathcal O(1)$ (ie the lookup time is independent of the number of elements). Clearly, you need storage for all the $2^n$ pairs of $(m,k)$. Now the preparation time assumes that you can find $m$ such that $P(k,m)$ is true, but this is usually possible in constant time, e.g. by evaluating a hash function or an encryption cipher.

Answer 2

Brute Force

Let's say your password was all digits (e.g. 607552)

If your password has length 1, it will take up to 10 attempts to crack:

0, 1, 2, 3 ..., 9

If your password has length 2, it will take up to 100 attempts to crack

00, 01, 02, ... 10, 11, 12, ... 20, 21, 22, ... 99

If your password has length 3 it will take up to 1000 attempts to crack

See the pattern? The number of attempts is $10^n$. It's the same idea if you are cracking a password with $n$ bits. (Since a bit can be 0 or 1, instead of 0-9, it's a power of 2 instead of 10).

Lookup Table

While a brute-force attack tries all possible passwords to see if they produce the right hash, a lookup table is a fast way to do the opposite: get a password based on a hash. It does this by hashing all the possible passwords ahead of time, and storing the results in a table.

Method 1:

Store the items in an array, sorted by hash. When given a hash, guess the position in the array of this hash, based on the numerical value of the hash. (I.e. if the numerical value is 25% of the maximum value the hash could be, then you would guess the index that is 25% of the total array size.) Your guess will be very close, because any good hash is evenly distributed. Go forwards or backwards until you find a match. This is freakishly close to $O(1)$, especially if you refine your guesses (binary-search-style) rather than just incrementing or decrementing.

The main disadvantage of this method is that initially sorting the table is asymptotically slower than generating it, namely $O(2^n \times \log (2^n)) = O(n 2^n)$.

Method 2:

This is essentially a hashmap, except using a library hashmap is silly when you already have a hash! Just use the first $n$ digits of your hash. That means: create an array of size $2^n$. In each slot goes a list of all hashes whose first $n$ digits equal that array index. (And their corresponding passwords.)

To look up a hash, take its first $n$ digits, and get the corresponding list out of the array. Traverse the list to find the hash. Like a hashmap, this takes $O(1)$ constant amortised time.