ci.dll — defensive termination hardening in SymCrypt ML-DSA rejection samplers

1. Overview

Verdict: The patch adds hard iteration limits and an error return to the statically-linked SymCrypt ML-DSA (FIPS 204 / "Dilithium") rejection-sampling routines, and updates their callers to propagate that error. The added counters and error code (0x8008) are real and verifiable in both builds. However this is not a reachable security fix. Each affected loop reads its bytes from a SHAKE (Keccak) sponge via SymCryptKeccakExtract, and every rejection threshold is a compile-time or parameter-set constant (eta = 2/4, q = 0x7fe001, tau). To make any of these loops fail to terminate, an attacker would have to supply a seed whose SHAKE output produced hundreds of consecutive out-of-range samples — which is cryptographically infeasible against a correct Keccak. The caps therefore guard a purely theoretical non-termination that cannot be driven by attacker-controlled input. This is defense-in-depth robustness hardening of a crypto library, classified as no security-relevant change. The unbounded-loop pattern (CWE-835 class) is discussed below only to characterize what the caps guard, not because a reachable defect exists.

2. Change Summary

Item 1 — Iteration cap added to RejBoundedPoly

What the loop does: SymCryptMlDsaRejBoundedPoly fills a polynomial of 256 coefficients (index edi, bound 0x100). Each pass reads one byte from a SHAKE (Keccak) squeeze via SymCryptKeccakExtract (0x18002bb18) and decodes up to two eta-bounded candidates. Eta is read from [rcx+0x16] (moved to r14 at entry) and is a per-parameter-set constant of 2 or 4. An out-of-range candidate is marked with the sentinel 0x80 and discarded without advancing edi. In the unpatched build the only loop guard is the outer bound at 0x18002a166 (cmp edi,0x100; jb 0x18002a08b); there is no independent iteration counter.

What changed: The patched function (0x180027128) adds an iteration counter esi checked at 0x1800271a6 (cmp esi,0x1e1; jnb 0x1800272a9) and incremented each pass at 0x18002724f. On overflow it sets edi = 0x8008 at 0x1800272a9 and returns that error in eax.

Why this is not a reachable vulnerability: The byte stream feeding the rejection test is SHAKE output, a cryptographic pseudorandom function of the seed — not raw attacker bytes. Even with full control of the seed, an attacker cannot search for a value that yields 481 consecutive rejections without breaking Keccak. The eta bound is a fixed constant. There is no attacker-controlled quantity that can force the loop past its cap, so the added limit closes only a theoretical non-termination, not a triggerable denial of service.

Item 2 — Iteration cap added to RejNttPoly

Same shape of change. The unpatched loop at 0x18002a22e reads 3 bytes from the SHAKE squeeze, masks the top byte to a 23-bit value (and byte [rsp+..+2],0x7f at 0x18002a244), and compares it to 0x7fe001 (= 8380417 = q, the ML-DSA prime modulus). If the value is >= q the branch at 0x18002a252 (jnb 0x18002a22e) rejects and loops back without decrementing the remaining-coefficient counter rbx (which starts at 0x100, decremented only on accept at 0x18002a25a). The patched function (0x1800272ec) adds counter r14d capped at 0x12a (298), checked at 0x180027369, incremented at 0x18002738d, with error mov edi,0x8008 at 0x1800273ad. q is a compile-time constant and the bytes are sponge output, so — as with Item 1 — the cap is not reachable by attacker input.

Item 3 — Iteration cap added to SampleInBall

The unpatched inner loop at 0x18002a346 reads a single byte per pass and rejects it while it exceeds the running index ebx (cmp eax,ebx; ja 0x18002a346 at 0x18002a360). The threshold derives from tau at [rsi+0x18], a parameter-set constant. The patched function (0x1800273e0) adds counter edi capped at 0x79 (121), checked at 0x18002749e, incremented at 0x1800274be, with error mov r14d,0x8008 at 0x180027502. Again the byte source is a SHAKE squeeze and the bound is a constant, so the cap is not reachable.

Item 4 — Error propagation added in callers

In the unpatched build the samplers never return an error (there is nothing to propagate), so the callers simply ignore the return. Once the patch gives the samplers a defensive error return, the callers were updated to check it. This is a direct consequence of Items 1–3, not an independent defect: with the input being sponge output, the error path is not reachable in normal operation.

