Chapter 2Block CiphersBlockciphers are the centr al tool in the design of p rotocols for shared-key cryptography (aka. sym-metric) cryptography. They are the main available “technology” we have at our disposal. Thischapter w ill take a look at these objects and describe the state of the art in their construction.It is important to stress that blockciphers are just tools—raw ingredients for cooking up some-thing more useful. Blockciphers don’t, by themselves, do something th at an end -user wou ld careabout. As with any powerful tool, one has to learn to use this one. Even an excellent blockcipherwon’t give you security if you use don’t use it right. But used well, these are powerful tools indeed.Accordingly, an important theme in several upcoming chapters will be on how to use blockcipherswell. We won’t be emphasizing how to design or analyze blockciphers, as this remains very muchan art.This chapter gets you acquainted with some typical blockciphers, and discusses attacks on them.In particular we’ll look at two examples, DES and AES. DES is the “old standby.” It is cu rrentlythe most widely-used blockcipher in existence, and it is of sufficient historical significance that everytrained cryptographer needs to have seen its description. AES is a m odern blockcipher, and it isexpected to supplant DES in the years to come.2.1 What is a blockcipher?A blockcipher is a function E: {0, 1}k× {0, 1}n→ {0, 1}n. This notation means that E takes twoinputs, one being a k-bit string and the other an n-b it string, and returns an n-bit string. Thefirst input is the key. The second might be called the plaintext, and th e output might be called aciphertext. The key-length k and the block-length n are parameters associated to the blockcipher.They vary from blockcipher to blockcipher, as of course does the design of the algorithm itself.For each key K ∈ {0, 1}kwe let EK: {0, 1}n→ {0, 1}nbe the function d efi ned by EK(M) =E(K, M). For any blockcipher, and any key K, it is required that the fun ction EKbe a permutationon {0, 1}n. This means that it is a bijection (ie., a one-to-one and onto function) of {0, 1}nto {0, 1}n.(For every C ∈ {0, 1}nthere is exactly one M ∈ {0, 1}nsuch that EK(M) = C.) Accordingly EKhas an inverse, and we denote it E−1K. This function also maps {0, 1}nto {0, 1}n, and of coursewe have E−1K(EK(M)) = M and EK(E−1K(C)) = C for all M, C ∈ {0, 1}n. We let E−1: {0, 1}k×{0, 1}n→ {0, 1}nbe defined by E−1(K, C) = E−1K(C). This is the inverse blockcipher to E.Preferably, the blockcipher E is a public specified algorithm. Both the cipher E and its inverseE−1should be easily compu table, meaning given K, M we can readily compute E(K, M), and given2 BLOCK CIPHERSK, C we can readily compute E−1(K, C). By “readily compute” we mean that there are public andrelatively efficient programs available for these tasks.In typical usage, a random key K is chosen and kept secret between a pair of users. T he functionEKis then used by the two parties to process data in some way before they send it to each other.Typically, we will assume the adversary will be able to obtain some input-output examples for EK,meaning pairs of the form (M, C) where C = EK(M). But, ordinarily, the adversary will not beshown the key K. Security relies on the secrecy of the key. So, as a first cut, you might thinkof the adversary’s goal as recovering th e key K given some input-output examples of EK. Theblockcipher should be designed to make this task computationally difficult. (Later we w ill refi nethe view th at the adversary’s goal is key-recovery, seeing that s ecur ity against key-recovery is anecessary but not sufficient condition for the security of a blockcipher.)We emphasize that we’ve said absolutely nothing about what properties a blockcipher shouldhave. A function like EK(M) = M is a blockcipher (the “identity blockcipher”), but we shall notregard it as a “good” one.How do real blockciphers work? Lets take a look at some of them to get a sense of this.2.2 Data Encryption Standard (DES)The Data Encryption Standard (DES) is the quintessential blockcipher. Even though it is now quiteold, and on the way out, no discussion of blockciphers can really omit mention of this construction.DES is a r emarkably well-engineered algorithm which h as had a powerful influence on cryptography.It is in very widespr ead use, and probab ly will be for some years to come. Every time you use anATM machine, you are using DES.2.2.1 A brief historyIn 1972 the NBS (National Bureau of Standards , now NIST, the National Institute of Standardsand Technology) initiated a program for data protection and wanted as part of it an encryptionalgorithm that could be standardized. They put out a request for su ch an algorithm. In 1974, IBMresponded with a design based on their “Lucifer” algorithm. This design would eventually evolveinto the DES.DES has a key-length of k = 56 bits and a block-length of n = 64 bits. It consists of 16 roundsof what is called a “Feistel network.” We will describe more details shortly.After NBS, several other bodies adop ted DES as a standard, including ANSI (the AmericanNational Standards Institute) and the American Bankers Association.The standard was to be reviewed every five years to see whether or not it should be re-adopted.Although there were claims that it would not be re-certified, the algorithm was re-certified againand again. Only recently did the work for finding a replacement begin in earnest, in the form ofthe AES (Advanced Encryption Standard) effort.2.2.2 ConstructionThe DES algorithm is dep icted in Fig. 2.1. It takes input a 56-bit key K and a 64 bit p laintextM. The key-schedule KeySchedule produces f rom the 56-bit key K a sequence of 16 subkeys, onefor each of the rounds that follows. E ach sub key is 48-bits long. We postp one the discussion of theKeySchedule algorithm.The initial permutation IP simply permutes the bits of M, as d escribed by the table of Fig. 2.2.The table says that bit 1 of the output is bit 58 of the input; bit 2 of the output is bit 50 of theBellare and Rogaway 3function DESK(M) // |K| = 56 and |M| = 64(K1, . . . , K16) ← KeySchedule(K) // |Ki| = 48 for 1 ≤ i ≤ 16M ← IP(M)Parse M as L0k R0// |L0| = |R0| = 32for r = 1 to 16 doLr← Rr−1; Rr← f(Kr, Rr−1) ⊕ Lr−1C ← IP−1(L16k R16)return CFigure 2.1: The DES blockcipher. The text and other figures describe the subroutinesKeySchedule,