= Specification for IMSI Pseudonymization on the Radio Interface for 2G and Above

== Introduction

=== Protecting the IMSI on the Radio Interface is Desirable

A long-standing issue in the 3GPP specifications is, that mobile phones and
other mobile equipment (ME) have to send the International Mobile Subscriber
Identity (IMSI) unencrypted over the air. Each IMSI is uniquely identifying the
person who bought the associated Subscriber Identity Module (SIM) used in the
ME. Therefore most people can be uniquely identified by recording the IMSI that
their ME is sending. Efforts are made in the 2G and above specifications to
send the IMSI less often, by using the Temporary Mobile Subscriber Identity
(TMSI) where possible.

But this is not enough. So-called IMSI catchers were invented and are used to
not only record IMSIs when they have to be sent. But also to force ME to send
their IMSI by immitating a Base Transceiver Station (BTS). IMSI catchers have
become small and affordable, even criminals actors without much budget can use
them to track anybody with a mobile phone.

=== Summary of Proposed Solution

The solution presented in this document is to periodically change the IMSI of
the ME to a new pseudonymous IMSI allocated by the Home Location Register (HLR)
or Home Subscriber Service (HSS). The next pseudonymous IMSI is sent to the SIM
via Short Message Service (SMS), then a SIM applet overwrites the IMSI of the
SIM with the new value. The only component that needs to be changed in the
network besides the SIM is the HLR/HSS, therefore it should be possible even
for a Mobile Virtual Network Operator (MVNO) to deploy this privacy
enhancement.

=== Summary of Existing Location Updating Procedures in RAN and CN

The subscriber's SIM is provisioned with the IMSI and cryptographic keys of a
subscriber, after the subscriber was added with the same data to the HLR/HSS.
In the Remote Access Network (RAN), the IMSI is sent over the air interface and
then transmitted to the Core Network (CN), where it is validated by the
HLR/HSS. The involved components vary by the generation of the network and
whether the SIM is attempting a Circuit Switched (CS) or Packet Switched (PS)
connection, but the principle is the same. This document uses 2G CS Location
Updating for reference, as in <<figure-imsi-regular>>.

The IMSI is transmitted in the Location Updating Request from ME. The VLR
needs an authentication challenge specific to the secret keys on the SIM to
authenticate the SIM, and looks the authentication challenges up by the IMSI.
If the VLR does not have any more authentication challenges for the IMSI (as it
happens when the VLR sees the IMSI for the first time), the VLR requests new
authentication challenges from the HLR. Then the HLR verifies that the IMSI is
known and, if it is unknown, sends back an error that will terminate the
Location Updating procedure.

After the VLR found the authentication challenge, it authenticates the SIM, and
performs a Classmark Enquiry and Physical Channel Reconfiguration. Then the VLR
has the required information to finish the Location Updating, and continues
with Process Update_Location_HLR (3GPP TS 29.002). Afterwards, the VLR assigns
a new TMSI with the Location Updating Accept, which is acknowledged by the TMSI
Reallocation Complete. In following Location Updates with the same MSC, the ME
sends the TMSI instead of the IMSI in the Location Updating Request.

