System Security I

01 / System Security IFrom a security goal to an experiment

A system may compute the right answer and still be insecure. A login protocol can accept its legitimate user, yet also accept an attacker who rearranges an old transcript. Encryption can recover the plaintext correctly, yet reveal whether two encrypted records are equal. We therefore ask two separate questions: does the construction work, and what can an adversary make it do?

This course develops that distinction through identification, digital signatures, authenticated key exchange and encryption. Its emphasis is the one used in the original lectures: write the messages, identify the adversary's interface, and derive an attack or a security argument. Device failures and exposure of ephemeral values are part of the analysis, not an afterthought.

Prerequisites are modular arithmetic, elementary probability and basic programming. System Security II develops the reductions behind these constructions. Security in Cloud Computing applies them to storage and private computation. These are study materials for the previous English-language courses, not a timetable or an announcement of a current course offering.

Four questions for every protocol

1. Goal: whose identity, message or session key is protected?
2. Interface: what may the adversary observe, choose, modify or reveal?
3. Winning condition: what event counts as a break, and which queries make that event trivial?
4. Assumptions: which mathematical problems, random choices and implementation properties are relied upon?

For a laboratory report, a successful run is evidence of one execution. A correctness derivation covers all valid inputs. A security reduction relates every efficient adversary in the specified model to a solver for a stated hard problem. These are different kinds of evidence.

Security is a property of a whole system

Begin with the assets, not the cipher. A system contains users, data, software, devices and relations between them: ownership, access rights, protocol messages and administrative commands. An attacker may read a record, change its contents, delete it or change its position in a sequence. It may identify a supposedly anonymous user, impersonate an account, or make a service unavailable. Preventing one of these events does not automatically prevent the others.

Confidentiality restricts who learns information. Integrity concerns unauthorised changes, including changes to context and order. Availability concerns continued service. Authentication establishes the relevant identity or origin. Privacy also asks what the system unnecessarily reveals about behaviour and relationships. A valid signature on every record does not stop an attacker from deleting the entire database. An encrypted database may still expose access patterns.

Separate a policy from the mechanism that enforces it. “Only the account owner may authorise a transfer” is a policy. A signature verifier is one component of its implementation. The application must still bind the signature to the destination, amount, account, operation and replay state. A correct cryptographic primitive with an incomplete signed message can enforce the wrong policy perfectly.

The gaps between these layers are frequent sources of failure. Testing a deployed endpoint cannot establish a theorem about every possible input. A theorem about an ideal protocol cannot establish that an administrator installed the right trust anchor.

What “negligible” actually means

A function $\nu(\lambda)$ is negligible if, for every positive polynomial $p$, it eventually becomes smaller than $1/p(\lambda)$. Thus $2^{-\lambda}$ is negligible, whereas $1/\lambda^2$ is not. The latter can look small for one parameter value but does not meet the asymptotic definition. “Polynomial time” also includes the number of oracle queries and the total length of the adversary's input and output.

For a concrete system, ask for numbers as well: time, number of attempts, number of users and success probability. An online adversary making $t$ independent guesses of a uniformly chosen $k$-bit challenge succeeds with probability at most $t/2^k$ by a union bound. Rate limits change the feasible value of $t$; they do not change the algebra of the challenge. An implementation error that makes the challenge predictable removes the premise of the bound.

02 / System Security IGroups, scalars and encodings

Let $G=\langle g\rangle$ be a cyclic group of prime order $q$. Group operations are written multiplicatively. Scalars belong to the field $\mathbb Z_q$, with all scalar sums and products reduced modulo $q$. A secret key is $a\in\mathbb Z_q^*$ and its public key is $A=g^a$. A fresh ephemeral scalar is $x\in\mathbb Z_q$ and its public commitment is $X=g^x$.

Scalar inversion means inversion in $\mathbb Z_q$, and is defined only for a nonzero scalar. Group inversion is a different operation. In an elliptic-curve library the same group law is usually additive: $A=a\cdot P$, $X=x\cdot P$ and $s\cdot P=X+c\cdot A$. The point $P$ replaces the generator $g$; multiplication of two curve points is not an operation of this additive group.

Canonical encodings matter. Hashing two strings by concatenating them without lengths can confuse different pairs of strings. Encode the protocol name, version, group, roles and fields unambiguously. A scalar hash and a hash-to-curve function are not interchangeable. RFC 9380 specifies hash-to-curve suites and domain separation.

Hash notation and output types

The group subscript names the actual output group. When a derivation uses a generic group $G$, write $\H_G$; use $\H_{G_2}$ if the output is in $G_2$. This does not identify distinct source groups or change a proof's assumptions. All hash inputs are unambiguously encoded byte strings; writing a tuple or group point as an input abbreviates its specified encoding. Independent roles use separate domains, even when they share the symbol $\H$.

A public deterministic hash-to-group function must not provide a publicly computable discrete logarithm of its output relative to the generator. Merely returning a point of the right type is insufficient. In the BLS WebAssembly demo, $\H_{G_1}$ denotes the group-hashing role implemented with MCL's hashAndMapToG1; scalar hashing has a different interface, hashToFr. The notation alone does not assert compatibility with an RFC 9380 suite or a standard BLS byte format. See RFC 9380 and MCL WebAssembly.

Two moduli, two different jobs

In the finite-field examples, take a prime $p$ and a prime divisor $q$ of $p-1$. The generator $g\in\mathbb Z_p^*$ has order $q$. Compute group elements modulo $p$, but compute their exponents modulo $q$. Reducing a response modulo $p$ instead of $q$ is a type error, even if a few test values happen to work. On an elliptic curve, the coordinate field and the prime-order scalar field play these two different roles.

For a hand calculation use $p=47$, $q=23$ and $g=2$. Then $2^{23}=1\pmod{47}$, and $2$ has order $23$. With $a=7$, the public key is $A=34$. With nonce $x=9$, the commitment is $X=42$. A challenge $c=3$ gives $s=9+7\cdot3=7\pmod{23}$. Verification computes $2^7=34$ and $42\cdot34^3=34\pmod{47}$. Every number has a declared type before it is used.

