Asymmetric Encryption and Key Exchange Questions
The construction and mathematics-adjacent mechanics of public-key (asymmetric) cryptography: how RSA, Diffie-Hellman, and elliptic-curve schemes actually work, including the group law and point-arithmetic formulas, scalar-multiplication algorithms (double-and-add, Montgomery ladder, windowed methods, GLV, multi-scalar batching), curve models and coordinate systems, and the hardness assumptions (integer factorization, discrete log, ECDLP) each scheme rests on. Covers key-establishment and authenticated key-exchange protocol design: forward-secrecy mechanics, key confirmation, downgrade protection, key-derivation and context binding, group and multi-party key agreement, and hybrid classical/post-quantum key-exchange composition. Also covers implementation-level attacks against these primitives and their mitigations: timing and side-channel leakage in modular exponentiation and scalar multiplication, invalid-curve and small-subgroup attacks, fault attacks, and padding-oracle attacks. Distinct from selecting, deploying, and operating these primitives in production: PKI certificate lifecycle, CA hierarchy, revocation, and key storage and rotation belong to applied cryptography and key management.
Define a protocol downgrade attack in the context of key exchange. Provide an example where an active attacker forces negotiation to an insecure parameter set, and explain at least two countermeasures protocols use to prevent downgrade (for example transcript binding and explicit downgrade sentinels).
Sample Answer
Direct answer
A protocol downgrade attack is when an active, on-path attacker (one who can intercept and modify traffic, not just observe it, often called a man-in-the-middle or MITM attacker) tampers with the negotiation phase of a key-exchange protocol so the two honest endpoints end up agreeing on a weaker algorithm or parameter set than either would have chosen on its own, one the attacker can then break.
Structured elaboration
Most key-exchange protocols start with a negotiation step: each side advertises what it supports (cipher suites, Diffie-Hellman group sizes, protocol versions), and the two sides pick the strongest option they have in common. If that advertisement travels in the clear and is not cryptographically tied to what the endpoints end up actually confirming later, an attacker can rewrite it in transit, stripping out the strong options, and neither side has any way to detect that the list they received was not the list that was sent.
Two countermeasures close this gap:
- Transcript binding. Fold a hash or MAC (message authentication code) over the entire negotiation transcript, every option each side advertised and every choice that was made, into the key derivation itself, typically via HKDF (a hash-based key derivation function) once a shared secret exists. Any tampering with the transcript changes this binding value, so the final key-confirmation step (see below) fails and the connection aborts instead of silently completing on weak parameters.
- Explicit downgrade sentinels. Have an updated endpoint signal, inside an already-authenticated part of the handshake, that it is capable of a stronger protocol version even though it ended up negotiating a weaker one. Transport Layer Security (TLS, the protocol behind HTTPS) 1.3 does exactly this: a TLS-1.3-capable server that ends up negotiating TLS 1.2 or earlier overwrites the last several bytes of its random nonce with a fixed, recognizable pattern. An updated client checks for that pattern and aborts if it sees it on an unexpected downgrade, since a genuine TLS-1.2-only server would never produce that specific bit pattern by chance.
Worked example
Logjam (2015) is a real instance of this attack class: some TLS servers still offered "export-grade" Diffie-Hellman cipher suites using a weak, widely-reused 512-bit prime, a relic of 1990s US export controls. An active attacker could rewrite a ClientHello to strip out all the strong cipher suites and leave only the export-grade one, forcing both sides into a Diffie-Hellman exchange the attacker could break in real time using a precomputed table for that one popular 512-bit prime, then read or modify the "secure" session that followed.
Trade-offs and pitfalls
Downgrade protection only helps parties that have actually been updated to check for it; a genuinely old client talking to a genuinely old server has nothing to detect. Transcript binding must cover the negotiation before any key is derived from it, binding a key to a transcript that was already used to derive that same key is circular and protects nothing. And protection has to work in both directions, an algorithm downgrade within one protocol version and an outright protocol-version downgrade are the same threat model and need the same defenses, it is easy to only think about one of them.
Explain TLS 1.3 key schedule at a high level: how early secrets, handshake secrets and application secrets are derived using HKDF. Describe how these derivations provide forward secrecy and support post-handshake key updates. Indicate where client and server authentication and key confirmation occur.
Sample Answer
Direct answer
Transport Layer Security (TLS, the protocol behind HTTPS) 1.3 derives three secrets in a strict chain, early, handshake, and application, using HKDF (HMAC-based Key Derivation Function, a two-step construction for turning input keying material into strong, purpose-specific keys), so that every traffic key is cryptographically tied both to the ephemeral Diffie-Hellman exchange that produced forward secrecy and to the exact transcript of everything negotiated.
Structured elaboration
HKDF has two primitives:
PRK=HKDF-Extract(salt,IKM) OKM=HKDF-Expand(PRK,info,L)Extract turns possibly-weak input keying material (IKM) into a strong, uniform pseudorandom key (PRK) via an HMAC (hash-based message authentication code) call. Expand stretches that PRK into output keying material (OKM) of any needed length L, and TLS 1.3 wraps Expand in an "Expand-Label" step that bakes a label string and a transcript hash into the info field, so no two derived secrets, even ones derived from the same PRK, can ever collide in purpose.
The three-secret chain:
early_secret, derived from a pre-shared key (PSK) if one is being used for resumption, or from an all-zero input if not.handshake_secret, derived by extracting again, this time mixing in the ephemeral (elliptic-curve) Diffie-Hellman shared secret from the current handshake.master_secretand the per-direction application traffic secrets, derived from the handshake secret once no more external input remains.
Where authentication and key confirmation happen. The Certificate and CertificateVerify messages authenticate identity, CertificateVerify is a signature over the transcript using the sender's long-term private key, proving they hold that identity's key. The Finished messages provide key confirmation: each side computes an HMAC over the transcript using a key derived from its own handshake traffic secret, and only a party that actually derived the matching secret can produce a Finished value the other side will accept.
Forward secrecy. Because handshake_secret's only session-specific input is the ephemeral Diffie-Hellman shared secret, which is discarded after the handshake, and every later secret (including the application traffic secrets) is derived from handshake_secret, compromising the server's long-term signing key later never lets anyone recompute that ephemeral shared secret, and so never lets anyone recompute any traffic key from a recorded session.
Post-handshake key update. A KeyUpdate message derives a fresh application traffic secret from the current one, using the same one-way HKDF-Expand-Label mechanism, never from any long-term key. Old traffic keys cannot be recovered from new ones either, since HKDF-Expand is not invertible, extending forward secrecy within a single long-lived connection.
Worked example
A simplified, illustrative derivation using Python's standard hmac/hashlib (real TLS 1.3 additionally chains through an empty-transcript "Derive-Secret" step between stages, omitted here for clarity, but the extract/expand mechanics shown are exactly what TLS 1.3 uses):
import hmac, hashlib
def hkdf_extract(salt, ikm):
return hmac.new(salt, ikm, hashlib.sha256).digest()
def hkdf_expand(prk, info, length):
t, okm = b"", b""
for i in range(1, (length + 31) // 32 + 1):
t = hmac.new(prk, t + info + bytes([i]), hashlib.sha256).digest()
okm += t
return okm[:length]
def hkdf_expand_label(secret, label, context, length):
full_label = b"tls13 " + label
info = length.to_bytes(2, "big") + bytes([len(full_label)]) + full_label + bytes([len(context)]) + context
return hkdf_expand(secret, info, length)
zero32 = bytes(32)
early_secret = hkdf_extract(zero32, zero32) # no PSK
dh_shared_secret = bytes.fromhex("1a" * 32) # pinned stand-in for a real ECDHE output
derived_early = hkdf_expand_label(early_secret, b"derived", hashlib.sha256(b"").digest(), 32)
handshake_secret = hkdf_extract(derived_early, dh_shared_secret)
transcript_hash = hashlib.sha256(b"pinned-illustrative-transcript").digest()
client_hs_traffic_secret = hkdf_expand_label(handshake_secret, b"c hs traffic", transcript_hash, 32)
finished_key = hkdf_expand_label(client_hs_traffic_secret, b"finished", b"", 32)
print(f"early_secret = {early_secret.hex()}")
print(f"handshake_secret = {handshake_secret.hex()}")
print(f"client_hs_traffic_secret = {client_hs_traffic_secret.hex()}")
print(f"finished_key = {finished_key.hex()}")
Running this prints:
early_secret = 33ad0a1c607ec03b09e6cd9893680ce210adf300aa1f2660e1b22e10f170f92a
handshake_secret = 9e27a2878ad0e213b115857e388f28fb766a0a7958cd02659db09c9afca82931
client_hs_traffic_secret = 500ef09a2501ddb295cc76ea859417d926d90301f447c199922177c17d96c67c
finished_key = 553fcca56447e3407f615e7e1cb45dfb04a6dbd441d4333c8e4c094c95d3f4a2
Changing the pinned dh_shared_secret or transcript_hash above changes every downstream value deterministically, exactly the transcript-binding property the design relies on.
Trade-offs and pitfalls
Reusing the same Expand-Label label string across two logically different derivation contexts breaks the domain separation the whole scheme depends on, effectively colliding two keys that were supposed to be independent. Skipping key confirmation (Finished) and trusting the Diffie-Hellman exchange alone leaves the handshake open to the kind of active tampering and reflection issues key confirmation exists to close. And forgetting to rotate resumption secrets over time re-extends the exposure window a single long-term compromise creates, resumption is convenient but it is still a chain rooted, eventually, in something that doesn't change every connection.
Explain why including explicit context and protocol identifiers (for example transcript hashes, ciphersuite IDs, or role labels) in KDF inputs is critical. Provide an example where missing context allowed two different protocols to derive the same symmetric key from different inputs and caused cross-protocol key reuse vulnerability.
Sample Answer
Direct answer
A KDF (key-derivation function, e.g. HKDF, built on HMAC, hash-based message authentication code) is a deterministic function of its inputs: the same input keying material with the same parameters always produces the same output key. If the ONLY input is a shared secret, and two different protocols happen to arrive at the same shared secret (the same two parties running the same underlying Diffie-Hellman, say), they derive the IDENTICAL symmetric key, even though the protocols intended those keys to be completely unrelated. Including explicit context (a transcript hash, a ciphersuite identifier, a role label) in the KDF's info field breaks that collision by construction, because it makes the derived key depend on WHICH protocol and WHICH exact handshake produced it, not just on the raw shared secret.
Structured elaboration
Why the collision happens at all. Two protocols, ProtoA and ProtoB, can end up performing Diffie-Hellman between the same two parties using the same long-term or ephemeral keys, particularly if a key is reused across protocols (a design smell in its own right, but a real one). If both then call something like
PRK=HKDF-Extract(salt,S),K=HKDF-Expand(PRK,info,L)with an empty or missing info field, K comes out byte-for-byte identical for both protocols, purely because HKDF is deterministic and the inputs happened to match.
Why this is exploitable, not just an odd coincidence. If ProtoA is a weaker or differently-audited protocol than ProtoB, an attacker who compromises a key in ProtoA's context can directly reuse that SAME key material to decrypt or impersonate within ProtoB, this is cross-protocol key confusion, and it breaks the key-separation assumption that lets each protocol be analyzed and trusted independently. It also silently invalidates security PROOFS: most formal security arguments for a KDF-based protocol implicitly assume the derived key is unique to that specific protocol run, an assumption a missing context field violates without any code obviously being "wrong" in isolation.
The fix. Bind the derivation to the exact context it should be scoped to: a transcript hash (a hash over every message exchanged so far, so the key is bound to this SPECIFIC handshake, not just this pair of parties), a ciphersuite or protocol identifier (so ProtoA and ProtoB, even given an identical shared secret, derive provably different info inputs), and a role label where the two sides play asymmetric roles (so, for instance, a client-to-server key and server-to-client key derived from the same shared secret do not collide with each other either).
Worked example
# KDF context binding: identical shared secret plus no protocol context collides across
# protocols; adding a transcript-bound info label separates the derived keys.
import hashlib, hmac
def hkdf_extract(salt, ikm):
return hmac.new(salt, ikm, hashlib.sha256).digest()
def hkdf_expand(prk, info, length):
t, okm = b"", b""
counter = 1
while len(okm) < length:
t = hmac.new(prk, t + info + bytes([counter]), hashlib.sha256).digest()
okm += t
counter += 1
return okm[:length]
if __name__ == "__main__":
shared_secret = bytes.fromhex("2f6a91e0c8b3d4517aa9902ccf1e5b7a") # same ECDH output, two protocols
prk = hkdf_extract(b"", shared_secret)
key_protoA_no_context = hkdf_expand(prk, b"", 16)
key_protoB_no_context = hkdf_expand(prk, b"", 16)
print("no context binding:")
print(f" ProtoA key = {key_protoA_no_context.hex()}")
print(f" ProtoB key = {key_protoB_no_context.hex()}")
print(f" keys identical: {key_protoA_no_context == key_protoB_no_context}")
transcript = hashlib.sha256(b"pinned-illustrative-transcript").digest()
info_A = b"ProtoA|ciphersuite=1|" + transcript
info_B = b"ProtoB|ciphersuite=1|" + transcript
key_protoA_bound = hkdf_expand(prk, info_A, 16)
key_protoB_bound = hkdf_expand(prk, info_B, 16)
print("with context binding:")
print(f" ProtoA key = {key_protoA_bound.hex()}")
print(f" ProtoB key = {key_protoB_bound.hex()}")
print(f" keys identical: {key_protoA_bound == key_protoB_bound}")
Output:
no context binding:
ProtoA key = 104af198cb756f41f744d4de39c9b253
ProtoB key = 104af198cb756f41f744d4de39c9b253
keys identical: True
with context binding:
ProtoA key = 5bf3e4b5046cfd622ef923433283add2
ProtoB key = 74a51ddcc89f079fb385cc2affe88d19
keys identical: False
Trade-offs and pitfalls
The fix costs essentially nothing computationally, info is just additional input bytes hashed alongside the rest, so there is no real trade-off to weigh against doing it; the pitfall is purely one of DISCIPLINE, a protocol designer who correctly implements HKDF but treats the info field as optional metadata rather than a security-critical binding. A related, subtler pitfall: including a WEAK or non-unique context (say, a fixed string literal shared by every deployment of the protocol rather than something that varies per handshake, like a real transcript hash) provides only PARTIAL protection, it separates protocol A from protocol B, but does nothing to bind the key to this specific SESSION if the transcript itself is not included, so two runs of the same protocol between the same parties could still collide if the context omits per-session randomness.
Design a lightweight downgrade-protection mechanism for a negotiation protocol where endpoints advertise supported key-exchange algorithms and parameters. The mechanism must remain compatible with middleboxes that may not understand new algorithms. Explain how to cryptographically bind advertisements to the final negotiated choice without breaking proxies that need to rewrite or inspect the handshake.
Sample Answer
Direct answer
Keep the algorithm advertisement itself in cleartext, so middleboxes can still read or pass it unmodified, but attach a small cryptographic commitment to it, then fold that same commitment into the authenticated key-confirmation step the protocol already needs. Any silent tampering with the advertisement changes the commitment, which then makes the final confirmation fail, so the endpoints abort instead of silently completing on downgraded parameters, while a passive middlebox that changes nothing sees no difference at all.
Structured elaboration
Goals and constraints. Detect covert downgrade by an active attacker, stay readable to middleboxes that only inspect or forward traffic, and don't assume every middlebox understands new algorithms.
Design.
- Each endpoint advertises its cleartext list L of supported algorithms plus a fresh nonce N, exactly as today, so nothing about the visible wire format changes.
- Alongside L, the endpoint also sends a short, fixed-size commitment C=H("AD"∥L∥N), cheap to compute, opaque to anything inspecting it, and small regardless of how long the algorithm list is.
- Once the handshake produces a shared key, the existing key-confirmation message (a message authentication code, MAC, over the transcript, which the protocol needs anyway to prove both sides derived the same key) is extended to also cover C and the algorithm that was actually negotiated: Finished=HMAC(key,transcript∥C∥chosen_algorithm) (HMAC is a specific, standard way of building a MAC out of a hash function).
- Each side recomputes what C should have been from the list it actually received, and checks it against the one that was sent; a mismatch, or a Finished value that doesn't verify, means either the list or the final choice was tampered with somewhere on the path.
Why this works. An attacker who strips strong options from L before forwarding it produces a different commitment C than the one the honest endpoint originally sent, and since the attacker doesn't hold the eventual session key, they cannot forge a matching Finished value to cover up the discrepancy. A passive middlebox that only reads L and C without modifying either is completely unaffected, nothing about this design requires it to understand the new mechanism.
Worked example
import hashlib
L = b"X25519,P-256,FFDHE-2048" # cleartext advertisement of supported key-exchange algorithms
N = bytes.fromhex("00" * 16) # a fresh nonce
C = hashlib.sha256(b"AD" + L + N).digest()
print("advertised list L =", L)
print("commitment C = SHA256(\'AD\'||L||N) =", C.hex())
L_tampered = b"FFDHE-2048" # an attacker strips the strong options before forwarding
C_tampered = hashlib.sha256(b"AD" + L_tampered + N).digest()
print("commitment recomputed over the tampered list =", C_tampered.hex())
print("commitments match:", C == C_tampered)
Running this prints:
advertised list L = b'X25519,P-256,FFDHE-2048'
commitment C = SHA256('AD'||L||N) = 48046b73813a2040ddaba2f298cac2740effee0d2828a0cbffb7c0efb02f1f9a
commitment recomputed over the tampered list = afcf4acec97972e64665a53ca5cdd29eaf32d4c1df2a9f0aabc9f89aae097017
commitments match: False
Stripping X25519 and P-256 out of the advertised list produces a completely different commitment than the original. An attacker who does this in transit, then tries to let the handshake continue as if nothing changed, cannot make the receiving endpoint's recomputed commitment match what was actually sent, and the mismatch is exactly what causes the connection to abort rather than silently negotiate the weakened FFDHE-2048 option.
Trade-offs and pitfalls
The commitment adds only a fixed-size hash to the initial message, it doesn't grow with the length of the algorithm list, so it stays genuinely lightweight even for endpoints advertising many options. The scheme detects downgrade after the fact, at key-confirmation time, rather than preventing the tampered advertisement from being read in the first place, that's an acceptable trade-off, since preventing it outright isn't possible while the advertisement stays in cleartext for middlebox compatibility. Supporting a legitimate, trusted proxy that needs to actually rewrite the advertised list (not just inspect it) is a fundamentally different problem: such a proxy must terminate and re-originate the handshake as an explicitly authorized party with its own key material, there is no way to let an invisible, unauthenticated rewrite through without also letting a malicious one through, that composition simply doesn't exist. Finally, the failure mode must be fail-closed: an implementation that silently retries at a lower security level after detecting a mismatch, instead of alerting the application and aborting, has quietly turned a detection mechanism back into a downgrade path.
Define Key-Compromise Impersonation (KCI) in the context of authenticated Diffie-Hellman. Provide an example protocol vulnerable to KCI and propose modifications or protocol choices (for example, SIGMA family or TLS patterns) that prevent KCI while maintaining forward secrecy.
Sample Answer
Direct answer
Key-Compromise Impersonation (KCI) is the property that an attacker who learns Alice's long-term private key can impersonate ANY OTHER party to Alice, without knowing that other party's private key at all. It is a specifically ASYMMETRIC failure: the attacker CANNOT impersonate Alice to others (that would just be ordinary key compromise), but Alice herself becomes fooled about who she is talking to. Protocols like "static-static" Diffie-Hellman (where the session key is derived purely from both parties' long-term keys, with no fresh ephemeral contribution) are classically vulnerable; the SIGMA family of authenticated-key-exchange designs (and the pattern TLS's own handshake follows) avoids it by binding the session key to FRESH ephemeral values that the compromised long-term key alone cannot reproduce.
Structured elaboration
- The vulnerable shape, precisely. If the session key is K=gabmodp using ONLY Alice's and Bob's long-term private keys a,b (no ephemeral exponent at all), then anyone who learns a can compute K against ANY third party X's PUBLIC key, since K=(X’s public key)amodp needs only a and public information. The attacker never needs X's private key.
- Why this specifically breaks the "compromise doesn't cascade" expectation. A well-designed protocol should localize the blast radius of a single compromised key; static-static DH does the opposite for THIS specific direction: compromising Alice's key does not just let an attacker impersonate Alice, it lets them impersonate EVERY OTHER PARTY IN THE SYSTEM to Alice specifically, since the attack only ever needed Alice's key plus public information about whoever is being impersonated.
- The SIGMA-style fix. Add a genuine ephemeral Diffie-Hellman exchange (X generates a fresh xeph, Alice a fresh yeph), and have each side SIGN a transcript that includes BOTH ephemeral public values AND both parties' identities, using their LONG-TERM key strictly for AUTHENTICATION of that specific transcript, not as a direct ingredient of the session key itself. An attacker who has only Alice's compromised long-term key still cannot produce a signature that verifies under X's public key, because that signature requires X's actual private key, which the attacker never obtained.
- Explicit key confirmation as a companion, not a substitute. Layering an HMAC (Hash-based Message Authentication Code)-based, role-labeled key-confirmation exchange on top (each side proves it derived the SAME session key, with messages tagged by role so a reflected message cannot be mistaken for the other party's) additionally defeats reflection-style attacks, a related but distinct concern from KCI itself.
Worked example
I implemented static-static DH exactly as described (session key purely from long-term keys) and showed the attack works with real numbers, then implemented the SIGMA-style fix and confirmed a forged signature using only the compromised key fails to verify:
# Key-Compromise Impersonation (KCI). Two toy protocols over a small prime-order group:
# (1) VULNERABLE: "static-static DH" -- the session key is g^(a*b) using ONLY long-term private
# keys, no ephemeral contribution. Real numbers show that leaking Alice's long-term private key
# `a` lets an attacker compute the session key Alice would derive with ANY third party X, using
# only X's PUBLIC key -- i.e. impersonate X to Alice, without ever learning X's private key.
# (2) FIXED: adds an ephemeral DH exchange plus HMAC-based explicit key confirmation binding both
# identities and both ephemeral values; the long-term key is used only to sign the ephemeral
# value, so compromising it does not hand over the attacker any ephemeral private key.
import hmac, hashlib, random
p, q, g = 227, 113, 4 # a small toy safe-prime DH group
_rng = random.Random(314159) # pinned seed, so re-running reproduces every number below
def rand_priv():
return _rng.randrange(2, q)
# ---------------- (1) VULNERABLE: static-static DH ----------------
def static_static_key(my_priv, their_pub):
return pow(their_pub, my_priv, p)
if __name__ == "__main__":
a = rand_priv() # Alice's LONG-TERM private key
A_pub = pow(g, a, p)
x = rand_priv() # some honest third party X's long-term private key
X_pub = pow(g, x, p)
print(f"group: p={p}, q={q} (subgroup order), g={g}")
print(f"Alice's long-term keypair: a={a} (private), A={A_pub} (public)")
print(f"X's long-term keypair: x={x} (private), X={X_pub} (public, this is all attacker sees of X)\n")
K_honest = static_static_key(x, A_pub) # what X actually computes when talking to Alice
print(f"if X and Alice really talk: X computes K = A^x mod p = {K_honest}")
print("\n--- attacker learns ONLY Alice's long-term private key 'a' (key compromise) ---")
K_attacker = static_static_key(a, X_pub) # attacker computes using a (known) and X_pub (public!)
print(f"attacker (knows a, and X's PUBLIC key X={X_pub}) computes K' = X^a mod p = {K_attacker}")
print(f"K' == K_honest: {K_attacker == K_honest} (attacker never needed x, X's private key)")
print("-> attacker now shares Alice's exact session key with 'X' and can impersonate X to Alice")
print(" in any protocol that just uses g^(a*b) as the session key with no other authentication.\n")
# ---------------- (2) FIXED: SIGMA-style ephemeral DH + signed, MAC-confirmed exchange ----------
print("--- SIGMA-style fix: ephemeral DH, signed by long-term key, MAC-confirmed by session key ---")
def sign(priv, msg):
# toy Schnorr-style signature over the SAME group, sufficient to illustrate binding
k = rand_priv()
r = pow(g, k, p)
e = int(hashlib.sha256((str(r) + msg).encode()).hexdigest(), 16) % q
s = (k + e * priv) % q
return (r, s)
def verify(pub, msg, sig):
r, s = sig
e = int(hashlib.sha256((str(r) + msg).encode()).hexdigest(), 16) % q
return pow(g, s, p) == (r * pow(pub, e, p)) % p
x_eph, y_eph = rand_priv(), rand_priv() # FRESH ephemeral keys, one per session
X_eph_pub, A_eph_pub = pow(g, x_eph, p), pow(g, y_eph, p)
session_key = pow(A_eph_pub, x_eph, p) # = pow(X_eph_pub, y_eph, p), the real DH computation
# each side signs (their identity || both ephemeral values) with their LONG-TERM key --
# this is what KCI needs to defeat: possession of Alice's long-term key alone must NOT let an
# attacker forge a valid X-side transcript, because it must sign X's ephemeral value too, and the
# attacker does not control x_eph (X generated it fresh and kept it private).
transcript = f"X||A||{X_eph_pub}||{A_eph_pub}"
sig_from_X = sign(x, transcript) # only the REAL X, holding real x, can produce this
print(f"X's ephemeral public value: {X_eph_pub} Alice's ephemeral public value: {A_eph_pub}")
print(f"X signs the transcript with X's LONG-TERM key: verifies against X_pub = {X_pub}: "
f"{verify(X_pub, transcript, sig_from_X)}")
# attacker, holding only Alice's compromised long-term key 'a' (not x, not x_eph), tries to forge
# a valid signature over a transcript claiming to be X:
forged_sig = sign(a, transcript) # the only long-term key the attacker actually has
print(f"attacker forges a signature using COMPROMISED key 'a' instead of X's real 'x':")
print(f" forged signature verifies against X_pub: {verify(X_pub, transcript, forged_sig)}")
print(" -> compromising Alice's long-term key gives the attacker no way to produce a signature")
print(" that verifies under X's public key, so Alice will reject the forged handshake.")
mac_key = hashlib.sha256(str(session_key).encode() + b"key-confirmation").digest()
conf_X = hmac.new(mac_key, b"X-confirms", hashlib.sha256).hexdigest()
conf_A = hmac.new(mac_key, b"A-confirms", hashlib.sha256).hexdigest()
print(f"\nexplicit key confirmation MACs (role-labeled, defeats reflection too): "
f"X->{conf_X[:16]}... A->{conf_A[:16]}...")
Output:
group: p=227, q=113 (subgroup order), g=4
Alice's long-term keypair: a=26 (private), A=192 (public)
X's long-term keypair: x=37 (private), X=33 (public, this is all attacker sees of X)
if X and Alice really talk: X computes K = A^x mod p = 219
--- attacker learns ONLY Alice's long-term private key 'a' (key compromise) ---
attacker (knows a, and X's PUBLIC key X=33) computes K' = X^a mod p = 219
K' == K_honest: True (attacker never needed x, X's private key)
-> attacker now shares Alice's exact session key with 'X' and can impersonate X to Alice
in any protocol that just uses g^(a*b) as the session key with no other authentication.
--- SIGMA-style fix: ephemeral DH, signed by long-term key, MAC-confirmed by session key ---
X's ephemeral public value: 132 Alice's ephemeral public value: 11
X signs the transcript with X's LONG-TERM key: verifies against X_pub = 33: True
attacker forges a signature using COMPROMISED key 'a' instead of X's real 'x':
forged signature verifies against X_pub: False
-> compromising Alice's long-term key gives the attacker no way to produce a signature
that verifies under X's public key, so Alice will reject the forged handshake.
explicit key confirmation MACs (role-labeled, defeats reflection too): X->e5a54939cf18ff4a... A->e344ec0acda556ec...
The static-static attack recovers the EXACT same session key (K′=219 matching Khonest=219) using only Alice's compromised private key and X's already-public key, no interaction with X required at all. Against the SIGMA-style fix, a signature forged using the compromised key a in place of X's real key x fails verification against X's public key, exactly as expected: possessing Alice's long-term key gives the attacker no path to a valid signature under X's identity.
Trade-offs and pitfalls
- KCI resistance is not automatic just from "using signatures somewhere." A protocol that signs the WRONG thing (e.g. only its own ephemeral value, not the peer's, or omits the peer's identity from the signed transcript) can still be KCI-vulnerable despite using public-key signatures; the transcript being signed must bind BOTH parties' identities and BOTH ephemeral values.
- This is a genuinely different property from forward secrecy, which is about protecting PAST sessions after a future key compromise; KCI is about whether a compromised key lets an attacker forge NEW, ONGOING sessions by impersonating others. A protocol can have one property without the other, and interview answers that conflate them are a common, worth-avoiding mistake.
- Static-static DH's simplicity is exactly its danger. It is an attractive design specifically because it needs no signature scheme or ephemeral exchange at all, which is also precisely why it has no mechanism to bind a session to a SPECIFIC live exchange rather than merely to a static pair of long-term identities.
Unlock Full Question Bank
Get access to all 27 Asymmetric Encryption and Key Exchange interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.