3. Pseudocode Diff

SymCryptMlDsaRejBoundedPoly (0x18002a00c → 0x180027128)

// ============================================================
// UNPATCHED — SymCryptMlDsaRejBoundedPoly (0x18002a00c)
// ============================================================
int RejBoundedPoly_unpatched(void* mldsaKey, void* shakeSeed, uint32_t* poly_out) {
    KECCAK_STATE st;                       // SHAKE (Keccak) squeeze context
    SymCryptKeccakAppend(&st, shakeSeed, ...);
    int edi = 0;                           // coefficient index

    while (edi < 0x100) {                   // outer bound: 256 coefficients
        uint8_t b;
        SymCryptKeccakExtract(&st, &b, 1, 0);   // squeeze 1 byte from SHAKE
        // decode two eta-bounded candidates from the byte's nibbles;
        // out-of-range candidates are marked 0x80 (rejected)
        if (cand0 != 0x80) poly_out[edi++] = coeff0;
        if (cand1 != 0x80 && edi < 0x100) poly_out[edi++] = coeff1;
        // no independent iteration counter
    }
    return 0;                               // never returns error
}

// ============================================================
// PATCHED — SymCryptMlDsaRejBoundedPoly (0x180027128)
// ============================================================
int RejBoundedPoly_patched(void* mldsaKey, void* shakeSeed, uint32_t* poly_out) {
    KECCAK_STATE st;
    SymCryptKeccakAppend(&st, shakeSeed, ...);
    int edi = 0;                            // coefficient index (ebx in asm)
    int esi = 0;                            // NEW: iteration counter

    while (edi < 0x100) {
        if (esi >= 0x1e1) {                 // NEW: 481-iteration limit
            return 0x8008;                  // NEW: error return
        }
        uint8_t b;
        SymCryptKeccakExtract(&st, &b, 1, 0);
        // ... same eta decode ...
        esi++;                              // NEW: always incremented
        if (cand0 != 0x80) poly_out[edi++] = coeff0;
        if (cand1 != 0x80 && edi < 0x100) poly_out[edi++] = coeff1;
    }
    return 0;
}

SymCryptMlDsaExpandS (0x180029424 → 0x18002651c) — Error Propagation

// ============================================================
// UNPATCHED — SymCryptMlDsaExpandS (0x180029424)
// ============================================================
void ExpandS_unpatched(...) {
    for (int i = 0; i < k; i++) {
        // return value ignored (sampler never fails in this build)
        SymCryptMlDsaRejBoundedPoly(key, seed, &s[i]);
    }
}

// ============================================================
// PATCHED — SymCryptMlDsaExpandS (0x18002651c)
// ============================================================
int ExpandS_patched(...) {
    for (int i = 0; i < k; i++) {
        int rc = SymCryptMlDsaRejBoundedPoly(key, seed, &s[i]);
        if (rc != 0) {                      // NEW: error check
            return rc;                      // NEW: propagate failure
        }
    }
    return 0;
}

SymCryptMlDsaSignEx (0x180020c1c → 0x180021394) — Overall Signing Cap

// ============================================================
// PATCHED ADDITION (not present in unpatched)
// ============================================================
// New upper bound on the ML-DSA signing rejection loop:
int max_iterations = *(uint8_t*)(rdi + 0x15) * 0x32e;  // k (module rows) * 814
if (current_iteration >= max_iterations) {
    return 0x8008;                          // circuit breaker
}
// Plus: a null-pointer guard added before the SymCryptMlDsaSigEncode (0x1800275d4) helper call.

4. Assembly Analysis

SymCryptMlDsaRejBoundedPoly (0x18002a00c) — Unpatched Loop

; UNPATCHED: SymCryptMlDsaRejBoundedPoly (0x18002a00c)
; rcx (arg1) moved to r14 at entry; eta selector is [r14+0x16] == [rcx+0x16]

0x18002a08b:  xor     r9d, r9d
0x18002a08e:  lea     rdx, [rsp+var_11F]      ; &output byte
0x18002a093:  lea     rcx, [rsp+var_110]      ; Keccak (SHAKE) state
0x18002a098:  lea     r8d, [r9+1]             ; extract 1 byte
0x18002a09c:  call    SymCryptKeccakExtract   ; squeeze 1 byte from SHAKE
0x18002a0a5:  mov     al, [r14+16h]           ; eta (2 or 4), parameter-set constant
;             ... decode two eta-bounded nibbles; 0x80 == rejected ...
0x18002a141:  cmp     dl, 0x80                ; second candidate rejected?
0x18002a146:  cmp     edi, 0x100              ; coefficients filled? (256)

