Project

General

Profile

Actions

Feature #4400

closed

Approach C: HLR decides and sends the entire next pseudo IMSI to SIM

Added by osmith about 4 years ago. Updated about 4 years ago.

Status:
Resolved
Priority:
Normal
Assignee:
Category:
-
Target version:
-
Start date:
02/17/2020
Due date:
% Done:

100%

Spec Reference:

Description

Overview

In contrary to previous approaches, the HLR decides the pseudo IMSI
independently of the SIM applet. The first pseudo IMSI gets allocated, as the
SIM card is provisioned. After that pseudo IMSI is used for the first time, the
HLR decides the next pseudo IMSI and sends it as SMS to the SIM. The SIM applet
overwrites its current IMSI with the new one, and uses it in the next location
update. Afterwards, the HLR will generate the next IMSI and so on.

Full session

2. HLR  -> SIM  NEW PSEUDO IMSI REQ, session_id=1, imsi_pseudo=123
3. HLR <-  SIM  NEW PSEUDO IMSI RESP ACK, session_id=1, imsi_pseudo=123

In Detail

1. The HLR has a table of allocated pseudo IMSIs. When provisioning a new SIM,
it randomly decides a new pseudo IMSI. There must be no existing entry in the
table with the same pseudo IMSI in the imsi_pseudo column, but the pseudo IMSI
may be the real IMSI of an existing entry.

id imsi imsi_pseudo session_id
1 100 200 0

(Other interesting fields to store in the table may be a boolean for
"provisioned", the allocation date and usage count. The usage count would
increase whenever the SIM does a successful Location Update with that pseudo
IMSI.)

2. The SIM does a successful Location Update with its current pseudo IMSI.

(Clean up: if the ACK from the SIM card in step 4 did not arrive in a previous
provisioning of a new pseudo IMSI, and the SIM has connected with the newer
pseudo IMSI entry, the old pseudo IMSI entry gets deleted now.)

Then the HLR creates a new entry with a new pseudo IMSI (generated as described
in 1.), and with the session_id increased by one.

id imsi imsi_pseudo session_id
1 100 200 0
2 100 123 1

The new information is encoded in an SMS and sent to the SIM.

HLR  -> SIM  NEW PSEUDO IMSI REQ, session_id=1, imsi_pseudo=123

3. The SIM applet verifies, that the session_id is higher than the last
session_id it has seen (initially: 0). If that is not the case, it discards the
message.

The SIM applet writes the new pseudo IMSI and session_id to the SIM card,
overwriting the old data. It acknowledges the new data with a SMS back to the
HLR:

HLR <-  SIM  NEW PSEUDO IMSI RESP ACK, session_id=1, imsi_pseudo=123

4. The HLR verifies, that an entry with the session_id and imsi_pseudo from the
NEW PSEUDO IMSI RESP ACK message exists in the table. If not, it discards the
message.

HLR it deletes the old entry with the same IMSI (in the example: the one with
imsi_pseudo=200).

id imsi imsi_pseudo session_id
2 100 123 1

Messages getting lost

What if "NEW PSEUDO IMSI REQ" gets lost?

Both the old and the new pseudo IMSI entry exist in the HLR.

The SIM will use the old pseudo IMSI in the next location update. The HLR will
try to send the same new pseudo IMSI with the same new session_id, as soon
as the next location update is complete.

What if "NEW PSEUDO IMSI RESP" gets lost?

Both the old and the new pseudo IMSI entry exist in the HLR.

The SIM will use the new pseudo IMSI in the next location update. The HLR will
then clean up the old pseudo IMSI entry, and proceed with generating a new
pseudo IMSI entry and sending it to the SIM, as usually.

Messages arriving late

What if "NEW PSEUDO IMSI REQ" arrives late?

The session_id will not be higher than the session_id, which the SIM card
already knows. Therefore, the applet will discard the message.

What if "NEW PSEUDO IMSI RESP" arrives late?

Session_id and imsi_pseudo from the message will not match what's in the HLR
database, so HLR will discard the message.

Warning the user if SMS don't arrive

An attacker could possibly block the SMS with NEW PSEUDO IMSI REQ from arriving
at the SIM applet. In that case, the SIM would continue using the old pseudo
IMSI indefinitely.

