Security › kem-34 · Constant-time review · Performance: x86_1 · arm_1
Rudraksh2 (kem-34)
| Candidate | Rudraksh2 |
|---|---|
| Family | Lattice-based KEM |
| Archive | Rudraksh2.zip (SHA-256: 569d526cf7abe38393f69a4513686fa86a0c3b3033cc225b84cc107b20b17b98) |
| Specification | kem-34-spec.pdf PDF |
| Performance | x86_1 · arm_1 |
kem-34-1: Rudraksh2-128 has a 2^64-iteration generic search before oracle costs
| Severity | Info |
|---|---|
| Scope | design |
| Status | Proof gap |
| Affected | Rudraksh2-128-I; the same 128-bit message dimension is specified for Rudraksh2-128-II |
| Discovery | Trivial |
| Exploitation | None demonstrated below the 80-bit target; oracle and other quantum costs are unbounded here |
| Credit | Zhenyu Xiong and Mingsheng Wang, with GLM-5.3 assistance |
| Date | 2026-09-30 |
Original source: PKC Forum post and verification package
Rudraksh2-128 samples a 16-byte encapsulation message m, then derives both the session key and the public encryption randomness as G(m || H(pk)) (params.h:41–50, KEM_lwekem128.c:73–97). Given a ciphertext and public key, a candidate message is publicly testable by recomputing the encryption. Generic Grover search therefore needs about 2^64 such oracle iterations. This is below the set's nominal 80-bit quantum exponent if one counts oracle calls alone, but each oracle must implement and uncompute the full public encryption test. The NGCC call does not specify the quantum cost metric precisely, and no gate-level estimate establishes total work below 2^80; this is an informational cost-model observation, not a vulnerability. The observation remains after replacing the contest placeholder XOF with an ideal primitive of the same dimensions.
The witness resets the deterministic test generator to recover the encapsulator's m, then reconstructs all 32 session keys as G(m || H(pk)) without using the secret key or ciphertext. It demonstrates the public reduction but does not run the generic 2^64 search.
Reclassification
Reclassified from Medium to Info on 2026-10-13: the 2^64 iteration count is unchanged, but no complete below-target quantum attack cost is established.
Reproducing
Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).
make -C kem-34 reproduce-message-space
python3 kem-34/reproduce_parameters.py
kem-34-2: Cortex-M4 uses an incompatible Minal decoder constant
| Severity | Low |
|---|---|
| Scope | implementation |
| Status | Confirmed |
| Affected | Rudraksh2-128 and -256 Cortex-M4 implementations |
| Discovery | Trivial |
| Exploitation | Honest cross-implementation sessions derive different keys |
| Credit | Zhenyu Xiong and Mingsheng Wang, with GLM-5.3 assistance |
| Date | 2026-09-30 |
Original source: PKC Forum post and verification package
The Cortex-M4 128- and 256-bit trees set MINAL_BETA to 0 (minal.c:15), whereas the specification, reference, and optimized implementations use 220. This constant changes the two-dimensional error-correcting code. Cross-tests reproduced zero matching keys in 200 sessions in each direction between Cortex-M4 and reference code; Cortex-M4 self-tests succeeded, and changing only the constant to 220 restored 200/200 interoperability in both directions. This is an availability/interoperability defect, not a confidentiality break.
Proposed fixes
The original post proposes changing MINAL_BETA to 220 in the Cortex-M4 128- and 256-bit implementations.
Reproducing
Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).
python3 kem-34/reproduce_parameters.py
The compact witness verifies the conflicting constants in the archived trees. The original package contains the full cross-implementation experiment.
kem-34-3: KEM entry points ignore caller-declared buffer lengths
| Severity | Low |
|---|---|
| Scope | implementation |
| Status | Confirmed |
| Affected | Rudraksh2 reference implementations |
| Discovery | Trivial |
| Exploitation | Out-of-bounds read from a caller-supplied short buffer |
| Credit | Zhenyu Xiong and Mingsheng Wang, with GLM-5.3 assistance |
| Date | 2026-09-30 |
Original source: PKC Forum post and verification package
kem_enc and kem_dec accept public-key and ciphertext lengths but never inspect them, and kem_dec likewise ignores the supplied secret-key length. They instead read the compile-time sizes (KEM_lwekem128.c:73–99,102–144). Passing kem_dec an allocation one byte shorter than the normal 912-byte ciphertext and its true length of 911 produces an AddressSanitizer heap-buffer-overflow read at poly.c:105, reached through indcpa.c:121. No disclosure, write, or control-flow impact is demonstrated.
Proposed fixes
The original post proposes validating caller-supplied lengths before accessing the public key or ciphertext.
Reproducing
Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).
make -C kem-34 reproduce-length-read
kem-34-4: Rudraksh2-II's modulus cannot support its specified NTT
| Severity | Info |
|---|---|
| Scope | design |
| Status | Confirmed |
| Affected | Rudraksh2-128-II, -256-II, and -512-II specifications |
| Discovery | Trivial |
| Exploitation | The specified NTT cannot be realized for these parameters; no security consequence is shown |
| Credit | Zhenyu Xiong and Mingsheng Wang, with GLM-5.3 assistance |
| Date | 2026-09-30 |
Original source: PKC Forum post and verification package
The specification requires a primitive 2n-th root of unity in Z_q for its negacyclic NTT. Every -II set uses q=4001, but q-1 = 4000 = 2^5 * 5^3; the largest supported negacyclic-NTT degree is therefore 16. The specified degrees are 64, 128, and 256, so none has the required root. The submission supplies no -II implementation. The polynomial ring itself remains implementable by a different multiplication method. This is a realization note, not a security vulnerability: no submitted -II implementation fails, and no attack or availability failure is shown.
Reproducing
Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).
python3 kem-34/reproduce_parameters.py
kem-34-5: Dual-hybrid attacks put Rudraksh2-512-I below its target
| Severity | Critical |
|---|---|
| Scope | design |
| Status | Probable |
| Affected | Rudraksh2-512-I |
| Discovery | Moderate |
| Exploitation | Estimated 2^495.5 operations for key recovery (MATZOV dual-hybrid, lattice-estimator gate-count model); not executed |
| Credit | Markku-Juhani O. Saarinen markku-juhani.saarinen@tuni.fi, with AI assistance |
| Date | 2026-10-31 |
The Rudraksh2-512-I public key is an uncompressed MLWE sample with ℓn = 2048, q = 7681 and CBD₂ secret and error (lwekem512/params.h). Table 14 claims Core-SVP 2^512 and 2^527 gates, and §3.2.5 states that the Core-SVP estimates meet the required security. The lattice-estimator's MATZOV dual-hybrid attack costs 2^495.5 in its default gate-count model and 2^482.1 in ADPS16 Core-SVP, below the primal attacks that Table 14 reflects. The estimate relies on the dual-attack heuristics the estimator adopts.
In Core-SVP the same attack gives 124.35 and 249.71 bits for Rudraksh2-128-I and -256-I, below Table 14's 129 and 267 and below their targets. In the gate-count model those sets are at 147.7 and 269.5 bits, above target, so they are not included in this rating.
Reproducing
Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).
LATTICE_ESTIMATOR_PATH=../lattice-estimator sage -python kem-34/reproduce_dual_hybrid.py
The script requires lattice-estimator commit 53da598 and prints the best attack for each Rudraksh2-I set in both cost models. It takes about nine minutes.