Past exam of the computer science course of the University of Oxford / 2015 / Computer security (A12073W1)

Solutions to all three questions of the examination dated 15 June 2015. The cover permits candidates to answer two questions.^[ref]

The authentication claims in Question 2 require particular care: the printed third message permits substitution of Bob's key ticket after his cryptographic nonce becomes public. The solutions distinguish the intended freshness argument from the Dolev-Yao model attack that defeats Bob's authentication. This is a property of the printed protocol, rather than a missing part of the source.

The Bell-LaPadula model protects information confidentiality by controlling information flow between security levels. Its simple security property says that a subject may read only objects whose classification does not exceed its maximum clearance:Thus a user cleared for confidential material cannot directly read a secret file. A readwrite permission includes reading and must satisfy the same restriction. This is an access control rule about who can learn existing contents; it says nothing by itself about where a cleared subject can subsequently copy them.

The Bell-LaPadula star property restricts information flow using the subject's current level. With the paper's distinction between blind writing and reading, its usual current-level formulation isHere $f_C(s)\le f_S(s)$ also holds. The first row means that reading above the current level is forbidden; the second is the familiar prohibition on writing down. Their conjunction gives the third row. Blind writing upwards is allowed because it need not disclose the higher file's contents to the writer.

For example, a subject operating at secret level cannot copy a secret file into a public file, even though its clearance would permit reading both files. More generally, any simultaneously readable object must be at most as highly classified as any writable object. A subject must not evade the rule by retaining secret information and then lowering its current level: level-changing transitions need their own safe treatment of retained information and open accesses.

First, the Bell-LaPadula model is a information confidentiality policy. It permits a low-level subject to overwrite a more highly classified object by blind writing. That can destroy a high-level file or introduce false data without disclosing its old contents. Thus it does not supply a data integrity policy, and it also does not ensure service availability. Modern multiuser operating systems require protection against modification and resource exhaustion as well as disclosure.

Second, a single hierarchy of classifications cannot express ordinary independent user ownership and selective collaboration. Two users at the same level may still need different permissions on their respective files; conversely, an authorised publication may deliberately release selected information to lower levels. The simple model lacks those owner-specific permissions and controlled release decisions. Adding discretionary access control, categories and explicit declassification mechanisms is substantial additional policy.

For distinct prime numbers $p,q$, compute the Euler totient functionThe RSA cryptosystem private exponent is a modular multiplicative inverse of the public exponent:Use the extended Euclidean algorithm on $3$ and $\phi (n)$. It produces integers $u,v$ with $3u+\phi (n)v=1$, and reducing $u$ modulo $\phi (n)$ gives a suitable positive $d$. Searching through possible exponents is unnecessary.

To see correctness even for a plaintext sharing a factor with $n$, write $3d=1+t\phi (n)$. Modulo $p$, either $m=0$ or Fermat's little theorem gives $m^{3d}=m$; the same holds modulo $q$. The Chinese remainder theorem then gives $c^d=m(\mathrm{mod}n)$. One may alternatively invert $3$ modulo $\mathrm{lcm}(p-1,q-1)$, but inversion modulo $\phi (n)$ is sufficient for this paper.

The essential exponent condition isOtherwise the modular multiplicative inverse defining $d$ does not exist. For large prime numbers greater than three, this is equivalent toIf, for example, $p\equiv 1(\mathrm{mod}3)$, the multiplicative group modulo $p$ has order divisible by three, and cubing is not a bijection; distinct plaintexts can have the same ciphertext. Unique decryption of all messages would then be impossible.

The prime numbers must also be distinct for the displayed totient formula, and selected sufficiently large and independently that integer factorization of $n=pq$ is infeasible. A small factor, equal factors, or an exceptionally small difference between $p$ and $q$ gives an avoidable factorisation weakness. These size and generation conditions address security; the congruence condition addresses invertibility of cubing.

All calculations are in modular arithmetic modulo $n$. Expand the two expressions appearing in the proposed quotient:The first is exactly $m$ times the second. Multiplication by the assumed modular multiplicative inverse therefore givesThe representative in $\{0,\dots ,n-1\}$ is the plaintext. This RSA related-message attack uses a relation between messages to turn two cubic equations into a linear equation; it does not recover the private key or factor $n$ in the invertible case.

