Cryptanalytic attack models and brute-force effort

Two ways in

There are exactly two approaches to attacking a conventional scheme. Cryptanalysis exploits the structure of the algorithm, usually together with some knowledge of the plaintext, to deduce a particular plaintext or — much worse — the key. Brute force simply tries every possible key on a piece of ciphertext until an intelligible translation appears. The two are not equally severe: recovering one message loses one message, while recovering the key loses all traffic sent under it, past and future.

What the analyst is assumed to have — the five models

Every model assumes the analyst already knows the encryption algorithm and holds the target ciphertext. They differ only in what is added on top. Ranked by increasing power to the attacker:

1. Ciphertext only — the algorithm and the ciphertext, and nothing else.
2. Known plaintext — plus one or more plaintext–ciphertext pairs formed with the secret key. The analyst did not choose them; they simply became known.
3. Chosen plaintext — plus ciphertext for plaintext messages the analyst selected.
4. Chosen ciphertext — plus the plaintext for ciphertext blocks the analyst selected. The mirror image of the previous model, and the one a learner who reads the word "chosen" and stops will confuse it with.
5. Chosen text — both of the two above at once. The most powerful model there is.

A close relative of the known-plaintext model is the probable-word attack: the analyst does not have a pair, but knows that a file of a certain type begins with a standard header, or that a message carries a fixed banner or copyright block at a known offset, and treats that guess as known plaintext.

Worked example — one channel, escalated through all five

A depot sends stock orders over a link encrypted with a fixed 40-bit-key cipher we will call HARBOUR-40.

Ciphertext only. The analyst taps the link and captures traffic. With nothing else to go on, the options are brute force or statistical attack on the ciphertext's structure. Only a weak algorithm actually falls here.

Known plaintext. The analyst learns that every order begins with the fourteen bytes DEPOT-ORDER-V2. That is a plaintext–ciphertext pair for the first block, handed over for free, and it is now possible to test a candidate key instantly instead of having to recognise plaintext by eye.

Chosen plaintext. The analyst places an order through the depot's public web form, knowing the text will be encrypted and sent down the same link under the same key. Now the plaintext is not merely known but selected — the analyst can pick inputs that make the algorithm's structure easiest to probe. This is the model that gets tested most often, and the giveaway is any stem in which the attacker gets to pick the plaintext first and see what comes out.

Chosen ciphertext. The analyst instead sends doctored ciphertext to the receiving end and observes what comes out — the receiver is being used as a decryption oracle.

Chosen text. The analyst has both handles at once.

Here is the design bar that the examiner is really after: an algorithm that fails to a ciphertext-only attack is simply weak, and a serious encryption algorithm is designed to withstand a known-plaintext attack.

Brute force costs half the key space, on average

A brute-force attack tries keys until one produces intelligible output. On average the right key turns up halfway through the key space, so a $k$-bit key costs about $2^{k-1}$ trials, not $2^k$. Dropping the factor of a half is the most common way to lose marks on a key-space question.

Worked example. A 56-bit key at $10^9$ trials per second. The average effort is $2^{55}$ trials. Recompute it rather than trusting a printed exponent: $2^{55}=3.6\times 10^{16}$, so the time is $3.6\times 10^{16}/10^9=3.6\times 10^7$ seconds, which is about 1.1 years. Give the same machine a 128-bit key and the same arithmetic returns roughly $5.4\times 10^{21}$ years. Building a machine a ten thousand times faster subtracts four orders of magnitude from that and changes nothing about the conclusion — which is exactly why key length, not machine speed, is the parameter that matters.

There is a second, less obvious half to brute force: you have to recognise the plaintext when it appears. Plain English announces itself. A compressed archive or a stream of numeric records does not, so a real attack needs an automated plaintext-versus-garble discriminator, and building one is part of the cost.

Unconditional versus computational security

A scheme is unconditionally secure if the ciphertext simply does not contain enough information to determine the plaintext, no matter how much ciphertext is available and no matter how much computing time is applied. Only the one-time pad meets that bar. Everything else in practical use — DES, AES, RC4, the lot — aims instead at computational security: the cost of breaking it exceeds the value of the information, or the time required to break it exceeds the useful lifetime of the information. Both halves of that definition are marks; a scheme protecting a value that expires in an hour needs far less than one protecting a medical record.