[[figure-imsi-regular]]
.Location Updating in 2G CS with IMSI
["mscgen"]
----
msc {
  hscale="1.75";
  ME [label="ME"], BTS [label="BTS"], BSC [label="BSC"], MSC [label="MSC/VLR"],
  HLR [label="HLR"];

  // BTS <=> BSC: RSL
  // BSC <=> MSC: BSSAP, RNSAP
  // MSC <=> HLR: MAP (process Update_Location_HLR, 3GPP TS 29.002)

  ME   => BTS [label="Location Updating Request"];
  BTS  => BSC [label="Location Updating Request"];
  BSC  => MSC [label="Location Updating Request"];

  --- [label="If necessary: VLR requests new authentication challenges for this IMSI"];
  MSC  => HLR [label="Send Auth Info Request"];
  MSC <=  HLR [label="Send Auth Info Result"];
  ---;

  BSC <=  MSC [label="Authentication Request"];
  BTS <=  BSC [label="Authentication Request"];
  ME  <=  BTS [label="Authentication Request"];
  ME   => BTS [label="Authentication Response"];
  BTS  => BSC [label="Authentication Response"];
  BSC  => MSC [label="Authentication Response"];
  BSC <=  MSC [label="Classmark Enquiry"];
  BTS <=  BSC [label="Classmark Enquiry"];
  ME  <=  BTS [label="Classmark Enquiry"];
  ME   => BTS [label="Classmark Change"];
  BTS  => BSC [label="Classmark Change"];
  BSC  => MSC [label="Classmark Update"];
  BSC <=  MSC [label="Physical Channel Reconfiguration"];
  BTS <=  BSC [label="Ciphering Mode Command"];
  ME  <=  BTS [label="Ciphering Mode Command"];
  ME   => BTS [label="Ciphering Mode Complete"];
  BTS  => BSC [label="Ciphering Mode Complete"];
  BSC  => MSC [label="Ciphering Mode Complete"];

  --- [label="Process Update_Location_HLR (3GPP TS 29.002)"];
  MSC  => HLR [label="Update Location Request"];
  MSC <=  HLR [label="Insert Subscriber Data Request"];
  MSC  => HLR [label="Insert Subscriber Data Result"];
  MSC <=  HLR [label="Update Location Result"];
  ---;

  BSC <=  MSC [label="Location Updating Accept"];
  BTS <=  BSC [label="Location Updating Accept"];
  ME  <=  BTS [label="Location Updating Accept"];
  ME   => BTS [label="TMSI Reallocation Complete"];
  BTS  => BSC [label="TMSI Reallocation Complete"];
  BSC  => MSC [label="TMSI Reallocation Complete"];
}
----

<<<
== Required Changes

=== Pseudonymous IMSI Storage in the HLR

The HLR must store up to two pseudonymous IMSIs (imsi_pseudo) and their related
counters (imsi_pseudo_i) per subscriber. Each subscriber initially has one
pseudonymous IMSI allocated. A subscriber has two valid pseudonymous IMSIs
only during the transition phase from the old pseudonymous IMSI to the new one.
The amount of available IMSIs must be higher than the amount of subscribers
registered with the HLR. If the amount of available IMSIs is too short, the HLR
can delay assigning new pseudonymous IMSIs until new IMSIs are available again.

.Examples for additional subscriber data in HLR
|===
| Subscriber ID | imsi_pseudo | imsi_pseudo_i
// example IMSIs taken from Wikipedia
| 123
| 310150123456789
| 1

| 234
| 502130123456789
| 1

| 234
| 460001357924680
| 2
|===

==== imsi_pseudo

The value for imsi_pseudo is a random choice from the pool of available IMSIs
that the HLR controls. The pseudonymous IMSI must not be used by any subscriber
as pseudonymous IMSI yet, but may be the real IMSI of a subscriber.

[[hlr-imsi-pseudo-i]]
==== imsi_pseudo_i

The counter imsi_pseudo_i indicates how often a subscriber's pseudonymous IMSI
was changed. The value is 1 for the first allocated pseudonymous IMSI of a
subscriber. When allocating a new pseudonymous IMSI for the same subscriber,
the new imsi_pseudo_i value is increased by 1. The counter is used by the SIM
applet to detect and ignore outdated requests related to changing the
pseudonymous IMSI.

=== SIM Provisioning

The HLR is allocating a pseudonymous IMSI for the subscriber. This pseudonymous
IMSI is stored as IMSI on the subscriber's SIM instead of the real IMSI.

==== SIM applet

The SIM is provisioned with a SIM applet, which is able to change the IMSI once
the next pseudonymous IMSI arrives from the HLR. A reference implementation is
provided in <<reference-src>>.

The SIM applet registers to a suitable SMS trigger (3GPP TS 03.19, Section
6.2). When an SMS from the HLR in the format of <<sms-format>> arrives, the
applet must verify that the SMS is not outdated by comparing imsi_pseudo_i from
the SMS with the last imsi_pseudo_i that was used when changing the IMSI
(initially 1 as in <<hlr-imsi-pseudo-i>>). The new value must be higher,
otherwise the SMS should not be processed further.

The SIM applet registers a timer with min_sleep_time from the SMS. When the
timer triggers, the IMSI of the SIM is overwritten with the new pseudonymous
IMSI, the TMSI and GSM Ciphering key Kc (3GPP TS 31.102, Section 4.4.3.1) are
invalidated. The current imsi_pseudo_i value is stored to compare it with the
next SMS. Afterwards, the EF~IMSI~ changing procedure in 3GPP TS 11.14, Section
6.4.7.1 is executed to apply the new IMSI.

