Project

General

Profile

Feature #4398

Approach B: Calculate pseudo IMSI with HOTP

Added by osmith about 2 months ago. Updated about 1 month ago.

Status:
Rejected
Priority:
Normal
Assignee:
-
Target version:
-
Start date:
02/14/2020
Due date:
% Done:

0%


Description

Similar to approach A in #4397, but without any collisions and problems with timestamps. Since timestamps are not used, so this is more similar to "An HMAC-Based One-Time Password Algorithm" (HOTP, RFC 4226).

Overview

The IMSI_PSEUDO is still calculated by both the HLR and SIM:

IMSI_PSEUDO_CUR = distribute(IMSI_RANGE_START, IMSI_RANGE_END, hash(IMSI_PSEUDO_SECRET + IMSI_PSEUDO_COUNTER_CUR))

The HLR tells the SIM when to increase IMSI_PSEUDO_COUNTER and by how much. This means, the HLR can skip colliding results. The IMSI that is initially configured for a new SIM must be stored in the HLR.

In Detail

Relevant information in the HLR per subscriber:
  • IMSI
  • IMSI_PSEUDO_CUR (current)
  • IMSI_PSEUDO_OLD (default: NULL)
  • IMSI_PSEUDO_SECRET
  • IMSI_PSEUDO_COUNTER_CUR (current, default: 0)
  • IMSI_PSEUDO_COUNTER_OLD (default: NULL)
  • IMSI_PSEUDO_COUNTER_SECRET
Relevant information in the SIM:
  • IMSI (= IMSI_PSEUDO_CUR)
  • IMSI_PSEUDO_SECRET
  • IMSI_PSEUDO_COUNTER (= IMSI_PSEUDO_COUNTER_CUR)
  • IMSI_PSEUDO_COUNTER_SECRET
New subscriber generation in the HLR:
  • HLR assigns new IMSI in [IMSI_RANGE_START, IMSI_RANGE_END]. The new IMSI must be unique (not be used by other subscribers as real IMSI), but another subscriber may use it as IMSI_PSEUDO_CUR or IMSI_PSEUDO_OLD.
  • HLR generates IMSI_PSEUDO_SECRET, IMSI_PSEUDO_COUNTER_SECRET with random data
  • HLR sets IMSI_PSEUDO_OLD = NULL, IMSI_PSEUDO_COUNTER = 0
  • HLR generates IMSI_PSEUDO_CUR (on failure provisioning the new subscriber fails!)
Generating IMSI_PSEUDO_CUR in HLR:
  • If this is not the first time generating the pseudo IMSI, set the old values to the current values:
    • IMSI_PSEUDO_OLD = IMSI_PSEUDO_CUR
    • IMSI_PSEUDO_COUNTER_OLD = IMSI_PSEUDO_COUNTER_CUR
  • Find new and unique IMSI_PSEUDO_CUR:
    • IMSI_PSEUDO_COUNTER_CUR++
    • IMSI_PSEUDO_CUR = distribute(IMSI_RANGE_START, IMSI_RANGE_END, hash(IMSI_PSEUDO_SECRET + IMSI_PSEUDO_COUNTER_CUR))
    • Try again if: IMSI_PSEUDO_CUR matches IMSI_PSEUDO_CUR of any other subscriber, or IMSI_PSEUDO_OLD of this or any other subscriber
    • Try up to MAX (e.g. 10) times (on failure: the range of available IMSIs is too small)
SIM card provisioning:
  • Usual data (auth stuff for AKA etc.)
  • IMSI_PSEUDO_CUR instead of the IMSI. The real IMSI is not written to the SIM card.
  • IMSI_PSEUDO_SECRET, IMSI_PSEUDO_COUNTER_CUR, IMSI_PSEUDO_COUNTER_SECRET
  • SIM applet
Location Update:
  • SIM uses the IMSI (which is actually the IMSI_PSEUDO) to perform location update
  • HLR finds the subscriber by comparing with IMSI_PSEUDO_CUR / IMSI_PSEUDO_OLD
  • If LU fails: stop here
  • If LU succeeds:
    • LU succeeded with IMSI_PSEUDO_OLD, then HLR writes old values back:
      • IMSI_PSEUDO_CUR = IMSI_PSEUDO_OLD
      • IMSI_PSEUDO_COUNTER_CUR = IMSI_PSEUDO_COUNTER_OLD
    • HLR generates new IMSI_PSEUDO_CUR, on failure it stops here
    • HLR sends an SMS to the SIM, something like: HASH(IMSI_PSEUDO_COUNTER_SECRET + IMSI_PSEUDO_COUNTER_DELTA + OLD_HASH_OR_SOMETHING)
    • SIM applet finds out the value of IMSI_PSEUDO_COUNTER_DELTA, by trying the hash with values in the range [1, MAX].
    • SIM applet overwrites the current IMSI of the SIM with the new pseudo IMSI

The purpose of the hashed counter is to prevent MITM attacks. Without IMSI_PSEUDO_COUNTER_SECRET, it is not possible to generate new messages that will be accepted by the SIM. OLD_HASH_OR_SOMETHING makes sure that the messages don't repeat (maybe store the hash of the previous SMS and put it there?). I have also thought about using asymmetric cryptography, to verify that the message was sent from the HLR. But it seems to me, that this would require much more processing power and storage space, which we don't have in the SIM applet.

