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.

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.

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.