Symmetric Encryption and Block Ciphers Questions
How symmetric-key primitives are constructed and why they work: block-cipher internals (Feistel networks vs substitution-permutation networks, the AES round structure and S-box design, key schedules and why a weak one degrades security), stream ciphers (ChaCha20 and CTR-mode keystream generation), and the internal mechanics of modes of operation (ECB, CBC, CTR, XTS, GCM), including why some are parallelizable, why ECB leaks structure, and why some require a unique nonce. Covers authenticated encryption construction internals (how GHASH and Poly1305 work, why nonce reuse breaks their security algebraically, formal security notions like IND-CPA and INT-CTXT), padding schemes and the mechanics of padding-oracle attacks, and cryptanalysis of block ciphers (differential and linear cryptanalysis, reduced-round attacks). This is the design and internals layer: how these primitives are built and proven secure, distinct from choosing which algorithm or mode to deploy, managing key lifecycle and rotation, or architecting data protection for a system, which belong to the applied cryptography layer.
Design an authenticated-encryption solution for a high-throughput, low-latency messaging system (e.g., RPC streaming). Specify concrete primitives (AEAD choices), per-connection and per-message nonce strategies, batch processing, associated data for routing metadata, rekeying policies, and how to handle out-of-order messages and replay protection. Justify how your design balances throughput and security.
Sample Answer
Direct answer
For a high-throughput, low-latency remote-procedure-call (RPC) streaming system, the right design is ChaCha20-Poly1305 or AES-Galois/Counter Mode (GCM) with hardware acceleration, one authenticated-encryption-with-associated-data (AEAD) primitive per connection under a session key, a per-message nonce built from a per-connection random salt plus a strictly monotonic sequence number (never randomly generated per message, since that is both slower and reintroduces collision risk), routing metadata carried as associated data (AAD, authenticated but not encrypted), a time-or-byte-budget rekeying policy, and a small sliding-window replay-detection structure to tolerate legitimate out-of-order delivery without accepting replays.
Structured elaboration
AEAD primitive choice: ChaCha20-Poly1305 is the better default on software-only or heterogeneous fleets (its performance does not depend on dedicated hardware instructions), while AES-GCM is preferable when AES-NI (hardware-accelerated AES) is guaranteed available, since hardware-accelerated AES-GCM typically outperforms software ChaCha20-Poly1305 substantially. Both are parallelizable at the block level (counter mode's blocks are independent of each other), which matters directly for high-throughput batch processing.
Nonce strategy: per-connection, generate a random salt once at connection setup, then derive each message's 96-bit nonce as salt || sequence_number, incrementing the sequence number by exactly one per message. This guarantees uniqueness structurally (no two messages on the same connection ever share a sequence number) without needing a fresh random draw per message, which both avoids the cost of per-message randomness generation and sidesteps the birthday-bound collision risk a fully random per-message nonce would carry.
Associated data for routing metadata: bind connection ID, message sequence number, and any routing/multiplexing metadata into the AAD, so this data is tamper-evident (any modification breaks the authentication tag) without needing to be encrypted (routers and intermediaries that need to read routing metadata can do so without decrypting the payload).
Rekeying policy: trigger a new session key well before the AEAD mode's own collision/invocation safety margin is approached. For random 96-bit nonces, the birthday-bound collision probability after N messages is approximately N2/297; solving for the N where that crosses a conservative 2−32 threshold gives N≈2(96+1−32)/2=232.5, roughly 6.07 billion messages. NIST SP 800-38D recommends staying below 232 invocations under one key for GCM with random nonces, a deliberately rounder, more conservative number than that exact birthday-bound solution (about 1.4x tighter). That derivation matters less for the design recommended here specifically: a counter-based nonce scheme like the one above can safely run closer to its full counter width before requiring a rekey, since it has no birthday-bound collision risk at all, only a hard wraparound limit.
Handling out-of-order messages and replay: because sequence numbers are strictly monotonic at the sender but the network can reorder or drop packets, the receiver keeps a small sliding bitmap window (for example, the highest sequence number seen plus a 64-bit bitmap marking which of the preceding 64 sequence numbers have already been accepted) rather than requiring exact in-order delivery; a message inside the window that has already been marked is rejected as a replay, a message ahead of the window slides the window forward, and a message far behind the window is rejected outright as stale.
Worked example
Concrete numbers for the nonce space and per-connection replay state, all pinned and computed directly:
block_bytes, counter_bits = 64, 32
max_bytes = (2 ** counter_bits) * block_bytes
print(f"ChaCha20 IETF variant limit per (key,nonce): 2^{counter_bits} blocks * {block_bytes}B = "
f"{max_bytes:,} bytes = {max_bytes/2**30:.0f} GiB")
window_bits = 64
print(f"replay-detection state per connection: a {window_bits}-bit bitmap = {window_bits//8} bytes")
Output:
ChaCha20 IETF variant limit per (key,nonce): 2^32 blocks * 64B = 274,877,906,944 bytes = 256 GiB
replay-detection state per connection: a 64-bit bitmap = 8 bytes
The 256 GiB figure is the hard per-(key,nonce) ceiling for a single ChaCha20 invocation (its internal block counter is 32 bits); it bounds how much data a single message can carry, not how many messages a session can send, since each message gets its own nonce via the sequence-number scheme above. The 8-byte replay bitmap is cheap enough to keep per active connection even at very large connection counts, letting the receiver tolerate up to 64 messages of reordering with negligible per-connection memory cost.
Trade-offs and pitfalls
The most common mistake in this exact scenario is using a randomly-generated nonce per message for "simplicity", which both costs a CSPRNG (cryptographically secure pseudorandom number generator) draw on the hot path and reintroduces the birthday-bound collision risk that a monotonic counter avoids entirely; for a high-throughput system, the counter-based approach is strictly better on both axes. A second pitfall is sizing the replay window too small for the actual network's reordering behavior, causing legitimate delayed messages to be rejected as replays; the window size is a tunable that should be set from measured reordering statistics, not a fixed default. Finally, remember that AAD is authenticated but never encrypted, so routing metadata placed there is visible to anyone who can see the wire traffic, appropriate for routing information but not for anything that itself needs confidentiality.
Provide scenarios where AES-SIV is preferable to AES-GCM or ChaCha20-Poly1305. Include considerations such as storage/deduplication, deterministic encryption requirements, environments with poor randomness, long-term data-at-rest protection, and whether streaming or low-latency requirements influence your choice.
Sample Answer
Direct answer
AES-SIV is preferable to nonce-based authenticated-encryption-with-associated-data (AEAD) modes like AES-Galois/Counter Mode (GCM) or ChaCha20-Poly1305 whenever the deployment cannot reliably guarantee a fresh, unique nonce for every encryption, deterministic output is actually useful (storage deduplication, content-addressable systems), or the data is long-lived at-rest data where a single nonce-reuse mistake anywhere in a multi-year lifetime would be catastrophic. It is the wrong choice whenever low-latency streaming throughput matters, or whenever the deterministic leak (equal plaintext plus equal AAD always produces equal ciphertext) is itself unacceptable for the data being protected.
Structured elaboration
Storage and deduplication: a storage system that wants to detect and collapse duplicate encrypted blocks (a common design in backup and content-addressable storage) needs identical plaintexts to produce identical ciphertexts, which is exactly what SIV's determinism provides and what a nonce-based mode structurally prevents (since a fresh nonce makes even identical plaintexts produce different ciphertexts every time, defeating deduplication entirely).
Environments with poor randomness: an embedded device with a weak or predictable random-number generator at boot cannot safely generate the fresh nonces GCM's proof requires; a single nonce collision under GCM is catastrophic (keystream reuse leaks plaintext directly, and the authentication key's internal state becomes algebraically solvable, enabling forgery). SIV removes the nonce entirely, so a weak RNG at boot cannot cause this specific failure category, though the device still needs the underlying key material to be properly random.
Long-term data-at-rest protection: for records that will sit encrypted for years, the operational risk of a nonce ever repeating across that entire lifetime (software bugs, clock resets, VM snapshot/restore duplicating a counter's starting state) compounds with every additional record written. SIV's misuse resistance means that even a caller-side bug that would otherwise cause nonce reuse has no catastrophic failure mode to trigger, a meaningfully different risk profile for data you cannot afford to be wrong about even once.
Where streaming or low-latency requirements dominate instead: SIV's S2V step has to process the entire (AAD, plaintext) before producing the synthetic IV that CTR-mode encryption depends on, so encryption cannot begin until the whole message is available; this is a poor fit for high-throughput streaming (live network protocols, large unbounded files) where nonce-based AEAD can begin encrypting and transmitting the first bytes immediately.
Worked example
The concrete trade-off between SIV's deduplication-friendly leak and GCM's much worse nonce-misuse failure, run side by side:
from cryptography.hazmat.primitives.ciphers.aead import AESSIV, AESGCM
siv = AESSIV(AESSIV.generate_key(bit_length=256))
dup1 = siv.encrypt(b"status:active", [b"row:1"])
dup2 = siv.encrypt(b"status:active", [b"row:2"]) # different AAD
dup3 = siv.encrypt(b"status:active", [b"row:1"]) # exact same (plaintext, AAD) as dup1
print("SIV: equal plaintext, different AAD -> ciphertexts differ:", dup1 != dup2)
print("SIV: equal plaintext, same AAD -> ciphertexts match (a duplicate-row signal):", dup1 == dup3)
gcm = AESGCM(AESGCM.generate_key(bit_length=128))
reused_nonce = b"\x00" * 12
g1 = gcm.encrypt(reused_nonce, b"transfer $500 ", None)
g2 = gcm.encrypt(reused_nonce, b"transfer $9999", None) # SAME nonce misused
xor_ct = bytes(a ^ b for a, b in zip(g1, g2))
xor_pt = bytes(a ^ b for a, b in zip(b"transfer $500 ", b"transfer $9999"))
print("GCM with a misused nonce leaks plaintext XOR directly, no key needed:", xor_ct[:len(xor_pt)] == xor_pt)
Output:
SIV: equal plaintext, different AAD -> ciphertexts differ: True
SIV: equal plaintext, same AAD -> ciphertexts match (a duplicate-row signal): True
GCM with a misused nonce leaks plaintext XOR directly, no key needed: True
This is the core of the trade-off in one comparison: SIV's worst case, under normal correct use, is a bounded, well-understood leak (equal input reveals equal output); GCM's worst case, the moment misuse happens even once, is direct plaintext recovery with no key required. For deployments that cannot guarantee flawless nonce handling forever, SIV's bounded failure mode is the safer default even though GCM has strictly better throughput and no equality leak when used correctly.
Trade-offs and pitfalls
The most common mistake is treating this as "SIV is always safer, use it everywhere"; that ignores the deduplication-signal leak, which is a real, sometimes unacceptable cost (authenticating a low-entropy field like a status flag under SIV lets an observer learn when two records share the same value, without decrypting either). A second pitfall is choosing SIV purely for its misuse resistance in a system that actually has a solid, well-tested nonce-management layer already; in that case GCM or ChaCha20-Poly1305 give strictly better throughput and no equality leak, and SIV's protection is solving a problem that does not exist in that deployment. The right framing is a risk trade: SIV trades a small, well-understood, always-present leak for eliminating a rare-but-catastrophic failure mode; whether that trade is worth it depends entirely on how much you trust your own nonce-management discipline and how sensitive the equality-of-input leak is for that specific data.
You need to design a streaming AEAD approach for encrypting very large files or live video where random access and partial validation are required. Propose a chunking scheme with per-chunk nonces and explain how to maintain integrity across chunks (e.g., chaining tags, a merkle tree, or higher-level signing), how to handle seeking and partial reads, and how to limit state while preventing replay or reorder attacks.
Sample Answer
Direct answer
Split the file or stream into fixed-size chunks, encrypt each one independently with AEAD (Authenticated Encryption with Associated Data, a cipher mode that gives you confidentiality and a tamper-evident authentication tag in one step) using a nonce (a value used once per key that a mode like GCM requires to never repeat) derived deterministically from a per-file salt and the chunk index rather than a stored counter, authenticate a header that binds file identity, key version, and stream completeness into every chunk, and pick one of three integrity-linking mechanisms depending on whether the priority is pure sequential streaming (chaining tags), true random access (a Merkle tree), or a single detached commitment (higher-level signing over a manifest).
Structured elaboration
Chunking and per-chunk AEAD. A fixed chunk size (commonly tens of KiB) trades per-chunk overhead (the AEAD tag plus header, typically 20 to 40 bytes) against random-access granularity. Each chunk is encrypted with AES-256-GCM (Advanced Encryption Standard, 256-bit key, Galois/Counter Mode) or ChaCha20-Poly1305, either of which gives per-chunk confidentiality and integrity in one call.
Nonce derivation. nonce_i = truncate(HMAC(S, i), 96 bits), where S is a per-file random 128-bit salt generated once (ideally from a CSPRNG, a cryptographically secure pseudorandom number generator) and stored, unencrypted, alongside the ciphertext. HMAC (hash-based message authentication code) here is just a keyed pseudorandom function, not proving anything to a third party. A deterministic-from-salt nonce beats a persisted counter for two reasons: a reader jumping straight to chunk 500 can recompute that chunk's nonce with zero prior state, and there is no mutable per-chunk value to lose or corrupt. Passing the index through HMAC(S, ...) rather than using it bare also makes the nonce sequence file-specific, so even an accidental key reuse across two different files does not also reuse the exact same nonce sequence.
Authenticated header. AD = file_id || key_version || chunk_index || is_last, passed as GCM's associated data (authenticated but not encrypted). Binding key_version defeats splicing a chunk encrypted under an old key into a file re-encrypted under a new one; binding chunk_index and file_id defeats moving ciphertext between positions or between files.
Cross-chunk integrity, the three options the question names:
- Chaining tags: fold each chunk's tag into the next chunk's associated data. O(1) memory for both writer and sequential reader, cheapest per-chunk cost, but a reader who seeks to chunk 500 cannot verify it without replaying the chain from a trusted anchor, so it does not give true random-access integrity. This is the right fit for a live, unbounded stream (a broadcast whose final length is not known upfront), because it needs no lookahead.
- Merkle tree: leaf_i = H(chunk_tag_i), build a tree, authenticate only the root. A reader wanting chunk 500 fetches it plus an O(log n) sibling-hash path and checks against the root, fetched once. This is the mechanism that actually satisfies "random access and partial validation" together, at the cost of an upfront full pass to build the tree (or careful incremental construction), which requires the total chunk count to be known, making it the right fit for a bounded file, not an open-ended live stream.
- Higher-level signing: sign or MAC just a small manifest (file_id, chunk_count, root_hash, key_version). Cheapest steady-state cost, but the signature only proves the manifest is authentic; you still need the Merkle proof to bind an individual chunk to that manifest, so in practice this is "Merkle tree, with the root's authenticity handled by a signature instead of a pre-shared value."
Seeking and partial reads. A reader at byte offset X computes chunk_index = X // chunk_size, re-derives that chunk's nonce and AD with no earlier state, fetches the ciphertext (plus, for the Merkle variant, its sibling path), and decrypts. No chunk depends on decrypting any other chunk, so seek cost is O(1) for chaining tags and O(log n) for a Merkle tree, never O(n).
Replay, reorder, and truncation. Reorder and copy-paste are caught by AD binding chunk_index: decrypting chunk 9's ciphertext against chunk 9's expected AD fails once the bytes actually came from chunk 5. Truncation (silently dropping trailing chunks) is not caught by per-chunk AEAD alone, because a truncated prefix is a set of individually valid chunks; the is_last flag closes this only if the reader requires the last chunk it accepts to carry is_last = true (or, for the Merkle variant, that the accepted chunk count matches the signed manifest). Replay of an entire stale version of the file is caught by key_version in the AD.
Worked example
import hashlib
import hmac as hmac_mod
from cryptography.hazmat.primitives.ciphers.aead import AESGCM
# --- Streaming AEAD chunking scheme demo ---
# Pinned inputs for reproducibility (a real deployment generates S randomly per file).
K = bytes(range(32)) # 32-byte AES-256-GCM key
S = bytes.fromhex("00112233445566778899aabbccddeeff") # 16-byte per-file salt
file_id = b"file-42"
key_version = 1
aesgcm = AESGCM(K)
TOTAL_CHUNKS = 3
def derive_nonce(salt: bytes, chunk_index: int) -> bytes:
# deterministic per-chunk nonce = truncate(HMAC(S, chunk_index), 96 bits)
mac = hmac_mod.new(salt, chunk_index.to_bytes(8, "big"), hashlib.sha256).digest()
return mac[:12]
def chunk_ad(file_id: bytes, key_version: int, chunk_index: int, is_last: bool) -> bytes:
# authenticated header binds key-version/file-id, position, AND stream-completeness
return file_id + key_version.to_bytes(2, "big") + chunk_index.to_bytes(8, "big") + (b"\x01" if is_last else b"\x00")
chunks = [b"chunk-0 payload.....", b"chunk-1 payload.....", b"chunk-2 payload....."]
store = {}
for i, pt in enumerate(chunks):
nonce = derive_nonce(S, i)
ad = chunk_ad(file_id, key_version, i, is_last=(i == TOTAL_CHUNKS - 1))
store[i] = aesgcm.encrypt(nonce, pt, ad)
print("nonces distinct:", len({derive_nonce(S, i) for i in range(TOTAL_CHUNKS)}) == TOTAL_CHUNKS)
for i in range(TOTAL_CHUNKS):
print(f"chunk {i}: nonce={derive_nonce(S, i).hex()} is_last={i == TOTAL_CHUNKS-1} ct_len={len(store[i])}")
def read_chunk(store, i, is_last):
# Reader RE-DERIVES nonce/AD from the position it asked for; never trusts stored metadata.
nonce = derive_nonce(S, i)
ad = chunk_ad(file_id, key_version, i, is_last)
return aesgcm.decrypt(nonce, store[i], ad) # raises InvalidTag on failure
# --- 1. normal round trip ---
recovered = [read_chunk(store, i, i == TOTAL_CHUNKS - 1) for i in range(TOTAL_CHUNKS)]
print("round-trip ok:", recovered == chunks)
# --- 2. copy-paste: overwrite on-disk chunk 2 with chunk 1's ciphertext bytes ---
tampered = dict(store)
tampered[2] = store[1]
try:
read_chunk(tampered, 2, is_last=True)
print("COPY-PASTE NOT DETECTED (bug)")
except Exception as e:
print("copy-paste rejected at position 2:", type(e).__name__)
# --- 3. reorder: swap on-disk chunks 1 and 2; AD position-binding alone must catch it ---
reordered = dict(store)
reordered[1], reordered[2] = store[2], store[1]
caught = 0
for i in (1, 2):
try:
read_chunk(reordered, i, i == TOTAL_CHUNKS - 1)
except Exception:
caught += 1
print(f"reorder rejected by per-chunk AD alone: {caught}/2 swapped positions failed verification")
# --- 4. truncation: attacker drops the final chunk; does per-chunk AEAD alone notice? ---
truncated = {0: store[0], 1: store[1]} # chunk 2 missing entirely
# A reader who is NOT told the true total chunk count and checks only chunks 0..1:
ok_without_completeness_check = True
try:
read_chunk(truncated, 0, is_last=False)
read_chunk(truncated, 1, is_last=False) # attacker also lies that chunk 1 isn't last
except Exception:
ok_without_completeness_check = False
print("truncation slips past per-chunk AEAD if is_last is not itself checked:", ok_without_completeness_check)
# But if the reader insists the LAST chunk it read must carry is_last=True, and stops only there:
try:
read_chunk(truncated, 1, is_last=True) # reader demands is_last on the last chunk it has
print("TRUNCATION NOT DETECTED (bug)")
except Exception as e:
print("truncation rejected once reader requires is_last=True on the final chunk it accepts:", type(e).__name__)
Output:
nonces distinct: True
chunk 0: nonce=bffa340d31b7af99a62b8773 is_last=False ct_len=36
chunk 1: nonce=6af717747d8a2890149f3fd1 is_last=False ct_len=36
chunk 2: nonce=28aaa4a90429753d0a4b208d is_last=True ct_len=36
round-trip ok: True
copy-paste rejected at position 2: InvalidTag
reorder rejected by per-chunk AD alone: 2/2 swapped positions failed verification
truncation slips past per-chunk AEAD if is_last is not itself checked: True
truncation rejected once reader requires is_last=True on the final chunk it accepts: InvalidTag
Trade-offs and pitfalls
Chaining tags versus a Merkle tree is a genuine trade-off, not a strictly-better-option choice: chaining gives the cheapest per-chunk cost and zero lookahead requirement, which is why live video (unbounded length, sequential playback) wants it; a Merkle tree gives true random access at the cost of O(log n) proof bytes per read and knowing the total chunk count upfront, which is why a large finite file wants it instead.
The deterministic-nonce derivation is safe only because the salt S is fresh per file. If S is ever reused across two different plaintexts under the same key (a hard-coded salt, or a broken random-number generator), chunk i of both files gets the identical nonce, which is a catastrophic AES-GCM nonce reuse for that pair of chunks, not a minor bug: it leaks the XOR of the two chunks' plaintexts and can enable forgery. Treat the salt exactly as carefully as a nonce, because functionally it is one.
Copy-paste protection stops at the boundary of what the associated data actually names: binding file_id stops a chunk moving between two different files sharing one key, but does nothing if the same key is (mis)used across two disks or two independent systems that happen to reuse a file_id value, so file_id needs to be as globally unique as any other value you are relying on for security.
Describe the cryptographic consequences of nonce or IV reuse in AEAD schemes (for example AES-GCM) when used after key establishment. Provide concrete examples of attacks (loss of confidentiality, forgery) and relate these issues back to choices made in key-derivation and nonce construction during the key-exchange design.
Sample Answer
Direct answer
Nonce or IV (initialization vector, a value used only once per key) reuse in an AEAD (Authenticated Encryption with Associated Data) scheme like AES-GCM (Galois/Counter Mode) breaks both halves of the construction at once: the CTR keystream repeats, letting an attacker recover the XOR of two plaintexts by XORing their ciphertexts with no key at all, and the GHASH authentication mask (GHASH is GCM's own hash function, which folds the ciphertext into the authentication tag using field arithmetic) repeats too, letting an attacker solve for the secret hash subkey and forge tags. The root cause almost always traces back to a choice made when the connection or session was set up: how nonces are constructed relative to the derived key, and whether that construction can ever repeat across restarts, re-keys, or multiple parties sharing a key.
Structured elaboration
The confidentiality break. With a reused (key, nonce), the CTR keystream KS = AES_K(J_0) for the FIRST block is identical across both messages. XORing the two ciphertexts cancels the keystream entirely: C1⊕C2=P1⊕P2. An attacker who knows or guesses one plaintext (a fixed-format field, a common header) immediately recovers the other, with zero cryptanalysis.
The forgery break. As with any GCM nonce reuse, the authentication mask E_K(J_0) and the hash subkey H are also fixed across the two messages: XORing the two messages' observed tags cancels that shared masking value, leaving an equation built only from public ciphertext and tag bytes that solves for H, after which the attacker can forge a valid tag for a brand-new message under that same nonce.
Where this actually comes from: key-derivation and nonce-construction choices. Nonce reuse is almost never "the programmer forgot a random call." It comes from structural decisions made during key exchange and session setup:
- A KDF (key derivation function) that derives ONE encryption key for the whole session but leaves nonce construction to a counter that gets reset on reconnect, restart, or failover, without also rotating the key.
- Two parties deriving the SAME symmetric key from a Diffie-Hellman-style exchange but not including a role/direction bit in either the key derivation or the nonce, so both sides' independently-incrementing counters collide.
- A protocol that reuses a long-lived key across many short sessions instead of deriving a FRESH per-session key, multiplying the number of times any given counter value could theoretically repeat.
How this is prevented at the design level, not just the implementation level. A KDF should derive a nonce SALT (or a fully separate per-session sub-key) alongside the encryption key, from context that is unique to that key-exchange instance (a session ID, a random value contributed by both sides, a role identifier). The nonce itself is then built as that salt combined with a monotonic counter, so uniqueness is guaranteed by construction rather than by hoping a counter never gets reset.
Worked example
Two different real messages encrypted under the SAME (key, nonce) via full AES-GCM, showing the plaintext-recovery step an eavesdropper performs with no key access at all:
R = 0xE1 << 120
def gf128_mul(x, y):
z, v = 0, y
for i in range(128):
if (x >> (127 - i)) & 1: z ^= v
v = (v >> 1) ^ R if v & 1 else v >> 1
return z
def to_int(b): return int.from_bytes(b, "big")
def to_bytes16(x): return (x & ((1 << 128) - 1)).to_bytes(16, "big")
def ghash(h, data):
y = 0
for i in range(0, len(data), 16): y = gf128_mul(y ^ to_int(data[i:i+16]), h)
return to_bytes16(y)
def pad16(b): return b if len(b) % 16 == 0 else b + b"\x00" * (16 - len(b) % 16)
def aes_ecb(key, block):
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
e = Cipher(algorithms.AES(key), modes.ECB()).encryptor()
return e.update(block) + e.finalize()
def inc32(j):
c = (int.from_bytes(j[12:], "big") + 1) % (1 << 32)
return j[:12] + c.to_bytes(4, "big")
def gcm_encrypt(key, iv, aad, pt):
h = to_int(aes_ecb(key, b"\x00"*16))
j0 = iv + b"\x00\x00\x00\x01"
out, j = bytearray(), inc32(j0)
for i in range(0, len(pt), 16):
j = j if i == 0 else inc32(j)
out += bytes(a ^ b for a, b in zip(pt[i:i+16], aes_ecb(key, j)))
ct = bytes(out)
gh = pad16(aad) + pad16(ct) + (len(aad)*8).to_bytes(8,"big") + (len(ct)*8).to_bytes(8,"big")
s = ghash(h, gh)
tag = bytes(a ^ b for a, b in zip(s, aes_ecb(key, j0)))
return ct, tag
key = bytes.fromhex("2b7e151628aed2a6abf7158809cf4f3c"[:32])
iv = bytes.fromhex("101112131415161718191a1b") # REUSED for both messages below
P1 = b"acct=104291 amt=50000"
P2 = b"acct=778823 amt=12000"
n = max(len(P1), len(P2)); P1p, P2p = P1.ljust(n, b" "), P2.ljust(n, b" ")
C1, _ = gcm_encrypt(key, iv, b"", P1p)
C2, _ = gcm_encrypt(key, iv, b"", P2p)
xor_ct = bytes(a ^ b for a, b in zip(C1, C2))
recovered_P2 = bytes(a ^ b for a, b in zip(xor_ct, P1p)) # attacker knows P1's format
print("recovered P2 matches real P2:", recovered_P2 == P2p)
Output:
recovered P2 matches real P2: True
An attacker who knows (or guesses) the format of P1, a common assumption for fixed-layout account or transaction records, recovers P2 completely from public ciphertexts alone, with no access to the key at any point.
Trade-offs and pitfalls
- The fix belongs in the key-exchange and session-setup design, not just in a code review checklist: bind nonce construction to a per-session salt derived alongside the key, and never let a nonce space be shared between two independently-counting parties without a role bit distinguishing them.
- Rekeying does not automatically solve nonce reuse; if the new key's nonce counter also resets to a value used under a PRIOR key derived from the same long-term secret without enough context separation, some misuse-resistant analyses still treat this as a live risk depending on the KDF's domain separation.
- Where operational nonce uniqueness cannot be guaranteed with confidence (embedded devices with unreliable clocks or storage, multi-writer systems), prefer a nonce-misuse-resistant AEAD (AES-GCM-SIV) over trying to harden ordinary AES-GCM's nonce discipline further.
A protocol constructs a 96-bit nonce as 32-bit timestamp || 64-bit counter and uses AES-GCM. Describe an attacker strategy exploiting counter wraparound, clock rollback, or cloned devices, and show how nonce reuse might occur in practice. Propose a robust nonce construction and server-side checks to prevent exploitation.
Sample Answer
Direct answer
A 96-bit nonce built as a 32-bit timestamp concatenated with a 64-bit per-device counter looks unique on paper, but an attacker (or just unlucky operational conditions) can force the SAME nonce to occur twice through counter wraparound within one timestamp second, a clock rollback that revisits a (timestamp, counter) pair already used, or two cloned devices that share the same epoch and counter state; any of these collapses to full AES-GCM (Galois/Counter Mode) nonce reuse, with the usual plaintext-recovery and forgery consequences. The fix is a nonce construction where at least one component is a durable, non-resettable, globally unique value, backed by server-side replay detection.
Structured elaboration
Attack path 1: counter wraparound within one timestamp second. If a device sends messages fast enough (or the counter starts near its maximum for any reason: overflow bugs, a manipulated starting value), the 64-bit counter can wrap back to 0 while the timestamp second has not yet advanced, producing an EXACT nonce repeat within that second.
Attack path 2: clock rollback. If the device's clock can be set backward (NTP correction, battery removal, or a compromised real-time clock) AND the counter is reset alongside it (a reboot that also zeroes the counter), the device can revisit an EXACT (timestamp, counter) pair it already used before the rollback, producing a genuine nonce collision, not just a theoretical one.
Attack path 3: cloned devices. Two devices provisioned from the same firmware image, sharing the same starting epoch and the same counter-reset behavior, will independently produce IDENTICAL nonce sequences if their clocks and counters happen to align, which is common right after a factory reset or a fleet-wide provisioning event.
A robust nonce construction. Combine a device-UNIQUE identifier with a MONOTONIC, non-resettable sequence number, persisted in non-volatile storage so it survives power loss and reboots: for example, nonce = device_id (32 bits) || monotonic_counter (32 bits) || per-message random salt (32 bits), where the monotonic counter is guaranteed (by the device's own storage and boot logic) to never repeat, and the device ID prevents two cloned devices from colliding even if their counters somehow do align.
Server-side checks. The server should track the HIGHEST counter value seen per device and reject anything less than or equal to it (strict monotonic enforcement), flag and alert on any observed rollback, and treat duplicate device IDs presenting from different network sources as a signal of possible cloning requiring re-provisioning.
Worked example
The collision arithmetic made concrete, plus its consequence when fed into real AES-GCM encryption:
def build_nonce(timestamp_32, counter_64):
return (timestamp_32 & 0xffffffff).to_bytes(4, "big") + (counter_64 & 0xffffffffffffffff).to_bytes(8, "big")
ts = 0x66f3a000
n1 = build_nonce(ts, counter_64=0xFFFFFFFFFFFFFFFF)
n1_next = build_nonce(ts, counter_64=(0xFFFFFFFFFFFFFFFF + 1) % (1 << 64)) # wraps within the SAME second
print("wraparound collision:", n1_next == build_nonce(ts, 0))
ts_earlier = 0x66f39ffe
nonce_then = build_nonce(ts_earlier, counter_64=17)
nonce_after_rollback = build_nonce(ts_earlier, counter_64=17) # clock + counter both revisit the same pair
print("rollback collision:", nonce_then == nonce_after_rollback)
Output:
wraparound collision: True
rollback collision: True
Both nonce-construction failure modes produce an EXACT, reproducible nonce collision, entirely from ordinary modular arithmetic on the timestamp/counter values, with no cryptographic weakness involved: the vulnerability is in the construction, not the cipher.
Trade-offs and pitfalls
- Timestamp-based nonce components are attractive because they're "free" (no extra storage needed) but they trade that convenience for exactly this collision risk whenever the clock or counter state is not perfectly reliable, which in practice includes almost every embedded or intermittently-connected device.
- Persisting a monotonic counter durably has its own cost (flash write wear on embedded devices, for example); a common mitigation is periodically reserving a BLOCK of future counter values in storage (write the max once, use many increments before the next persisted write) so a crash between writes still cannot cause reuse, at the cost of "burning" some counter space on every restart.
- Device cloning is a provisioning-process problem, not purely a nonce-construction problem; even a perfect nonce scheme cannot fully protect a system where the SAME key material was cloned onto two devices, since a shared key is itself the deeper vulnerability there.
Unlock Full Question Bank
Get access to all 30 Symmetric Encryption and Block Ciphers interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.