Google Cryptographer (Junior Level) Interview Preparation Guide

Design goals: confusion and diffusion

• Confusion: make relationship between key and ciphertext complex (nonlinear substitution).
• Diffusion: spread plaintext/statistical structure across many ciphertext bits (mixing/linear layers).

How paradigms achieve them

• Feistel network

  • Confusion: nonlinear round function F (S-boxes, modular ops) inside each round.
  • Diffusion: permutation of half-blocks and mixing across rounds; multiple rounds spread bits.
  • Invertibility: whole round is invertible by swapping halves and XORing; F itself need not be invertible.
  • Trade-offs: simpler invertibility allows complex F; inherently sequential (rounds depend on previous), lower parallelism but good for software with small memory; round-function can be complex without requiring bijectivity.
  • Example: DES (classical 16-round Feistel).

• Substitution–Permutation Network (SPN)

  • Confusion: parallel S-box layer of small bijective nonlinear substitutions.
  • Diffusion: linear mixing/permutation layer (P-box, MDS matrices) that is invertible and spreads bits.
  • Invertibility: requires each component (S-boxes and linear layer) to be invertible; whole cipher inverted by applying inverse layers in reverse.
  • Trade-offs: highly parallel (S-boxes independent), excellent for hardware and SIMD; must design invertible S-boxes and linear layers (cost in algebraic design); often fewer sequential dependencies.
  • Example: AES (Rijndael) — invertible S-box + MixColumns linear diffusion.

Practical considerations

• Security vs performance: Feistel can use heavier non-bijective F for security; SPN offers high throughput and hardware friendliness.
• Implementation constraints: block size, key schedule, side-channel resistance affect S-box/linear design.
• Round count and structure chosen to balance confusion+diffusion until avalanche and resistance to cryptanalysis (differential/linear).

Brief description of the vulnerability
An algorithm-confusion flaw occurs when the server trusts the JWT header's "alg" field to choose verification logic. If the server supports both HMAC (HS256, symmetric) and RSA (RS256, asymmetric) and uses the same key storage, an attacker can switch algorithms (e.g., set alg=HS256) and have the server verify an attacker-controlled HMAC using the server's RSA public key as the HMAC secret — effectively forging tokens.

How an attacker exploits it (concrete steps)

• Obtain the server's RSA public key (often public by design).
• Create a JWT with the desired claims.
• Set header "alg":"HS256".
• Sign the token using HMAC-SHA256 with the RSA public key as the secret.
• Present token to the server; if the server uses the 'alg' value to select HMAC and uses the public key as the HMAC secret, verification passes.

How to detect during protocol analysis

• Threat-model endpoints supporting both symmetric and asymmetric algs.
• Test cases: send tokens where alg differs from key type (e.g., sign with HMAC using public key, sign with RSA but claim HS algorithm).
• Static review: search code paths that switch verification by header without validating key type/usage.
• Fuzz inputs: malformed/contradictory headers, "none" algorithm, key-id (kid) mismatches.
• Confirm whether public RSA keys are ever used as HMAC secrets in code or config.

Fixes at server implementation level

• Never trust the JWT "alg" field to choose verification. Instead:
  • Maintain a mapping of accepted algorithm → key type and key entry (e.g., kid→(algorithm, key material, usage)).
  • Look up the key (by configured policy or kid) and enforce that the key's algorithm/type matches the token's expected algorithm. Reject tokens where they mismatch.
  • Prefer explicit server-side policy: only accept RS256 for tokens issued by asymmetric issuers and only HS256 for symmetric issuers; do not allow either on the same endpoint.
  • Reject "none" algorithm.
  • Use well-maintained crypto libraries and call the library verification function that takes the expected alg as a parameter (do not allow the library to auto-select alg based on header).
  • Separate key stores: never store symmetric secrets and asymmetric public keys in the same key slot or reuse public keys as HMAC secrets.

Additional best practices

• Require and validate "kid", map it to a key with enforced usage flags (sign/verify, algorithm).
• Perform automated regression tests that attempt algorithm-swapping attacks.
• Log and alert on algorithm mismatch attempts.

High-level point: Hashing multiple entropy sources is fine as an “entropy combiner” if you treat hashing as extraction (remove bias, collisions) and you have reliable, independent, min-entropy estimates. For a production RNG with long-lived state, prefer a standardized DRBG (e.g., HMAC-DRBG / CTR-DRBG / Hash-DRBG) because it provides proven extract-then-expand primitives, internal state management, reseeding logic, and forward/backward security guarantees.

