[Carson] If we treat an encryption function--as the one in GSM--as something
that takes a message, produces an encrypted message,
and it consumes a key to perform that.
There are different ways in which you can make this resistant against time-memory trails.
Three different mitigations.
First, you can make the message unpredictable.
Sounds obvious. Why would you encrypt something predictable?
But a lot of systems do just encrypt a whole stream of data,
some of which is encrypted. Something is worth protecting. GSM mixes the two.
[Dave] All of these attacks you know some--because of the GSM protocol--
there are some messages that are very easy to guess. >> [Carson] Exactly.
[Dave] And you know what they are and can you those in this attack.
To exchange a text message, for instance, between the base station and your phone,
somewhere between 20 and 40 messages are exchanged,
only one of which has the actual text message content.
Another one may have some unpredictable set of information.
All the rest is just management information--encrypted though--
and that management information is usually--
[Dave] Does it make sense as one solution to not encrypt the management information.
[Carson] Clear, yeah. There's a standard extension that suggests exactly that.
But basically the whole ecosystem would have to change to accommodate for that.
Currently, it's just the encryption is switched on at some point
and everything thereafter is encrypted, be it predictable or not.
There are measures, though, to make predictable messages more randomized
to create some wiggle room for how you send a message.
That's currently being deployed--not in all networks, though.
I've not seen--one of the two American networks I don't think has it.
You need to know the base station is understanding if you change the protocol like that.
The base station would have to change to go all the way of making all messages unpredictable,
but even changing the base station controllers, bigger installations
that control dozens of base stations that control dozens of base stations
would do the job, and those are usually software updateable,
because they have to accommodate for usually faster connections all the time.
Now, more secure connections that could that, too, hasn't been seen too much yet.
We do track that on gsmmap.org.
The second way, of course, of making this system uncorrectable
is to decrease the key size sufficiently so that none of these tradeoffs
leads to practical values anymore.
That is used, for instance, in 3G and 4G networks most of the time.
Then a third way of protecting against these types of attacks that assume,
if you predict a message you have a direct mapping between message out and key,
is to introduce an auxiliary input.
It's usually called either a "nonce" for random number or initialization vector.
GSM, in fact, does have an initialization vector,
so you would think that it breaks the correlation between key and message.
Now you'd have to compute your table separately for every nonce.
This is sort of like adding SALT to passwords.
Exactly. This is the exact same system as adding SALT.
This has been included in GSM.
However, the nonce is only effective if the attacker has to go for the key
to break the system.
There are different encryption functions that are attackable
with time-memory trade-offs in different ways,
in particular for block ciphers.
This protection measure works out of the box,
because the block cipher consumes the key, crunches it in complex ways
and outputs the message.
Unlike those, stream ciphers take the key, do once more computation,
do the same computation again, do the same computation again--
in the case of GSM 100 times--and then outputs the message.
It becomes a function that's consistent over very many smaller functions
and the nonce is, of course, only input at the very beginning.
To make this now resistant against time-memory tradeoff
their intermediate states--those results of the first round, second round, and so forth
to the 100th round--have to be a non-attackable time-memory tradeoff.
That sometimes is achieved by a large, internal state of the function.
For instance, the GPRS functions or etch function--2.5G networks--
they also consume a 64-bit key,
but they have an internal state of at least 96 bits.
That is a protection, because now the attacker has to go for the key after all.
However, if you use a small internal state, then the attacker can go to attack
that internal state and GSM falls exactly in this category,
and then the countermeasure doesn't work anymore.
So the internal state is still 64 bits. >>Exactly. >>Combining the key and the nonce.
Yeah. Message in, the key, and the message out as well as the internal state--
everything is 64 bits in GSM.
Of course, adding a large internal state doesn't come at a great cost.
It takes a few more flipflops and hyper-implementation or slightly larger words
in the software implementation.
This didn't prevent the attack that you described,
but the attack you showed us would actually be better than this.
To do the n lookups would have taken hours.
You were able to show it working in a manner of seconds or minutes.
To explain why JSM is more vulnerable, we have to go a little bit into this discussion
we started earlier on the hundred little functions instead of one big function--
what makes this a stream cipher.
This stream cipher consumes in the beginning both a key and IV, as we've seen,
but does a computation 100 times to produce an internal state
that is then mapped onto the output that's then XORed
with the message is basically the output message.
Interesting is this part, though.
Each of these links is such a small computation
that you can easily reverse it.
It is nonlinear, meaning you cannot really reverse it without 100% certainty,
but it's such a small computation that you can just kind of brute force the input space.
[Dave] Okay. >>[Carson] Right? So little--
[Carson] But the input space is small.
[Carson] Yeah, just a few bits change in each of these steps,
so you can just go through all the possibilities of input space and see which ones
map back to your output. Right?
Now, you may end up with several, so it's not always that only one of the inputs
would have produced. That's exactly the nonlinear property.
However, this may look as a complication at first
but does, in fact, help the hacker because each of these also generates
a key for some given IV that you assume.
Well, at least some. Some may be dead ends.
But at least in a lot of cases you can track one point that you store in your table
back to different keys. >>[Dave] I see.
Different starting key IV pairs lead to the same output.
Exactly, and on average, for each value that you store in the table
you have 13 keys that you find every time.
Only one of them will be the correct one.
Sometimes even all 13 are wrong. >>[Dave] I see.
[Carson] But if you do find a key it will just be one of them.
However, storing this point in the table is equivalent to storing 13 points in this table.
[Dave] Right, and now each lookup is the equivalent of doing 13 lookups.
[Carson] No, the lookup is actually the same effort, but the storage is decreased.
This is basically an inherit encryption function for rainbow tables
that this system comes with.
We are 13 times more efficient with this encryption function
than with a generic 64-bit encryption function.
Thirteen times and such a tradeoff with all the different tweaks
is the difference between hours and seconds.
[Dave] You're shrinking the table by a factor of 10,
which is making all the lookups less expensive. >>[Carson] Exactly.
Basically we're having 13 times more storage, and the crate of storage is quadratic.
We're more efficient as an approximation by this factor,
and that's the difference between seconds and hours.
That's why SMS can be snooped in seconds.