A 4-digit PIN plus 40 bits of padding is encrypted as one 64-bit block, either with a 64-bit block cipher or with a stream cipher / OTP using a 64-bit keystream. How does the brute-force cost to recover the PIN compare, and what does the result say about the slogan "a cipher is secure ⇔ brute force is impossible"?

With fixed, known padding, brute-forcing the stream cipher / OTP is far cheaper than brute-forcing the block cipher — you enumerate the 10 000 PINs, not $2^{64}$ keys. So the slogan only half-holds: impossible brute force is necessary, but not sufficient for security.

Setup: A 4-digit PIN and 40 bits of fixed padding (e.g., 0xEFFFFFFFFF) form one 64-bit block. It is encrypted twice — once with a 64-bit block cipher, once with a stream cipher (or OTP) of 64-bit keystream.

Block cipher brute force:

• Must search the key space: try each of $2^{64}$ keys, decrypt the block, check the 40 known padding bits
• Cost: $2^{64}$ trials — infeasible

Stream cipher / OTP brute force (fixed, known padding):

• Keystream is XORed with plaintext: $C = M \oplus K$
• Skip the key space — enumerate the plaintext space instead: only 10 000 possible PINs
• For each candidate $P_i$, the implied keystream $K_i = C \oplus (P_i \text{ || padding})$ is fully determined by the known padding bits — you don't need to "guess" a key at all
• Cost: $\approx 10^4$ trials — orders of magnitude cheaper

The apparent paradox: The OTP is supposed to be perfectly (information-theoretically) secure, yet brute-forcing the PIN here is almost trivial. Contradiction with the slogan?

Resolution: Replace the 40 bits of fixed padding with 40 random bits. Now every PIN candidate is equally consistent with the ciphertext — the attacker can still try all $10^4$ PINs, but no candidate is distinguishable from any other. The OTP is genuinely perfectly secure.

Slogan correction: "Cipher secure ⇔ brute force impossible" is wrong as a biconditional.

• Necessary: if a cipher is secure, brute force on it must be impossible (or useless).
• Not sufficient: "brute force is hard to mount" alone doesn't prove security — slide 42 shows brute force on the OTP is easy, yet (with random padding, slide 43) the OTP is still perfectly secure because the attacker can't distinguish the right answer.

The real predicate isn't "is brute force computationally possible?" — it's "does brute force yield a distinguishable result?"

Go deeper:

• One-time pad (Wikipedia) — perfect secrecy, and why easy brute force still doesn't break it.