Cryptanalysis and the Attack Models

4. Chosen ciphertext. The attacker can choose a ciphertext and obtain the matching decrypted plaintext, or at least learn whether decryption succeeded. Systems that report "bad padding" hand this over, and that one bit of feedback is enough to recover plaintext byte by byte. The chapter on cipher block chaining shows the mechanism.

5. Chosen text. Both 3 and 4 at once. The strongest attacker, and the model a modern cipher is expected to resist.

Two kinds of security, and the one that matters

Unconditionally secure. No amount of ciphertext, and no amount of computing, is enough to recover the plaintext, because the ciphertext simply does not contain enough information to determine it. Exactly one cipher in this syllabus is unconditionally secure, the one-time pad, and its chapter proves it.

Computationally secure. Either the cost of breaking the cipher exceeds the value of the information, or the time required to break it exceeds the useful lifetime of the information. Every other cipher in this book is in this class. Notice that both tests are about economics, not mathematics: a cipher protecting a share price for one minute needs far less than one protecting a medical record for fifty years.

This is why key length recommendations carry dates, and why NIST publishes transition schedules rather than permanent answers.

The cost of brute force, computed

The listing below takes the keyspaces of the ciphers in this syllabus and works out how long an exhaustive search takes at two speeds: one thousand million keys a second, which is roughly a single modern processor core, and one million million million keys a second, which is far beyond any machine that exists and is included to show that the large keyspaces do not care.

SECONDS_IN_YEAR = 365.25 * 24 * 60 * 60

def show(name, keyspace_bits, extra=""):
    keys = 2 ** keyspace_bits
    average = keys // 2
    for rate, label in ((10 ** 9, "1e9/s"), (10 ** 18, "1e18/s")):
        years = average / rate / SECONDS_IN_YEAR
        if years < 1 / 365.25:
            t = "%.3g seconds" % (average / rate)
        elif years < 1:
            t = "%.3g days" % (years * 365.25)
        else:
            t = "%.3g years" % years
        print("%-22s %4d bits  %-7s %s" % (name, keyspace_bits, label, t))
    if extra:
        print("%-22s %s" % ("", extra))

show("Caesar", 4.7, "25 keys in all, so the bits are only an analogy")
show("DES", 56)
show("two-key 3DES", 112)
show("AES-128", 128)
show("AES-256", 256)

Caesar                    4 bits  1e9/s   1.2e-08 seconds
Caesar                    4 bits  1e18/s  1.2e-17 seconds
                       25 keys in all, so the bits are only an analogy
DES                      56 bits  1e9/s   1.14 years
DES                      56 bits  1e18/s  0.036 seconds
two-key 3DES            112 bits  1e9/s   8.23e+16 years
two-key 3DES            112 bits  1e18/s  8.23e+07 years
AES-128                 128 bits  1e9/s   5.39e+21 years
AES-128                 128 bits  1e18/s  5.39e+12 years
AES-256                 256 bits  1e9/s   1.83e+60 years
AES-256                 256 bits  1e18/s  1.83e+51 years

Read four things out of that.

DES at one core is 1.14 years, which is why DES fell. Not because the number is large but because it is not large enough: a thousand such cores bring it to about ten hours, and at the fanciful rate in the second row it is thirty-six thousandths of a second. In 1998 a purpose-built machine did it in under three days, and the chapter on the strength of DES gives that machine's name and date.

AES-128 at a million million million keys a second is still more than five million million years. Brute force against a 128-bit key is not a matter of waiting for better hardware; the number does not come down within any span that means anything, and a machine running at a million million million keys a second does not exist.

The jump from 56 to 112 bits multiplies the time by about seventy-two thousand million million, from 1.14 years to 8.23e+16 years. Doubling a key length does not double the work, it squares the size of the keyspace, and that is the single most important intuition in this chapter.

The Caesar row is honest about being an analogy, and the printed bit count is not. The program was given 4.7 bits, which is 26 keys, and printed it with an integer format as 4; the timing beside it was computed from the 26. The timing is what matters: it is instantaneous, which is the point of the next chapter. It is also a small demonstration of why a number in a book should be produced by the program that printed it, because a bit count of 4 would be wrong and a reader would have no way to know.

A worked example: what an attacker actually does

The setup. An opponent captures ciphertext from a college portal. They do not know the cipher's key. They know, because the algorithm is published, that it is AES with a 128-bit key.

Step 1: consider brute force. From the table, out of the question.

Step 2: consider cryptanalysis of the algorithm. AES has been attacked publicly since 1998 and no attack materially better than brute force is known against the full cipher. So this route is closed too.