For nonzero $d\in\mathbb Z_q$, division by $d$ means multiplication by $d^{-1}$, not floating-point division. For example, $8^{-1}=3\pmod{23}$ because $8\cdot3=1\pmod{23}$. Do not write a program that divides integers as real numbers and reduces the rounded result afterwards.

Authentication factors and public keys

The opening lectures distinguish something a user knows, something the user has, and a biometric property. We focus on knowledge of a secret key. A public key identifies that secret mathematically; it does not, by itself, identify a human. A certificate, an authenticated directory, a previously checked fingerprint or another trust mechanism must connect the key to the intended identity. An attacker who replaces both a key and its displayed name has not solved a discrete logarithm.

03 / System Security IAdversaries, views and freshness

A passive adversary records honest executions. An active adversary sends its own messages and may interleave sessions. A device adversary may additionally learn or influence state inside an endpoint. We do not simply call one of these an “attacker”: we specify exactly which interface it has.

For identification, a passive training view may contain polynomially many honest transcripts. In an active training phase, the adversary plays the verifier and chooses challenges. In the later impersonation phase it must convince a fresh honest verifier without a live relay to the honest prover. Allowing such a relay changes the goal and can make basic challenge-response identification trivially relayable.

For signatures, a signing oracle returns signatures on chosen messages. For encryption, a decryption oracle returns plaintexts or rejection. For key exchange, separate session instances have their own messages, state and acceptance event. A reveal query must name both the instance and the secret being returned.

Freshness is part of a security definition. A key-indistinguishability experiment that permits direct revelation of its challenge key measures nothing useful. Conversely, excluding every interesting compromise can make a model too weak to describe the intended device.

A complete identification experiment

1. Generate parameters and an honest key pair. Give the public parameters and public key to $\mathcal A$.
2. In passive training, give it honest transcripts. In active training, let it choose each challenge after seeing the prover's commitment. Bound the number of sessions by a polynomial.
3. End access to the honest prover. Start a new honest verifier, with fresh independent randomness, and let $\mathcal A$ act as prover.
4. Count success exactly when that verifier accepts the target identity.

In this experiment the advantage is the acceptance probability, not its distance from $1/2$. There is no hidden challenge bit to guess. Key secrecy alone is weaker: an adversary may impersonate a user without ever computing that user's key. The examples below do exactly that.

The training phase must say whether sessions are sequential, concurrent or resettable. In a reset attack a device may be returned to a previous state, causing its randomness to repeat. A proof that assumes fresh coins in every session does not cover such an interface. Likewise, a denial-of-service attack may be important operationally while lying outside an impersonation experiment.

04 / System Security ISchnorr identification, message by message

The prover knows $a$ and the verifier knows $A=g^a$. The prover samples $x\leftarrow_{\$}\mathbb Z_q$, sends $X=g^x$, receives a uniformly sampled $c\leftarrow_{\$}\mathbb Z_q$, and returns $s=x+a\cdot c$. The verifier accepts precisely when

Correctness follows by substituting the honest response:

Why is the challenge sent after the commitment? If the attacker knows $c$ in advance, it chooses any $s$ and sets $X=g^s\cdot A^{-c}$. The verification equation then holds without knowledge of $a$. The same algebra later becomes a legitimate simulator in a proof: the simulator controls a challenge that a real impersonator does not control.

Two accepting transcripts with the same commitment and different challenges reveal the key:

This is a conditional extraction statement. It does not say that an eavesdropper can force honest executions to reuse a commitment, nor that every rewind of an arbitrary adversary succeeds. The probability argument appears in the second course.

05 / System Security IAttacks are executable arguments

Consider an incorrect replacement $s=x+a+c$ with verification $g^s=X\cdot A\cdot g^c$. Given an old accepting transcript $(X,c,s)$, an attacker sends the same $X$ and answers a new challenge $c'$ with $s'=s-c+c'$. The verifier accepts. The attack needs neither a discrete logarithm nor the old nonce.

Another incorrect replacement is $s=c\cdot(x+a)$ with verification $g^s=(X\cdot A)^c$. Choose $t\leftarrow_{\$}\mathbb Z_q$, set $X=g^t\cdot A^{-1}$, and answer any challenge with $s=c\cdot t$. This is a full impersonation algorithm: it chooses the first message before seeing the challenge.

In a third example the prover sends $W=g^{a\cdot x}$ and the verifier only checks $g^s=W^c$. An attacker can choose $t$, send $W=g^t$ and answer $s=t\cdot c$. The equation contains no effective binding to the claimed identity's public key. Correctness of the honest execution has concealed a missing authentication condition.

A useful attack write-up

State the adversary's known values, its chronological message sequence, and the final acceptance calculation. Do not define an early message using a challenge that has not yet arrived. Do not grant the adversary a secret absent from its model. An algebraic expression for a forged answer is not an attack if computing it requires solving the original hard problem.

Exercise. For each flawed protocol, change one equation and determine whether the attack still works. Do not assume that an arbitrary repair is secure. Give a complete attack transcript for every broken instance you find, including its public verification calculation.

A replay cache does not repair an affine response

Suppose the verifier remembers previous commitments and rejects a repeated $X$. For the broken response $s=x+a+c$, observe $(X_0,c_0,s_0)$, choose a fresh scalar $r$, and send $X_1=X_0\cdot g^r$. On receiving $c_1$, answer

The verifier obtains $g^{s_1}=X_0\cdot g^r\cdot A\cdot g^{c_1}=X_1\cdot A\cdot g^{c_1}$. The commitment is new, but the attack survives. A cache addresses byte-for-byte repetition, not this algebraic malleability.

