Key Establishment and Agreement Questions

Deep understanding of key exchange mechanisms including Diffie-Hellman, ECDH, and modern constructions using KDFs (HKDF). Understanding of parameter negotiation, protection against downgrade attacks, forward secrecy properties. Knowledge of key confirmation mechanisms and post-handshake key updates. Awareness of post-quantum key exchange candidates and transition strategies.

HardTechnical

100 practiced

Compare formal security models used for key exchange: the CK model, the eCK model, and the Universal Composability (UC) framework. Explain which adversary capabilities each model captures (for example ephemeral key reveal, state reveal) and which security properties like PFS and key-compromise impersonation are expressible in each.

Sample Answer

**Brief overview**

Compare three formal frameworks used to prove security of key-exchange: the CK (Canetti–Krawczyk) model, the eCK (extended-CK) model, and the Universal Composability (UC) framework. Focus: adversary capabilities (ephemeral/session-state/long-term corruption) and which properties (PFS, KCI) each can express.

**CK model (basic authenticated DH-style KE)**

- Adversary capabilities modeled: - Session-key reveal (Ask the session oracle for its session key). - Long-term key reveal (reveal party’s long-term secret). - Session-state reveal: typically *not* modeled (the internal ephemeral state of an unfinished session is not exposed). - Partnering and corruptions are treated as in-game oracles.- Security properties expressible: - Mutual authentication and session confidentiality under those oracles. - Perfect Forward Secrecy (PFS): CK can capture PFS when long-term keys are revealed *after* session completion; but because it does not model session-state/ephemeral reveals, some realistic attacks are out of scope.- Limits: - Cannot naturally express adversary who learns ephemeral secrets or session state before completion; so some real-world forward-secrecy and KCI scenarios are not covered.

**eCK model (extended CK)**

- Adversary capabilities modeled: - Session-state / ephemeral-key reveal: modeled explicitly (the adversary may obtain ephemeral private values used in a session). - Long-term key reveal: allowed, including simultaneous revelations of long-term key of one party and ephemeral key of the other (but usually prevents trivially breaking the tested session by revealing everything of the same session). - Session-key reveal, corruptions, and pre-play of ephemeral values are included.- Security properties expressible: - Stronger PFS (often called forward secrecy even when some long-term keys are compromised) — eCK captures many attacks CK misses. - Key-Compromise Impersonation (KCI) resistance can be formulated: eCK can express and prove resistance to KCI-style adversaries because it lets the adversary hold long-term keys but not the honest party’s ephemeral secrets in the tested session.- Limits: - eCK is still non-compositional: proofs are in a stand-alone game; subtle stateful composition issues are not addressed.

**Universal Composability (UC) framework**

- Adversary capabilities modeled: - Very expressive: adaptive corruptions (static or adaptive), state exposure, arbitrary composition with other protocols, and environmental interaction. - Session-state/ephemeral exposure can be modeled explicitly, and UC allows modeling corruptions that reveal all local state. - Requires explicit ideal functionality for KE; security means real protocol emulates that functionality even under arbitrary composition.- Security properties expressible: - PFS and KCI can be expressed if the ideal functionality encodes them; UC gives strong guarantees under composition (PFS under concurrent runs, sub-protocol compromises, etc.). - KCI and fine-grained exposures are definable and preserved under composition.- Trade-offs: - Stronger guarantees require stronger setup assumptions (CRS, PKI, common reference string, signatures with ideal functionalities). Many KE protocols cannot UC-emulate a desirable KE functionality without such setups. - UC proofs are heavier and may force protocol redesign or unrealistic assumptions.

**Comparison summary (practical implications)**

- CK: simpler, widely used; covers many classic proofs but misses ephemeral/state exposure scenarios — limited PFS/KCI expressiveness.- eCK: strengthens CK by allowing ephemeral/session-state reveals and models many realistic attacks; suitable for proving robustness vs. ephemeral/key leakage and KCI-style threats in the stand-alone setting.- UC: strongest guarantee (composability, adaptive state exposure), but often needs setup assumptions and more complex proofs; use when protocol must safely compose in complex systems.

