Reports › kem-03 · Constant-time review
BAG-Loong (kem-03)
| Candidate | BAG-Loong |
|---|---|
| Family | Code-based (rank metric) |
| Archive | BAG-Loong.zip (SHA-256: 2795fd57d3d00791652256362b4a21982116d3aad1fb63633dac923e0e76e05b) |
kem-03-1: Secret-dependent pivoting in the Gabidulin decoder
| Severity | Medium |
|---|---|
| Scope | side-channel |
| Status | Confirmed |
| Affected | Reference implementations, all four parameter sets |
| Discovery | Moderate |
| Exploitation | Local control-flow/cache observer; key recovery not demonstrated |
| Credit | Markku-Juhani O. Saarinen markku-juhani.saarinen@tuni.fi, with AI assistance |
| Date | 2026-09-23 |
Decapsulation forms a rank-code word by multiplying the public ciphertext component by secret x and adding the second ciphertext component (src/loong_pke.c:1003-1014). The Gabidulin decoder then searches for a pivot with a discrepancy-dependent while loop, swaps at the chosen index, and branches into different polynomial-update paths (src/gabidulin.c:213-279). The executed path and addresses thus depend on the recipient secret, not just public ciphertext. A co-resident timing/cache observer can learn information about the intermediate. No inversion from observed pivot sequences to the private vector, full key-recovery attack, or remote channel is shown; a key-dependent pivot is not by itself a Critical break.
Reproducing
Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).
The source-level witness is the decapsulation call in src/loong_kem.c:217-218, the secret-key product in src/loong_pke.c:1003-1014, and the value-dependent pivot loop in src/gabidulin.c:213-279 under Implementations/Reference_Implementation/Loong-Block-ms-128/. The same files occur in the other reference parameter directories. See constant_time.md for the secret/public classification.