We could possibly count the location updates done with the same pseudo IMSI in
the SIM applet, and warn the user if the same pseudo IMSI has been used more
than N (e.g. 5) times.

(Could be possible by listening to EVENT_DOWNLOAD_LOCATION_STATUS?)

End2end encryption

When deploying the IMSI pseudonymization, the operator should make sure that
the pseudo IMSI related SMS between the HLR and the SIM cannot be read or
modified by third parties. Otherwise, the next pseudonymous IMSI is leaked, and
in case of modifying the IMSI in the SMS, the SIM may be locked out of the
network.

OTA SMS are usually encrypted and authenticated (TS 03.48), with algorithms and
key lengths that the operator chooses (depending on the SIM and how it is
configured).

It was considered to add an additional layer of end2end encryption for the
pseudonymized IMSIs on top, but this is out-of-scope for this project. For
reference, once could pre-provision a random "imsi_pseudo_key" with the SIM
card, store it in the pseudo IMSI table in the HLR, and deploy a new encryption
key together with each new pseudo IMSI, attached to the NEW PSEUDO IMSI REQ.

Advantages over previous approaches

  • The range of available IMSIs, and the algorithm for determining IMSIs, can be
    changed without provisioning new SIM cards
  • Guaranteed that there are no collisions, since the SIM doesn't need to
    reproduce the IMSI with a counter value. The HLR determines the IMSI
    independently and sends it as a whole to the SIM.
  • SMS arriving late is not an issue

CC: laforge, neels


Related issues

Related to IMSI Pseudonymization - Feature #4398: Approach B: Calculate pseudo IMSI with HOTPRejected02/14/2020

Actions
Related to IMSI Pseudonymization - Feature #4397: Approach A: Calculate pseudo IMSI with TOTPRejected02/14/2020

Actions
Related to IMSI Pseudonymization - Feature #4401: Proof of concept for counting Location Updates in SIM appletResolvedosmith02/18/2020

Actions
Related to IMSI Pseudonymization - Feature #4404: Research: Make sure that we can silently detach the IMSIStalled02/19/2020

Actions
Actions #1

Updated by osmith about 4 years ago

  • Related to Feature #4398: Approach B: Calculate pseudo IMSI with HOTP added
Actions #2

Updated by osmith about 4 years ago

  • Related to Feature #4397: Approach A: Calculate pseudo IMSI with TOTP added
Actions #3

Updated by neels about 4 years ago

  • Tracker changed from Bug to Feature
Actions #4

Updated by osmith about 4 years ago

  • Description updated (diff)

neels gave feedback: NEW SESSION REQ and NEW SESSION RESP can be removed, if we let the HLR suggest the same pseudo IMSI that was already allocated, until the SIM accepts it.

Text updated.

Actions #5

Updated by osmith about 4 years ago

  • Description updated (diff)

laforge gave feedback about the scope of the project. Text updated: additional encryption layer removed from the protocol description and placed in the "End2end encryption" section as note.

Actions #6

Updated by osmith about 4 years ago

  • Description updated (diff)
Actions #7

Updated by osmith about 4 years ago

I've created a README.md for imsi-pseudo.git based on the description of this issue:

https://gerrit.osmocom.org/plugins/gitiles/imsi-pseudo

(Seems like it is not yet synced to git.osmocom.org?)

Actions #8

Updated by osmith about 4 years ago

  • Assignee set to osmith
Actions #9

Updated by neels about 4 years ago

Discussion: when to change the pseudo IMSI?

Changing the pseudo IMSI is only possible when the subscriber is attached and can send and receive SMS.
It is always the HLR that decides when to change the IMSI.

Some options:

  • upon each (periodic) Location Updating
  • upon each Complete Layer 3
  • timer based

One might think that we need to sanitize and separate IMSI changes from other service requests, but
once a conn to the subscriber is established (Complete Layer 3), the IMSI can be changed at any time without affecting that particular connection.

For example, at first I thought we need to make sure to not mix normal SMS with those that change the IMSI,
but it is perfectly fine to negotiate a new IMSI mixed with other activity.
The new IMSI should only come into effect upon the next Complete Layer 3.

A problem can still occur when the SIM card changes the IMSI and the ACK is not sent in the same conn:

SIM ---Complete-Layer-3--> MSC
SIM <---------------NEW-IMSI------ HLR
SIM <--Clear-------------> MSC
(SIM uses new IMSI)
SIM ---Complete-Layer-3--> MSC
SIM ----------------NEW-IMSI-ACK-> HLR

A realistic scenario for this would be: A Location Updating is carried out by the MSC.
The HLR reacts quickly to send the NEW-IMSI SMS, received in the same connection as the LU.
After that, the MSC Clears the conn, since no more transactions are pending.
The SIM still needs to send the NEW-IMSI ACK, hence opens a new conn (CM Service Request to send the SMS).

The question is: which IMSI should be used now?
Should the SIM re-attach with the new IMSI, and only then send the ACK for the new IMSI?

One possibility would be that the SIM remains on the old IMSI until the SMS to ACK it has been sent and RP-ACKed by the MSC.
Yet, neither MSC nor SIM can ever be sure that the ACK SMS has actually arrived at the HLR managing the IMSIs.

Probably the simplest solution is to make the HLR accept both old and new IMSIs while in transition.
But is it then really necessary to send a NEW-IMSI-ACK? The SIM has already ACKed the new IMSI by using it to attach to the MSC.

Another part in this puzzle is the MSC's state.
An MSC considers an IMSI attached only when a Location Updating has occured.
If a SIM changes its IMSI and sends another CM Service Request, the MSC would reject this IMSI, which it does not know.

In Osmocom, we could teach the HLR to tell the MSC about a changed IMSI. But one goal of this project is to not modify network components other than HLR and SIM.

So, a SIM that has changed its IMSI must always do a Location Updating for IMSI Attach first thing after changing its IMSI.

This leads me to this flow:

                         MSC <--SMS-NEW-IMSI--- HLR
SIM <-----Paging-------- MSC
SIM ---Pag.Resp--------> MSC
SIM <--SMS-NEW-IMSI----- MSC
SIM <--Clear-----------> MSC

SIM ---IMSI-Detach-----> MSC

SIM ---LU-IMSI-Attach--> MSC
                         MSC ---Update-Location--> HLR
                                (= implicit NEW IMSI ACK)
Actions #10

Updated by neels about 4 years ago

also consider TMSIs: when changing the IMSI, the SIM should discard its TMSI used for the network.
The MSC still associates that TMSI with the previous IMSI.
Hence, each LU-IMSI-Attach after a new IMSI must send the new IMSI in clear, over the unencrypted air interface.

A person maliciously surveilling the network would see this IMSI in clear. It would be an IMSI Attach of an unknown random IMSI.
However, it would probably be possible to time-correlate it to a previous IMSI-Detach.

Hence, to actually be able to preserve privacy, the SIM should not immediately change the IMSI upon receiving an SMS with NEW-IMSI.
What if a random timer in the SIM causes the IMSI change some minutes after receiving the new IMSI?
This doesn't help, the correlation is done between the IMSI Detach (probably using the previous TMSI) and the new IMSI Attach.

Maybe the SIM applet can somehow cause the IMSI Detach to be skipped.
Once a Location Updating with the new IMSI happens, the HLR could tell the MSC to purge the previous IMSI, with no visibility on the air interface.
(This is important to avoid having two IMSIs with the same MSISDN in the MSC)

Actions #11

Updated by neels about 4 years ago