For the second broken response $s=c\cdot(x+a)$, an observed transcript with $c_0\ne0$ gives $s_0\cdot c_0^{-1}=x_0+a$. Send $X_1=X_0\cdot g^r$ and answer $s_1=c_1\cdot(s_0\cdot c_0^{-1}+r)$. Again the equation holds. The earlier attack without any observed transcript is even stronger. When reporting a weakness, distinguish the weakest interface sufficient for the attack from an unnecessarily powerful one.

Work an attack all the way through

For the affine-response example take the toy parameters above, $a=7$, $x_0=9$, $c_0=3$. The broken response is $s_0=19$. Choose $r=4$, so $X_1=42\cdot2^4=14\pmod{47}$. For a new challenge $c_1=11$, answer $s_1=19-3+4+11=8\pmod{23}$. Both sides of the broken verification equation are $21\pmod{47}$. This is a successful impersonation with a new commitment, not merely a symbolic observation.

Checkpoint. Which input has disappeared from $s-c$? Why does changing the challenge no longer test knowledge of the secret? Explain the same failure without using the phrase “weak cryptography”.

06 / System Security ISimulation, deniability and a malicious verifier

An honest Schnorr transcript need not be evidence that a particular prover participated. Given $A$, choose uniform $c,s\in\mathbb Z_q$ and define $X=g^s\cdot A^{-c}$. The result passes verification. For any fixed $a,c$, the correspondence $x\mapsto s=x+a\cdot c$ is a bijection. Consequently this sampler has exactly the honest transcript distribution when honest nonces and challenges range over the full field.

This is a statement about a view, not an online impersonation. The sampler chooses $c$ before $X$; a real impersonator must choose $X$ before the honest verifier reveals $c$. The order of information makes the same equation useful in a proof and useless as a guaranteed attack on the live protocol.

Now let a malicious verifier choose $c=\H(\mathtt{id}\|A\|X)$. A transcript must satisfy this additional relation. Choosing independent $c,s$ and solving for $X$ no longer produces the required view. Under a random-oracle idealisation, a trial hits the additional relation with probability about $1/q$. This shows why the simple honest-verifier simulator is insufficient. It is not, on its own, a theorem that every form of deniability fails.

Anonymity, witness indistinguishability, zero knowledge and deniability are related but different. Anonymity hides which member acted. Zero knowledge concerns what the verifier learns beyond the statement. Deniability concerns what a transcript can establish to an outside party under a stated model. Always say whether that party has auxiliary information, whether the verifier is malicious and whether device randomness has been exposed.

Exercise. Write two transcript tests: the ordinary Schnorr verification equation, and that equation plus the hash-defined challenge. Generate simulated honest-verifier transcripts and compare the outcomes. Explain why the second test does not contradict honest-verifier zero knowledge.

07 / System Security ICompromised randomness: leakage, setting and reset

One research family, several ways to obtain useful equations. In the publication map, randomness leakage and setup also covers ephemeral leakage, ephemeral setting and randomness injection. Here ephemeral means used for one protocol execution. Setting refers to controlling these internal values, not merely choosing the public message to be signed.

These interfaces can expose the same algebraic weakness without being identical security experiments. Reset does not necessarily set a nonce to zero or to a known constant. A deterministic implementation may also derive different nonces for different messages despite a reset; establish actual reuse before applying the attack.

The nonce is temporary, but its exposure may compromise a permanent key. In an ordinary Schnorr transcript with known $x$ and nonzero $c$,

If $c=0$, that single response gives no such equation for $a$. This exceptional case must not be hidden by division by zero. With a uniformly random challenge it occurs with probability $1/q$.

If the attacker chose $x$ rather than learned it, the very same one-response calculation applies. With reuse, two accepting scalar responses for the same key and commitment satisfy

Subtract to eliminate the unknown nonce:

The inverse exists only when $c\ne c'$ modulo $q$. For signatures, different messages usually give different hash challenges, but the condition to check is the challenge inequality itself. Two unrelated nonces leave an unknown difference and do not justify this formula.

Worked example. In the group of order $23$ introduced above, let $a=7$, $x=9$, $c=3$ and $c'=11$. The responses are $s=7$ and $s'=17$. If $x$ is known, $(7-9)\cdot3^{-1}=7\pmod{23}$. If only repetition is known, $(7-17)\cdot(3-11)^{-1}=7\pmod{23}$. In the second calculation the attacker does not use $x$.

Choosing $x$ from a small range creates another route: enumerate candidates and test $g^x=X$. A large group cannot compensate for a nonce with very little entropy.

From the attack to the proof model

In a compatible chosen-nonce query model, the simulator can sample a nonce itself, submit it to the setting interface and return it as a leak. Thus security against that setting interface covers the corresponding sampled-and-revealed query. The converse does not follow automatically: observing a random nonce does not give arbitrary control over its value. Phase restrictions, adaptive choices and the timing of exposure still matter.

The modified Schnorr study addresses learning or setting prover ephemerals. Anonymous deniable identification, Section 2, additionally distinguishes chosen prover ephemerals in training from leaked verifier ephemerals during impersonation. These are useful reasons to group the papers together while retaining the precise interface in each proof.

A proof extractor can obtain the matching pair through rewinding or a forking lemma. A real attacker may obtain it through device reset. The cancellation is shared; the ability and probability of obtaining the pair must be justified separately. With a group-valued response, cancellation can instead produce a hard group element, not the scalar key. This distinction is developed in System Security II.

Exercise. Use the calculator above. Recover the same key first from a disclosed nonce and then from the two responses without using that nonce. Repeat with equal challenges and explain why inversion fails. Finally change the nonce between runs: identify the additional unknown rather than reporting a recovered key.

The local research demonstrations identification schemes, Okamoto identification and the leakage-oriented proof of concept complement this arithmetic example. Their equations and acceptance checks are useful to inspect; a browser demo is not a hardened signing device.

08 / System Security IWhen the verifier's randomness is exposed

