Cryptography Fundamentals Questions

Recommendation Memo — Evaluation of New Post‑Quantum KEM

Recommendation
I recommend a time‑boxed pilot adoption rather than immediate enterprise‑wide deployment. The KEM’s computational speed is attractive, but immature proofs and large ciphertexts present measurable operational and security risks.

Security (proof maturity)

• Status: heuristic security with partial reductions; lacks broad cryptanalysis and formal proofs.
• Risk: potential for undiscovered structural weaknesses; unknown long‑term confidence vs. NIST finalists.
• Mitigation: require independent third‑party cryptanalysis and a 6–12 month review window before full rollout.

Operational impacts

• Latency: CPU latency benefit for handshake computations — positive for CPU‑bound services.
• MTU and fragmentation: ciphertext expansion likely to exceed common MTUs (e.g., 1500 bytes) causing fragmentation and increased packet loss risk—must test across network paths and middleboxes.
• Storage/DB: per‑session or archived ciphertext growth (estimate +X–Y%) affects DB sizing, backup, and replication costs.
• Interoperability: larger messages can break legacy clients, load balancers, VPN gateways and TLS stacks that assume modest key sizes.

Standardization & timeline

• Not standardized; expect 12–36 months before formal standards if vetting continues. Prefer alignment with NIST/ISO outcomes.

Staged rollout plan

1. Lab validation: interoperability, MTU/fragmentation, performance, and fuzz testing (2–4 weeks).
2. Canary pilot: internal services in isolated VPCs using dual‑stack (classic KEM + new KEM) with traffic mirroring and real‑time metrics (3 months).
3. Gradual expansion: add lower‑risk external endpoints and tuned MTU settings; require third‑party audit signoff before broader deployment.
4. Full deployment: contingent on cryptanalysis results and community/standards progress.

Rollback plan & triggers

• Triggers: discovery of critical cryptanalysis, fragmentation causing >1% error, latency regressions >10%, or unacceptable storage growth thresholds.
• Rollback actions: switch to fallback classical KEM via negotiated downgrade (dual‑stack design), revoke new KEM keys, and deploy configuration flags to disable new KEM in 30 min rolling updates. Maintain audited backups of pre‑change states.

Conclusion
Proceed with cautious pilot, prioritize independent cryptanalysis and MTU/interoperability testing, and require clear success criteria and rollback capability before enterprise adoption.

Approach (brief)
Use multiplicative blinding: pick random r in (1,n-1), compute c' = c * r^e mod n. Perform CRT exponentiation on c' to get m' = (c')^d mod n using dP,dQ and qInv. Unblind m = m' * r^{-1} mod n. Add post-checks to detect faults.

Code (Python-like)

import secrets
def modinv(a,m): return pow(a,-1,m)

def rsa_crt_blinded(c, p,q, dP,dQ, qInv, e):
    n = p*q
    # 1. blinding
    r = secrets.randbelow(n-2)+2
    r_e = pow(r, e, n)
    c_blind = (c * r_e) % n

    # 2. CRT exponentiation on c_blind
    m1 = pow(c_blind % p, dP, p)
    m2 = pow(c_blind % q, dQ, q)
    h  = ( (m1 - m2) * qInv) % p
    m_blind = (m2 + h * q) % n

    # 3. unblind
    r_inv = modinv(r, n)
    m = (m_blind * r_inv) % n

    # 4. verification / fault detection
    if pow(m, e, n) != c % n:
        raise ValueError("Decryption/signing failed: verification mismatch")
    return m

Why blinding helps

• Multiplicative blinding randomizes the exponentiation input; timing or power traces correlate to random r^e * c, not the fixed secret key-dependent internal values. This breaks correlation exploited in timing/SPA attacks.

Additional checks vs fault-injection

• Verify m^e ≡ c (mod n) as above; detects incorrect CRT recombination or induced faults.
• Recompute with non-CRT (single exponentiation) on failure or periodically as sanity check.
• Use exponentiation algorithms constant-time and with blinding for intermediate values.
• Implement redundancy: compute both CRT paths and cross-check m1 and m2 lengths/limits; check p and q sizes and primality on key load.
• Protect memory, use integrity checks and watchdog to reduce glitch/fault windows.

Complexity

• Two modular exponentiations modulo p and q (faster than single mod n), plus blinding/unblinding costs O(log e) multiplications.

Approach (brief)
Compute AES S-box algebraically: 1) multiplicative inverse in GF(2^8) (0 -> 0), implemented via constant-time field operations and a fixed addition chain to compute x^(254) = x^-1; 2) apply the affine transform. No table lookups or secret-dependent branches.

