AAKA: An Anti-Tracking Cellular Authentication Scheme Leveraging Anonymous Credentials

AAKA: An Anti-Tracking Cellular Authentication Scheme Leveraging Anonymous Credentials

Speakers: Hexuan Yu

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=VxIdjsbi6bk

Overview

The talk introduces AAKA, a novel Anti-Tracking Cellular Authentication Scheme designed to address the persistent privacy concern of mobile tracking by Mobile Network Operators (MNOs). MNOs routinely collect granular geographic data and timestamps, enabling them to track subscriber locations and movements. This sensitive data is frequently sold to third-party data brokers or Location-based Service providers, leading to significant privacy violations, as evidenced by major U.S. carriers facing fines since 2020 for unauthorized disclosure of subscriber location records. The problem is exacerbated by advancements in localization technology, such as 5G New Radio's sub-meter precision, making real-time, fine-grained location information transparent to MNOs and facilitating detailed profiling and linkage attacks across the proliferating cellular-connected devices.

AAKA confronts a fundamental dilemma: balancing subscriber privacy with accountability. While Cell-site Location Information (CSLI) is crucial for lawful interception (LI) in criminal investigations, current 3GPP standards lack technical solutions to prevent MNOs from accessing LI data without proper Law Enforcement Agency (LEA) oversight. AAKA's core objective is to preserve identity privacy, minimize a subscriber's location footprint against untrusted MNOs, and prevent illegal surveillance, all while maintaining compatibility with existing cellular access and service models. The scheme achieves this through anonymous credentials, zero-knowledge proofs, and a novel identity escrow mechanism that ensures lawful de-anonymization only occurs with multi-party collaboration under strict warrant conditions.

Background

▶ Watch: Introduction: The problem of mobile tracking and privacy (0:00)

The pervasive issue of mobile tracking stems from the fundamental architecture of current mobile networks, where MNOs inherently acquire a user's permanent identifier during service. Specifically, the Authentication and Key Agreement (AKA) process reveals a user's identity to both their Home Network (HN) and the Serving Network (SN).

Within this architecture, the USIM (Universal Subscriber Identity Module), a hardware chip, securely stores critical subscription credentials. These include the SUPI (Subscription Permanent Identifier), which uniquely identifies a USIM, and long-term secret keys like the subscriber permanent key 'k'. The SUPI itself contains the HN Identifier (MCC+MNC) and a Mobile Subscriber Identification Number (MSIN) that identifies the specific UE within an MNO. These credentials are mirrored in the HN's ARPF (Authentication Credential Repository and Processing Function). While 5G introduced the SUCI (Subscription Concealed Identifier) to encrypt the MSIN field of the SUPI using ECIES (Elliptic Curve Integrated Encryption Scheme) with the HN's public key (pkHN), this primarily protects against outsider attacks. The HN, possessing its secret key (skHN), can still decrypt the SUCI, and vulnerabilities like Bidding-Down attacks can force UEs to downgrade to less secure 2G/LTE networks where IMSI (the predecessor to SUPI) is transmitted in plaintext.

When a UE attaches to a cellular network, a mandatory AKA process occurs, mutually authenticating the UE and SN and establishing a secured anchor key (KSEAF). The SN relies on the UE's HN to relay authentication vectors, and upon successful authentication, the HN informs the SN of the UE's SUPI and provides KSEAF. Subsequently, the UE receives a GUTI (Global Unique Temporary Identifier) for sessions within a Registration Area, reducing authentication frequency. However, even in Idle mode, UE location is reported, and next-generation networks promise even more precise localization, making a UE's trajectory increasingly transparent to MNOs.

Existing privacy solutions largely focus on protecting against outsiders. For instance, AKA+ and AKA' aim to resist linkability from active outsiders, and proposals like GUTI reallocation attempt to protect location privacy. However, these often fall short against an honest-but-curious MNO, which is the primary adversary model AAKA targets. Other approaches, like ZipPhone's ephemeral IMSI switching or PGPP's SUPI nullification via blind signatures, either lack realistic update mechanisms or require significant architectural changes and the introduction of a trusted third party (TTP), making them difficult to deploy in practice. AAKA, in contrast, aims for a practical, backward-compatible solution that directly addresses the MNO as the adversary.