The verifier also has a device and a random generator. Suppose its challenge $c$ is generated early and an oracle reveals it before the prover sends $X$. The attacker chooses $s$, computes $X=g^s\cdot A^{-c}$, sends $X$, waits for the already known challenge and sends $s$. This is now a valid chronological attack. Moving the challenge computation into an HSM does not help if that HSM's interface leaks the value too early.

The relevant property is unpredictability when the first message becomes fixed. It is not enough that the challenge was once sampled randomly. By contrast, learning a public challenge after the commitment is ordinary protocol behaviour, not a challenge-leakage attack. A reveal oracle needs a time of availability as well as a return type.

The two-flow example in the lectures

Here $\mathcal D_\ell$ is a digest of a canonically encoded group element, with a fixed $\ell$-bit output. Consider the Stinson–Wu-style classroom exchange. The verifier, which knows $A=g^a$, samples $r$ and sends $C=g^r$ together with $h=\mathcal D_\ell(A^r)$. The prover first checks $\mathcal D_\ell(C^a)=h$ and only then returns $Z=C^a$. The verifier tests $Z=A^r$. Honest correctness is $C^a=g^{r\cdot a}=A^r$.

The hash check is significant: a prover should not blindly act as an exponentiation oracle for an arbitrary received point. Nevertheless, if the verifier's $r$ is disclosed, an attacker can compute $A^r$ using the public key and impersonate the prover. No information about $a$ is needed. This is an attack in a stronger device-exposure model, not a claim that the normal transcript contains $r$.

What a device boundary must specify

Separate the long-term key store, random generator, protocol state and wire interface. An attacker may read one while being unable to read another. Power traces, timing, electromagnetic observations and injected faults are possible physical interfaces, but they do not all return an exact scalar. A theoretical oracle returning $x$ models a particular consequence of compromise; a real side-channel experiment must establish what it actually recovers.

For each proposed countermeasure ask which interface it removes. A hardware random generator does not prevent a program from logging its output. Deterministic nonce derivation can address accidental random-generator failure, but exposure of the derived Schnorr nonce still enables the algebraic attack. Domain separation and secret-dependent derivation have to be analysed together with the permitted exposure, not used as slogans.

09 / System Security IFrom identification to digital signatures

A signature can be verified after the signer has left. There is no live verifier to sample $c$. A Schnorr-style Fiat–Shamir construction derives the challenge from the statement and commitment. In the teaching profile used here,

The signature is $\sigma=(X,s)$. Verification recomputes $c$ from the received $X$, message and authenticated public key, then checks $g^s=X\cdot A^c$. This is a generic pedagogical profile, not a byte-compatible specification of a deployed signature standard. The older slides omit some context fields; they are explicit here to avoid cross-key and cross-protocol ambiguity.

In EUF-CMA, the adversary obtains signatures for messages of its choice and wins by returning an accepting signature on a message not previously signed. Strong unforgeability additionally rules out a new signature on an already signed message. These goals should not be silently exchanged.

If the challenge is only $c=\H(m)$, it is known before the commitment. An attacker chooses $s$ and sets $X=g^s\cdot A^{-c}$, producing an accepting signature. If the challenge space is tiny, guessing a challenge before selecting a commitment becomes feasible. Collision resistance alone is not a replacement for the assumptions of a random-oracle proof.

The Fiat–Shamir proof models $\H$ as a consistent random oracle. Its simulator may program previously unanswered queries; real software does not control its hash function in this way. The proof course explains the exact point where this distinction enters.

10 / System Security IThree signature failures, three different lessons

Missing commitment binding

If $c=\H(m)$, all required hash inputs are known before $X$ is chosen. Compute $c$, choose $s$ and set $X=g^s\cdot A^{-c}$. Return $(X,s)$ for $m$. Verification accepts with probability one. The attacker has not found a collision and has not inverted the hash. The construction asked the hash to bind the wrong data.

An algebraic “hash” that preserves the challenge

In a deliberately broken finite-field example, messages are scalars and $c=m+\operatorname{enc}(X)\pmod q$, where $\operatorname{enc}$ is a public scalar encoding. From a signature $(X_0,s_0)$ on $m_0$, choose $r$, and compute

The new challenge equals the old one, and $g^{s_1}=X_1\cdot A^{c_0}$. Choose a trial with $m_1\ne m_0$ to meet the fresh-message winning condition. In the integer-group slide example the public encoding is the represented integer reduced modulo $q$. It is not a cryptographic hash and must not be confused with hash-to-curve in BLS.

A challenge space small enough to search

Let $\mathcal{H}_{\mathrm{bad}}$ be a deliberately shortened scalar hash. If it has only $h$ possible outputs, choose a message $m$, trial response $s$ and trial challenge $c$, compute $X=g^s\cdot A^{-c}$ and test whether $\mathcal{H}_{\mathrm{bad}}(X,m)=c$. For fresh inputs in the ideal model the success probability is $1/h$ per trial, so the expected work is $h$ trials. A $20$-bit space is about one million possibilities, irrespective of how large the underlying group is.

An alternative starts from a signed message and searches for another message with the same challenge at the fixed commitment. This is a target preimage search for that challenge, with expected work about $h$, not the generic birthday-collision cost $\sqrt h$. A birthday collision between arbitrary hash inputs does not necessarily preserve the commitment or a signature already available to the attacker.

Why signing the “same text” may mean different bytes

The verifier authenticates bytes, not a rendered document. Include unambiguous field lengths, a protocol domain and the relevant key/context. Normalisation, invisible characters, ambiguous JSON encodings or omitted operation names can make an application interpret signed bytes differently. Changing the encoding is a protocol change: specify it, test both sides and do not silently accept multiple encodings of one scalar or point.

Exercise. Build the three broken constructions separately. For each, provide a forgery, show every verification equation, and state whether a signing query was needed. Then explain which one of message binding, commitment binding or challenge entropy failed. These are independent checks.

11 / System Security IAuthenticated key exchange and its attacks

