Security › kem-02 · Constant-time review · Performance: x86_1 · arm_1

Amoeba (kem-02)

kem-02-1: The FO check compares only every fourth ciphertext byte

Original source: NGCC PKC Forum report

Jinnuo Li reported the attack in the NGCC PKC Forum. Amoeba's Fujisaki--Okamoto decapsulation re-encrypts the decoded message, but cmp() advances its byte index by four. Amoeba-576 consequently checks only 262 of 1,047 ciphertext bytes; changes in the other 785 bytes cannot trigger implicit rejection. The same source defect appears in every submitted parameter set.

This exposes a plaintext-checking primitive of the type developed by Das in ePrint 2026/1682: unchecked ciphertext coefficients can be swept across decoding thresholds to obtain linear information about the reused Ring-LWE secret. Li reports recovering all ten official Amoeba-576 KAT secret keys in about 3*10^4 decapsulation queries per key. Our independent witness uses a blind external-parity coordinate as a controlled first error, then binary-searches 320 other blind coordinates per chosen ciphertext. It recovers all 576 secret coefficients from 80 ciphertexts and 128,161 oracle calls, constructs a new decapsulation key without copying the original secret-key bytes, and recovers ten fresh honest encapsulations' shared secrets. Seeds 1, 2, and 3 reproduced. The measurement and regression are local and finish in about 17 seconds on this 28-vCPU host; they are less query-efficient than Li's method.

The attack assumes a reused KEM key and an observable valid-plaintext/derived-key signal. The local witness models that signal using the decapsulation output and an attacker-computable candidate key. An application that never exposes a usable downstream accept/reject signal is not shown vulnerable to remote key recovery by this witness.

The fix is to compare the complete ciphertext in constant time. A full-byte comparison is also required by the scheme's stated FO construction and IND-CCA2 argument.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

make -C kem-02 exploit

The source-level witness verifies the vulnerable loop in all five trees, enumerates the 262 checked positions for Amoeba-576, and exercises checked and unchecked mutation controls.

For independent end-to-end recovery, use Sage's Python (with NumPy and SciPy):

make -C kem-02 exploit-key-recovery PYTHON=/path/to/sage/bin/python

The attack-only library is linked from the same submitted Amoeba-576 object files as the normal harness library, but additionally exports the public CPA encryption and hash helpers needed to make chosen valid ciphertexts. It does not patch the candidate's comparison or decoder. The original secret key is supplied only to the decapsulation oracle and to score the recovered coefficients; the reconstructed key and fresh shared-secret checks do not copy it. A checked-byte mutation is a negative control.

kem-02-2: Secret-derived ECC decoding indexes a syndrome table

The Amoeba decapsulator decrypts under the private key and ECC-decodes the resulting codeword. Its Hamming decoder branches on each codeword bit and on the syndrome, then loads syndrome_map[s_h_key] (src/backend/hamming.c:131,157-183). Both the branch decisions and the table address derive from secret-key decryption of the ciphertext. This is a local control-flow/cache side channel independent of the incomplete ciphertext comparison elsewhere in decapsulation. The code also returns an explicit decoder-failure bit (ccakem.c:61-62), but neither that bit nor this trace has been turned into a separate demonstrated key-recovery oracle. A candidate-specific chosen-ciphertext recovery argument is still needed.

Constant-time fix (easy, hence Low): compute the syndrome with fixed XORs and correct the codeword by comparing every position with the syndrome under a mask, instead of branching and indexing syndrome_map. For a Hamming code this is a small fixed cost per block.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

Follow src/backend/ccakem.c:60-80 → src/backend/cpapke.c:438-447 → src/backend/hamming.c:131,157-183 under Implementations/Reference_Implementation/Amoeba-576/; the same decoder pattern appears in the other reference sets. This is a source-level witness, not a measured timing benchmark. See constant_time.md for the secret/public classification.