If the SMS with the counter update does not reach the SIM (e.g. because an attacker is blocking it), the old pseudo IMSI can still be used. Maybe we could increase another counter in the SIM applet whenever using the same pseudo IMSI, and display a warning message to the user if no new pseudo IMSI has been provisioned, that somebody is tampering with the network?

Problems

  • Still needs a high range of IMSIs that can be used for pseudonymization: to make sure that the previous pseudo IMSI is still working in case the counter SMS did not arrive, each real IMSI must get two pseudo IMSIs (old, current). We also need additional space so we don't run into too many collisions.
    • Approach to dramatically reduce required IMSIs: ACK the new pseudo IMSI by the SIM, then we can safely de-allocate the old pseudo IMSI. I need to figure out the details though.
      • With a 3x ACK back and forth, and a timeout in the HLR, it should be possible to have at most 3 allocated pseudo IMSIs (most of the time just 1 per subscriber!) and be able to try a new one even if there are multiple failures in a row. I will write this out in detail next week.
  • How to detect in the SIM that a message arrived late (see below)?

CC: laforge, neels


Related issues

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

Related to IMSI Pseudonymization - Feature #4400: Approach C: HLR decides and sends the entire next pseudo IMSI to SIMResolved02/17/2020

History

#1 Updated by osmith about 2 months ago

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

#2 Updated by osmith about 2 months ago

  • Description updated (diff)

#3 Updated by neels about 2 months ago

points to explore:

What if the HLR tells the SIM to increment the counter, but that message gets lost / arrives late?
Do we need some sort of re-sync? (reminds me of UMTS AKA where the SIM sends AUTS to re-sync the milenage SQN. I guess we can't send anything from SIM to HLR before LU, right?)
Do we need some sort of tolerance for missed messages, to prevent locking the SIM out forever?

#4 Updated by osmith about 2 months ago

neels wrote:

What if the HLR tells the SIM to increment the counter, but that message gets lost / arrives late?

See above:

If the SMS with the counter update does not reach the SIM (e.g. because an attacker is blocking it), the old pseudo IMSI can still be used. Maybe we could increase another counter in the SIM applet whenever using the same pseudo IMSI, and display a warning message to the user if no new pseudo IMSI has been provisioned, that somebody is tampering with the network?

neels wrote:

Do we need some sort of re-sync? (reminds me of UMTS AKA where the SIM sends AUTS to re-sync the milenage SQN. I guess we can't send anything from SIM to HLR before LU, right?)

As long as we keep the old pseudo IMSI around, and only set IMSI_PSEUDO_OLD to IMSI_PSEUDO_CUR after successful LU (-> we know that the SIM is using the new pseudo IMSI), we should not need to re-sync.

neels wrote:

Do we need some sort of tolerance for missed messages, to prevent locking the SIM out forever?

This should also be achieved by storing the old pseudo IMSI, and only overwriting that value after the SIM is successfully using the new pseudo IMSI.

#5 Updated by osmith about 2 months ago

  • Description updated (diff)

neels wrote:

What if the HLR tells the SIM to increment the counter, but that message gets lost / arrives late?

Actually, what I wrote above does not fully cover this.

If the message to increase the counter gets lost, the HLR would still have IMSI_PSEUDO_COUNTER increased in the database.
To fix this, we can store the old counter together with the old IMSI in the database, and reset the current counter to the old value if the SIM is connecting with IMSI_PSEUDO_OLD.
I've updated the text above accordingly.

If the message arrives late... let's think through an example:

  • SIM does LU with pseudo IMSI
  • HLR generates new pseudo IMSI #1 and sends SMS
  • SIM does not receive SMS and does LU again with the old pseudo IMSI
  • HLR generates new pseudo IMSI #2 and sends SMS
  • SMS with pseudo IMSI #1 arrives, SMS with pseudo IMSI #2 does not arrive (or later)

We must make sure, that the SIM ignores the SMS with pseudo IMSI #1, but does not ignore pseudo IMSI #2.

Right now, I can think of counting the number of location updates in the SIM, and then ignore SMS where the count does not match (e.g. by placing the count in the hash, too). But this is fragile on its own, what if the count goes out of sync? I'll think some more about that (also more input welcome). Maybe we could directly send the new counter value instead of the delta, and sign it instead of using the hash? (I've suggested using hashing, because I thought the sim applet does not have enough processing power to validate the signature, but that might as well be wrong / there could be a simpler solution.)

#6 Updated by osmith about 2 months ago

  • Description updated (diff)

#7 Updated by osmith about 2 months ago

  • Description updated (diff)

#8 Updated by osmith about 1 month ago

Based on the feedback, I'm working on a new approach and will post it soon as "Approach C".

#9 Updated by osmith about 1 month ago

  • Related to Feature #4400: Approach C: HLR decides and sends the entire next pseudo IMSI to SIM added

#10 Updated by osmith about 1 month ago

  • Status changed from Feedback to Rejected

Also available in: Atom PDF

Add picture from clipboard (Maximum size: 48.8 MB)