Diffie–Hellman agreement alone is not authentication. Alice sends $X=g^x$ and Bob sends $Y=g^y$; both compute $g^{x\cdot y}$. A man in the middle can replace both values and establish a different secret with each endpoint. Encrypting subsequent traffic under those secrets does not retrospectively authenticate the exchange.

An authenticated key exchange, AKE, must bind the key to a protocol execution and intended peer. Distinguish key secrecy, peer authentication, key confirmation and forward secrecy. A party can derive a secret without knowing that its peer completed the protocol.

A common key-secrecy experiment returns either the tested session key or an independent random string of the same length. If the hidden choice is $b$ and the adversary guesses $b'$, one convention defines advantage as $|\Pr[b'=b]-1/2|$. Other papers multiply this by two. A comparison of bounds must use one convention consistently.

Follow the man in the middle numerically or symbolically

Alice sends $X=g^x$, which Eve replaces by $E_B=g^u$ on the way to Bob. Bob sends $Y=g^y$, which Eve replaces by $E_A=g^v$ on the way to Alice. Alice derives $E_A^x=X^v$; Bob derives $E_B^y=Y^u$. Eve computes both from $X,Y,u,v$ and can decrypt, modify and re-encrypt traffic. Alice and Bob need not share the same key for the application to appear functional.

Adding a static scalar to an exponent does not authenticate this exchange. If the first messages become $X=g^{x+a}$ and $Y=g^{y+b}$ but neither party validates a binding to $A$ and $B$, Eve can still replace the two points by points with exponents it knows. The honest equations contain secrets, yet the receiving party never checks that the sender used those secrets.

A signature can authenticate an exchange but not the intended peer

In the lecture's incomplete signed-DH exchange, the signature covers a session identifier, a role and the ephemeral values, but the accompanying identity is not bound under the derived key. Eve can replace Bob's signature by its own signature on the same values and replace the displayed identity by Eve. Alice's identity-to-signature check may pass while Bob continues the exchange believing Alice is his peer. Whether the final run is an unknown-key-share attack depends on the exact remaining messages and acceptance conditions; write those down rather than calling every substitution a full key-recovery attack.

This motivates a separate identity binding under the newly derived secret. It also explains why merely checking that some trusted certificate signed a pair of points is weaker than authenticating the intended peer in this session.

Forged identification inside a key exchange

The lecture also inserts the broken affine response into DH: the initiator sends $X$, the responder sends $Y$ and challenge $c$, and the initiator replies with a challenge for the responder and $s=x+a+c$. The responder's corresponding response has the same defect. The session key is derived from the DH points.

An attacker can use an old affine transcript to answer a fresh challenge with a new commitment, as shown in the identification chapter. It can make a peer accept the claimed identity without knowing the exponent of that commitment and therefore without necessarily knowing the DH session key. This establishes a false-authentication event. Calling it an unknown-key-share attack additionally requires exhibiting another honest session that holds the same key with a conflicting peer identity. Key recovery, false authentication and UKS are three separate claims.

12 / System Security IBinding identities: SIGMA and a replay lesson

SIGMA separates two jobs: signatures authenticate the ephemeral exchange, while a MAC under a DH-derived key binds the identity to that exchange. Let $K_{\rm mac}$ and $K_{\rm app}$ be separately derived from $g^{x\cdot y}$ and the transcript context. An explanatory three-message flow is:

1. Alice sends $X$.
2. Bob sends $Y$, his identity, a signature over the ordered ephemeral values and roles, and a MAC of his identity under $K_{\rm mac}$.
3. Alice sends her identity, the corresponding role-specific signature and a MAC of her identity.

The signatures are checked against trusted identity-to-key bindings. The MAC is not a public signature: it demonstrates consistency with the newly derived secret. Identity-protecting variants encrypt identity-bearing payloads and distinguish which peer's identity is protected against which observer. This outline is not a replacement for the detailed flows and model in Krawczyk's SIGMA paper.

Needham–Schroeder: encryption is not identity binding

In the public-key version, write encryption under Bob's public key as $\{\cdot\}_B$. The familiar core exchange is $\{N_A,A\}_B$, then $\{N_A,N_B\}_A$, then $\{N_B\}_B$. Alice might willingly start a run with a malicious participant, who reuses her messages to authenticate to Bob. The middle encrypted message does not identify the responder whose run it belongs to.

Lowe's repair binds Bob's identity into that message: $\{N_A,N_B,B\}_A$. Alice now rejects a response from a different peer than the one she intended. The lesson is not that one extra name secures every protocol; the corrected term closes this particular cross-session confusion. See Lowe's attack and repair.

Lowe's interleaving, without skipping a message

Alice intentionally begins with Eve, who is a registered participant with a valid key. Eve also starts a run with Bob while claiming to be Alice. Encryption is ideal in this example: Eve never decrypts a ciphertext addressed to Alice or Bob.

In the repaired middle message, Alice reads the responder identity $B$. Her local session expects Eve, so she refuses step 5. Certificates were not missing and encryption was not broken. The missing information was the relation between this reply and Alice's intended peer.

Key transport and a signature on too little context

Another lecture example has the responder choose a session key, sign only a hash of that key and encrypt the result to the requester. A malicious registered requester can decrypt the package and re-encrypt its contents to another participant. If that participant accepts the responder's signature without a recipient and session binding, the attacker knows a key that appears to have arrived from the responder. Encrypting the same signed object to a new recipient did not invalidate the signature.

Distinguish key transport, where one party chooses the key, from contributory agreement. Bind a transported key to its recipient, roles, algorithm, purpose and session. A secure key-transport design requires a complete construction and model, not just “sign, then encrypt”.

13 / System Security ICompromise patterns in AKE

KCI and deniable authentication

Let an authentication message be a ring signature for the ring consisting of Alice and Bob. Either participant can create such a signature. This can make a transcript unsuitable as transferable proof that Alice, rather than Bob, produced it. It also means that an adversary who steals Bob's long-term signing key can create that ring signature while claiming to Bob that Alice sent it.

