So in this real-world example of phone numbers and people, for instance
if we didn't have the phone book yet we could start with every phone number
and call every person and ask for their names.
You'd go through a brute-force phase that may take a couple of months
but once your're done with this you have this beautiful phone book or code book
as they call it in Cryptography that allows you to do
the second and third and forth and infinite number of look-ups in basically zero time.
So that's the basic idea of an attack that then uses very little time
in fact zero encryption functions are needed after the pre-computation phase
but that invests storage, in this case the storage to store every possibility
to achieve the faster computation.
And that's the basic scheme that in this case is not practical
because this amount of storage would equal Petabytes
in fact hundreds of Petabytes and that storage is available to no hacker in the world.
Google may have this much, but nobody wants to break GSM phone calls for cheap.
So we need improvements on this scheme.
Luckily there are many possible choices between this one extreme, the code book
that uses a lot of storage and very little time and the other extreme, brute force
that uses a lot of time but very little storage. And those we want to discuss next.
Some trade-off points are achieved by a technique called Time Memory Trade-Offs.
And that works as follows: We again start with a table of many of these keys.
And for each of them again, apply the encryption function
but not just once but several times.
And of the resulting data set there of course will be of the same amount of samples
again we want to have the same coverage.
We throw away most everything, these things in the middle
and only keep the first and the last column.
Now this should be equivalent in coverage to a data set
that in the simplest scheme took a lot more storage capacity, and here's how.
You're looking up a message found in the last column, then clearly it works as before.
You find the encrypted message in this last column and
you look up the key through following the chain that led up to this message.
So, after finding the message in the last column, you go to the matching entry
of the first column and compute the encryption function, in this case twice.
and that's the key you wanted.
However, how do you find now a message that is in the middle
that you didn't in fact store on the hard disk.
For this you'll have to apply an encryption function first and then find it.
This parameter three is configurable, of course.
And to correct something of the size of the GSM 64-bit key
we would want to choose a parameter more on the magnitude of a million.
So this table becomes a million columns wide
of which you only stored the first and the last.
Now if this before took Petabytes and now you only have to store a millionth of it
you're down to manageable Terabytes.
And that's exactly where we want to be to launch this attack on today's computers.
There is a large amount of academic work to solve these practicality problems
two of which we want to look into to solve, exactly these two problems now.
The first one is called Distinguished Points.
Distinguished points work off this principle.
You again start with a large list of keys and for each of these your start computing
encryption functions, other than before though
you're not computing a certain number of encryption functions
but rather you're computing until you hit a certain distinguishing criteria.
Often times the number of zero bits at the end of your output.
Each of these computations are terminated very quickly or terminate very late
so they vary in length, the chains.
The number of zero bits, however, determines the average length.
So instead of a square data set, so to say
where you have a stable height and a stable width
you get more a zigzag data set where each line is of different lengths
but on average you will have the same coverage.
Now this solves the hard disk bottleneck because you don't have to go
through your computation and chainlink by chainlink look up on the hard disk.
You know that nothing that doesn't have the right number of zeros at the end
will ever be stored on the hard disk, so you keep computing
up to let's say on average a million and only then you have to do one hard disk look-up.
So this scheme is clearly superior to the first one
in that it requires the same number of encryption functions
it requires the same amount of storage but it only requires a single hard disk look-up.
So really now you are at seconds Terabytes and for the hard disk for milliseconds.
In solving the second bottleneck, the pre-computation expense
that's a little bit more tricky and there's a technique needed
that gives this whole project it's name, so-called Rainbow Tables.
Rainbow tables look as follows:
again, start with a long list of keys and you do the encryption function
for each of these keys as before, and you go through all the colors of the rainbow
in this case a million different colors with a million different encryption functions
before terminating your chain.
Whether or not you will need a high coverage very much depends
on your attack scenario, of course.
In GSM, for instance, as we saw before, there's a lot of different packets that are
attackable so maybe your coverage for each single one of them can be very low
and, in fact, in the project that we computed, the coverage is much smaller than 1%.
That's still enough to track each transaction with a probability much above 80%.
So, the Rainbow Table helped us to some degree
but we actually mixed it with Distinguished Points to kind of mix the benefits of both.