Summary of important aspects so far:

  • IMSI pool managed in HLR; HLR tells SIM when to move to a new IMSI.
    • When the HLR sends an SMS to the SIM, it can never be sure how soon the SMS arrives / how soon the new IMSI is first used.
      Hence the HLR must "park" a newly allocated IMSI alongside an old IMSI up until the new IMSI is actually used.
    • HLR can "never" invalidate a parked new IMSI.
      The SIM has no fallback to a previous IMSI, so if a new IMSI has been dealt out to a SIM, the HLR must accept it however distant in the future.
      (Say, the applet changed the IMSI in the SIM, but then the phone goes out of power for months, the HLR must still accept the new IMSI,
      or the SIM is locked out and needs to be re-provisioned.)
      • Todo: consider a fallback mechanism in the SIM to be able to free unused new IMSIs in the HLR?
    • In the worst case, all NEW-IMSI Requests are dropped, and every subscriber occupies two IMSIs
    • HLR should re-send "parked" new IMSIs regularly
    • The HLR can decide to allocate less new IMSIs as the IMSI pool depletes
  • MSC functionality remains unchanged, hence
    • The previous IMSI must be detached or invalidated in the VLR to avoid duplicate MSISDN
    • A new IMSI must always attach to the MSC with Location Updating (IMSI Attach)
      • We need no NEW-IMSI-ACK SMS from the SIM to the HLR, the mandatory LU for IMSI Attach already serves the purpose of ACKing the new IMSI.
    • The SIM must drop its TMSI when it changes its IMSI (MSC associates the TMSI to the old IMSI)
  • The goal is privacy, hence it should be hard to follow IMSI changes: avoid time correlation between old and new IMSI.
    The longer the delay between events of old and new IMSI, the more subscribers change their IMSIs concurrently,
    the harder it is to follow one particular IMSI.
    • Insert a delay between the NEW-IMSI Request and the actual time that the SIM changes to the new IMSI.
      (avoid correlating SMS of an old IMSI/TMSI to the new IMSI attach)
      • The delay affects how long a subscriber keeps two IMSIs allocated in parallel,
        so the HLR should probably tell the SIM about the amount of delay in the NEW-IMSI-Request message
        (i.e. make this configurable without SIM modification).
      • The delay will never be precise, since the SMSC may introduce arbitrary delay for random reasons.
        (optional todo: maybe the SMS transaction conveys to the SIM how long delivery has taken?)
    • The phone can detach (IMSI-Detach old IMSI or TMSI) and then attach (LU with new IMSI) in short succession,
      but this would be pretty obvious for attackers to correlate old TMSI/IMSI with new IMSI.
    • It is important to keep the subscriber attached with (almost) no interruption in service.
      So it is not an option to IMSI-Detach, then wait some random time period, and only attach later.
      There must be ideally no delay of "moving" the MSISDN from the old IMSI to the new IMSI in the VLR.
      • Omit the MS ---IMSI-Detach--> MSC (TODO: is this possible from SIM applet?)
      • Invalidate the MSC's state for the old IMSI from the HLR: as soon as the new IMSI shows up in an Update Location, do:
        • option: send a Purge MS of the old IMSI from the HLR to the MSC?
        • option: send an Insert Subscriber Data for the old IMSI with an invalid MSISDN?

The usefulness of the project seems to pivot on the visibility of the IMSI Detach.
If we can't omit the IMSI Detach message, then we either introduce an interruption in network service,
or we make it easy to correlate old and new IMSIs by time correlation of Detach and Attach.
A likely conclusion is that we also need to modify the MSC to play along in the IMSI swap
with custom messages from the HLR to reach effective obfuscation of subscriber identity.

Actions #12

Updated by neels about 4 years ago

Open question: how to interface HLR and SMS service

  • SMS-over-GSUP?
  • SMPP handler and CTRL interface to osmo-hlr?
Actions #13

Updated by laforge about 4 years ago

On Tue, Feb 18, 2020 at 04:33:42PM +0000, neels [REDMINE] wrote:

  • IMSI pool managed in HLR; HLR tells SIM when to move to a new IMSI.

One disadvantage of such an "explicit" mechanism relying on OTA SMS is that any
intermediary / adversary can just block those SMS and thereby render the entire
mechanism unusable. A mechanism that allowed the SIM to autonomously switch to
a different IMSI would be more robust against that kind of attack, but then of course
has other disadvantages.

  • MSC functionality remains unchanged, hence
    • The previous IMSI must be detached or invalidated in the VLR to avoid duplicate MSISDN

This can be done explicitly by the HLR sending a (IIRC) CancelLocation or PurgeMS request. for the old IMSI.

This is what would normally happen if the IMSI e.g. meanwhile registered at another MNO (after
jumping from one country to another), and the HLR would then inform the old VLR/MSC that the
ISMI is gone.

This way we can make sure no "same MSISDN at two IMSIs" and related unspecified behavior occurs
in the VLR/MSC.

The usefulness of the project seems to pivot on the visibility of the IMSI Detach.
If we can't omit the IMSI Detach message, then we either introduce an interruption in network service,
or we make it easy to correlate old and new IMSIs by time correlation of Detach and Attach.