This is the key-compromise impersonation issue in the lecture's deniable signed-DH example. The adversary knows its chosen DH exponent, so it can also form the MAC under its DH key with Bob. Replacing an ordinary signature with a ring signature changes the authentication claim. Ring unforgeability says that someone in the ring authorised the message, not that it was the particular member Bob hoped to authenticate.

An ephemeral-compromise example: KEA-style algebra

Write Alice's static key pair as $(a,A=g^a)$ and Bob's as $(b,B=g^b)$. They exchange $X=g^x,Y=g^y$ and derive a key from $B^x$ and $Y^a$ on Alice's side, and $X^b$ and $A^y$ on Bob's side, in the same order with the identities. Each pair matches algebraically.

An attacker impersonating Alice chooses $u$ and sends $X=g^u$. If Bob's ephemeral exponent $y$ is revealed, it can compute both $B^u$ and $A^y$. It knows Bob's derived key without knowing Alice's static secret. This is a failure under that reveal interface; it does not contradict a theorem whose freshness rule excludes the exposed session.

Seeds, exponents and NAXOS

In this NAXOS chapter, $\H$ is the separately domain-separated scalar oracle called $H_1$ in the original protocol; session-key derivation uses $\mathsf{KDF}$, the original $H_2$ role. These are different functions, not two names for one oracle. The transmitted point uses $x=\H(r_A,a)$, where $r_A$ is an ephemeral seed. The peer analogously uses $y=\H(r_B,b)$. Revealing the seed $r_A$ is not the same as revealing the exponent $x$. The derivation combines static and ephemeral inputs for a particular security model; the second course gives the three DH components explicitly.

To see why the distinction matters, suppose Eve sends $X=g^u$ and learns Bob's derived exponent $y$ from a malicious hash implementation. It can compute $A^y$, $B^u$ and $Y^u$, precisely the three components used by Bob. Learning only $r_B$ does not grant that computation without $b$. The attack concerns the stronger interface returning $\H(r_B,b)$, not an ordinary public hash query whose secret input Eve does not know.

Certified hash-derived contributions: the second eKCI example

In another historical example, Alice and Bob have certified static public keys $A=g^a$ and $B=g^b$. Their fresh random values are $r_A,r_B$. Write $h_A=\H(r_A,0)$ and $h_B=\H(r_B,0)$ for scalar hashes. They exchange $C_A=A^{h_A}$ and $C_B=B^{h_B}$, and compute

Separate labelled hashes of $Z$ supply two directional encryption keys and an application key. Under the directional keys, the parties exchange their random values and certificates. After decryption, Bob checks Alice's certificate and $C_A=A^{\H(r_A,0)}$; Alice checks the corresponding equation for Bob. This binds the received contribution to a public key and an opened random value, but it does not answer every compromise question.

Suppose Eve learns both Bob's static secret $b$ and his current $r_B$. Eve chooses its own $r_E$, sets $C_A=A^{\H(r_E,0)}$ while claiming Alice's identity, and receives $C_B$. It computes $Z=C_A^{b\cdot\H(r_B,0)}$, derives the directional keys and sends an encryption of $r_E$ with Alice's valid public certificate. Bob's commitment check passes. Eve never needed Alice's secret: it used Alice's public key to form the point and Bob's exposed local secrets to derive the key.

The forged first message must be a group element $A^{\H(r_E,0)}$, not a bare hash scalar; writing only the latter, as in the abbreviated attack slide, is a type error. The exposure here includes both relevant secrets of Bob's session, a combination many AKE freshness predicates exclude. The example explains that particular failure, not a break of a theorem that rules out that combination.

A certificate confirms a public-key binding. It does not guarantee the secrecy of the device's temporary inputs, nor does it stop an attacker from including somebody else's already public certificate in a message. State exactly which secrets are exposed and at what time before judging a repair.

A useful exposure ledger

For each accepted session record the owner, intended peer, role, received points, transcript identifier, key and completion time. Then add a separate list of reveal events with timestamps. Mark exactly which value each reveal gives the adversary. Check freshness after writing this ledger, rather than making the model exclude an attack just discovered.

Exercise. Compare revealing $(a,y)$ with revealing $(a,x)$ in a protocol that mixes long-term and ephemeral secrets. Explain why “two revealed values” is not a meaningful security classification by itself. Distinguish a later compromise after a completed matching session from a compromise that enables active impersonation during the exchange.

14 / System Security IEncryption: correctness, privacy and integrity

For public-key encryption, key generation returns $(pk,sk)$, encryption maps $(pk,m)$ and coins to a ciphertext $C$, and decryption maps $(sk,C)$ to $m$ or rejection $\bot$. Correctness requires successful recovery for ciphertexts produced by honest encryption.

An IND-CPA challenge encrypts one of two equal-length chosen messages. Public-key encryption needs no special encryption oracle because anyone has the public key. IND-CCA1 permits decryption queries before the challenge. IND-CCA2 also permits them afterward, except for the challenge ciphertext itself. Related ciphertexts are not generally excluded; resilience against their use is precisely part of the goal.

ElGamal is the right example of a limited guarantee

For a group-valued message $m\in G$, choose $r\leftarrow_{\$}\mathbb Z_q$ and set

The factors cancel because $C_1^a=g^{r\cdot a}=A^r$. Under the DDH assumption, this construction has an IND-CPA argument. It is malleable: for nonidentity $t\in G$, the related ciphertext $(C_1,t\cdot C_2)$ decrypts to $t\cdot m$. A CCA2 adversary can submit this different ciphertext and divide the answer by $t$. Correct decryption and CPA security did not imply CCA2 security.

For bit strings, a hybrid design derives a symmetric key from a shared secret and uses authenticated encryption with associated data, AEAD. Its nonce requirements, key derivation, ciphertext validation and context binding are part of the construction. “ElGamal plus a hash” alone is not a complete authenticated-encryption specification.

One-time pads and deterministic leakage