Recommendation for a cryptographer: use eCK for stronger stand-alone assurances about ephemeral and KCI resilience; use UC when composition and concurrent security are required and you're willing to commit to the necessary setup assumptions.

HardTechnical

97 practiced

Given a client advertises supported groups [X25519, secp256r1] and a server responds selecting a group, describe a concrete man-in-the-middle downgrade attack that coerces connections to secp256r1 (assume secp256r1 implementation is known to have an exploitable bug). Explain how the attacker manipulates messages and how to detect and mitigate such attacks in protocol design and implementation.

Sample Answer

**Situation & goal (brief)** An on-path attacker wants both client and server to use secp256r1 (which has a known exploitable bug) even though the client prefers X25519. The attacker manipulates the handshake to coerce secp256r1 so they can exploit the vulnerability.

Attack steps (concrete manipulation)- Intercept ClientHello (supports groups = [X25519, secp256r1], and likely includes a key_share for X25519).- Modify ClientHello: remove X25519 from supported_groups and replace/insert a secp256r1 key_share containing an attacker-generated ephemeral secp256r1 public key. Forward the modified ClientHello to the server.- Server, seeing only secp256r1 advertised and receiving a secp256r1 key_share, selects secp256r1 and replies with ServerHello + ServerKeyShare (server's secp256r1 pubkey).- Attacker completes two parallel handshakes: - With server: use attacker’s secp256r1 key_share from the forged ClientHello so server completes as normal (server thinks client uses secp256r1). - With client: present a forged ServerHello claiming secp256r1 was selected, include an attacker-controlled secp256r1 ServerKeyShare that matches the key the attacker used toward the client.- Because both sides now use secp256r1 endpoints controlled/observed by the attacker, they can trigger the known bug in the server’s secp256r1 implementation (e.g., malformed curve points, small-subgroup abuse, or invalid-cofactor handling) and exploit it during the key agreement or subsequent crypto operations.

Why this works- The attacker removed the safer preferred group from the client’s advertisement and supplied attacker-generated key shares compatible with the coerced group. Neither endpoint authenticates the chosen group or binds the selected key-exchange group to long-term authentication early enough to prevent this manipulation.

Detection signals- Mismatch between client-offered groups and server-selected group as seen by endpoint logs (client believes it offered X25519 but server selected secp256r1).- Unexpected key-share types or key parameters (client sees a secp256r1 ServerKeyShare despite not offering one).- Presence of active modification in network path (packet drop/retransmit patterns, TTL/hop anomalies).- Certificate and signature check failures are unlikely here; instead monitor for group-choice inconsistencies in telemetry and alerts when a weaker/insecure group is negotiated.

Mitigations (protocol design + implementation)- Bind key-exchange group selection into the transcript that the server signs during authentication (ensure the signed ServerHello includes explicit supported_group and key_share identifiers). TLS 1.3 already signs the handshake transcript — implementations must include the selected group and key share in what is covered by the signature/hash.- Client-side enforcement: refuse connections where the negotiated group is not in the original ClientHello or where the server selected a group the client did not advertise. Do strict validation: if you advertised X25519 and sent only X25519 key_share, abort if server selects secp256r1.- Downgrade sentinels: include explicit downgrade indicators in version/group negotiation (like TLS 1.3’s downgrade protection) and verify them.- Server hardening: patch or remove vulnerable secp256r1 code; implement strict point validation (reject malformed points, enforce cofactor handling), constant-time checks, and memory-safety practices.- Policy: prefer safe groups (X25519) and deprecate/remove legacy groups from supported lists; enable telemetry to detect unusual negotiated group patterns.- Application-layer binding: use channel binding/post-handshake application verification of group and key material where possible.

Takeaway (cryptographer view)- Downgrade MITM attacks exploit any gap between what endpoints advertise and what is cryptographically bound/covered by authentication. The fix is twofold: design protocols to cryptographically bind negotiated parameters into authenticated transcript, and ensure implementations validate parameters and drop deprecated, unsafe groups.

HardTechnical

77 practiced

Design a hybrid key-exchange composition that combines an IND-CCA secure post-quantum KEM and ECDH so that the final session key remains secure if at least one component remains secure. Provide a formal composition strategy (how to mix secrets with HKDF or PRF) and explain why naive concatenation or XOR can be unsafe.

Sample Answer

**Approach / goal**

Design a robust hybrid KEX so final session key K is secure if either IND-CCA post‑quantum KEM (KEM) or classical ECDH remains secure (i.e., “either” guarantee). Use proven KDF-based key‑combining rather than raw concatenation/XOR.

**Formal composition (recommended)**

1. Run KEM to get shared secret s_pq (or KEM ciphertext + decaps). 2. Run ECDH to get shared secret s_ec. 3. Use a labeled HKDF extract-then-expand to mix both with context info (roles, transcript, nonces):

text

PRK = HKDF-Extract(salt = H(transcript || role || nonce), IKM = s_pq || s_ec)
K = HKDF-Expand(PRK, info = "HybridKEX v1" || transcript, L)

Alternatively do two-step extract to preserve independence:

text

PRK1 = HKDF-Extract(salt1, IKM = s_pq)
PRK2 = HKDF-Extract(salt2, IKM = s_ec)
PRK = HKDF-Extract(salt3, IKM = PRK1 || PRK2)
K = HKDF-Expand(PRK, info, L)

**Why this is secure / rationale**

- HKDF-Extract behaves like a randomness extractor: if at least one IKM has min-entropy, PRK is pseudorandom. Labeled salts/info bind to transcript to prevent cross-protocol reuse and replay.- Two-stage extract avoids structural collisions and preserves proofs that reducing to one component’s security yields PRK indistinguishable from uniform.

**Why concatenation or XOR can be unsafe**

- Concatenation without extract can leak structure: an adversary that breaks one primitive may learn s_ec and then mount partial‑key confirmation or substring attacks on KEM outputs; extract avoids leaking raw secrets.- XOR assumes both secrets are uniformly random and independent; if one has low entropy or is chosen adversarially (e.g., ECDH with small subgroup), XOR can reveal the other or collapse entropy. HKDF handles entropy asymmetry and adversarially biased inputs.

**Implementation notes / best practices**

- Include transcript, nonces, and role labels in info/salt; enforce IND‑CCA KEM and authenticated ECDH if possible; keep domains separated and versioned.

MediumSystem Design

83 practiced

For a high-throughput TLS server handling millions of short-lived connections daily, compare three server-side strategies: ephemeral-only ECDHE per connection, server-static ECDH (server static key), and ephemeral ECDHE with the server signing the ephemeral key. Analyze CPU cost, PFS guarantees, certificate and signing load, and session-resumption impacts. Recommend a pragmatic approach.

Sample Answer

**Clarify scope & assumptions**- TLS 1.2/1.3 context (recommend TLS 1.3); use modern curves (X25519 / P-256) and ECDSA certs where possible.- “Millions of short-lived connections daily” → many full handshakes unless resumption/PSK used.

**Comparison (CPU, PFS, cert/signing load, session-resumption impact)**

1) Ephemeral-only ECDHE per connection- CPU: Highest. Every connection computes an ECDH (server scalar mult) and verifies client/auth steps. Using X25519 reduces cost but still non-trivial at scale.- PFS: Strong (each connection has fresh ephemeral keys).- Certificate/signing load: Low per-connection if server uses long-term cert only to sign certificate once at handshake start (TLS1.3 signs ephemeral in handshake transcript) — but signature cost occurs per full handshake.- Resumption: Heavy load unless you enable PSK/session tickets; without resumption, cost scales with connections.