For each candidate nonzero offset $k\in \{1,\dots ,2^{16}-1\}$, expansion givesConsequently, if $D_k$ is invertible, the candidate isCompute the modular multiplicative inverse using the extended Euclidean algorithm, then verify both $m_k^3\equiv c_1$ and $(m_k+k{)}^3\equiv c_2(\mathrm{mod}n)$. The RSA cryptosystem cubing map is a bijection, so an accepted candidate cannot be a different plaintext with the same first ciphertext. This costs fewer than $2^{16}$ trials, each involving polynomially many operations in the bit length of $n$.

There is a useful way to handle every denominator exception for a correct nonzero $k$. Compute $g=\gcd (D_k,n)$. If $1<g<n$, this greatest common divisor factors $n$, allowing ordinary RSA cryptosystem decryption. If $g=n$, then $D_k=0(\mathrm{mod}n)$. The permitted prime numbers are $2(\mathrm{mod}3)$ and much larger than $k$, so $k$ is invertible modulo each. The equation $m^2+km+k^2=0$ would make $m/k$ a nontrivial cube root of one, impossible in a group of order coprime to three. Thus $g=n$ cannot occur for the correct nonzero offset under these hypotheses.

If the bound in the question is read as also allowing $k=0$, then $c_1=c_2$ and there is no additional information: the problem reduces to inverting a single ordinary RSA cryptosystem ciphertext. The small-offset attack requires a nonzero difference; that is the natural reading of distinct related messages.

Avoid constructing the huge integers $c^{3^j}$ explicitly. Maintain $a_0=c$ and $a_j=a_{j-1}^3\mathrm{mod}n$, computing $g_j=\gcd (a_j-c,n)$ after each step.

In case (1), the nontrivial greatest common divisor $g_k$ is one of the prime factors $p,q$. Divide $n$ by it, compute $d$ with the extended Euclidean algorithm, and return $c^d\mathrm{mod}n$.

In case (2), $a_k=c(\mathrm{mod}n)$. The preceding value satisfies $a_{k-1}^3=c(\mathrm{mod}n)$. Cubing is a bijection on the residue classes modulo $n$, so there is only one such cube root, namely the original plaintext $m$. ThereforeFor $k=1$, the preceding value is $a_0=c$; a fixed point is its own plaintext. Keeping the previous iterate makes the recovery immediate once the RSA cycling attack succeeds.

Take the positive integer $k$ whose existence is allowed by the question and writeModulo $p$, if $c=0$ then $c^{3^k}=c$ directly. Otherwise Fermat's little theorem applies, since $3^k-1$ is a multiple of $p-1$. Hence $c^{3^k}=c(\mathrm{mod}p)$. The same two-case argument works modulo $q$. By the Chinese remainder theorem,soThis also covers a ciphertext that is not coprime to $n$; applying Euler's theorem without checking that hypothesis would miss this detail. Equivalently, repeated application of a permutation on a finite set eventually returns to the starting point, although the arithmetic argument gives the requested sufficient exponent.

The fact that a nontrivial factor usually appears before a full return does not say that either event appears soon. Each iteration of the RSA cycling attack is inexpensive, but the number of iterations can be enormous. The multiplicative orders governing returns modulo $p$ and $q$ need not be small, and writing down a large return exponent does not provide a fast way to search the preceding iterations.

If this procedure factored arbitrary well-generated RSA cryptosystem moduli in feasible time with substantial success, it would solve the associated integer factorization problem efficiently. If it instead rapidly returned the predecessor of a ciphertext without factoring, it would solve the RSA inversion problem. Both are intended to be infeasible for appropriate parameters. Efficient integer factorization certainly breaks RSA cryptosystem security; the reverse implication for general RSA inversion problem algorithms is not known.

Thus the stated observation alone provides no serious general attack on well-generated parameters. It also does not prove a lower bound: special moduli or messages with short cycles can be weak, and the hardness claims are computational assumptions.

Bilateral authentication means that each participant obtains assurance of the other's identity and participation in the relevant run: Alice authenticates Bob and Bob authenticates Alice. An observed name in a message is not such assurance. The protocol must prevent an adversary from supplying the evidence while the named peer is absent.

Session key transport means conveying an already selected session key securely to its intended users. Here Tim selects $k_{AB}$ and sends it inside separate public-key-encrypted tickets for Alice and Bob. This differs from having Alice and Bob jointly derive a key to which both contribute.

