A Hybrid BP-SAT Attack on MILENAGE: Combining the Complementary Strengths of Algebraic and Soft-Analytical Side-Channel Attacks

What it is

A preprint (Dubrova, Jendral, Backlund, Näslund; ePrint 2026/2487) on single-trace profiled side-channel attacks against MILENAGE in USIM cards. It combines belief-propagation SASCA with SAT-based ASCA to recover the subscriber key K and the operator secret OPc.

How it works

• The target is the first AES-128 invocation, on RAND⊕OPc under K. OPc is unknown to the attacker.
• Neural networks output posterior distributions over AES S-box output byte values across multiple rounds.
• SASCA runs belief propagation over a factor graph. In 6.1% of attacks it recovers K correctly but settles on a wrong OPc.
• ASCA encodes the same predictions and the algorithm's relations as SAT. It enforces global consistency, which removes the wrong-OPc ambiguity. Under a 1-hour timeout and the authors' constraint-selection strategy, it succeeds in only 34% of attacks.
• The hybrid runs BP first and passes the refined predictions to the SAT solver. It resolves every case where SASCA got K right and OPc wrong. 87.7% + 6.1% = 93.8%, so the gain equals that failure class and nothing else.
• The hybrid has a lower average runtime than either method alone, even though it does more work per attack.

flowchart LR
    T[Single trace] --> NN[NN byte posteriors]
    NN --> BP[BP refinement]
    BP --> SAT[SAT solver]
    SAT --> KO[K and OPc]
    NN -.->|SASCA only: 6.1% wrong OPc| KO
    NN -.->|ASCA only: 34% in 1h| KO

Preconditions / Affected

• The attacker needs a profiling phase to train the neural networks, so a device equivalent to the target must be available.
• The attacker needs a trace of the first AES invocation in MILENAGE on a USIM.
• The page's abstract does not name specific card products or vendors.

What to do

For implementers, the proposed countermeasure masks each AES round key with an independent, per-device secret. The authors state it reduces the attacker's advantage over guessing K and OPc to zero bits. They confirm empirically that it defeats the hybrid attack in all evaluated cases. The abstract gives no implementation detail, such as key storage, performance cost or compatibility with deployed cards, so read the full paper before relying on it.

Caveats

• Only the abstract was available. The evaluation setup (hardware, noise, number of attacks, the SAT constraint-selection strategy) is not visible.
• The 34% ASCA figure depends on the 1-hour timeout and the authors' constraint selection, so it is not a hard limit of the method.
• About 6% of hybrid attacks still fail.
• The zero-bit claim is the authors' own, and the page records no independent verification.
• The paper is a preprint.