Single-Trace SAT-Assisted Side-Channel Attack on MILENAGE

Abstract

The MILENAGE authentication algorithm is the most widely deployed authentication mechanism in 3G, 4G, and 5G mobile networks. Its security relies on the secrecy of two 128-bit values stored in the Universal Subscriber Identity Module (USIM): the subscriber key, Ki, and the operator-specific parameter, OPc. Previous side-channel attacks on MILENAGE followed a two-step approach. First, the intermediate value Ki ⊕ OPc is recovered using correlation-based or deep learning-based power analysis targeting the AES invocation that encrypts RAND ⊕ OPc. Next, the first-round AES key is recovered through power analysis and subsequently converted to Ki. None of the previous attacks were able to recover the complete subscriber key from a single trace. This paper presents an attack that can recover the complete subscriber key from a single power trace with 40% success probability on average. The presented method combines profiled deep learning-based power analysis with Boolean satisfiability (SAT) solving. Deep learning models predict the input bytes of AES S-boxes across multiple rounds, and the resulting predictions are ranked according to their posterior probabilities. The ranked predictions are then incorporated as constraints into a SAT model of the MILENAGE algorithm. In this way, both Ki and OPc can be recovered simultaneously from the satisfying assignment returned by the SAT solver. The effectiveness of the attack is tested on commercially available programmable USIM cards.