C implementation (constant-time bit ops, no tables)

#include <stdint.h>

/* GF(2^8) AES irreducible poly: x^8 + x^4 + x^3 + x + 1 -> 0x11B */
static inline uint8_t gf_mul(uint8_t a, uint8_t b) {
    uint8_t res = 0;
    for (int i = 0; i < 8; ++i) {
        /* conditional xor without branch */
        uint8_t mask = -(b & 1);
        res ^= a & mask;
        uint8_t hi = a & 0x80;
        a <<= 1;
        /* reduce if overflow */
        a ^= (uint8_t)((hi >> 7) * 0x1B);
        b >>= 1;
    }
    return res;
}
static inline uint8_t gf_square(uint8_t a) { return gf_mul(a, a); }

/* compute x^254 = inverse for x != 0 using fixed addition chain */
static uint8_t gf_inv(uint8_t x) {
    if (!x) return 0;
    uint8_t x2  = gf_square(x);         // x^2
    uint8_t x3  = gf_mul(x2, x);        // x^3
    uint8_t x5  = gf_mul(x3, x2);       // x^5
    uint8_t x10 = gf_square(x5);        // x^10
    uint8_t x20 = gf_square(x10);       // x^20
    uint8_t x40 = gf_square(x20);       // x^40
    uint8_t x50 = gf_mul(x40, x10);     // x^50
    uint8_t x100= gf_square(x50);       // x^100
    uint8_t x200= gf_square(x100);      // x^200
    /* combine to get x^254 = x^(200+50+4) */
    uint8_t t = gf_mul(x200, x50);      // x^250
    uint8_t x4  = gf_square(x2);        // x^4
    return gf_mul(t, x4);               // x^254
}

uint8_t aes_sbox_nontable(uint8_t in) {
    uint8_t y = gf_inv(in);
    /* affine transform: b = A*y ^ c, where A is fixed matrix; implement bitwise */
    uint8_t out = 0;
    uint8_t c = 0x63;
    for (int i = 0; i < 8; ++i) {
        /* compute bit i as y_i ^ y_{(i+4)%8} ^ y_{(i+5)%8} ^ y_{(i+6)%8} ^ y_{(i+7)%8} ^ c_i */
        uint8_t bit = ((y >> i) & 1)
                    ^ ((y >> ((i+4)&7)) & 1)
                    ^ ((y >> ((i+5)&7)) & 1)
                    ^ ((y >> ((i+6)&7)) & 1)
                    ^ ((y >> ((i+7)&7)) & 1)
                    ^ ((c >> i) & 1);
        out |= bit << i;
    }
    return out;
}

Key points & reasoning

• Multiplication uses branchless shift/xor and constant loop count (8 iterations) so no secret-dependent memory or timing from branches.
• Inversion via fixed addition chain yields fixed sequence of multiplies/squares; avoids data-dependent loops or table indexes.
• Affine transform is bitwise and branchless.

Performance vs table-driven S-box

• Table approach (256-byte lookup) is much faster (single memory read) and simpler; CPU latency >> arithmetic here.
• Table lookups are vulnerable to cache-timing attacks if attacker can observe cache state (shared cache, speculative attacks).
• Algebraic implementation is slower (many GF multiplies per byte) but constant-time and side-channel resistant at software-level.

Hardware AES acceleration trade-offs

• AES-NI (or ARM Crypto) does SBOX internally in microcode/hardware constant-time and is both fastest and side-channel resistant for typical usage — prefer hardware when available and trusted.
• If hardware not available or untrusted, algebraic / bit-sliced implementations or masked variants provide resistance at higher CPU cost.

Notes & extensions

• For high-throughput, consider bit-slicing and SIMD to amortize cost across many bytes; combine with masking for stronger resistance against power/EM side channels.
• Validate against test vectors and ensure compiler doesn't optimize branches or table replacements—use volatile or inline asm guards if needed.

Situation & short summary
A MAC-then-encrypt scheme that computes HMAC-SHA256 over the plaintext, then encrypts the plaintext with AES-CTR and sends (ciphertext, MAC). At a high level this is insecure: AES‑CTR is a malleable stream cipher and the MAC is computed on the plaintext only, so the receiver cannot reliably detect whether ciphertext was tampered before decryption.

Concrete security issues

