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

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.