Why simple hashing can be adequate

• Use-case: one-shot seed accumulation (e.g., boot seed) where you collect many independent sources and immediately seed a secure PRF-based generator.
• Requirements: each source has quantified min-entropy; adversary cannot control > allowed threshold; you apply a proper extractor (HMAC or HKDF-style keyed extract) rather than raw hash concatenation.
• Example: seed = HKDF-Extract(salt, concat(samples)) then key the PRF. HKDF provides proven entropy extraction even when some inputs are weak.

When to use a standardized DRBG

• Long-lived generator, repeated outputs, networked devices, or where state compromise is a real risk.
• DRBGs specify internal state update rules, reseed intervals, prediction resistance modes, and limits on output-per-seed (e.g., NIST SP800‑90A constraints).
• HMAC-DRBG gives a keyed PRF with internal K/V state and standardized reseed_counter semantics—this yields established forward secrecy on rekey and bounds on prediction after partial compromise.

Designing reseed policy and procedures

• Entropy thresholds: require reseed when accumulated fresh entropy ≥ security_strength bits (e.g., 128/256).
• Event triggers: periodic (time-based), request-count-based, health-test failure, or external event (network compromise).
• Parameters: follow standards—e.g., limit output-per-reseed and reseed intervals (NIST suggests a reseed_counter limit like 2^48 for DRBGs; choose conservative values for embedded or high-risk systems).
• Practical: reseed if either T seconds elapsed OR R outputs produced OR new hardware event; require at least X bits of estimated entropy from independent sources before accepting reseed.

State-compromise recovery

• Detection: monitor entropy source health tests, seed-usage anomalies, and external alerts.
• Immediate steps on suspected compromise:
  • Stop using existing generator output.
  • Gather fresh entropy from multiple independent sources; require conservative min-entropy (exceed security strength).
  • Reinitialize using an extractor (HKDF/HMAC) with fresh randomness and a new unique salt/nonce.
  • If possible, perform forward-recovery: rotate keys derived from the DRBG only after reseeding with entropy that adversary cannot have seen.
• Additional mitigations:
  • Use forward-secure constructions (periodic rekey) so past outputs remain safe after compromise.
  • Keep an immutable audit log of reseed events and entropy estimates.
  • Zeroize internal state on compromise and enforce secure erasure.

Practical recommendations for a cryptographer

• Prefer extract-then-expand (HMAC/HKDF) over raw hash concatenation.
• Use a standardized DRBG for long-lived use and follow NIST/ISO guidance for limits and reseed policies; tune reseed counters conservatively for your threat model.
• Always perform health tests, conservative entropy estimation, and require entropy from diverse, independent sources for reseed.
• Define and document an incident response (stop, gather >security_strength bits, reinit, rotate dependent keys, log).

This approach balances theoretical soundness (provable extraction and PRF security) with operational resilience (reseed, detection, recovery).

Situation assessment — how to detect scope

• Pull logs with (timestamp, key-id, IV/nonce, counter, ciphertext, tag, client/session id). Search for duplicate IV/nonce values tied to the same key-id.
• From ciphertexts: group messages by (key-id, IV). Any group with size >1 is reuse.
• Validate by computing C1 xor C2 = P1 xor P2 (if any plaintext known, you can recover others). Use known-plaintexts or protocol headers to confirm reuse and estimate bits of keystream recovered.
• Check authentication results: reused IVs may still verify; check for unexpected successful forgeries or unusual traffic patterns (replays).

Immediate mitigation (first 0–6 hours)

• Stop the offending encryption process or flip it to safe fail: disable issuance of that key or block messages using the reused IVs.
• Rotate the symmetric key immediately for all services that used the key. Mark the old key compromised.
• Reject or quarantine incoming messages encrypted under the compromised key/IV pairs. Increase monitoring and alerting for reuse.
• If practical, switch to an alternate vetted key-management path and require unique nonces (e.g., 96-bit counter or deterministic per-message IV).

Remediation & forensics (24 hours – weeks)