2) Server-static ECDH (server static key embedded in certificate or used without fresh ephemeral)- CPU: Lowest per-connection (no ephemeral scalar mult per handshake on server side), small cost for signing if cert already presents static public key.- PFS: None. Compromise of server static key breaks past sessions.- Certificate/signing load: Lower, fewer signing operations during handshake.- Resumption: Works normally; but lack of PFS is unacceptable for many threat models.

3) Ephemeral ECDHE with server signing the ephemeral key (ephemeral key generated per-connection then signed by server's long-term key)- CPU: Moderate–high. Server still does a scalar mult per connection. Additional signing (ECDSA) per handshake increases cost beyond pure ECDHE if signature is separate; in TLS1.3 the server signs handshake transcript (already expected).- PFS: Strong (ephemeral DH provides PFS).- Certificate/signing load: Higher signing throughput; but using ECDSA reduces cost vs RSA. Can offload signing to HSMs or sign servers.- Resumption: Same as ephemeral ECDHE — needs PSK/tickets to avoid repeated full handshakes.

**Operational mitigations**- Use TLS 1.3: reduces round-trips and uses ephemeral keys by default.- Enable session resumption (session tickets / PSKs) and rotate resumption keys frequently (e.g., hourly) to balance PFS-like guarantees for resumed sessions.- Prefer X25519 + ECDSA for lower CPU.- Offload crypto: dedicated TLS termination (hardware TLS, BoringSSL async, kernel TLS) or HSMs for signing.- Batch or cache signatures where protocol allows (avoid re-signing identical material).

**Recommendation (pragmatic for a cryptographer)**- Default: Ephemeral ECDHE per full handshake (TLS 1.3, X25519 + ECDSA) to preserve PFS and modern security.- Scale: Aggressively use session resumption (tickets/PSK) with short-lived ticket keys rotated from a secure key manager so most short-lived connections resume cheaply while still limiting exposure window.- Offload: Use hardware acceleration / TLS terminators or dedicated signing infrastructure (HSMs / signing service) to handle signature throughput.- Avoid server-static ECDH unless regulatory/perf constraints absolutely require it and you accept loss of PFS.

Rationale: Ephemeral ECDHE gives required PFS; resumption + rotated ticket keys minimizes repeated handshake cost; offload/signing choices keep CPU and certificate loads manageable without sacrificing security.

EasyTechnical

82 practiced

In a long-lived connection such as a TLS session, what are post-handshake key updates? Why are they used, and what safety properties must a protocol preserve when performing post-handshake rekey (for example ordering guarantees, rollback prevention, and rate-limiting)?

Sample Answer

**Brief definition**Post-handshake key updates are messages sent after a TLS (or similar) session has been established that refresh the symmetric keys used to encrypt/authenticate application data without performing a full handshake. They derive new keys from existing key material (often via the key schedule) to limit exposure of long-term session keys.

**Why they’re used**- Maintain forward secrecy by rotating keys periodically.- Limit the window of plaintext compromise if symmetric keys leak.- Respond to long-lived session requirements (hours/days) without full re-authentication.- Reduce cryptographic load compared to full handshakes while keeping performance acceptable.

**Safety properties a protocol must preserve**- Ordering guarantees: key update messages must be applied deterministically and unambiguously; sender/receiver must agree on which record numbers use old vs new keys to avoid decryption failures or loss of integrity.- Rollback prevention: include monotonic counters or transcript-derived nonces/MACs so an attacker cannot force parties to accept older keys; binding updates into transcript/state prevents replay of prior key states.- Authenticated transition: updates must be authenticated (e.g., MACed or covered by AEAD) and integrity-protected to stop injection.- Rate-limiting: prevent resource exhaustion or state churn by limiting frequency of updates (e.g., min interval or max number in flight), and require explicit acknowledgements when necessary.- Consistency across endpoints: define failure modes (resync, close) when updates desynchronize to avoid silent downgrade.- Forward/backward secrecy: new keys should be derived so compromise of current keys does not expose past or future keys (use one-way key derivation with fresh nonces).

**Concrete example (TLS 1.3)**TLS 1.3’s KeyUpdate uses a single authenticated message; each side advances its sending key and may request the peer to do likewise. The update is tied to the handshake secrets and transcript, uses a defined update function KDF(traffic_secret) → new_traffic_secret, and limits frequency to avoid amplification attacks.

**Takeaway**Post-handshake rekeying balances security and performance; design must enforce ordered, authenticated, monotonic key evolution with protections against rollback, replay, and DoS.

Unlock Full Question Bank

Get access to hundreds of Key Establishment and Agreement interview questions and detailed answers.

Join thousands of developers preparing for their dream job.