• MAC over plaintext only: An attacker can modify ciphertext; the receiver decrypts to a modified plaintext and then the MAC check (computed over original plaintext) will fail only if the receiver still compares to the sent MAC — but if attacker manipulates delivery order or causes decryption first, decryption is done on attacker-controlled data before integrity is confirmed (dangerous).
• AES-CTR malleability: Flipping bits in ciphertext flips corresponding bits in plaintext; attacker can perform predictable plaintext modifications without knowing key.
• Chosen-ciphertext attacks / oracle risk: If the system leaks any information on decryption failures (timing, error messages), attacker can use malleability to learn plaintext or MAC — e.g., flip ciphertext to test guesses and observe MAC verify behavior.
• Replay and reordering: No binding between MAC and ciphertext (MAC not authenticated over ciphertext or IV/counter), so attacker can replay or swap messages, or reuse IVs causing keystream reuse.

Example attacks

• Bit-flip to change fields (e.g., change amount in a payment): flip ciphertext bits; receiver decrypts and processes before MAC check, causing unauthorized actions.
• CBC/CTR oracle: Using chosen-ciphertext probes and observing whether MAC comparison runs or fails (timing) to recover plaintext bytes.
• Keystream reuse: If IV reuse occurs, attacker XORs two ciphertexts to cancel keystream, recovers XOR of plaintexts and can manipulate MACs.

Concrete fixes

• Use AEAD: Replace with AES-GCM, AES-CCM, or ChaCha20-Poly1305 which provide authenticated encryption in one operation; they authenticate ciphertext, associated data, and IV and resist CCA.
• Encrypt-then-MAC if AEAD unavailable: Compute C = Enc(k_e, IV, P), T = HMAC(k_m, IV || C), send (IV, C, T). Verify MAC over IV||C before decryption. This prevents decryption of tampered ciphertexts.
• Ensure unique nonces/IVs and bind associated data (headers, sequence numbers) into the AEAD or MAC.
• Implement constant-time MAC comparisons and uniform error messages to avoid oracles.

Why these are better

• AEAD / encrypt-then-MAC ensures integrity is checked over ciphertext (not plaintext) before any decryption, preventing malleability-based exploitation and chosen-ciphertext leakage. AEAD is standardized, formally analyzed, and avoids subtle composition pitfalls.

Approach (brief)
Implement RFC6979 section 3.2: run an HMAC-DRBG seeded with private key and message hash (both as octet strings) using HMAC-SHA256; produce pseudorandom bits, convert to integer k = bits2int(T) and accept if 1 <= k < q; otherwise reseed per RFC and retry. This avoids biased nonces because generation is uniform across the group order space and independent of external RNG failures.

Code (Python, HMAC-SHA256):

import hmac, hashlib, math

def bits2int(b, qlen):
    i = int.from_bytes(b, 'big')
    blen = len(b) * 8
    if blen > qlen:
        return i >> (blen - qlen)
    return i

def int_to_bytes(x, length):
    return x.to_bytes(length, 'big')

def rfc6979_generate_k(priv_key_bytes, hash_bytes, q):
    hlen = 32  # SHA256 output size in bytes
    qlen = q.bit_length()
    bx = priv_key_bytes + hash_bytes

    V = b'\x01' * hlen
    K = b'\x00' * hlen

    K = hmac.new(K, V + b'\x00' + bx, hashlib.sha256).digest()
    V = hmac.new(K, V, hashlib.sha256).digest()
    K = hmac.new(K, V + b'\x01' + bx, hashlib.sha256).digest()
    V = hmac.new(K, V, hashlib.sha256).digest()

    while True:
        T = b''
        tlen = 0
        while tlen < qlen:
            V = hmac.new(K, V, hashlib.sha256).digest()
            T += V
            tlen += len(V) * 8

        k = bits2int(T, qlen)
        if 1 <= k < q:
            return k

        K = hmac.new(K, V + b'\x00', hashlib.sha256).digest()
        V = hmac.new(K, V, hashlib.sha256).digest()

Why this avoids biased nonces

• The DRBG produces values uniformly across the 0..2^qlen-1 range then truncates to qlen bits; acceptance only when 1..q-1 discards out-of-range values, avoiding the modulo bias that would occur if one reduced a larger range by mod q.
• Deterministic seeding from (priv, hash) ensures reproducible nonces and removes entropy-source failures.

Validation against RFC6979 vectors

• Use appendix test vectors (e.g., for secp256k1 / SHA-256) which supply priv, msg hash, and expected k. Compare produced k to expected.
• Also cross-check by signing with produced k and verifying signature against known-good implementations (e.g., openssl, python-ecdsa) and ensure reproducibility across inputs.