A trusted third party is an additional participant whose correct behaviour and protection of its secret state are assumptions on which the other parties rely. Here Alice and Bob rely on Tim to associate identities with the right public keys, generate fresh session keys, and keep the long-term shared secrets confidential.

Tim is allowed to know $k_{AB}$, so the intended cryptographic confidentiality claim excludes the network adversary, rather than excluding Tim. Correct behaviour by Tim does not make every message purportedly sent by Tim authentic: the recipients must still verify the relevant evidence.

In the Dolev-Yao model, an adversary controls the network: it can intercept, suppress, delay, replay and redirect messages, impersonate network senders, and construct messages from values it knows. In particular, it can concatenate or split unprotected tuples, and can apply encryption using any known public key or known symmetric key.

Cryptography is idealised. Without the required private key or symmetric key, the adversary cannot recover a protected plaintext or construct an otherwise unavailable protected value. It cannot invent an unknown long-term secret merely because the containing ciphertext is visible. Protocol failures arise from the arrangement of messages even when these cryptographic primitives behave perfectly.

Alice's own freshness evidence is the ticketAfter decryption, she checks her pending cryptographic nonce, the long-term shared secret and both identities. Only Alice and Tim know ${secret}_A$; with honest Tim and an unpredictable new ${nonce}_A$, a valid matching ticket establishes that Tim generated this session key after that challenge was issued. A merely unused but predictable challenge does not establish that temporal ordering.

The claimed authentication of Alice to Bob, however, is false for the printed protocol. To exhibit the failure, let $I$ initiate message 1 using Alice's name while Alice is absent. Bob and Tim carry out messages 2 and 3 normally. Write the genuine message 3 as $(U,b,V)$, where $b={nonce}_B$ and $V=E_{{pk}_B}(A\Vert B\Vert k_{AB})$. The adversary intercepts it, learns the unencrypted $b$, and chooses a symmetric key $z$ of its own.

The adversary sends BobBob's checks of $b$ and the ticket identities pass, because anyone can encrypt using his public key. Bob sends message 4 using $z$; the adversary suppresses that message and returns $E_z(\text{Hello Bob})$ as message 5. Bob accepts Alice, although Alice has done nothing. No encryption has been broken.

The tempting intended argument is that only Alice, Bob and Tim could know the transported key, so message 5 proves Alice's participation. The substituted ticket invalidates its premise: Bob's accepted key is $z$, which the adversary knows.

Alice can still authenticate Bob when she accepts a genuine fresh ticket and successfully checks $E_{k_{AB}}(\text{Hello Alice})$. The session key inside her ticket is Tim's genuine key, protected by her public key together with ${secret}_A$. Tim gives that same key only to Alice and to the holder of Bob's private key. The adversary cannot derive it, and honest Tim does not send the greeting. Alice has not sent that greeting either. Thus the matching greeting is evidence that Bob obtained the key and participated. The different final greetings prevent simply reflecting Alice's own confirmation back at her.

Bob's intended freshness test is that ${nonce}_B$ was hidden in his request encrypted for Tim, so a matching answer must follow Tim's processing of that request. This establishes that Tim revealed that cryptographic nonce; it does not authenticate the adjacent ticket. The substitution attack in solution may use an old adversary-known $z$ instead of a fresh one. Bob accepts it even though its freshness is false.

The defect is the absence of a cryptographic binding between Bob's cryptographic nonce and his key ticket. A repair must bind the identities, both cryptographic nonces and the session key under message authentication verifiable as Tim's, for example a digital signature by Tim over the response, checked before Bob accepts. Merely moving the nonce inside a public-key-encrypted ticket is insufficient once an attacker knows or predicts it: anyone can create such an encryption.

The final messages contain fixed greetings, rather than a fresh challenge for their particular run. Their freshness is inherited entirely from the session key. If a key is reused, a previously recorded $E_k(\text{Hello Alice})$ or $E_k(\text{Hello Bob})$ becomes acceptable evidence again. An adversary can then mount a replay attack without knowing $k$ and without the purported speaker taking part in the new run.

Reusing a previously compromised session key is worse: the adversary can create both confirmations and read protected traffic. Fresh independent session keys limit that reuse, although they cannot fix the unauthenticated-ticket flaw shown in solution.

An unpredictable random $64$-bit cryptographic nonce is better for Alice than a predictable counter, provided repetitions are detected or made sufficiently unlikely. Alice wants a matching ticket to imply a response to her present challenge, and the protocol lets anyone ask Tim for a ticket containing a chosen ${nonce}_A$.