Step 3: attack something else. And this is the real lesson. The opponent stops attacking the cipher and attacks the key, the implementation or the person: a password that generates the key and can be guessed; a key stored in a file that is backed up to a public bucket; a timing difference in the implementation; a clerk who will read out a code over the telephone. Every successful real attack in Module 2 of this syllabus is of this kind.

The step that carries the marks. "The cipher is strong" and "the system is secure" are different claims. A question asking you to assess a system's security is not asking about AES's key length; it is asking where the weakest point is, and it is almost never the cipher.

Distinctions that carry marks

What beginners get wrong here

Brute force is not cryptanalysis. They are the two separate approaches in the definition, and a question that asks for "approaches to attacking a cipher" wants both, named and distinguished.

"On average half the keys" is part of the definition. Exhaustive search succeeds after half the keyspace on average, not after all of it, and the factor of two is worth stating because it is in the standard phrasing.

A large keyspace does not make a cipher strong. It makes brute force infeasible, which is a different claim. The monoalphabetic cipher of the next chapter but one has a keyspace of twenty-six factorial, which is far beyond brute force, and a schoolchild can break it with a pencil.

"Broken" rarely means "plaintext recovered". In cryptanalysis a cipher is considered broken when any attack does better than brute force, even if it is still far too expensive to run. That is why a cipher can be "broken" in a paper and still be safe to use for years, and why the retirement dates in the trend chapter lag the attacks.

Quick revision

• Two approaches: cryptanalysis (uses the algorithm's structure and knowledge of the plaintext) and brute force (tries every key; on average half of them).
• Five models, weakest attacker first: ciphertext only, known plaintext, chosen plaintext, chosen ciphertext, chosen text.
• Known plaintext is realistic because of fixed headers and formats. A modern cipher must resist chosen text.
• Unconditionally secure: only the one-time pad. Computationally secure: everything else, and the test is economic.
• Computed: DES 56 bits is about 1.14 years at a thousand million keys a second; AES-128 is beyond any machine.
• Doubling the key length squares the keyspace.
• A strong cipher does not make a secure system; the weak point is the key, the implementation or the person.
• "Broken" in cryptanalysis means "better than brute force", not "readable".

Test yourself

1. Name and distinguish the two general approaches to attacking a symmetric cipher. Cryptanalysis uses the nature of the algorithm together with knowledge of the general characteristics of the plaintext, or some plaintext and ciphertext pairs, to deduce a plaintext or the key. Brute force tries every possible key until an intelligible translation appears, and on average succeeds after half the keyspace. Cryptanalysis exploits design; brute force ignores it.

2. List the five attack models and what the attacker holds in each. Ciphertext only: the algorithm and ciphertext. Known plaintext: also one or more plaintext and ciphertext pairs under the same key. Chosen plaintext: also the ability to encrypt plaintext of their choice. Chosen ciphertext: also the ability to decrypt ciphertext of their choice, or to learn whether decryption succeeded. Chosen text: chosen plaintext and chosen ciphertext together.

3. Why is known plaintext a realistic model rather than a pessimistic one? Because real messages have predictable parts: standard headers, fixed salutations, file format signatures, repeated field names. An attacker who knows the message format therefore knows some plaintext before starting, without any special access.

4. Distinguish unconditionally secure from computationally secure, and name a cipher in each class. An unconditionally secure cipher cannot be broken however much ciphertext and computing power are available, because the ciphertext does not determine the plaintext; the one-time pad is the only example. A computationally secure cipher is one where the cost of breaking exceeds the value of the information or the time exceeds its useful life; DES, AES and RSA are all in this class.

5. Roughly how long does exhaustive search of a 56-bit key take at a thousand million keys a second, and what does that tell you about DES? About 1.14 years on average. It tells you DES was defensible in 1977 and indefensible once a thousand such processors, or a purpose-built machine, could be pointed at it, which is what happened in the 1990s. The cipher did not change; the cost of computing did.

6. Why does a large keyspace not by itself make a cipher strong? Because cryptanalysis does not search the keyspace. A monoalphabetic substitution has twenty-six factorial keys, which is far beyond brute force, and yet letter frequencies in the ciphertext reveal the mapping directly. Resistance to brute force and resistance to cryptanalysis are separate properties and both are required.

7. What does a cryptanalyst mean by saying a cipher is "broken"? That some attack performs better than exhaustive search, even if it remains far too expensive to carry out. It is a statement about the design rather than about present-day readability, which is why an algorithm can be broken in a paper years before it is formally withdrawn from use.