For $C=m\oplus K$ with a uniform, independent, message-length key used once, perfect secrecy is possible. Reusing $K$ gives $C\oplus C'=m\oplus m'$. This is not the same security setting as an encryption scheme with a reusable short key. Deterministic public-key encryption likewise exposes equality and permits trial encryption of a small candidate dictionary. These failures do not require breaking the underlying cipher.

15 / System Security IEncryption experiments and worked attacks

From ciphertext-only observation to CCA2

A ciphertext-only attacker has records but no chosen-input interface. A known-plaintext attacker also knows some corresponding plaintexts. A chosen-plaintext attacker selects inputs to encryption. A chosen-ciphertext attacker submits ciphertexts for decryption. An adaptive attacker chooses its next input using earlier answers; a nonadaptive attacker fixes its query list in advance.

These are interfaces, not names of encryption algorithms. Caesar substitution leaks statistical structure to ciphertext-only observation and is also broken under stronger interfaces. A genuinely one-time pad with an independent fresh pad for every message is not “broken by CPA” merely because the attacker can see encryptions of chosen messages. The lecture's pad failures require reuse or another violation of its one-time assumptions.

For IND security, the challenger generates a key and the adversary submits equal-length $m_0,m_1$. The challenger samples a hidden bit $b$ and returns $\operatorname{Enc}(pk,m_b)$. The adversary outputs $b'$. CCA1 stops access to decryption before the challenge. CCA2 continues that access but forbids the exact challenge ciphertext. It does not forbid every ciphertext mathematically related to it.

