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

Mithril (kem-22)

kem-22-1: Reversed decryption offset invalidates the failure estimate

Original source: GitHub issue #15

Encryption adds q/(2p) before compressing c_m. Algorithm 1 specifies p/(2t) - q/(2p) during decryption, and the live decoder in arith/packing.c:215 applies the corresponding +126 for Mithril-256. (The similar poly_subp in pke.c is unused.) Centering the compression remainder instead requires q/(2p) - p/(2t). The specified sign leaves the Mithril-128/-256 decoder substantially off center, whereas the submitted decryption-failure analysis assumes a centered error. The report does not establish a new key-recovery attack or a numerical honest-failure probability.

Samuel's concrete Mithril-256 record uses the submitters' own PKE and KEM functions: an honestly formed ciphertext gives different encapsulated and decapsulated secrets. Its wrong bit has LWR noise 136 and compression remainder 254; the specified offset yields 514, beyond the decision margin 512, while the centered offset yields 262. This pinned record depends on the submitted hash output and need not persist under an ideal replacement, but the erroneous decoder offset is independent of that hash choice.

Reproducing

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

D=kem-22/Implementations/Reference_Implementation/Mithril-256
T=$(mktemp -d)
gcc -O2 -DRRLWR_SECURITY_LEVEL=256 -I"$D" -I"$D/utils" -I"$D/arith" \
    "$D"/arith/{poly,ring,packing,uniform}.c "$D"/{pke,kem}.c \
    "$D"/utils/{auxfunc,drng}.c kem-22/reproduce_decoding_constant.c -o "$T/repro"
"$T/repro"

The program prints CONFIRMED only when the official decapsulator returns a different secret for the pinned honest encapsulation. It does not estimate the failure rate.