Suppose an adversary predicts that Alice's next challenge for Bob will be $a$. Before Alice starts that run, the adversary sends $(A,B,a)$ to Bob as message 1. Bob asks Tim for a session key $k$ and returns the genuine pair $(U,E_k(\text{Hello Alice}))$ in message 4. The adversary stores that pair and lets the early run lapse. Later, when Alice really emits $(A,B,a)$, the adversary blocks it and delivers the stored pair. Alice's ticket and greeting checks pass, despite the key and Bob's participation predating her run. This is a preplay attack on freshness and recent participation. Bob need not accept Alice's eventual message 5 for Alice's acceptance to have failed its freshness goal.

Success requires the predicted value and identities to match, an early run that yields the matching ticket and greeting, and Alice to accept solely from the outstanding value without additional expiry or run binding. No session key disclosure is needed to defeat freshness; if that old key has also been compromised, impersonation and loss of cryptographic confidentiality follow as well.

A guess at a particular uniformly random value has probability $2^{-64}$ per independent attempt, with success approximately $r/2^{64}$ for $r$ distinct guesses when that ratio is small. Random choice does not itself guarantee uniqueness: among $t$ independent values the birthday problem collision scale is approximately $t(t-1)/2^{65}$. Counter uniqueness and unpredictability are different requirements.

Bob especially needs unpredictability, because ${nonce}_B$ is intended to be secret until Tim processes the request. A predictable counter destroys even that limited assurance.

If the adversary knows Bob's next value $b$, it initiates a run with Alice's name and intercepts Bob's request. Without consulting Tim, it chooses a key $z$, constructs $V^{\ast }=E_{{pk}_B}(A\Vert B\Vert z)$, and sends $(U^{\ast },b,V^{\ast })$ as message 3, with any suitably shaped opaque ticket $U^{\ast }$ for Alice. Bob cannot inspect that ticket. He accepts $z$, sends message 4, and accepts the adversary's $E_z(\text{Hello Bob})$. Alice and Tim need not participate.

This preplay attack requires a correct prediction of Bob's outstanding value, knowledge of his public key, and the ability to intercept or race the genuine response. Observing an earlier unencrypted response may expose a counter value from which to predict the next. With an independent uniformly random hidden $64$-bit value, blind prediction succeeds with probability $2^{-64}$ per attempt.

In particular, random cryptographic nonces do not make the printed protocol sound. After the genuine message 3 reveals $b$, the adversary can use exactly the substitution in solution. Predictability allows an earlier attack without Tim; lack of response binding allows an attack even with perfect unpredictability.

A denial-of-service attack can exploit both an honest relay and replay at Tim. The adversary repeatedly sends cheap unauthenticated message-1 requests naming Alice and Bob. Bob then performs the public-key encryption in message 2, and Tim performs a private-key decryption, generates a session key, looks up the users' records and performs two public-key encryptions. The adversary's first messages contain no cryptographic work.

Alternatively, after observing one valid message 2, the adversary submits copies directly to Tim. It remains well formed; the printed protocol has no request-replay cache. Tim's promise to reject malformed requests does not imply duplicate suppression. Each replay can provoke the expensive operations again. If such a cache is added, the repeated-message-1 method still induces distinct requests through Bob unless admission is controlled.

Place a proof of work gate before Tim performs the expensive private-key decryption in message 2. Binding the puzzle to the whole request prevents solving a cheap puzzle once and reusing it with different tickets.

For example, let $R$ be the exact encoding of message 2, including identities, Alice's cryptographic nonce and Bob's encrypted component. On receiving a proposed request, Tim does only cheap length and format checks and returns a fresh challenge $r$, an expiry time $t$, a difficulty $d$ and a cookieHere $s_T$ is Tim's cookie secret and the message authentication code prevents alteration of the challenge or difficulty. Tim need not retain large amounts of per-request state merely to issue the cookie.

The requester finds a suffix $w$ such thatUnder the usual unpredictable-hash-output model, this takes an expected $2^d$ trials; verifying a proposed suffix needs one cryptographic hash function evaluation after checking the request digest and cookie. Preimage resistance motivates search difficulty, but the exact $2^d$ estimate also uses that distribution assumption.