kem-02-3: The decryption-failure bound omits detected two-error rejections

Original source: NGCC PKC Forum post

Section 2.3.2 says the shortened extended Hamming decoder corrects one error but rejects exactly two. Nevertheless its quoted decryption-failure bound uses only the probability of three or more errors. The submitted CPAPKE_Decrypt returns -1 when decode_ECC detects two errors, and CCAKEM_Decaps propagates that rejection. Those events must count when bounding honest key-agreement failures and the PKE failure term used in §3.1.2's CCA reduction.

Under the submission's own Gaussian and independent-bit approximation, counting two-error events changes the Amoeba-576 tail from 2^-130.2722 to 2^-86.1221; the calculation in the official archive's Security/noise_estimation.ipynb gives both numbers, while Table 4 quotes a roughly 2^-133.3 failure claim. The revised figure is not a measurement or certified bound for correlated implementation noise, and this accounting flaw is not a second demonstrated key-recovery attack.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

python3 kem-02/reproduce_dfr_tail.py

This is a static/model calculation, not a runtime failure measurement. The standalone script reproduces all five two- and three-error tails from Security/noise_estimation.ipynb in the official Amoeba archive; the notebook need not be present to run the script. Inspect hamming.c:157-183, cpapke.c:438-447, and ccakem.c:60-63 in the Amoeba-576 reference tree for the actual rejection path.

kem-02-4: A one-bit ciphertext change writes outside the Hamming correction buffer

The Hamming syndrome_map (hamming.c:8) holds check-bit positions up to 1023, but the correction buffer c_corr has 523 bytes, and hamming.c:177 flips c_corr[q] without a bound check. Flipping the top bit of one compressed c2 coefficient makes decapsulation write past the buffer; stack protection then aborts the process in every parameter set.

The same incorrect syndrome mapping can be reached by an honest ciphertext with one noise error on a check coefficient at positions 516–521, so this is also a decapsulation reliability defect. The witness now tests a neighboring check bit whose mapped correction stays inside the buffer; it returns without aborting in all five sets.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

python3 kem-02/reproduce_ecc_stack_write.py

kem-02-5: Withdrawn — unseeded caller repeats Amoeba keys

Original source: Han's PKC Forum post

The official NICCS API makes the caller responsible for randomness: its KAT driver defines drng_algorithm (api/API_PKC/Implementations/Reference_Implementation/AlgorithmInstance/KAT_KEM.c:42) and seeds it before key generation (:105). The algorithm code normally declares this state extern. Amoeba instead defines the global in cpapke.c:13, so an unseeded caller still links and silently uses the zero-initialized state. Its unused CPAPKE_Init() helper (:15-19) suggests initialization but is not called by kem_keygen.

Fresh unseeded processes return identical Amoeba keys, while two explicitly seeded processes differ. The same unseeded-process test also repeats keys for Aigis-Enc+, Mithril, UVW, BAG-Loong and BRA. This is a consequence of omitting the caller's required seeding step, not an Amoeba-specific universal key pair. The finding is withdrawn; Amoeba's self-defined global is a robustness concern, not a demonstrated break of correctly seeded key generation.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

make -C kem-02 check-unseeded-keygen

The check launches two fresh child processes per parameter set and compares SHA-256(pk || sk), then repeats with two explicit distinct seeds as a control. It demonstrates the effect of violating the API's seeding contract.

kem-02-6: Pre-FO decoder failures give a full chosen-ciphertext key recovery

Reference: Xiong and Wang, ePrint 2026/2232, 2026-09-28 revision, §8

CCAKEM_Decaps returns -1 immediately when CPAPKE_Decrypt reports an ECC failure, before the Fujisaki--Okamoto re-encryption comparison and implicit rejection. An attacker can therefore force and observe a secret-dependent decoding-failure bit. A ciphertext with scalar c1=delta, one pinned pilot bit, and one swept probe bit reveals the threshold q/4+delta*s_i; matching the 32 possible compressed-c2 responses recovers that secret coefficient.