The system model for AAKA involves three main participant types:

1. UE (User Equipment): Comprising the Mobile Equipment (ME) and the SIM, which securely stores permanent confidential materials (SUPI, 'k') and verifiable anonymous credentials.
2. MNO (Mobile Network Operator): Can act as an HN (Home Network), issuing credentials, or an SN (Serving Network), providing network access. AAKA ensures anonymous access to both.
3. LEA (Law Enforcement Agency): The lawful entity responsible for de-anonymizing UEs, operating in collaboration with MNOs and requiring a valid legal warrant.

The threat model for AAKA is specifically designed to address honest-but-curious MNOs. These MNOs are assumed to honestly adhere to network protocols but may attempt to compromise UE privacy by profiling and abusing location information. The SIM/USIM is assumed to be a tamper-resistant secure element, serving as the root-of-trust. The ME is considered semi-trusted, capable of offloading non-critical cryptographic tasks. Communication channels are assumed to be insecure, requiring protection against passive and active attackers, replay attacks, and IMSI-Catcher attacks, with AAKA specifically designed to be resistant to the latter.

Key Findings

▶ Watch: Novel Identity Escrow scheme for lawful de-anonymization (2:30)

AAKA's core contributions and key findings collectively address the mobile tracking problem by MNOs, offering a robust and practical solution:

• Anti-Tracking Privacy Enhancement: AAKA leverages anonymous credentials and zero-knowledge proofs (ZKPs) during credential presentation. This allows a UE to selectively disclose only verifiable attributes necessary for network access, while its permanent identifier (MSIN) remains concealed. Crucially, credential presentations generated by different subscribers are indistinguishable, and multiple accesses by a single subscriber are unlinkable, making it impossible for MNOs to build persistent profiles.
• Anti-Counterfeiting Protection: The credentials within AAKA are cryptographically secured to be unforgeable and non-transferable. This is guaranteed by the underlying cryptographic primitives (e.g., Boneh-Boyen Signatures), hardware-level protection provided by the SIM, and the secure Over-the-Air (OTA) SIM provisioning protocol.
• Lawful De-anonymization: To balance privacy with accountability, AAKA introduces a novel Identity Escrow scheme. This mechanism ensures that MNOs (both SN and HN) must collaborate with an authorized LEA to de-anonymize a user's identity, and only within a specific geographical area and time frame as mandated by a warrant. AAKA provides a cryptographic guarantee that de-anonymization requires the presence of all three parties (SN, HN, and LEA), preventing any single curious MNO or unauthorized LEA from independently compromising user privacy.
• Non-interactive Roaming Support: Unlike existing primary authentication protocols like 5G-AKA, which are interactive and require the Home Network's involvement for roaming UEs, AAKA enables a Serving Network to independently authenticate an unknown UE during general roaming scenarios. This eliminates the need for communication with the UE's HN, significantly reducing communication overhead and latency, a key benefit for network efficiency. This is facilitated by AAKA's non-designated credential verifier method.
• Compatibility and Practicality: AAKA is designed for seamless integration with existing cellular infrastructure. It utilizes the standard SIM without introducing new network entities. The optimized anonymous credential protocol is pairing-free on the UE side, a critical design choice given the computational constraints of mobile devices. All cryptographic computations for the UE are feasible with the latest cellular SIMs. Experimental evaluation confirmed its practicality, showing that credential presentation generation takes approximately 52 milliseconds on a constrained host device (like a Raspberry Pi 4), and the overall UE registration process adds only about 60 milliseconds compared to 5G-AKA, an acceptable overhead considering the significant privacy and roaming benefits.

In essence, AAKA provides a robust, anti-tracking mobile access solution that meticulously integrates secure and efficient anonymous credential schemes and authentication protocols. It achieves anonymity, unlinkability, and a carefully controlled lawful de-anonymization capability, all while maintaining compatibility with the current 5G cellular architecture.

Technical Deep Dive

▶ Watch: Non-interactive roaming support eliminates Home Network involvement (3:00)

AAKA's robust privacy and security guarantees are built upon several advanced cryptographic primitives and a meticulously designed two-phase protocol: System Setup & Credential Issuance, and Presentation and Verification.