The requester returns $(R,r,t,d,\tau ,w)$. Before any expensive decryption, Tim verifies the cookie, expiry, work and request binding, and atomically records that this challenge has been consumed. Repeated submissions of a consumed challenge are rejected cheaply. Short expiry bounds the storage needed for spent challenges. A cookie alone is insufficient: without one-use enforcement, the attacker could replay a single valid solved request indefinitely.

To charge the work to the initiator rather than Bob, Bob can relay the challenge to Alice and forward her solution. The adversary's fake Alice must then solve each puzzle instead of making honest Bob do it. Tim must issue challenges and reject bad proofs with bounded inexpensive processing, and difficulty should be chosen so that many verified requests require substantial aggregate work. This mitigates the computational denial-of-service attack; it does not correct the separate authentication flaw.

In a ciphertext-only attack, the adversary sees ciphertexts but has no supplied corresponding plaintexts. In a known-plaintext attack, it also knows one or more matching plaintext–ciphertext pairs. In a chosen-plaintext attack, it can select plaintexts and obtain their encryptions, possibly choosing later inputs from earlier results.

The ordinary exhaustive key search is a known-plaintext attack: given $x$ and $c=E_k(x)$, try candidate keys $k^{\prime }$ and compare $E_{k^{\prime }}(x)$ with $c$. A uniformly selected $m$-bit key has average position $(2^m+1)/2$ in any fixed search order, so

This counts testing until the actual key is reached. One known pair may leave false candidate keys when $m$ is large relative to the block length $n$; additional pairs distinguish them. If a plaintext has recognisable redundancy, a ciphertext-only attack can sometimes test keys by that redundancy instead, but this is an additional assumption rather than the standard supplied-pair setting.

Perfect secrecy means that observing the ciphertext changes no probability concerning the plaintext. For every distribution of the message $X$, and every $x,c$ with $\mathrm{Pr}(C=c)>0$,Equivalently, for every pair $x,x^{\prime }$ the conditional probability distributions of the ciphertext are identical:The randomness here comes from independent key generation and any encryption randomness. The claim is information theoretic: unlimited computation cannot extract information about $X$ from $C$ beyond what was known beforehand.

Let $s=k\oplus \mathrm{rev}(k)$ be the effective mask. For each position $i$,Thus the mask is always a palindrome, even though $k$ itself is uniformly random. The exclusive or of the ciphertext bits in a mirror pair isbecause the equal mask bits cancel. The observer learns the corresponding plaintext parity exactly. If $n$ is odd, the middle mask bit is also zero, so the middle plaintext bit is exposed directly.

An explicit failure of perfect secrecy works for every $n\ge 1$. Choose $X$ uniformly from $0^n$ and $10^{n-1}$. For $X=0^n$, the ciphertext is a palindrome with probability one. For $X=10^{n-1}$ and $n\ge 2$, toggling just the first bit breaks the mirror equality, so the ciphertext is a palindrome with probability zero. For $n=1$, the effective mask is zero and $C=X$. Observing $C$ therefore distinguishes these two messages perfectly.

There are only $2^{\lfloor n/2\rfloor }$ possible effective masks, each equally likely. Hence even a fresh $n$-bit key supplies at most $\lfloor n/2\rfloor$ independent masking bits in this construction. Choosing a long, uniform, one-use key is insufficient if the encryption transformation collapses its randomness.

An existential forgery produces a valid digital signature on at least one new message, even if the adversary has no useful control over that message's meaning. A universal forgery gives a way to forge a digital signature on an arbitrary specified message. Recovering the private key suffices for a universal forgery, but is not required if another general signing method exists.

In a key-only signature attack, the adversary knows the verification public key and the public scheme. In a known-message signature attack, it additionally obtains valid message–digital signature pairs whose messages it did not choose. In a chosen-message signature attack, it can ask for digital signatures on messages it chooses, possibly adaptively. Its final forged message must not be one of the messages already submitted for signing; otherwise simply returning a supplied pair would count as a forgery.

For authenticate-then-encrypt, write the intercepted pair as $(c,t)=(E_k(x),E_k(s))$, where $s=f(sk,x)$. Each trial key $k^{\prime }$ givesThe adversary can check the public relationThe true key always passes. An incorrect key will generally fail, and further intercepted pairs can eliminate accidental matches. This gives a ciphertext-only attack with a useful key-testing predicate even when the plaintext has no recognisable format. It makes exhaustive key search applicable with less prior information; it does not reduce the generic key-space size below $2^m$.

