Breaking First-Order Masked Kyber with Belief Propagation Alone

What it is

Jahandideh and Batina (ePrint 2026/2448, preprint) recover the long-term key of a first-order masked Kyber768 implementation on an ARM Cortex-M4. They need about 2200 decapsulation power traces. The traces use only authentic ciphertexts that pass ciphertext-validity checks, so rejecting malformed or chosen ciphertexts does not block the attack. The secret is freshly re-shared before every decapsulation, and the attack still works.

How it works

• The leakage used is weak second-order leakage, taken from both arithmetic shares of each noisy message coefficient.
• A profiled neural network estimates a Hamming-weight distribution for each of the two shares.
• The two distributions are combined into a likelihood on the decryption noise coefficient. That noise is a known affine function of the secret and the public-key error.
• A belief-propagation solver accumulates these likelihoods across traces and keeps their non-Gaussian shape. It approximates the interference from the other key coordinates as Gaussian, and an Onsager (AMP) correction handles feedback between each factor and the current beliefs.
• The solver recovers all 1536 secret and error coefficients with no lattice reduction.

Preconditions / Affected

• The attacker needs a profiling phase (the network is profiled) and power-trace access to a first-order masked Kyber768 decapsulation.
• The evaluation is on a Cortex-M4, under a stated leakage model.

Caveats

• Under the evaluated leakage model, even exact Hamming weights of both shares carry about 97% less mutual information about a noise coefficient than the exact Hamming weight of the unmasked coefficient. The attack works by accumulating many weak observations, so the per-trace signal is small.
• Baselines at the evaluated trace budgets:
• Least squares does no better than guessing all zeros.
• A greedy inequality solver fails even with exact Hamming weights.
• The primal-lattice cascade does not lower the trace requirement. Below BP's recovery threshold its output is too diffuse for practical lattice recovery.
• At 2000 traces, BP-derived hints lower the estimated BKZ block size from 624 to 505, which is still impractical.
• The practical gap is therefore the BP solver's recovery threshold, around the stated 2200 traces. Below it, the hint-based lattice route does not rescue the attack.
• The page gives no countermeasure guidance. Its stated conclusion is that first-order masking is insufficient against this combined leakage.