This talk will be by Sylvain Munaut
who works with the Osmocom project.
He will talk today about the osmo-gmr satellite phones.
After the talk there will be the opportunity to ask questions.
You can approach one of the microphones
and then you have the chance to ask one question.
Please give a round of applause to Mr Sylvain Munaut!
*Applause*
- Hi! Thank you for being here.
As he said I'm going to talk about satellite phones today.
I'll first talk with a quick recap of the previous work we've done.
At 28C3 there was a presentation on this subject.
But there were some pieces missing.
So, I'm just gonna recap what we did previously
and then move on to the new stuff
which is the speech codec and cipher
reverse engineering and cracking that's been done.
First, what is GMR exactly?
GMR stands for GEO-Mobile Radio and
it's an ETSI standard for satellite phones.
It's heavily inspired from GSM and
if you read the GMR specs
there is plenty of reference to go see the GSM spec.
There is actually two standards named GMR:
GMR-1 and GMR-2.
They are not an evolution of one another.
They are competing standards
that have been developed by distinct companies
and then both have been standardized to ETSI.
Today, we're gonna be looking at GMR-1.
That comes in 3 evolutions. It started with plain old GMR-1
which is voice calls and SMS.
It evolved to include packet data. That's called GMPRS.
And then there was a later evolution
to interconnect with the 3G core network
and improve the air interface and that's GMR-1 3G.
But we'll be mostly looking at the first version
which is still used.
Among the deployments the one we focused on was Thuraya.
The reason why is that it's the most common
commercial operator where you can actually buy SIM
and place phone calls.
The satellites are visible from Europe
which is kind of a requirement for me to look at the signal.
This operator is mostly active in the middle east, Asia and Africa.
In Europe you don't see too many people
with satellite phones because we have GSM coverage.
But there are other operators and we actually read recently
that there is a new deployment planned for Europe
called Solaris Mobile and they said
they're going to use GRM-1 3G
but the satellite isn't launched yet.
This is the coverage zone for Thuraya.
As you can see Europe is very well covered
so there is no problem if you want to receive the signal.
If you are somewhere in that area you can see it.
So, since it's so heavily inspired by GSM
it makes sense to compare it to it.
The first thing they did is to rename everything.
So, instead of a base transceiver station
you have a GEO transceiver station.
Instead of a base station controller
you have a GEO station controller.
Instead of a mobile station you have a mobile earth station.
Then they did some actual useful stuff like
use specialized features for satellites.
The first one is terminal-to-terminal calls.
When you're usually placing a call
your signal goes from your satellite phone to the satellite
then it goes back to the core network on earth
and then, if you're calling another satellite phone
it would have to again go back up to the satellite
and back to the other phone and that means that
you pay 4 trips from earth to space
and since the satellite is in geosynchronous orbit
it's pretty far away.
So, to reduce the delay in communication
they have the so-called terminal-to-terminal calls where
the call network will still handle establishing
the channel but once the call is established
the data is going directly from one phone to the satellite
and directly back down to the other phone
without any involvement from the network.
It never even sees the packets.
They also have this call called “High Penetration Alerting”
That's because like in the movies you see people using
satellite phones in bunkers and stuff like that
in practice, as soon as you are inside
you can't see the satellite and you can't place a call at all
but you still might want to be able to at least…
you know, you can't pick up the phone
but you want to know that somebody is calling you
and so they have this specialized channel
which has an incredible amount of error correction on it
so that even with very very low signal
you can still get an indication that somebody is trying to call you
please run outside so you can take the call.
There's also a very tight integration to GPS
For example, all the Almanac and Ephemeris data
are actually broadcasted by the Thuraya satellite
so that your phone can get a lock faster
and when you place a phone call the very first thing
that your phone will do is send your exact GPS coordinates
in clear to the operator.
They do this for two reasons:
The first one is: If you're not on the right frequency
for this particular geographic location they can tell you
“OK. You shouldn't be connecting on this frequency
use this one! It has a much better signal
and you get better quality”.
That's one reason. The other reason is purely commercial:
It's for billing because if you're calling
while you are in certain countries it's gonna cost more
than if you are on the other side of the border
and so they need to know where you are
to bill you correctly.
And then compared to GSM, of course, they introduced
the two things we're gonna look at today:
They changed the speech codec to something called AMBE
and they changed the cipher. They are not using A5/1
or A5/2 or A5/3 or that kind of stuff.
They use something called A5/GMR-1.
If you look at the protocol stack
anything in the lower layers
(radio modulation, TDMA frame structure)
it's completely different because you have to deal with
the particular of the satellite communication.
You find the same kind of concept
and you find the control channels and broadcast channels
but their implementation is different.
If you go up one layer to the data link layer
you have something very similar to LAPDm.
Again, they needed some minor adaptation
because bandwidth costs a lot on a satellite.
They reduce the size of the overhead by reducing the header
and since you have so much delay
going from your phone to the satellite and
back down to the earth station then again to your phone
you have something like nearly 500 ms of delay
because you have basically 4… no 250 ms, sorry,
because you have both paths up and down
and so, with that delay you need more time for the acknowledgement
to come in, so they increased the window size.
Anything above that, so, layer 3
radio resource, since it's managed the radio channel
is still a bit different but anything above that
is strictly the same as GSM. It actually interoperates
with the GSM core network which means I can take
my Belgian operator SIM put it into a Thuraya phone
and I can roam onto the satellite and place calls
which is really nice except for the price you pay
at the end of the month.
For packet data it's essentially the same thing.
Anything that's close to the lower level
like RLC and MAC is gonna be different,
anything above interoperates with GSM
so you're gonna be speaking to a GSM core network
SGSN and GGSN and all that good stuff.
So, osmo-gmr, what we presented last time,
is essentially everything you needed to go from RF to wireshark.
That includes the hardware setup
(how you can build an antenna, what LNA to use, what SDR receiver to use)
At that time we didn't actually have RTL-SDR,
the cheap DVB dongle you can use as SDR.
Nowadays we do which means that for less than 100 bucks
you can get an antenna, LNA and SDR receiver and all
that we need to listen to those signals.
Then we did all the SDR processing which is
taking that raw data, filtering it, selecting the channel
doing the demodulation getting actual data bits out of it.
Then, channel coding which is converting those data bits into
layer 2 frames. Then, interpreting those layer 2 frames
into channel assignment and follow those assignments
into a demonstration application.
And finally, the wireshark dissector which takes this
and presents it nicely in a way you can read stuff.
But there is two things we couldn't do:
First, we couldn't see past the ciphering mode command
which as soon as ciphering was enabled
we couldn't see anything because
we knew the key because it was our own calls
and we can read the key from the SIM
but we didn't know the algorithm that was used to cipher
so there was no way for us to decipher that.
And we also had no way to get the voice data,
converting the frame into actual audio that we can listen to
We couldn't do that and that's what we're gonna look into.
So the first thing is the speech codec.
It's called AMBE for Advanced Multi-Band Excitation.
It's not a codec in itself. AMBE is more a family of codecs
which means you have several codecs which are named AMBE
which are different versions of one another
slightly different so that they're not compatible.
It's not documented in the standard
which is really annoying. When I started working on GMR
I really thought that the codec was in there
and then I discovered it wasn't. That was a bad day.
There is a bit of specification in there
but it only gives a high level description like
“The codec takes audio as input and produces 80 bits of output
every 20 ms” but nothing that can be used to
realistically implement a decoder.
That codec is made by a company DVSI Inc.
whose entire business is codecs. That's all they do
which is probably why there are incompatible versions
of AMBE because they can sell different versions.
These guys, they do sell a small USB stick that
can decode some of the variants. For example, you can decode
DStar audio which is also another AMBE codec
or P25 which is used in law enforcement radio in the US
(it's also an AMBE variant)
and the cheap USB stick can decode that.
Unfortunately, it's incompatible with the GMR-1 variant
because that's the first thing I did, I contacted DVSI
to know what were my options.
And short of buying a source code license which is just too expensive
is buying the appliance which is called NET-2000.
And not only does it cost like 2000 Euros
which is way too much for a hobby project
but you also have to special-order it with a GMR-1 firmware
and you have to sign some non-reverse engineering agreement
which… That wasn't an option.
We still had some hope. The first hope we had is that
as I said P25 uses an AMBE variant as well
and this particular variant is actually documented.
So you can download the standard for that particular
variant of AMBE and you have all the math and all the specs
so you can write a decoder and somebody actually wrote
a decoder which is open source which is called ambelib
and so we can use that code as a base to modify it. That was a lead.
The other lead, of course, is that the codec is somewhere in the phone.
The phone is obviously capable of decoding audio
so maybe we can find it in there.
But before we can start searching for the codec
it's good to have a basic understanding of how the codec works
so that we know what we're looking for.
The first thing to understand: it's a vocoder.
It's not a general-purpose audio codec
which means if you try to feed it music it's gonna perform horribly
because a general-purpose audio codec will try to model
what your ear can actually hear and what it can't
whereas a vocoder is gonna try to model the speech
and reconstructs something that sounds like
but is not actually the same thing.
They will drop a lot of information.
To do that the first thing they do is to split your speech
into small segments which are compressed independently.
In the case of GMR-1 those segments are 10 ms long and
they are combined by pair and each pair is compressed
into a single frame. And then, for each of those small segments
they will represent it in 4 parameters. Those 4 parameters are
the pitch which is the fundamental frequency
of the periodic component of your voice,
the gain which is how loud you are talking,
something called voiced/unvoiced decision,
we're gonna see what this is right after
but essentially you have the fundamental frequency
and for each harmonic, two times the frequency,
three times the frequency, four times the frequency,
you have a bit that says is that component voiced or unvoiced
and then you have the amplitudes for the various harmonics.
If you want to play back the voice you have to do 3 things:
The first thing is unpacking.
That's taking the 80 bits of the voice frame
and reconstruct quantized parameters from it.
All the parameters are not just put in order one after the other
because some of the bits in a frame will receive more error correction
than others and some of the bits are more sensitive to errors than others
and so they will be placed at specific places in the frame
so that if errors do happen, hopefully it will affect something
that is not too important.
That's the unpacking step.
The second one is dequantization.
That's going from the quantized, compressed parameters
into floating point value or integer values
which will represent the real parameters
that are going to be used in the last step
which is synthesis. And synthesis is taking those parameters
and reconstructing actual audio that sounds like the original voice.
To do a quick overview of the synthesis step
what you do is you take for each possible harmonic,
so, f0, 2 f0, 3 f0,…
you have the voiced/unvoiced decision
and what voiced means is that you're gonna reconstruct
that particular frequency as a pure sinusoidal tone,
and if it's unvoiced you're just gonna fill that small band with noise.
And with that they can reconstruct human voice pretty well.
So, now that we know more or less how the codec works
and what we are looking for
we can start looking at where we are gonna find this codec.
The phone we looked at is the Thuraya SO-2510.
We looked at it mostly because it was the cheapest phone on eBay.
And that also means that it's the simplest
which means you have less places to look into.
We knew the codec was in the DSP. How did we know that is that
there is simply no other places it could be.
There are a bunch of chips on that phone, of course,
there is only two where it could possibly be:
the TI OMAP main processor,
and then they also have like a small ASIC
which is named the DALMA ASIC because
there is a big DALMA marking on it.
At first, we thought that that chip was the AMBE codec.
But it turned out that we found some Korean paper
from the phone manufacturer that described
the phone architecture. And there is a schematic
of the internals of that ASIC and it showed
it only had satellite radio functions
and absolutely nothing to do with the codec
which means there was a good chance it was in the TI OMAP processor.
Why in the DSP? Well, because it just makes sense
to make the codec in the DSP especially since DVSI
the company that makes the codec mostly sells those codecs as a
DSP precompiled library that you can buy.
Pretty standard process: We get the firmware update from the Internet.
From there we can extract the actual DSP image
which is the code that is loaded into the DSP.
Thankfully it's supported by IDA
which makes the whole process easier to reverse engineer.
But it's still like 250KB of binary data
and since it's a DSP it has no I/O
which means there is not a single string in it.
And also it's a DSP which means it's written in DSP assembly.
I don't know if you ever tried to read that
but it's not the most understandable thing in the world
because it's highly optimized for speed, of course.
And I actually looked at that code and went over it a few times
and took a few hours and looked at it
and I couldn't see anything in it.
And one day I get an email from a colleague in OSMOCOM,
Dieter Spaar, asking me if I had ever looked at that codec
and I told him “yeah I looked
but I couldn't really find anything.
Do you see anything?”
And six hours later he sent me
“I think this is the entry point
for the encoding and decoding functions”
“Oh, OK. Good!”
The way he found that from what I remember is that
you look at what would a codec use.
And of course it's gonna access the audio path
so you can look at the audio DMA setup, and audio DMA interrupts.
You can also look for constants that you know are used in the codec,
for example, I said that the frames are 80 bits,
so you can look for the constant 80 somewhere in the code.
You can look at it.
It will produce 160 audio samples per frame decoded
so you can look at the constant 160.
Once you actually found one function
there is something that kind of stands out,
it's that since they ship that as a binary library
they don't really trust the guy who implements the rest of the DSP code
to setup the C runtime properly
and so what they do is they switch everything at each call into the codec.
They switch the stack, they re-setup/reconfigure the C runtime,
so that it's really independent.
Once you find one function, finding the other is pretty easy,
you can just look for that particular function prelude
that happens at each call at the audio library.
OK, so, we know where the code is
but it's still a massive amount of code.
I think it's like one third of the DSP code is the audio codec.
So, It's not something you can easily reverse engineer in a few hours.
So, before trying reverse engineering we just tried,
OK, maybe we can just run it.
It turns out that TI has this really nice program called
TI Code Composer Studio which includes a simulator
and it's a really nice piece of software because
not only can you pretty accurately simulate any of the DSPs
you can also completely configure the surrounding environment
in which it runs so you can setup arbitrary memory map.
You can also trace all memory access to see what part
of memory is being read or being written or being executed.
You can also access a file on your host system.
So you can use fread and fwrite
and the simulator would automatically translate those calls
into actual reading from the audio, hard drive and write to your hard drive
so you can read a compressed file that you saved
and it will write an audio wave file at the output.
And the way to do that is pretty straightforward.
You essentially just need to take the binary dump that
you have from the firmware update
and you need to find a way to mix in your own custom code.
The way to do that: You create a new object file like ELF
except in this case it's called COFF, a common object file format.
But it's the same idea.
You can just link to it like you would link any other piece of binary.
You write a simple main function
that will basically fread your compressed samples,
call the decoding function or at least what you hope
is the decoding function and fwrite the audio samples.
And surprisingly it worked. It didn't require that much effort.
In like a couple of days it was all working.
It didn't work on the first try. There was a couple of pitfalls.
But essentially the IDE is there and it can probably be applied
to other things as well.
Of course there is some pretty big downsides.
At first, it's pretty slow. Definitely sub-real-time
even on a modern laptop.
It also requires TI Code Composer Studio
which is a Windows application and it's also not free.
You have a 30 days evaluation period but that's about it.
So it's really not that practical.
But it was running in the simulator.
There is no real reason it cannot run on real hardware.
Of course, that's what we try next.
Unfortunately, on real hardware
you can't just put memory anywhere you want.
When the codec runs in the phone,
it runs inside a TI-OMAP which is an ARM plus a DSP
and that chip has an MMU which means
you can create any virtual memory you want.
But if you're trying to run on a cheap DSP board
that you can get for 50 bucks,
those usually don't include an MMU at all
which means you need to find a board
which has memory at the right places
because the binary you have has been linked to a specific physical addresses
and it needs to run at that particular addresses.
Thankfully, Dieter found one such board with a compatible memory map
and it had SDRAM. Well, we needed it to have some memory.
It also included Ethernet which means we can make some networked appliance
where we submit samples and get them back.
That was really nice.
The process of migrating the code from the simulator
to the board is actually pretty smooth because
of the way TI Code Composer Studio works.
You just basically select that as a target
and since the memory was at the right place it pretty much worked.
Now, it wasn't quite as fast as we want it
because it was only running about real-time at the first try
and that's because SDRAM is slow especially when you do
a bunch of random accesses the SDRAM isn't really fast.
The codec has unfortunately a lot of big data tables
which are accessed constantly like to compute cosines.
So, what Dieter did is basically identify a couple
of those big tables that are accessed very often
and then just migrated them to internal SRAM.
You just find the one or two places
where the code reads from those tables
and just patch the address to another address
and redirect it to there.
And that got the code running much faster, about 16x faster than real-time.
And honestly, that was good.
I wasn't really planning on doing anything else on the hardware
and so I ordered the same board… except I didn't.
I somehow ended up clicking on the wrong button in the
TI store or something and when the board arrived
I didn't have the right one.
At that point I had two choices:
I could just order the same board
and wait one more week,
or I could try to run the code on it anyway.
The second board didn't have Ethernet. It had USB.
But most importantly it didn't have any SDRAM at all.
It only had internal SRAM
and unfortunately not at the right address.
So I just figured: OK. I'm just gonna try to relocate the binary
and make it run on another address. How hard can it be?
It turned out to be pretty straightforward because
in I think less than a day it was running
and that's really thanks to IDAPython and the simulator.
Basically what I did is in IDAPython which is the
scripting language in IDA reverse engineering software
you can iterate through all the opcodes, then for that
opcode you can test: Is there an absolute memory reference
somewhere in that opcode? If no, then don't do anything.
If there is an absolute memory reference,
is that reference falling somewhere in a place that
I'm trying to relocate or not? If it is a place
I'm trying to relocate then just patch that opcode
and change the absolute memory reference to the new place.
Go through all the code like that and try to run it.
Of course, it didn't work the first time around
because there was a couple of pitfalls in that approach
but using the simulator it was pretty easy to find out where
things were going wrong because you take the original code
you run everything in the simulator and you trace every
memory access, then you take your potentially relocated code
you run it again in the simulator and trace every memory access
Decoding the same frame it should be deterministic
and so you should have the exact same memory access patterns
in both cases. And as soon as you see that they are diverging
you know that somewhere a branch wasn't taken or
something went wrong and you can go at that place in your code
look and see why the relocation didn't work.
It only took two tries to have the code running.
It was running on my board and I didn't have to order a new one
which was pretty nice.
So we have a hardware USB decoder
which is very useful but you still have to carry it around
or plug it into a network server or something
which isn't necessarily something you want.
I wanted something I could checkout into git, basically.
So, I started reverse engineering the entire codec.
Now, it turned out to be very painful.
As I said, to reconstruct audio you have three main steps.
The first one is unpacking and it's just basically bit shuffling.
It's like the first thing the codec does which means
it's really easy to find and it's really easy to follow.
So, no problem there.
The second step is dequantization and it took like 95% percent
of the work because it's lot of math.
It's all written in DSP assembly, in fixed-point
and sometimes you're looking at a function to figure out
what that function does you have to run it with different
parameters to see what does that thing compute.
Graphing is really useful for that. You just feed some
inputs into the simulator see what output is generated
and just plot it in PyLab or something.
And then you can see, OK, that actually computes a logarithm.
There is still a lot of code there and there was no
other option for that part because the quantization step
is completely specific to GMR. It's not shared with any
of the other AMBE variants.
The synthesis part is even more complicated, is even more
code in the DSP but I really didn't want…
after finishing the dequantization I really didn't want
to the synthesis, so I just assumed that the synthesis step
was gonna be very similar to the one in P25.
So I took the mbelib existing open-source code for P25,
I ripped out the unpacking and dequantization out of it.
That's because it's the one for P25, of course.
I just plugged in my own implementation
and run it through the synthesis.
There's a couple of things you need to take care of
mostly because P25 uses 20 ms frames, GMR uses 10 ms frames.
So, I basically dropped one frame every other frame in GMR
and just used the 10 ms parameter synthesized 20 ms of speech
but it produced something where you could follow
a conversation and it worked.
I was still not really happy about it because the code quality
of mbelib was really not that good.
Its performance is also not that good.
It wasn't actually faster than the hardware decoder.
So, in the end I went back to the actual P25 specifications
that I had and rewrote a clean implementation
of the synthesis step. I just guessed the difference.
Every time it says 20 ms I just put 10 ms. When there is
a 512-bin FFT I just put 256
and adapted stuff as I went.
And the resulting code is in the git
and you can decode voice.
I think it works pretty well.
You can hear some subtle differences
compared to the original codec
because DVSI did do a bunch of stuff to
improve the voice quality. It's their whole business.
And I didn't go through all of that.
But… From my point of view, I'm done on this and I'm not
gonna go any further. We have C code we can run.
So. That's good.
*Applause*
Thank you.
Next, we move on to the cipher.
We didn't reverse engineer the cipher.
That was done by a team at the Bochum university
led by Benedikt Driessen.
Right after we publ… After 28C3, basically…
Actually, at 28C3 we already had some contacts with them but
the paper wasn't published yet.
And we actually have them validate their data and their attack
using osmo-gmr.
I definitely encourage you to read the paper that they published
because the method they used. They are actually the ones
who extracted the DSP image which we used to reverse engineer the codec.
They were the first ones to extract it from the
file that you can download online.
And then, there is some pretty interesting stuff in there.
As I said, they also published an attack on that cipher
which is a ciphertext-only attack
and I'll show some of the results later on.
So, what does the cipher look like? Well, it looks like that.
If you are familiar with A5/2 or even A5/1
that should look very familiar because
it's pretty much the same thing.
So you have 4 linear feedback registers.
The first 3 ones are combined using a nonlinear output function
into the actual key stream. And then you have a 4th register
which a few of the bits are tapped. They go to a nonlinear
clocking function and that function is gonna determine
how fast the other registers are clocked.
So, not all registers advance at each output bit.
And as I said, it is very similar to… it's actually a copy of A5/2
except they changed every number like… they don't…
the polynomial for the linear feedback registers are different,
which bits are tapped to combine into the output are different.
Same thing for R4 but it's the exact same structure
which means we can reuse the attack that works on A5/2.
This cipher obviously has an initialization step
where you basically take the key and the frame number
that you want to encrypt
and you have some process to initialize
the LFSR with those data.
But really the only thing to retain
is that the initialization process is entirely linear.
There is some XOR and LFSR being involved.
So that's pretty much…
…the thing to remember.
The actual irregular clocking only is applied when you
generate bitstream for encrypting the frame.
Since we are gonna talk about attacks on ciphers
in some details there are a few things that you may not remember
if you don't do algebra all the time.
This is a very very quick reminder.
So, you should know is that when you see GF(2) that's
just a fancy term for binary.
What we call addition in GF(2) is just the XOR operation.
Multiplication is just the logic AND
and you can do everything with that.
If you accept those definitions, then algebra over binary
is gonna be pretty much the same as algebra over real numbers
and all the nice properties are gonna be applicable
to binary math as well.
I mentioned previously “linear” and I will mention it
several times in the rest of this talk.
When I say “linear” it's either a constant,
or a variable or unknown multiplied by a constant
but you never have two variables multiplied together
because then it becomes quadratic and it's not linear anymore.
Being linear has some nice properties like linear systems of equations
we have very fast algorithms to solve them
and every linear operation can be represented as matrix operation
which is especially useful… we're gonna be dealing with
hundreds of unknowns and spelling them out is not an option.
We have to have some way of representing that and that's
matrix operations, essentially.
One other important thing to know is:
When you have an operation that adds redundancy, for example,
channel coding where you add the CRC
or where you do convolutional coding,
adding error correction adds redundancy to your message
and when you have redundancy you can create what's called
a parity check matrix to check if that redundancy in that present.
So, for a CRC you check the CRC for example.
But it can be generalized to anything that adds redundancy.
It can be checked. And that becomes very useful to
make the attack much faster.
So, a little more detail about what the guys at Bochum did.
They published a ciphertext-only attack
that means you only need to capture data off the air
and directly with that you feed it to the attack
and it can give you the key.
Their target was called TCH3 frames
and those are traffic frames, they're what carries the voice
which means you have a lot of them because
as long as the conversation is still going,
frames that are being generated constantly,
several tens of them per second.
They didn't start from nothing. As I said
the cipher is heavily based on A5/2, so,
it kind of makes sense to read the papers
that were published about A5/2 attacks.
The most interesting one and one of the most advanced one is called
“Instant Ciphertext-Only Cryptanalysis of GSM encrypted communication”
It's kind of math-heavy but
it provides an attack on A5/2 that recovers the key instantly
which is really nice.
They modified this attack. They tweaked it for GMR-1
because the frames are different.
There's different amount of bits.
The cipher is slightly different.
And they also did something a little weird.
They tried to guess more bits
some of the bits they tried to brute-force.
I'm not exactly sure why.
I think it's to reduce the number of unknowns.
But I don't know if it actually had the desired effect.
And in the RUB paper they published their result:
With 350 GB of precomputed data using 32 TCH3 frames
they managed to recover the key in something like 40 minutes
which is not bad, definitely, and it works.
But the original attack is named “instant”.
40 minutes isn't instant – to me, at least.
So, we started looking for a better attack.
We started off the same paper because it's kind of
the state of the art of A5/2 attacks
but we really didn't do anything fancy.
We just used it exactly as they said in the original paper
and we just did the necessary tweaks for A5/GMR-1,
changing the matrix and the length of the vector,
really nothing fancy.
We also decided to attack a different type of channel
and this is probably what makes the most difference.
We decided to target FACCH3 control frames
instead of the TCH3 voice frames.
There is a very big advantage to targeting those frames.
First, they use a different kind of modulation and training sequence.
From an RF point of view they are much easier to receive.
And that's pretty important if you're trying to mount an attack because
as soon as you have a bit error in the reception
it will make your equations inconsistent
and you won't actually be able to solve for the key as easily.
So, this is a very nice property of those frames.
The other very nice property is that we have known
plaintext on the FACCH3 channel, the control channel.
There are some predictable frames that we know will there
and we know where they will be.
the voice traffic is completely unpredictable.
It's someone talking.
The control traffic will follow some very known patterns
and I'll show an example of plaintext which is really trivial.
Some other of the nice properties of the control channel is:
There is much more redundancy.
In TCH3 not all the bits are actually error-corrected
which means you don't have that much information
while for the control channel each layer-2 bit that you transmit
is almost quadrupled before you put it on the air
which means you can build a lot of equations very fast
without many bursts. In the RUB attack they needed 32 frames,
probably because there is not much redundancy in the TCH3 frames.
And also, as a nice bonus that we discovered later is that
the FACCH3 control channel is also used to negotiate
other types of channels like the channels that are used
when you send FAX or when you establish a data call
over satellite networks.
It's actually negotiated using that type of control channel
which means the same kind of attack can work to crack
not only voice but also data calls and FAX.
This is an example of the plaintext.
I don't know if you can really see it.
But essentially on the top you have the cipher mode command
the first line in blue is the cipher mode command.
So everything after that is in theory ciphered.
This is, of course, the enciphered view.
And the three marked packets in gray and black
are the very predictable texts
and what they are is acknowledgements.
Because of the delay on the GSM channel
there is some outstanding acknowledgement
that still need to be sent when the ciphering is turned on.
You get empty packets with incrementing sequence number
and the ACK bit set.
Something changes in them, the sequence number, but
as soon as you can count, predicting them is trivial.
This definitely works in practice like 100% of the time.
I never really had any problem with that.
So, how do you build a plaintext attack?
The general goal is… what you're trying to achieve
is build a giant system of equations that's linear
and that you can solve.
It's gonna have the form A * x = b
b is the cipher stream that is generated by A5/GMR-1
x is some representation of the internal state of the cipher
that you are trying to find
and A is a giant matrix that you can precompute
that's only dependent on the structure of the cipher.
Each row of A and b are gonna represent one bit of the output
and how to combine that internal state to generate that cipher stream bit.
As I mentioned, the initialization process is linear
and that's very important for two things.
First, from the internal state of the cipher
you're gonna be able to recover the key
which is not entirely true. There is one bit of the key
that you can't recover because that bit of the key
turns out to have absolutely no effect on the output whatsoever.
so, you can't recover it but doesn't matter either.
The other thing is that
you're gonna need to build a lot of equations.
That system is gonna be big.
In a single burst of data you won't have enough equations.
You're gonna need multiple of them.
But, of course, those multiple bursts are gonna have different
frame numbers because they're sequential.
They're not gonna wrap before a long time.
But since the initialization is entirely linear
you can actually derive equation from one frame number
from an equation built out of another frame number.
But, of course, it would be too easy. The cipher isn't entirely linear.
so, we have to “linearize” it and
when I first started looking at a crypto attack on A5/2
in the paper it was always one line that said
oh yeah, we linearize the cipher
and they kind of always assumed the readers know what that means
which I didn't at the time.
So, I decided to be a little more explicit.
The two nonlinear elements are the output function
which uses a majority function where you take three bits
and it outputs whichever bit is more common
and you can rewrite that majority function as being
the sum of a plus b multiplied by c
or if you wish a XOR b AND c.
And the problem is the b multiplied by c because
that's quadratic, that's not linear.
That means that we can't introduce that.
And the way to linearize that is to kind of ignore it.
For every possible quadratic term that's gonna be generated
by that nonlinear output function
you generate a new unknown.
In reality that unknown isn't really unknown.
It's a function of your other variables but
you can't represent it in a linear fashion.
So, you just ignore it and say “OK, this is a new unknown, deal with it”.
Actually, there is a lot of possible combinations
which adds 594 new unknowns to your equation system
which means that you're gonna need a bunch more equations
to be able to actually solve it.
But at least it makes it linear. So, there is hope.
The other nonlinear thing in that cipher is the clocking.
As I said, all the LSFR don't advance at the same rate.
Some are clocked once or zero times at each output bit.
And this is a function of the value of R4 at that particular time.
So, how do we linearize that?
Well, R4 is a 17-bit linear feedback register.
So, we can know all its future states from any…
As soon as we have a good state at one particular time
you can predict all the future states
because it's clocked all the time.
And in those 17 bits the initialization step forces
one of those bits to one.
So, there is only 16 bits that you don't know
which means there is only 65536 possible clocking
patterns for the cipher.
So, the way we approach that is we just brute-force it.
You just assume that R4 is gonna be equal to that value
after the initialization and you just assume that
and try to solve and crack the cipher by using that assumption.
And if you find the Kc, well, then maybe it's the right one.
You just repeat that 65536 times and most of the time
if your guess about R4 is incorrect
the system will end up being inconsistent
and you won't actually have any solution.
But this still requires solving 65536 systems
which is fast but not that fast.
There is actually a trick that we can apply to do better guesses.
When you build these giant equation systems
it turns out that some of the equations that you construct
they are not gonna be independent. Some of them are
gonna be related to each other.
And so some of the rows are redundant. And what's nice is:
If they're redundant we can actually test for that redundancy.
For the 65536 possible systems that you need to solve,
you also have an An * x = b
there is a bunch of rows in An that are gonna be linear dependent.
So, for each of them you can build a parity check matrix Hn
so that you have this nice property of a parity check matrix
where you multiply b by Hn and you get a zero matrix.
But all those Hn, you can precompute them.
That's the offline data of the attack.
You precompute those giant matrices,
then you take b which is the cipher text you got from the cipher,
you multiply it by this matrix and if it gives you zero,
you know that this particular R4 value might be correct.
You don't know if it's correct or not,
but at least it might be.
If the result is non-zero then you know that R4 is definitely
not the correct R4 and so instead of solving an entire
system of equations the only thing you need to do is
do one matrix multiplication and that is pretty fast.
And in the end you're gonna have a couple of possible matches
so you're gonna solve like maybe 3 or 4 systems of equations
instead of solving 65536 and that's much much faster.
Now, how do you go from a known-plaintext attack
to a ciphertext-only attack?
I'm not gonna detail that much but essentially
the channel coding operation introduces redundancy
and you can kind of null out that…
if you take the last equation you have
H multiplied by y plus g.
H is a function of the channel coding.
You can compute it. It's known.
y is the data that you received off the air.
So, you know it as well.
g is also a function of the channel coding operation.
So, you know it. So everything on the left you know.
And the last value is H multiplied by A
which is what you had in the known-plaintext attack,
so you know it as well.
And everything you don't know is x and so, again,
you have a linear system of equations that you can solve.
And the same R4 quick-scan method can be applied
to scan very quickly and not have to solve everything.
So, this is the result.
If you use the fact that you know some plaintext
you need about 50 Megabytes of data precomputed,
you need to receive 8 bursts or even 4 if you
by any chance have the right frame number alignment,
and in like 500 ms you can get the key back.
And that's on a 6 year old laptop.
On any recent machine it's really instant.
If you want to use the ciphertext-only variant,
and honestly I really don't know why you would
because the known-plaintext works, so you might as well use it.
But if you want it purely for academic purposes,
then you need 8 bursts,
about 5 Gigabytes of data,
and then it takes a little longer
like about 1 second to recover the key.
A few things I would like to look at in the future,
is C-band.
The satellite has to talk back to the earth station
and this happens in a different frequency band
and this is what we would like to look at,
essentially, the feeder link
If any of you have a large dish, satellite dish,
and want to provide data for us please contact us,
we're looking for it.
We're also started looking into packet data
and some other stuff.
A quick note about other satellite phone systems,
please don't assume that just because Thuraya GMR-1
is broken that the others aren't unless you have
actual proof that they aren't because the only
reason we chose Thuraya is because the phone was
the cheapest on eBay.
So, given that all the satellite phone systems also…
you know, you can find commercial interceptors for them,
there is a big chance that they're not much more secure.
I like to thank a few people:
Dimitry Stolnikov, the main other author in osmo-gmr
doing a bunch of the RF capture stuff,
Dieter Spaar for reverse engineering of the AMBE codec
and all the help he provided there
and the RUB team, of course, for their support in
reverse engineering the cipher,
and the organizer for having me
and thank you for your attention!
*Applause*
- Thank you very much! We now have time for a few questions.
First, are there questions from the Internet?
Not yet. So, if you have a question, please
approach one of the microphones.
Yes, please, microphone number 3!
- Yes, I have a rather not technical but political question:
So, you said in the beginning there was like a short
way of communication that only the satellite transmits
the voice data, so there is no ground station involved?
- Yes. - Do you think that this might upset some of the people
who like to intercept calls because it makes intercepting
the voice data much more complicated
than just going to ground station and say
“I want to listen to this”?
- First, just because the satellite will send the data back
directly to their mobile phone
doesn't mean the satellite can't also provide a copy
of it to the earth station. It just doesn't go through.
But the satellite can obviously send a copy of it if they want to.
- And probably there will be a possibility for the ground station
to say “Don't do that direction connection”.
- On the other hand they can also just intercept it off the air
because it's so easy to listen to it.
Last year there was a talk with somebody
that looked at satellite pictures
and they saw that one of the spy satellites was relocated
like right next to the Thuraya-2 satellite.
You can look that up. It was a presentation last year.
It was pretty interesting to see that… yeah…
If you want to listen to it you can do it.
- Thank you!
- Next question from microphone number 2!
- I've two questions: Can you hear both sides of the conversation
or only one side of the conversation? The second question is:
How big of a dish do you need?
- If you want to receive L-band which is
just listen to the communication from the satellite to the phone
you don't need a dish, you need like a small antenna.
You can even do it with a modified GPS antenna and a piece of metal.
So, it's really easy and really cheap to do.
You can only hear the the part of the conversation
that comes from the satellite to the phone.
So, if by any chance that guy is speaking to another phone
you can hear both sides because you can intercept both
channels simultaneously.
But in general, you either
only hear one side or you can also be close enough to the
actual satellite phones to receive the uplink
that goes from the phone to the satellite.
Dimitry showed me like a commercial intercept system
where apparently they use like planes to intercept the uplink.
They just fly over the area of interest
so they can more easily receive the uplink from the phones.
- One final question. Please make it short
because we are running out of time.
- I'll try my best.
Launching your own satellite is certainly not an option
but do you see any practical applications
in terms of what you did with GSM?
- Not really. It would be interesting to try start a net
because there is nothing that says that you have to be on a satellite.
You could technically start a base station on earth
using that protocol and it would work.
And the phones have much more power than a GSM phone.
But other than that, you could build an IMSI catcher
for satellite phones if you wanted to
and you'd definitely beat the signal strength of the satellite
with your own setup.
- Thank you.
- Please give the speaker another round of applause!