Past exam of the computer science course of the University of Oxford / 2015 / Computer security / 3 / e

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.