; --- Outer loop bound (the only guard) ---
0x18002a166:  cmp     edi, 0x100              ; table index < 256?
0x18002a16c:  jb      0x18002a08b             ; loop back — no independent iteration counter

SymCryptMlDsaRejBoundedPoly (0x180027128) — Patched Loop

; PATCHED: SymCryptMlDsaRejBoundedPoly (0x180027128)

0x1800271a2:  mov     ebx, edi               ; ebx = coefficient index (0)
0x1800271a4:  mov     esi, edi               ; esi = iteration counter (0)
0x1800271a6:  cmp     esi, 0x1e1             ; NEW: iteration count >= 481?
0x1800271ac:  jnb     0x1800272a9            ; NEW: jump to error path
0x1800271bf:  lea     r8d, [r9+1]            ; extract 1 byte
0x1800271c3:  call    SymCryptKeccakExtract
;             ... same eta decode ...
0x18002724f:  inc     esi                    ; NEW: always increment counter
0x18002729b:  cmp     ebx, 0x100
0x1800272a1:  jb      0x1800271a6            ; loop back through the cap check

; --- Error return path ---
0x1800272a9:  mov     edi, 0x8008            ; NEW: error code, returned in eax

SymCryptMlDsaRejNttPoly (0x18002a1ac) — Unpatched q-Rejection Loop

; UNPATCHED: SymCryptMlDsaRejNttPoly (0x18002a1ac)
0x18002a229:  mov     ebx, 0x100             ; remaining coefficients
0x18002a22e:  xor     r9d, r9d
0x18002a231:  lea     rdx, [rsp+var_110]     ; &output value
0x18002a236:  lea     rcx, [rsp+var_100]     ; Keccak (SHAKE) state
0x18002a23b:  lea     r8d, [r9+3]            ; extract 3 bytes
0x18002a23f:  call    SymCryptKeccakExtract  ; squeeze 3 bytes from SHAKE
0x18002a244:  and     byte [rsp+var_110+2], 0x7f  ; mask top byte -> 23-bit value
0x18002a249:  mov     eax, dword [rsp+var_110]
0x18002a24d:  cmp     eax, 0x7fe001          ; >= q (8380417, compile-time constant)?
0x18002a252:  jnb     0x18002a22e            ; reject: loop back without decrementing rbx
0x18002a254:  mov     dword [rdi], eax       ; store accepted coefficient
0x18002a256:  add     rdi, 0x4
0x18002a25a:  sub     rbx, 0x1               ; decrement remaining count (accept only)
0x18002a25e:  jnz     0x18002a22e

Patched SymCryptMlDsaRejNttPoly (0x1800272ec) inserts cmp r14d, 0x12a; jnb 0x1800273ad at 0x180027369, inc r14d at 0x18002738d, and error mov edi, 0x8008 at 0x1800273ad.

SymCryptMlDsaSampleInBall (0x18002a288) — Unpatched Inner Loop

; UNPATCHED: SymCryptMlDsaSampleInBall (0x18002a288)
0x18002a346:  xor     r9d, r9d
0x18002a349:  lea     rdx, [rsp+var_140]
0x18002a34e:  mov     r8, rsi                ; extract 1 byte (rsi == 1)
0x18002a351:  lea     rcx, [rsp+var_130]     ; Keccak (SHAKE) state
0x18002a356:  call    SymCryptKeccakExtract
0x18002a35b:  movzx   eax, [rsp+var_140]
0x18002a360:  cmp     eax, ebx               ; ebx = running index (tau-derived)
0x18002a362:  ja      0x18002a346            ; reject and retry — no independent counter

Patched SymCryptMlDsaSampleInBall (0x1800273e0) inserts cmp edi, 0x79; jnb 0x180027502 at 0x18002749e, inc edi at 0x1800274be, and error mov r14d, 0x8008 at 0x180027502.

Side-by-Side Key Difference

All five sites are real. None is reachable by attacker input, because the loop-driving bytes are SHAKE output and the thresholds are constants.

