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

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.