Sylvain Munaut: osmo-gmr: What's up with sat-phones ?

http://media.ccc.de/browse/congress/2014/31c3_-_6267_-_en_-_saal_g_-_201412271600_-_osmo-gmr_what_s_up_with_sat-phones_-_sylvain_munaut.html

At 28C3 we introduced the very first steps of the osmo-gmr projects. During this talk, we will present the various advances that have been made in this project on various aspects (voice codec, crypto algorithm, ...)

Sylvain Munaut

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!

subtitles created by c3subtitles.de
Join, and help us!