In these notes distinguish the guessing bias $\delta=|\Pr[b'=b]-1/2|$ from the normalised advantage $2\delta$. A perfect distinguisher has bias $1/2$ and normalised advantage $1$. An algorithm that always guesses zero has bias zero. Be explicit about this convention when comparing reductions.

Why addition over the integers is not a one-time pad

The formula $C=m+K$, with decryption $m=C-K$, is correct. It is not yet a secrecy theorem. There is no uniform distribution on all integers, and choosing $K$ from a finite interval can reveal information through the ends of the ciphertext range. In a finite group, adding a uniformly random independent group element does give a uniform mask. Reusing it gives $C-C'=m-m'$. The probability space, not the superficial similarity of formulas, determines which claim is valid.

ElGamal re-randomisation gives a second CCA2 attack

Let $C^*=(U,V)=(g^r,m_b\cdot A^r)$. Choose nonzero $t\in\mathbb Z_q$ and submit

This is a different ciphertext because $g^t\ne1$. Decryption returns

The oracle answer identifies the challenge message. This attack changes both components while preserving the plaintext. The earlier attack changes the plaintext by a known factor. Both satisfy the CCA2 rule forbidding only the exact challenge ciphertext.

Important boundary. The standard DDH game-hop proof given in System Security II establishes IND-CPA for ordinary ElGamal. It does not simulate an arbitrary pre-challenge decryption oracle and therefore does not, by itself, establish CCA1. We do not carry over the stronger CCA1 label from the historical slides without a separate assumption and proof.

Integrity, associated data and release of plaintext

For a modern application, authenticated encryption takes a key, nonce, plaintext and associated data. Associated data is authenticated but not encrypted: a record type, protocol version or sequence number can belong there. Decryption returns the plaintext only after authentication succeeds, or returns $\bot$. Applications must not act on unauthenticated provisional plaintext.

An AEAD nonce is not necessarily a secret. Its uniqueness requirement depends on the chosen construction. A Schnorr nonce, by contrast, must remain secret and must not be reused across distinct challenges. Sharing the word “nonce” does not make the requirements interchangeable. The AEAD interface in RFC 5116 is useful for separating these inputs.

Exercise. Give two distinct challenge messages and implement both ElGamal CCA2 transformations in a local simulator. Record the challenge, the modified ciphertext, the oracle result and the final guess. Add an assertion that the modified ciphertext is not byte-identical to the challenge.

16 / System Security IFrom a group equation to a system

Before doing group arithmetic, decode the input, check canonical representation and the required group or subgroup, and apply the construction's nonidentity rules. Use a vetted cryptographic random source. Keep scalar values separate from points and keep source groups separate when pairings are used. Never replace a hash-to-group operation by “hash to a publicly known scalar, then multiply the generator” without analysing the resulting known discrete logarithm.

Use independent domains for signatures, challenges, key derivation and commitments. Bind identities and roles into the appropriate authenticated data. Define replay handling and the point of acceptance. Erase ephemeral state where the platform actually supports doing so; ordinary JavaScript garbage collection cannot promise immediate secure erasure.

Timing, branches, memory access and fault handling belong to implementation security. A correct modular exponentiation routine may still leak through an exponent-dependent operation pattern. Conversely, noisy measurements that fail to distinguish two keys do not establish constant-time behaviour. Study the generated operations and use suitable implementation-analysis tools as well as tests.

The historical exercises refer to Charm and older curve choices. Preserve these as reproducible study examples, not as deployment recommendations. The MCL project documents its actual group operations and supported configurations. Pairing support does not itself validate a construction or its choice of security parameters.

17 / System Security IAttacking outsourced storage and computation

Cloud outsourcing makes the distinction between a valid equation and the intended service especially visible. The attacker may operate the storage or computation service itself. It does not have to send malformed packets or steal a user's key: it may simply retain less state or evaluate another function. The cloud course develops the constructions and corresponding countermeasures.

A server that deletes data but still passes

In Drzazga, Krzywiecki and Salin's multi-copy PDP cryptanalysis, the adversary changes its stored representation before the challenge. In one vulnerable variant, all tags share the same file-level hash. A retained block and tag can be scaled by the sum of the challenge coefficients. The verification equation accepts even though the other blocks are gone. In the probabilistic variant, the server can retain column sums and aggregated tags instead of the individual copies.

An attack report should identify four things: the promised state, the smaller retained state, the response algorithm, and the check that still accepts. It is not enough to say that “aggregation is insecure”: correctly designed authenticators also aggregate. The failure is that the particular verification relation loses the dimension it was meant to check. Work through the complete attack and repaired equations.

Homomorphic encryption and the wrong decryption interface

Let $C^*=\operatorname{Enc}_{pk}(m_b)$ be an IND-CCA2 challenge, with $m_0=0$, $m_1=1$ in a plaintext field of odd order. Suppose a public homomorphic operation can produce an encryption of a sum. The attacker forms a ciphertext

Correctness gives $\operatorname{Dec}_{sk}(C')=m_b+1$. Because the plaintext changed, $C'$ is not the prohibited challenge ciphertext. An unrestricted CCA2 decryption oracle returns either 1 or 2, which determines $b$. This is a permitted query in that experiment. It does not break a claimed IND-CPA property; it shows why a freely malleable encryption interface is incompatible with this unrestricted CCA2 promise.

In an application, a decryption endpoint that accepts arbitrary ciphertexts can recreate this problem. Authenticate the job, authorised inputs and recipient, and define which results may be released. Merely checking that a ciphertext decodes as the right group type is not authorisation. A MAC added to a ciphertext also changes which evaluations remain permitted; the whole protocol, including its evaluation and verification mechanism, needs analysis.

There is a separate malicious-server attack: return an encryption of zero instead of the requested encrypted inner product. Decryption succeeds because it is a valid ciphertext. Correct decryption does not certify correct evaluation. Verification of outsourced computation needs additional evidence tied to the agreed function and inputs. The two-level WebAssembly example deliberately demonstrates functional homomorphism, not such a proof.

Logs and authenticated false conclusions

A log entry signed by an authorised provider key may reliably establish who issued that entry. It does not establish that the underlying event was observed correctly or that no entries were omitted. Consider three different adversaries: one edits an already acquired file, another disables a logger before an event, and a third uses a stolen authorised session. A content hash can detect the first change relative to a trusted earlier digest; it does not solve the latter two cases.

Use the forensics chapter to specify the collection layer and the missing observations. Build a synthetic timeline with a gap and resist the temptation to report “nothing happened” during that gap. This is the evidentiary analogue of accepting a PDP equation without checking what retained state it implies.

18 / System Security ILaboratory programme

Run attacks only against your own code or a deliberately isolated teaching environment. Do not point an exercise at university services, public endpoints or another student's machine. For each exercise submit the model, code, inputs, transcript, acceptance result and an explanation of the result.

1. Identification. Implement Schnorr with clearly separated prover and verifier state. Test altered commitments, challenges and responses. Demonstrate the first two attacks in the attack chapter.
2. Nonce failure. Produce two signatures with one nonce and distinct challenges. Recover the key and check its public image. Also test equal challenges and explain why extraction fails there.
3. Signature binding. Implement the deliberately broken $\H(m)$ challenge and forge a signature without the key. Compare with the full teaching transcript hash. Do not describe the absence of a found attack as a proof.
4. Encryption. Implement group ElGamal, then show the related-ciphertext transformation. Submit both the decryption calculation and the corresponding CCA2 query sequence.
5. AKE. Trace a DH man-in-the-middle execution and a Needham–Schroeder interleaving. Record each endpoint's believed peer, actual key and acceptance point. Explain what the identity-binding repair changes.
6. Device model. Compare revealing a nonce, injecting a nonce and revealing a long-term key. Identify exactly which attacks become possible in each case.
7. Application security. Use the maintained OWASP WebGoat teaching project in a local, isolated setup. For selected exercises describe the trust boundary, the missing validation or access-control check, and a negative test for the repair. Application bugs and cryptographic-model failures should not be conflated.
8. Malicious cloud service. Implement the PDP deletion attack or the additive related-ciphertext attack against your own local verifier/oracle. Record the reduced stored state or modified ciphertext and the final acceptance result. Then test a repair appropriate to the claimed property. Do not send challenges or decryption queries to a real service.

For a stronger submission, add automated regression tests: honest transcripts pass, each modified field fails where intended, the insecure variants admit the documented attacks, and invalid scalars or group encodings are rejected before expensive arithmetic.

Submission structure

Keep the report reproducible. Give the group and scalar domains, exact encoding, software version and entry command. For each experiment include the adversary's permitted inputs, the messages in time order, the final check and a short explanation of what the result does and does not establish. Use fixed test vectors for regression tests, but cryptographic randomness in realistic executions. Never use a tiny teaching group to protect real data.

Separate the deliberately broken construction from the repaired one in code. A flag hidden inside a common verifier makes it too easy to test the wrong variant. In particular, never leave the insecure hash-to-known-scalar map enabled in a BLS example that is labelled as the real scheme.

19 / System Security IReview problems with worked answers

20 / System Security IPublished references

The explanations above are self-contained. These references supply original definitions, analyses and implementation specifications, not an alternative archive of the course.

• Schnorr. Efficient Signature Generation by Smart Cards. The identification/signature algebra used throughout both courses.
• Fiat and Shamir. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. From an interactive challenge to a message-dependent challenge.
• Pointcheval and Stern. Security Arguments for Digital Signatures and Blind Signatures. Random-oracle simulation and classical forking arguments; developed in the second course.
• Krawczyk. SIGMA: the SIGn-and-MAc Approach to Authenticated Diffie–Hellman and Its Use in the IKE Protocols. Roles of signatures, MACs and identity protection.
• Lowe. An Attack on the Needham–Schroeder Public-Key Authentication Protocol. Why ideal encryption does not prevent cross-session confusion.
• LaMacchia, Lauter and Mityagin. Stronger Security of Authenticated Key Exchange. Exposure models and NAXOS.
• Shoup. Sequences of Games. An organised way to justify changes in a security experiment.
• IETF. Hashing to Elliptic Curves, RFC 9380 and AEAD Interface, RFC 5116. Precise interfaces that prevent common implementation ambiguities.

Continue with System Security II: constructions and proofs. Its first chapters turn the transcript equations into explicit simulators and extractors, then explain the probability losses needed for a security theorem.