5. Reachability Analysis

1. Where the samplers run. Windows Code Integrity reaches these routines during ML-DSA operations:
2. Verification (SymCryptMlDsaVerifyEx → SymCryptMlDsaSampleInBall, and matrix expansion via SymCryptMlDsaExpandA → SymCryptMlDsaRejNttPoly).
3. Key generation / import (SymCryptMlDsaKeyGenerateEx → SymCryptMlDsaExpandS → SymCryptMlDsaRejBoundedPoly).

4. Signing (SymCryptMlDsaSignEx), which also drives SymCryptMlDsaSampleInBall.

5. What feeds the rejection test. The seed fed to each SHAKE squeeze comes from key/signature material (rho / seed, or the challenge hash c-tilde). But the loop's accept/reject decision is made on the SHAKE output, not on the seed bytes directly. SymCryptKeccakExtract is a sponge squeeze: a cryptographic pseudorandom stream.

6. Why the loops cannot be forced to hang. For each loop, non-termination would require every squeezed sample to be rejected for the entire cap length:

7. RejNttPoly: every 3-byte, 23-bit value >= q (0x7fe001). The per-sample rejection probability is (2^23 - q)/2^23 ≈ 0.098%.
8. RejBoundedPoly: every decoded eta candidate out of range (sentinel 0x80).

9. SampleInBall: every sampled index byte greater than the running threshold. Producing hundreds of consecutive rejections would require finding a seed whose SHAKE output has that structure, which is equivalent to defeating the pseudorandomness of Keccak. No attacker-controlled quantity in these paths permits that. The rejection thresholds (eta, q, tau) are compile-time / parameter-set constants, not attacker-tunable.

10. Conclusion. The added iteration caps and the error-propagation chain guard a condition that cannot be produced by any attacker input. There is no reachable denial of service, no out-of-bounds access (the byte source is an internal sponge, not an external finite buffer), no information leak, and no memory-corruption primitive. The change is defensive robustness hardening of the statically-linked SymCrypt library.

6. Impact Assessment

Mitigation Relevance

Bottom line: A robustness/termination guarantee added to the ML-DSA rejection samplers. It bounds each loop and returns a clean error (0x8008) instead of relying on the sampler always eventually accepting. Because the loop input is sponge output and the bounds are constants, no reachable security defect is fixed or removed.

7. Debugger Observation Guide

For a researcher wishing to observe the samplers under WinDbg/KD. These offsets are RVAs; use lm ci to get the runtime base.

Breakpoints

; -- RejBoundedPoly --
bp CI_BASE+0x2a00c           ; SymCryptMlDsaRejBoundedPoly entry
bp CI_BASE+0x2a08b           ; rejection loop body (1-byte SHAKE squeeze)
bp CI_BASE+0x2a166           ; cmp edi,0x100 (the only bound guard)

; -- RejNttPoly --
bp CI_BASE+0x2a1ac           ; SymCryptMlDsaRejNttPoly entry
bp CI_BASE+0x2a22e           ; rejection loop body (3-byte SHAKE squeeze)
bp CI_BASE+0x2a252           ; the jnb that rejects (value >= q)

; -- SampleInBall --
bp CI_BASE+0x2a288           ; SymCryptMlDsaSampleInBall entry
bp CI_BASE+0x2a346           ; inner rejection loop body (1-byte squeeze)

; -- SHAKE squeeze --
bp CI_BASE+0x2bb18           ; SymCryptKeccakExtract

; -- Callers --
bp CI_BASE+0x29424           ; SymCryptMlDsaExpandS
bp CI_BASE+0x29284           ; SymCryptMlDsaExpandA
bp CI_BASE+0x209b4           ; SymCryptMlDsaKeyGenerateEx
bp CI_BASE+0x20c1c           ; SymCryptMlDsaSignEx
bp CI_BASE+0x21108           ; SymCryptMlDsaVerifyEx
bp CI_BASE+0x21580           ; SymCryptMlDsakeySetValue

What to Inspect

At CI_BASE+0x2a00c (SymCryptMlDsaRejBoundedPoly entry): - rcx = ML-DSA key/params pointer ([rcx+0x16] selects eta = 2 or 4) - rdx = SHAKE seed buffer - r9 = output polynomial buffer (0x100 coefficients, 0x400 bytes)