// FIXME: do we need to enforce the LU now, with an arbitrary CM Service
// Request, or would this only be necessary for Osmocom? (OS#4404)
=== Process Update_Location_HLR

All IMSI Pseudonymization related changes to Process Update_Location_HLR
(3GPP TS 29.002) are optional. All deviations from the existing specification
that are outlined in this section are expected to be enabled or disabled
entirely where IMSI pseudonymization is implemented.

[[figure-imsi-pseudo]]
.Process Update_Location_HLR with IMSI pseudonymization changes
["mscgen"]
----
msc {
  hscale="1.75";
  MSC [label="MSC/VLR"], SMSC [label="SMS-SC"], HLR [label="HLR"];

  MSC   => HLR  [label="Update Location Request"];

  --- [label="If new pseudonymous IMSI was used: deallocate and cancel old pseudonymous IMSI"];
  HLR box  HLR  [label="Deallocate old pseudonymous IMSI"];
  MSC  <=  HLR  [label="Cancel Location Request"];
  MSC   => HLR  [label="Cancel Location Result"];
  ---;

  MSC  <=  HLR  [label="Insert Subscriber Data Request"];
  MSC   => HLR  [label="Insert Subscriber Data Result"];
  HLR box  HLR  [label="Start Next_Pseudo_IMSI_Timer"];
  MSC  <=  HLR  [label="Update Location Result"];
  MSC box  MSC  [label="Finish Location Updating with ME"],

  HLR box  HLR  [label="Wait for Next_Pseudo_IMSI_Timer expiry"];
  |||;
  ...;
  |||;
  HLR box  HLR  [label="Next_Pseudo_IMSI_Timer expired"];

  HLR box  HLR  [label="\nAllocate new pseudonymous IMSI\nif subscriber only has one allocated\n"];
  SMSC <=  HLR  [label="Next Pseudonymous IMSI SMS"];
  SMSC box SMSC [label="Deliver SMS to ME"];
}
----

==== Update Location Request
When Update Location Request arrives, the HLR does not look up the subscriber
by the IMSI, but by the pseudonymous IMSI instead. Unless the subscriber has
two pseudonymous IMSI allocated and used the old pseudonymous IMSI in the
Update Location Request, this is followed by the existing logic to continue with
Insert Subscriber Data Request.

===== Update Location Request With New Pseudonymous IMSI

If the subscriber has two pseudonymous IMSIs allocated, and the newer entry was
used (higher imsi_pseudo_i, see <<hlr-imsi-pseudo-i>>), this section applies.
The older pseudonymous IMSI is deallocated in the HLR. This is done as early
as possible, so the timeframe where two pseudonymous IMSI are allocated for one
subscriber is short.

A Cancel Location Request with the old pseudonymous IMSI is sent to the VLR, so
the conflicting subscriber entry with the old pseudonymous IMSI is deleted from
the VLR. Receiving a Cancel Location Result is followed by the existing logic
to continue with Insert Subscriber Data Request.

===== Update Location Request With Old Pseudonymous IMSI

If the subscriber has two pseudonymous IMSIs allocated, and the older entry was
used (lower imsi_pseudo_i, see <<hlr-imsi-pseudo-i>>), the newer entry is _not_
deallocated. This could lock out the subscriber from the network if the SMS
with the new pseudonymous IMSI arrives with a delay.

==== Insert Subscriber Data Result

ISD works like before, then set Next_Pseudo_IMSI_Timer

==== Next_Pseudo_IMSI_Timer Expires

* if subscriber has only one pseudo IMSI:
  * abort if not enough IMSIs available
  * generate new pseudo IMSI as described earlier
  * set imsi_pseudo_i like last one + 1
* send SMS to subscriber's SIM with newer pseudo IMSI

[[sms-format]]
==== SMS Format

* min_sleep_time
* imsi_pseudo
* imsi_pseudo_i

== Error Scenarios
=== Next Pseudonymous IMSI SMS is Lost
=== SMS Arrives Late

// === SMS Arrives Before Timer Expires
// FIXME: OS#4486

[[reference-src]]
== Reference Implementation with Source Code

== Recommendations for Real-World Implementations
=== ATT = 0
=== End to End Encryption of SMS
=== Warning the User if the IMSI Does Not Change
=== User-configurable Minimum Duration Between IMSI Changes

<<<
include::./common/chapters/gfdl.adoc[]