Cryptography Preliminaries

AAKA leverages several advanced cryptographic building blocks:

• Bilinear Groups: The scheme relies on pairing-based cryptography to solve the Decisional Diffie-Hellman (DDH) problem. It uses three bilinear cyclic groups, G1, G2, and GT, all of prime order 'p', with generators g1 for G1 and g2 for G2, an isomorphism ψ from G2 to G1, and a bilinear map 'e' from G1 x G2 to GT. For efficiency, AAKA operates in asymmetric Type-3 settings, where an efficient homomorphism from G2 to G1 is not assumed to exist.
• Proof of Knowledge (ZKP): AAKA utilizes Non-Interactive Zero-Knowledge Proofs (NIZK), typically constructed using the Fiat-Shamir heuristic. These proofs allow a prover (UE) to demonstrate possession of secret information without revealing the secrets themselves, ensuring privacy.
• Boneh-Boyen Signature (BBS): The BBS scheme is a short signature scheme proven existentially unforgeable under the q-SDH assumption. A signer with secret key 'x' and public key X = gx generates a signature σ = g1(1/(x+m)) for a message 'm'. AAKA employs an efficient method to prove knowledge of a BBS signature without revealing 'm', using a blinding factor 'r' and a ZKP, which is crucial for constrained UE devices as it eliminates pairing operations on the prover's side.
• Keyed-Verification Anonymous Credentials (KVAC): AAKA adapts a KVAC construction by Camenisch et al. that incorporates BBS. This scheme constructs algebraic MACs for a vector of messages. While traditional KVAC schemes often depend on a designated verifier assumption (requiring the verifier to be the issuer), AAKA extends this to support non-designated verifiers, allowing any MNO (SN) to verify credentials without needing the HN's issuing keys, albeit with two pairing computations which are acceptable for MNO servers. This is critical for supporting non-interactive roaming.
• ElGamal Encryption: Used for the identity escrow function, ElGamal is semantically secure under the DDH assumption. It encrypts a message 'm' with a public key 'h' and a random value 'r' into a ciphertext (C1=gr, C2=m hr). Its homomorphic properties are beneficial for advanced cryptographic protocols.

System Setup and Credential Issuance

The AAKA protocol begins with an initial setup and a credential issuance phase:

A. System Setup:

All MNOs first agree on a universal credential format. During initial provisioning (e.g., of a physical SIM or eSIM profile), the following parameters are securely provisioned into the tamper-resistant SIM/USIM:

1. The permanent identifier SUPI.
2. The permanent secret key k shared with the HN.
3. The public key of the LEA, pkLE (denoted as 'h'), used for activating Lawful Interception functions.
4. The public key of the HN, pkHN.
5. pars, public parameters for verifying issued credentials.

The HN exclusively stores its secret issuance/signing key ik, corresponding to pars. The LEA generates its ElGamal keys (pkLE, skLE).

B. Credential Issuance (Issue and Obtain):

This sub-protocol involves the HN issuing a verifiable anonymous credential and the UE securely obtaining it.

1. Issue (HN): Initiated typically after a monthly payment, the HN prepares a vector of four attributes, m = (m1, m2, m3, m4):

• m1: Boolean for subscription activity status.
• m2: Expiration date (e.g., end of payment cycle).
• m3: HN ID (MCC + MNC).
• m4: The MSIN, the unique part of the SUPI, which will be concealed during presentation.

The HN computes a Boneh-Boyen signature **σ = g1(1/(x0 + Σ(mi*xi))) and auxiliary signatures σi = σ(xi) for i=(0,...,4). It appends a zero-knowledge proof π0 to attest to the correct formation of auxiliary parameters and knowledge of its secret issuing key ik. The complete credential, Cred = (m, σ, σi, π0)**, is securely sent to the USIM via the dedicated 5G OTA remote provisioning channel.

1. Obtain (UE): Upon receiving Cred, the USIM performs three checks:

• Verifies **σ0 * Π(σimi) = g1**.
• Verifies that auxiliary signatures σi are from the HN's issuing key.
• Verifies the authenticity of the issuing key ik against pars using the non-interactive ZKP π0.