At CI_BASE+0x2a08b (RejBoundedPoly loop body): - edi = current coefficient index; advances toward 0x100 as samples are accepted.

At CI_BASE+0x2a22e (RejNttPoly loop body): - rdi = current coefficient write pointer (advances by 4 on accept) - rbx = remaining coefficients (starts at 0x100, decrements on accept)

At CI_BASE+0x2a24d (RejNttPoly, after squeeze, before q check): - eax = candidate coefficient; compared to 0x7fe001 (q).

At CI_BASE+0x2bb18 (SymCryptKeccakExtract): - rcx = Keccak (SHAKE) state - r8 = number of bytes to squeeze (1 in RejBoundedPoly/SampleInBall, 3 in RejNttPoly) - This is a squeeze from an internal sponge state; it does not read an external buffer and never runs out of output.

Key Instructions / Offsets

Expected Observation

During a normal ML-DSA operation the samplers accept within a handful of squeezes and the counters advance to completion. On the patched build a sampler that somehow failed to accept would return 0x8008 once its iteration cap (481 / 298 / 121) is reached. Under real inputs the caps are never approached, because SHAKE output rejects only a small fraction of samples.

Struct/Offset Notes

; ML-DSA key/params (arg1 / rcx at sampler entry):
;   +0x14 : l (column dimension) used by ExpandS
;   +0x15 : k (row dimension) — used as signing-loop bound (k * 0x32e) in SignEx
;   +0x16 : eta selector (2 or 4) for RejBoundedPoly
;   +0x18 : tau (SampleInBall threshold input)

; Output polynomial buffer:
;   0x100 coefficients x 4 bytes = 0x400 bytes total

; Keccak (SHAKE) state passed to SymCryptKeccakExtract:
;   an internal sponge; squeezing produces pseudorandom output on demand

8. Changed Functions — Full Triage

ML-DSA Rejection-Sampling Path (Defensive Hardening — not attacker-reachable)

Behavioral (Non-Security)

Cosmetic / Refactor

• SbpParseSignatureDatabase (0x18000beb8) (similarity 0.247): refactor extracting the parse loop into helper SbpParseSignatureDatabaseFromBuffer (0x18001dc20). Functionally equivalent parsing logic.
• SymCryptMlDsakeyInitialize (0x18002b32c) (similarity 0.695): ML-DSA key-init — register reallocation (rsi→rdi, rcx_2→rdx_1). No logic change.
• SIPolicyAreCustomKernelSignersAllowed (0x1800706c4) (similarity 0.171): rewritten iteration logic but functionally equivalent (checks policy flags). Low similarity is due to structural rewrite, not behavioral change.

9. Unmatched Functions

No functions were added or removed between the unpatched and patched binaries (unmatched_unpatched: 0, unmatched_patched: 0). All changes are in-place modifications to existing functions: - No new sanitizers or validation functions were introduced as standalone code. - No functions were deleted (no removed security checks). - The iteration caps and error propagation were inlined into the existing rejection-sampling functions and their callers.

10. Confidence & Caveats

Confidence: High (in the classification)

Rationale: - The assembly diff is clear and consistent: every affected sampler gains an explicit iteration counter with a cmp/jnb guard absent in the unpatched binary, and the error code 0x8008 appears at each patched site with all callers updated to check it. These facts were verified against both builds at exact addresses. - The byte source at every rejection site is the SHAKE (Keccak) squeeze (SymCryptKeccakExtract), and the rejection thresholds are compile-time / parameter-set constants: eta (2 or 4) from [rcx+0x16], q = 0x7fe001 (8380417), and tau from [rcx+0x18]. None is attacker-tunable. - Because the loop-driving stream is a cryptographic sponge output, sustained rejection to the cap length is not producible by any attacker-supplied seed. The change therefore has no reachable security impact and is classified as defensive hardening of the statically-linked SymCrypt library — no security-relevant change.

What a reader can independently confirm: 1. The added counters and error returns exist at the stated addresses in ci_patched and are absent in ci_unpatched. 2. The bytes compared against each threshold come from SymCryptKeccakExtract, not from an external buffer. 3. The thresholds are immediates / fixed struct fields, not attacker-controlled values.

These three points together establish that the fix bounds a theoretical non-termination rather than a reachable denial of service.