The usual approximate false-pass chance $2^{-n}$ is an ideal-behaviour estimate, not a consequence of the bare permutation identities alone. The decisive point is that the encrypted digital signature supplies publicly checkable redundancy once a candidate decryption key is tried.

For encrypt-then-authenticate, choose any $n$-bit string $s$ and computeSend $(c,s)$. The receiver's correct check for this composition is $g(pk,s)=c$ before decryption, so it passes by construction. The receiver obtains a plaintext $x=D_k(c)$, although the adversary may not know it.

The finite domains justify the signature relation: $g\circ f$ is the identity on $2^n$ messages, so $f$ is injective and therefore bijective. Hence $g=f^{-1}$ and also $f\circ g$ is the identity. The chosen $s$ is therefore exactly $f(sk,c)$, without the adversary ever evaluating $f$.

This is a key-only signature attack against raw unrestricted trapdoor signing. It does not invert $g$ at a chosen target and does not contradict the assumption that signing an independently specified new message is hard. It exploits choosing the digital signature first. The observation concerns the paper's raw construction, rather than every encrypt-then-authenticate scheme.

For encrypt-and-authenticate, the transmitted pair is $(E_k(x),s)$ with $s=f(sk,x)$. The recovery map is public, so any observer computesNo symmetric key, exhaustive key search or oracle is needed. Publishing this message-recovery digital signature reveals the entire plaintext and breaks cryptographic confidentiality outright. A digital signature of a suitable digest would have different leakage properties, but the printed construction signs the raw block.

The standard attack on this raw trapdoor construction chooses a candidate digital signature $s$ first, computes $y=g(pk,s)$, and uses a failure of preimage resistance to find $x$ with $h(x)=y$. Thenso $(x,s)$ verifies. The resulting message is selected by the inversion procedure, rather than being an arbitrary prescribed document. This is an existential forgery under a key-only signature attack whenever the inversion weakness applies with nonnegligible success to those sampled digests.

The phrase “fails to be preimage resistant” must be read with its target distribution. Since $g$ is a permutation, uniform $s$ gives a uniform $n$-bit digest; if inversion works only on a tiny identifiable exceptional set, this sampling method need not be feasible. Merely knowing a valid signed message and recovering that same message from its digest is not a new forgery. Producing a different message there requires a failure of second-preimage resistance. Part solution removes the coverage qualification by explicitly granting inversion at every digest.

A failure of collision resistance supplies distinct messages $x,x^{\prime }$ withAsk the legitimate signer to sign $x$, obtaining $s=f(sk,h(x))$. Output $(x^{\prime },s)$ without ever requesting a digital signature on $x^{\prime }$. Its verification succeeds becauseThusThe adversary chooses the collision pair, but cannot in general insist that one member equal an independently specified target. A known-message signature attack would require the stronger ability to collide with an already signed message; finding an arbitrary collision alone does not provide that.

Choose any candidate digital signature $s$, compute $y=g(pk,s)$, and invoke the granted algorithm to find $x$ with $h(x)=y$. Output $(x,s)$. Every chosen $s$ now leads to a valid message, with no need to search for a digest on which inversion happens to work.

This is stronger coverage than the generic failure discussed in solution, but it does not by itself give a universal forgery. For a target message $x_{\ast }$ fixed beforehand, the adversary needs $s$ satisfying $g(pk,s)=h(x_{\ast })$, which inverts the trapdoor map $g$. Inverting $h$ instead produces some message for a chosen digest and does not compute that $s$.

Nor does an arbitrary preimage algorithm necessarily produce a message different from $x_{\ast }$ when invoked on $h(x_{\ast })$: it may return $x_{\ast }$ itself. Thus a universal forgery under a chosen-message signature attack needs an additional alternative-preimage guarantee, precisely the distinction supplied in solution.

The stated ability is a complete failure of second-preimage resistance. Given an arbitrary target message $x$, compute $x^{\prime }\ne x$ with $h(x^{\prime })=h(x)$. Ask the signer for a digital signature on $x^{\prime }$ only, obtaining $s=f(sk,h(x^{\prime }))$. Thenso $(x,s)$ is a forgery of the chosen target. The inequality $x^{\prime }\ne x$ ensures that the adversary has not requested the target's own digital signature.

Under a known-message signature attack, the same weakness also gives an existential forgery: take an observed signed $x$, find its different second preimage, and reuse the digital signature. The universal forgery claim uses the stronger chosen-message signature attack capability to request the companion of whichever target was specified.