• Preserve full disk/log images and export all crypto material and telemetry for forensic analysis. Record timelines: when reuse started, which code/deployment introduced it.
• Quantify affected messages and sensitivity (PII, credentials). Attempt keystream recovery for reused-IV groups: if any plaintext portions are known (headers, protocol constants), derive keystream and recover other plaintext bytes. Log recovered data and scope of exposure.
• Conduct root-cause: inspect IV generation code (CSPRNG misuse, truncated counters, shared counters across processes, library misuse). Patch code and add unit tests ensuring nonce uniqueness.
• Full key rotation: generate fresh keys with secure KDFs, revoke old keys, and re-encrypt stored data as required. Publish signed statements of key rotation internally and to stakeholders.
• Update protocol: mandate 96-bit unique nonces with either monotonic counters per key or AEAD constructions with non-repeating IV (or switch to schemes that avoid IV reuse risks, e.g., AES-SIV for misuse resistance).
• Improve telemetry: log IV uniqueness, rate-limit reuse, add alerts when any IV repeats for a key, and add periodic audit jobs.

Recovering trust

• Produce a transparent incident report: scope, technical root cause, data exposed, remediation actions, and mitigations to prevent recurrence.
• Offer remediation for affected customers (forced credential resets, re-encryption, monitoring).
• Run independent cryptographic review and publish results.
• Harden CI/CD: require crypto regression tests, static analysis for RNG/nonce usage, and pair code review for crypto changes.

Why: AES-GCM nonce reuse leaks keystream and enables plaintext recovery and tag forgeries; immediate key revocation and forensic keystream recovery limit damage and help restore system integrity.

Brief definition

A chosen‑prefix collision (CPC) is where an attacker picks two arbitrary distinct prefixes P and P' and then finds suffixes S and S' so that H(P || S) = H(P' || S'). Unlike identical‑prefix collisions (where the two messages share a common prefix), CPC lets the attacker control meaningful differing headers—critical for forging structured objects like X.509 certificates.

How it became feasible against MD5

• MD5 has differential weaknesses that make building near‑collisions for different prefixes tractable. Techniques combined:
  • Differential cryptanalysis to derive controllable bit-differences through compression function steps.
  • Message modification and multi-block construction to fix internal state differences across blocks.
  • Practical tooling (Stevens et al.) that automated finding suffixes with complexity far below brute force (far less than 2^128).
• These reduced CPC cost from infeasible to practical on commodity clusters for MD5.

X.509 forged certs — attack outline