Xiong and Wang's public artifact recovers 517 Amoeba-576 coefficients. Further extension to their analysis initially probes all 522 coefficient positions represented in c2, then uses c1=delta*X^j and multiplication in Z_q[X]/(X^576-X^288+1) to expose the 54 positions outside c2 and resolve the four boundary positions 518--521. The local witness thereby recovers all 576 coefficients, serializes them as a new decapsulation key, and recovers the shared secret from a fresh honest encapsulation. The submitted secret key is read only to score the recovered vector; the fresh shared-secret test uses the reconstructed key. Runs use about 24,200 oracle calls and complete in under a minute on this host (about four CPU seconds, with wall time dominated by isolating crashing queries in child processes). A service that exposes the return value or the associated decoder crash provides the oracle directly.

Do not propagate any decoder result before the constant-time full-ciphertext FO check. Fold all decoding errors into the implicit-rejection mask, and separately bound the correction index to remove the out-of-bounds write.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

sh kem-02/reproduce_dfo_key_recovery.sh

The witness builds against the unmodified Amoeba-576 reference sources, contains crashing oracle calls in child processes, requires exact recovery of all 576 coefficients, and verifies a fresh shared secret with the reconstructed key.

kem-02-7: Four-way ECC loops overrun a 523-byte plaintext buffer

Original source: LK-PQC-Hunter's PKC Forum post

RLWE_ECC_N is 523, but encode_MSB and decode_MSB advance in groups of four while testing only i < RLWE_ECC_N (src/backend/cpapke.c:165–183). Their last iteration at i = 520 reads pt[523] on encryption and writes pt[523] on decryption; PTXT has valid indices 0–522. The forum reports AddressSanitizer read and write failures on honest reference Amoeba-576/1152 operations. Our certificate checks the same loop and buffer dimensions across all ten trees. The write is a fixed, one-byte tail access; the available evidence does not establish attacker-directed state corruption or a cryptographic consequence. The tail must be handled without accessing index 523.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

python3 kem-02/reproduce_ecc_tail.py

This certificate checks the source bounds; the sanitizer runs are attributed to the forum post.

kem-02-8: Amoeba's four-call SM3 expansion has only a 256-bit internal state

The specification's §1.4 (physical pp. 7–8) treats G(ID(pk),m) as a 1024-bit hash and requires a 512-bit encapsulation message at the higher levels. Its order ID(pk) || m avoids the shared first-message-block bottleneck. The submitted CCAKEM_Encaps instead implements G as four SM3-256 calls on m || counter || ID(pk) (src/backend/ccakem.c:35–45); each call reads the same first, full 64-byte block m. After that block, all four outputs depend on just one 256-bit SM3 chaining state. The remaining counter and public-key ID bytes, as well as SM3 padding, are known.

In the KEM real-or-random game, the attacker receives the challenge ciphertext and a candidate 512-bit shared key. For each of 2^256 possible first-block states, the attacker can finish the four SM3 computations, derive the pre-key, and evaluate the specified KDF on that ciphertext (ccakem.c:48–51). The real key is in this set; an independent random 512-bit key matches one of the candidates with probability at most 2^-256. This is a concrete, albeit infeasible, distinguisher below both claimed classical levels. It uses no decapsulation oracle.

The limitation is specific to the frozen SM3-based expansion, not to an ideal 1024-bit G. The specification calls its symmetric components replaceable plugins (physical p. 9); replacing them with an appropriate independent 1024-bit hash would require evaluating a different instantiation. The conclusion persists if the contest pseudoXOF used as the final KDF is idealized with its present dimensions.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

python3 kem-02/reproduce_sm3_cv_ceiling.py

The certificate verifies the first-block alignment, four SM3 calls, and final 512-bit key derivation in both high-level reference builds. The 2^256 enumeration is not run.