I doublt IMSI DETACH is used much in real-world networks these days as it is unauthenticated
and hence subject to spoofing.

Actions #14

Updated by laforge about 4 years ago

On Tue, Feb 18, 2020 at 04:44:23PM +0000, neels [REDMINE] wrote:

  • SMS-over-GSUP?

no, that would mean you need an external SMSC first. It's like MNCC: Either you
use the internal, or all related handling is external.

  • SMPP handler and CTRL interface to osmo-hlr?

SMPP certainly is the way to go. And yes, if it was external to osmo-hlr, it would
be best. We preferably don't want to burden the normal osmo-hlr code with all related
complexities of this research project.

Actions #15

Updated by osmith about 4 years ago

laforge wrote:

One disadvantage of such an "explicit" mechanism relying on OTA SMS is that any
intermediary / adversary can just block those SMS and thereby render the entire
mechanism unusable. A mechanism that allowed the SIM to autonomously switch to
a different IMSI would be more robust against that kind of attack, but then of course
has other disadvantages.

Indeed. laforge, what do you think about warning the user from the SIM applet, if the pseudo IMSI does not change?
Elaborated here: https://osmocom.org/issues/4400#Warning-the-user-if-SMS-dont-arrive

The usefulness of the project seems to pivot on the visibility of the IMSI Detach.
If we can't omit the IMSI Detach message, then we either introduce an interruption in network service,
or we make it easy to correlate old and new IMSIs by time correlation of Detach and Attach.

I doublt IMSI DETACH is used much in real-world networks these days as it is unauthenticated
and hence subject to spoofing.

Created new issue #4404 for doing a proof of concept for silent IMSI detach.

neels wrote:

Open question: how to interface HLR and SMS service

Created new issue #4403 for that discussion, please follow up there.

Actions #16

Updated by laforge about 4 years ago

On Wed, Feb 19, 2020 at 10:35:24AM +0000, wrote:

what do you think about warning the user from the SIM applet, if the pseudo IMSI does not change?

yes, makes a lot of sense. good idea.

I doublt IMSI DETACH is used much in real-world networks these days as it is unauthenticated
and hence subject to spoofing.

Created new issue #4404 for doing a proof of concept for silent IMSI detach.

what do you mean by proof-of-concept? Wouldn't it simply be a test to register to the
three German networks with a respective operator SIM card and check if switching the
phone off caues an IMSI DETACH? Or, actually, it would probably be sufficient to look
at the SI (or the LU ACCEPT?) where the network indicates if IMSI DETACH procedure shall
be used or not. Any of the above should be possible with OsmocomBB.

Actions #17

Updated by osmith about 4 years ago

laforge wrote:

I doublt IMSI DETACH is used much in real-world networks these days as it is unauthenticated
and hence subject to spoofing.

Created new issue #4404 for doing a proof of concept for silent IMSI detach.

what do you mean by proof-of-concept? Wouldn't it simply be a test to register to the
three German networks with a respective operator SIM card and check if switching the
phone off caues an IMSI DETACH? Or, actually, it would probably be sufficient to look
at the SI (or the LU ACCEPT?) where the network indicates if IMSI DETACH procedure shall
be used or not. Any of the above should be possible with OsmocomBB.

Oh I did not realize that it can be done that way, especially that it's encoded in the SI / LU Accept. I'll update that issue.

Actions #18

Updated by osmith about 4 years ago

  • Related to Feature #4401: Proof of concept for counting Location Updates in SIM applet added
Actions #19

Updated by osmith about 4 years ago

  • Related to Feature #4404: Research: Make sure that we can silently detach the IMSI added
Actions #20

Updated by osmith about 4 years ago

Updated the README, that describes the whole process, with all the feedback above:

https://gerrit.osmocom.org/plugins/gitiles/imsi-pseudo/+/refs/heads/master/README.md

Actions #21

Updated by osmith about 4 years ago

  • Status changed from New to Resolved
  • % Done changed from 0 to 100

This is the approach we will describe in our spec and implement. Closing.

Actions

Also available in: Atom PDF

Add picture from clipboard (Maximum size: 48.8 MB)