If all validations succeed, the UE accepts and stores Cred on its USIM.

Presentation and Verification (Part 1)

This protocol serves as AAKA's alternative to 5G-AKA for mutual authentication and key agreement, ensuring UE anonymity.

1. Connection Request (UE to SN): The UE's USIM generates a random nonce α (challenge) and a temporary EC private key u, kept securely within the USIM. It computes the public key uG. The pair (α, uG) is encrypted using the SN's public key (pkSN) to form Req, similar to SUCI concealment in 5G. The UE sends Req = U, αpkSN to the SN.
2. SN Identification and Session Key Generation (SN to UE): The SN decrypts Req using its secret key skSN to retrieve U and α. It generates its own temporary EC private key v and public key V = vG. To implicitly prove its authenticity, the SN correctly responds to α. It also generates a random challenge nonce β (to prevent credential abuse by a malicious ME) and signs a hash of V, α, and β using skSN. The SN sends Res = V, α, β, signed_hashskSN to the UE and computes the shared ECDH key Ks = vU for secure communication.
3. SN Authentication and Session Key Generation (UE): The USIM receives Res, recomputes the hash over V, α', and β, and checks it against the decrypted signed hash. It implicitly authenticates the SN by verifying that α' (decrypted from Res) equals its original challenge α. If successful, the USIM computes the shared session key Ks = uV. The nonces α and β are not revealed to the ME; β is crucial for binding to the one-time verifiable credential presentation.

Demo / Proof of Concept

▶ Watch: Understanding current mobile network architecture and tracking (4:00)

To validate AAKA's practicality and efficiency, a proof-of-concept prototype was implemented and evaluated.

A. Experimental Environment:

The evaluation setup mimicked a real-world cellular environment:

• MNO: Implemented on a standard PC (Intel Core i7-11700k, 3.6GHz, 8-core, 64-bit CPU, Linux OS).
• UE: Emulated by a Raspberry Pi 4 (1.5GHz 64-bit quad-core Cortex A72 ARM v8, 4GB RAM, 64GB SD card), representing a constrained host device comparable to an older mid-range Android phone.
• SIM Cards: Two types were used: Card A (sysmoISIM-SJA2, 64KB EEPROM, Java Card SDK 2.2.1) and Card B (NXP JCOP J3R110, Java Card SDK 3.0.5). A PC/SC compliant smart card reader connected the SIMs to the ME.
• Cryptographic Parameters: Standard parameters were adopted: Curve25519 for ECDH, and the pairing-friendly BN-254 curve for pairings (providing approximately 100-bit security). Symmetric encryption used was AES-128 CTR, and hash digests were SHA-256.
• Libraries: The implementation utilized mcl (C++) for pairing-based cryptography and pyca (Python) for standard cryptographic operations.

B. Time Consumption:

All computation times were averaged over 10 runs and measured in milliseconds (ms):

| Entity | Operation | Time (ms) |

| :----- | :-------- | :-------- |

| HN | Issue | 1.87 |

| UE | Obtain | 38.66 |

| UE (SIM) | Req + SNAuth | 131.30 |

| UE (ME) | PresGen | 51.72 |

| SN | Res | 0.078 |

| SN | Verify (roaming) | 4.51 |

| HN | Verify (non-roaming) | 1.09 |

Key observations from the time consumption results:

• Credential Issuance: The HN issues a credential very quickly (1.87 ms), and the UE obtains and verifies it within a reasonable 38.66 ms.
• Presentation and Verification: The most time-consuming part on the UE side is the Req + SNAuth step (131.30 ms), which is primarily due to on-card EC private key generation (98.11 ms) and shared key computation (33.19 ms) within the SIM. The PresGen operation, offloaded to the ME, takes 51.72 ms.
• MNO Operations: SN operations are extremely fast, with Res taking only 0.078 ms. Verification in roaming mode (requiring two pairing operations and six exponentiations) takes 4.51 ms, while in a non-roaming scenario (where SN=HN and the issuing key is known), verification is even faster at 1.09 ms.

C. Comparison with Current 5G Solution (5G-AKA):

AAKA was compared against 5G-AKA using the same hardware environments:

| Scheme | UE (Hybrid USIM+ME) | UE (ME Only) | MNO (SN+HN) |

| :----- | :------------------ | :----------- | :------------ |

| 5G-AKA | 124.04 + T ms | 3.69 ms | 3.81 + Δ ms |

| AAKA | 184.22 ms | 52.92 ms | 4.59 ms |

• UE Side (Hybrid USIM+ME): AAKA's total UE-side execution (Req + SNAuth + PresGen) is 184.22 ms. 5G-AKA's equivalent takes 124.04 ms (for ECDH) plus additional 'T' ms for other resting steps.
• UE Side (ME Only): If all computations are performed purely on the ME (e.g., SUCI concealment by ME for 5G-AKA), 5G-AKA takes only 3.69 ms, whereas AAKA takes 52.92 ms.
• MNO Side: For 5G-AKA in roaming, MNO operations take 3.81 ms plus a communication latency 'Δ' between HN and SN. For AAKA, SN verification in roaming takes 4.59 ms.

Key Finding: AAKA introduces an additional 50-60 ms computation overhead on the UE side (in the hybrid USIM+ME setting) compared to 5G-AKA in a non-roaming scenario. However, a significant advantage of AAKA is the elimination of communication overhead between the SN and HN during roaming, which can be substantial in practice. This compensation makes AAKA's execution overhead acceptable on constrained host devices, especially given the enhanced privacy and roaming efficiency it provides.

Defensive Implications

▶ Watch: How UE authentication and registration reveal sensitive data (4:40)

AAKA significantly enhances defensive capabilities against mobile tracking by MNOs, primarily through its Presentation Generation and Lawful De-anonymization protocols, backed by robust security properties.

Presentation Generation (PresGen - UE)

This is the core mechanism for anonymous network access. To register, the UE generates a one-time anonymous presentation, Pres, from its stored Credential.