• Attacker crafts benign intermediate CA cert (prefix P) and a target victim cert template (prefix P').
• Using MD5 CPC they produce suffixes S, S' yielding same MD5 hash.
• CA signs the benign cert: Sign( H(P || S) ) = Sign( H(P' || S') ). Because hashes match, the signature validates the malicious cert too, creating a trusted CA or rogue end‑entity cert (Flame/rogue CA incidents).

Mitigations: algorithm + policy

• Move to collision‑resistant hashes (SHA‑256+, SHA‑3); MD5 and SHA‑1 deprecated.
• CA/B Forum policies and browser vendors banned MD5/SHA‑1 for cert signatures, enforced minimum hash/key sizes, blocked cross‑signing of legacy algs, and added CT/strict revocation checks.
• Protocol hardening: include more data in signed scope (extensions, serials), and avoid weak parsing that permits attacker‑controlled alignment.

Remaining practical risks

• Legacy systems still accepting MD5/SHA‑1 or allowing RSA signatures over attacker‑controlled hash inputs remain vulnerable.
• Chosen‑prefix attacks have been shown practical for weaker hashes (SHA‑1 chosen‑prefix cost dropped with large resources). For modern hashes like SHA‑256/512 there are no known practical CPCs today; theoretical or quantum risks remain long‑term.
• Operational pitfalls (mixed‑algorithm chains, poor input canonicalization, or hardware/firmware using legacy libs) are the main residual risk. Vigilant policy, crypto agility, and correct implementation remain essential.

Direct answer

Start from the decision the ritual has to produce, not the calendar slot. Invite only the people who can actually make or unblock that decision, not everyone with an interest in the topic. Set the cadence to match how fast the underlying work changes, and instrument the ritual itself so you can tell whether it is producing decisions or just producing a meeting.

Structured elaboration

1. Name the single output first. Before picking attendees or a cadence, write down the one decision or artifact the ritual exists to produce (for example, "which cross-team dependencies get prioritized this cycle"). If you cannot name it, you are designing a status meeting, not a working ritual.
2. Minimum viable roster. Invite decision-owners, not stakeholders who only want visibility. A rule of thumb: if someone in the room has to say "let me check with my team" before committing to anything, they are a proxy, not an owner, and the room is one person too big.
3. Cadence tied to decision half-life. Match the frequency to how fast the thing being decided actually changes, not to habit. Too frequent and there is nothing new to decide between sessions; too infrequent and blockers age past the point where the ritual could have caught them early.
4. Session shape. Require light pre-work (so room time is spent deciding, not getting everyone up to speed), time-box the agenda to the decision at hand, and keep a running decision log so the group is not re-litigating the same question every time.
5. How you would know it is working (leading indicators, not attendance):

Worked example

Say the ritual is a recurring dependency review for a platform initiative touching four delivery teams. The roster is the four team leads plus the program owner as facilitator, five to six people, not the fifteen who are merely affected. The teams plan in two-week sprints, so a dependency raised today needs to be resolved before the next sprint's planning starts or it blocks that team. That reasoning sets the floor: the review has to run at least once per sprint, so biweekly, thirty minutes, is the minimum cadence that keeps blockers from aging past one planning cycle. A weekly cadence would mean showing up with nothing new most weeks; a monthly one would let a blocker sit for up to two sprints before anyone with authority to fix it even hears about it.

Trade-offs & pitfalls

• The most common wrong turn is defaulting the invite list to "everyone affected." The ritual becomes a broadcast, decision-owners tune out because nothing gets decided with fifteen people in the room, and the ritual quietly becomes theater.
• Choosing cadence by convention ("let's do it weekly like standup") instead of the decision's actual refresh rate produces either a hollow meeting or a slow one, and both erode trust in the ritual over time.
• Junior candidates describe running the meeting well. Senior candidates describe designing the meeting so it can be evaluated and retired: a built-in check for whether it is still adding value, and a plan for what replaces it if it is not.
• Skipping the decision log is a quiet failure mode: without a record of what was already decided and why, the group re-opens the same debate every session and the ritual's real cost shows up as fatigue, not as an obvious complaint.

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.

Situation (brief):
While auditing a TLS stack used in our product, I found a timing side-channel in the RSA-PSS verification routine that leaked partial key-dependent information during signature checks.

Discovery method & timeline:

• Week 0: Static review + micro-benchmarks flagged variable-time behavior in modular exponentiation path.
• Week 1: Differential timing experiments across 10k signatures confirmed a measurable correlation with key bits.

Verification steps:

• Reproduced locally with controlled inputs and high-resolution timers.
• Built a statistical model (Pearson correlation + t-tests) showing timing variance correlated to Hamming weight of intermediate values (p < 0.001).
• Created a proof-of-concept extractor that reduced entropy of private key candidates.

Responsible disclosure & coordination:

• Day 10: Notified product security and CISO with technical write-up and PoC.
• Coordinated with upstream library maintainers and agreed on a 90-day embargo for public disclosure.
• Filed a coordinated CVE request and kept stakeholders informed weekly.

Mitigation & implementation:

• Implemented constant-time modular exponentiation and hardened signature verification by removing conditional branches dependent on secret data.
• Added exhaustive unit tests, timing regression tests, and CI checks that assert bounded timing variance.
• Released patched binaries and rolled hotfixes to production within 4 weeks of disclosure.

Impact metrics:

• Pre-fix timing leakage: correlation coefficient 0.42; post-fix: 0.01 (near noise).
• Proof-of-concept key-entropy reduction: from 160 bits to 145 bits pre-fix; after fix remained 160 bits.
• CVSS lowered from 9.1 to 2.1 after patching and mitigations.
• No active exploits observed in telemetry post-deployment; endpoint detections for related anomalous probes dropped 95%.

Takeaway:
The issue underscored the need for constant-time implementations and automated timing checks in CI; I helped integrate these safeguards into our dev lifecycle.

Approach (brief)
Validate JWTs against a keyset that may contain multiple public-key versions. Enforce an algorithm whitelist; map kid→key metadata (pubkey, alg, version, status). Return explicit error codes.

Data structures

• key_store: Dict[kid -> { "pub": PEM, "alg": "RS256", "status": "current|rotated|deprecated", "expires_at": ts }]
• ALLOWED_ALGS = {"RS256","ES256"}
• DEPRECATED_ALGS = {"HS256","none"}

Flow / Pseudocode

import time
from jwt import decode as jwt_decode, InvalidSignatureError, ExpiredSignatureError, InvalidAlgorithmError

def verify_jwt(token, key_store, allowed_algs=ALLOWED_ALGS):
    # 1. parse header without verifying to get kid, alg
    header = jwt_decode(token, options={"verify_signature": False, "verify_exp": False})
    kid = header.get("kid")
    alg = header.get("alg")

    if alg in DEPRECATED_ALGS or alg not in allowed_algs:
        return {"ok": False, "error": "deprecated-alg" if alg in DEPRECATED_ALGS else "unsupported-alg"}

    key_meta = key_store.get(kid)
    if not key_meta:
        return {"ok": False, "error": "unknown-kid"}

    if key_meta.get("status") == "deprecated":
        return {"ok": False, "error": "unknown-kid"}  # or explicit "deprecated-key"

    pub = key_meta["pub"]
    try:
        payload = jwt_decode(token, key=pub, algorithms=[alg], options={"require": ["exp"]})
        return {"ok": True, "payload": payload}
    except ExpiredSignatureError:
        return {"ok": False, "error": "expired"}
    except InvalidSignatureError:
        return {"ok": False, "error": "invalid-signature"}
    except InvalidAlgorithmError:
        return {"ok": False, "error": "deprecated-alg"}

Caching strategy

• Use an in-memory LRU cache of key_store with TTL per key (expires_at). Refresh from origin (JWKS endpoint) asynchronously when TTL near expiry or on cache-miss.
• Keep both current and a small window of rotated keys (e.g., last N versions or N hours) marked "rotated" for verification but not issuance.
• On key rotation, publish new jwks; mark old as "rotated" then "deprecated" after grace period.

Notes (cryptographer lens)

• Prefer asymmetric (RS/ECDSA) with explicit alg identifiers; avoid algorithm negotiation.
• Ensure constant-time signature verification provided by vetted library; validate key parameters (curve, modulus size) when loading keys.

Requirements & goals

• Protect private keys for TLS client auth and server signing, ensure availability, non-repudiation, auditable access, rapid compromise recovery, minimal downtime.

High-level choices

• Use FIPS 140-2/3 Level 3 HSMs (cloud-managed HSM cluster or on-prem HSM appliances) for primary key material. For multi-cloud ops, use Cloud KMS backed by HSMs (e.g., Cloud HSM/AWS KMS with custom key store) to get durability and key ceremony compliance.
• Keep offline encrypted backups of key material only when HSM export is permitted — prefer non-exportable keys and use wrapping keys / split knowledge (Shamir) for any backups.

Key lifecycle & rotation cadence

• Keys have explicit states: Active → Standby (dual-signing) → Retire → Destroy.
• Server signing keys: rotate every 90 days (or earlier if policy/regulator requires); TLS client-auth keys: rotate annually or on compromise.
• Use overlapping validity: provision new key, issue certs, run dual-signature period (e.g., 48–72 hours) to ensure in-flight sessions validate.

Zero-downtime rotation

• Generate new keypair inside HSM/KMS; publish new certificate while keeping old key active for existing sessions.
• For server signing, support dual-signing: sign with both old and new during transition; clients accept either signature using cert chain checks.
• Use rolling deployment across load-balanced servers; ensure old key remains available until all sessions using it expire.

Access controls & separation of duties

• RBAC: least privilege; distinct roles — Crypto Ops (can request rotation), Key Custodians (can approve export/sharing), Auditors (read-only).
• Use multi-party approval (M-of-N) for sensitive operations (export, emergency key recovery).
• HSM policies enforce key usage flags (sign-only, no-export) and require PINs or quorum.

Audit & monitoring

• Immutable audit logs for all key ops (create, sign, export attempt, rotate, destroy) shipped to SIEM with tamper-evident storage.
• Alerts on anomalous patterns (unexpected exports, failed auths, unusual frequency of sign ops).

Backups & offline storage

• If export required: wrap private key with a root-wrapping key split among custodians; store encrypted shares in geographically separated secure vaults (air-gapped or hardware-secured).
• Periodically test recovery with blinding ceremony.

Compromise & emergency procedures

• Immediate: revoke certificates, mark keys as compromised in KMS/HSM, rotate to new keys generated in HSM, publish CRLs/OCSP stapling and push to clients.
• For client-auth: revoke client certs and require re-issuance; for server-signing: re-sign recently issued artifacts where possible.
• Run post-mortem, rotate all related keys, update audit, notify stakeholders per incident response SLA.

Trade-offs / rationale

• HSMs provide cryptographic boundary and non-exportability; cloud KMS gives scalability and operational ease — choose both where compliance and scale demand. Split backups and M-of-N minimize insider risk while enabling recovery. Dual-signing and rolling deployments enable near zero downtime.