1. Credential Blinding: To ensure anonymity and unlinkability, the original signatures σ and σi from the Credential are blinded using a randomly chosen blinding factor r. This results in randomized signatures σ' = σr and σi' = σir. The UE then proves the correct formation of these randomized signatures and the validity of embedded attributes. To optimize for constrained UEs, an auxiliary precomputing parameter ō = Π(σi'mi) is introduced, allowing the SN to perform verification with only two pairing checks: e(ō, g2) = e(σ', X0).
2. Identity Escrow Function Generation: For lawful interception, the UE generates an escrowed identity by encrypting its private attribute m4 (the MSIN) under the LEA's public key h (pkLE) using ElGamal encryption. This yields **(C1, C2) = (g1r', m4 * hr'), where r' is a random value. The UE attaches a zero-knowledge proof π to commit to the SN that (C1, C2) is genuinely derived from its authentic m4. This single NIZK binds all required witness parameters (m4, r, r') and their relations. The final challenge C for this NIZK is computed over commitment values and the random challenge β received from the SN, effectively binding the presentation to the current session and ensuring non-transferability. The UE then sends Pres = (mi, ō, σ', σi', C1, C2, A, B, π) to the SN over the secure channel established with Ks**.

SN Verification and UE Registration (Verify - SN)

The SN receives and parses Pres.

1. It verifies public attributes m1 (activity status) and m2 (expiration date) to assess subscription validity.
2. The SN identifies the HN from m3 and retrieves the relevant public verification parameters X0.
3. The SN performs the NIZK verification of π, recomputing commitments, a hash digest C', and checking if C' = C. It also verifies specific proof components and performs the critical pairing equality check e(ō, g2) = e(σ', X0), which confirms the UE's possession of a valid Credential.
4. If all verifications succeed, the Authentication Management Function (AMF) generates and allocates a temporary identifier (GUTI) to the UE.
5. The escrowed identity (C1, C2), HN identifier m3, shared session key Ks, and the GUTI are recorded in the SN's database as a mapping vector.

Finally, the fresh GUTI is sent to the UE over the secure channel, signaling successful registration.

UE Deregistration and Lawful De-anonymization

• UE Deregistration: To minimize its location footprint and avoid linkability risks, AAKA requires UEs to de-register and initiate a new registration when moving outside the AMF region they initially registered with. The SN (or UDM) then deactivates the UE context, but the context, including the escrowed identity, is stored in the SN's database as dictated by LI requirements.
• Lawful De-anonymization: This process is designed to prevent mass surveillance by requiring multi-party collaboration between the SN, HN, and an authorized LEA. No MNO can de-anonymize a UE independently.

1. Upon receiving a valid Geofence Search Warrant specifying a geographical area and time frame, the SN identifies the GUTIs that meet these criteria.
2. The SN then sends the correlated escrowed identity (C1, C2) to the LEA.
3. The LEA, possessing its secret key skLE securely stored in a Trusted Platform Module (TPM), can decrypt m4 (the MSIN) by computing **m4 = C2 * (C1skLE)-1**.
4. The full SUPI is then reconstructed by combining the decrypted m4 with m3 (MCC, MNC), which the UE presented to the SN during registration.
5. This target SUPI is then fed into existing LI Network Functions (e.g., LEMF, MDF, LIPF, LICF) residing in the HN to retrieve further information, such as the real-world identity of the UE owner and home address provided during subscription.

This multi-party collaboration mechanism purposefully makes mass surveillance more difficult and also supports targeted searches for known individuals by integrating a dedicated TPM with LI NFs for real-time decryption of escrowed identities.

Security Analysis

AAKA's security analysis confirms its effectiveness:

• Unforgeability (Theorem 3): The PresGen and Verify algorithms are unforgeable, meaning an adversary cannot forge a legitimate Credential or a valid proof of attributes. This is guaranteed by the unforgeability of the underlying BBS-based MAC.
• Anonymity and Unlinkability (Theorem 4): AAKA ensures both unlinkability and anonymity across different UE registrations. The subscriber's identity (MSIN) remains undisclosed to any MNO, and multiple presentations from the same Credential are unlinkable. Different presentations from different UEs are indistinguishable. These properties are guaranteed by the zero-knowledge nature of the proofs under the random oracle model, making it impossible for any MNO alone to trace a specific UE.
• Outsider Attack Resistance: Credential Issuance is protected by existing OTA provisioning. The Presentation and Verification protocol resists replay attacks because the UE's temporary private key 'u' is always safeguarded within the SIM. Tampering is detected by signed hash values.
• Secure Computation Splitting and Non-transferability: Critical operations (e.g., generating 'u' and 'Ks') are restricted to the SIM, while resource-intensive tasks (e.g., PresGen) are delegated to the semi-trusted ME. This ensures 'u' and 'Ks' remain secure within the SIM. Non-transferability is ensured by binding valid presentations to the SN's unique challenge nonce β, which a dishonest ME cannot fabricate.

Key Takeaways

• Comprehensive Anti-Tracking Solution: AAKA effectively addresses mobile tracking by MNOs, leveraging anonymous credentials and zero-knowledge proofs to prevent MNOs from profiling user locations and movements.
• Novel Lawful De-anonymization: The scheme introduces a unique Identity Escrow mechanism that enables lawful interception only through mandated, multi-party collaboration between the Serving Network, Home Network, and an authorized Law Enforcement Agency, preventing unilateral misuse by any single entity.
• Enhanced Roaming Efficiency: AAKA supports non-interactive roaming, allowing a Serving Network to authenticate UEs independently without involving the Home Network, significantly reducing communication overhead and improving network efficiency.
• Practical and Compatible Design: AAKA is fully compatible with existing 5G cellular architecture and standard SIMs, requiring no new network entities. Its cryptographic computations are optimized for constrained UE devices, with a pairing-free design on the UE side.
• Acceptable Performance Overhead: Experimental evaluations demonstrate that AAKA introduces an additional 50-60 ms computation overhead on the UE side compared to 5G-AKA. However, this is deemed acceptable given the elimination of substantial communication overhead during roaming and the significant privacy benefits.
• Strong Privacy Guarantees: AAKA provides robust anonymity and unlinkability against honest-but-curious MNOs, ensuring that a subscriber's permanent identity (MSIN) remains concealed and that multiple network accesses by the same user cannot be linked.

About the Speaker(s)

The talk was presented by Hexuan Yu. Further details about their title or affiliation were not provided in the supplied metadata or transcript.