There are a few basic operations that are useful to understand. Before, we studied basic operations on normal text characters, such as by shifting the characters using alphabets. Now, we are concerned with operations on binary data.

The AND operator (sometimes written as &, ·, or ×) operates on 2 bits. The result is a 1 if both operands are 1, and 0 otherwise (and hence, only 1 if the first operand "and" the second operand are 1). The reason symbols for multiplication are used for AND is that this operates identically to numerically multiplying the binary operands.

The OR operator (sometimes written as | or +) also takes two operands, and produces a 1 if either the first operand "or" the second operand is a 1 (or both), and 0 only if both are 0. Sometimes this can be represented with the plus symbol, since it operates similarly to addition, except that in this case, 1 + 1 = 1 (or 1| 1 = 1), since we only have 1 bit to represent the output.

The XOR (exclusive-OR, also called EOR) operator, commonly written as ^ (especially in code) and ⊉ (often in text), operates the same as the OR operator, except that it is 0 if both arguments are 1. Hence, it is 1 if either argument is 1, but not both, and 0 if neither is 1.

XOR has many uses. For example, it can be used to flip bits. Given a bit A (either 0 or 1), calculating A ⊉ 1 will give the result of flipping A (producing a result that is opposite of A).

Table 4-2 shows the outputs of the AND, OR, and XOR bitwise operators.

The final basic operation is the bitwise NOT operator. This operator takes only a single operand and simply reverses it, so that a 0 becomes a 1 and a 1 becomes a 0. This is typically represented, for a value a, as ~ a, a, or ¬ a (in this book, we mostly use the latter). This can be combined with the above binary operators, by taking the inverse of the normal output. The most used of these operators are NAND and NOR.

All of these operators naturally extend to the byte and word level by simply using the bitwise operation on each corresponding pair of bits in the two bytes or words. For example, let a = A7 and b = 42 (both in hexadecimal). Then a &b = 02, a |b = E7, and a ⊉ b = E5.

In this book, I will try to show bits numbered from 0 up, with bit 0 being the least significant. When possible, I will try to stick with MSB (big endian) byte order, and most significant bit order as well. One final notation that is handy when specifying cryptographic algorithms is a notation of how to glue together various bits. This glue (or concatenation) is usually denoted with the || symbol. For example, the simple byte, written in binary as 01101101 would be written as

0 || 1 || 1 || 0 || 1 || 1 || 0 || 1

We might also specify some temporary value as x and want to specify the individual bits, such as x₀, x₁, and so on. If x is a 4-bit value, we can use the above notation to write

x = x₃ || x₂ || x₁ || x₀

Because we may be working with large structures with dozens or hundreds of bits, it can sometimes be useful to use the same glue operator to signify

concatenating larger structures, too. For example, if y is a 64-bit value and we want to reference 8 of its byte values, we might write them as

y = y₇ || y₆ || y₅ || y₄ || y₃ || y₂ || y₁ || y₀

In this case, we will let y₀ be the least significant 8 bits, y₁ the next bits, and so forth.

I will try to be clear when specifying the sizes of variables, so that there will be as little confusion as possible. Even I have had some interesting problems when implementing ciphers, only to discover it is because the sizes were not properly specified, so the various pieces did not fit together.

Again, I find it useful to have some code snippets in this chapter so that you can more easily see these algorithms in action.

And again, as in the previous chapter, I will have the examples in Python. This is for several reasons:

I won't have time to introduce every concept used, but I will try not to let something particularly confusing slip through. It is my intention that the examples will provide illumination and not further confusion.

With that little bit of introductory material out of the way, we can start exploring how we build block ciphers using some of the tools that we have developed, as well as a few more additional tools we shall build in the following sections.

The terminology for a digital substitution is called a substitution box, or S-box. The term box comes from the fact that it is regarded as a simple function: It merely accepts some small input and gives the resulting output, using some simple function or lookup table. When shown graphically, S-boxes are drawn as simple boxes, as in Figure 4-1.

Figure 4-1. Graphical representation of a 4-bit S-box.

S-boxes normally are associated with a size, referring to their input and output sizes (which are usually the same, although they can be different). For example, here is a representation of a 3-bit S-box, called simply S :

S[0] = 7 S[3] = 4 S[6] = 0
S[1] = 6 S[4] = 3 S[7] = 1
S[2] = 5 S[5] = 2

This demonstrates one of the simpler methods of showing an S-box: merely listing the output for every input. As we can see, this S-box, S, almost reverses the numbers (so that 0 outputs 7, 1 outputs 6, etc.), except the last two entries for S [6] and S [7].

We can also specify this S-box by merely writing the outputs only: We assume that the inputs are implicitly numbered between 0 and 7 (since 7 = 2³ − 1). In general, they will be numbered between 0 and 2^b − 1, where b is the input bit size. Using this implicit notation, we have S written as

[7, 6, 5, 4, 3, 2, 0, 1]

Of course, in the above S-box, I never specified which representation of bits this represents: most significant or least significant. A word of caution: Some ciphers do actually use least significant bit order (such as DES), even though this is fairly uncommon in most other digital computing. This can be very confusing if you are used to looking at ciphers in most significant bit order, and vice versa.

As specified above, S-boxes may have different sizes for inputs and outputs. For example, an S-box may take a 6-bit input, but only produce a 4-bit output. In this case, many of the outputs will be repeated. For the exact opposite case, with, say, a 4-bit input and 6-bit output, there will be several outputs that are not generated.

Sometimes S-boxes are derived from simpler moves. For example, we could have a 4-bit S-box that merely performs, for a 4-bit input x, the operation 4 −x mod 16, and gives the result. The S-box spelled out would be

[4, 3, 2, 1, 0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5]

S-boxes have some advantages, as we can see. They can be very random, with little correspondence between any input bits and output bits, and have few discernible patterns.

One primary disadvantage is size: They simply take a lot of space to describe. The 8-bit S-box for Rijndael, shown in Figure 4-2, takes a lot of space and requires implementing code to store the table in memory (although it can also be represented as a mathematical function, but this would require more computation at run time).

Another tool, the permutation box (or simply, P-box), is similar to an S-box but has a slightly different trade-off: A P-box is usually smaller in size and operates on more bits.

A P-box provides similar functionality to transpositions in classical cryptography. The purpose of the permutation box is to permute the bits: shuffle them around but without changing them.

P-boxes operate by mapping each input value to a different output value by a lookup table — each bit is moved to a fixed position in the output. Most P-boxes simply permute the bits: one input to one output. However, in some ciphers (such as DES), there are expansive and selective permutations as well, where the number of output bits is greater (some bits are copied) or smaller (some bits are discarded), respectively.

P-boxes are normally specified in a similar notation to S-boxes, only instead of representing outputs for a particular input, they specify where a particular bit is mapped to. Assume that we number the bits from 0 to 2^b − 1, where b is the size of the P-box input, in bits. The output bits will also be numbered from 0 to 2^c − 1, where c is the size of the P-box output, in bits.

Figure 4-2. Full listing of the Rijndael's 8-bit S-box.

For example, an 8-bit P-box might be specified as

P = [351047 62]

This stands for P[0] = 3, P[1] = 5, P[2] = 1, ..., P[6] = 6, P[7] = 2. The operation means to take bit 0 of the input and copy it to bit 3 of the output. Also take bit 1 of the input, and copy it to bit 5 of the output, and so forth. (Note that not all bits necessarily map to other bits — e.g., in this P-box, bits 4 and 6 map to themselves.) The example in Figure 4-3 illustrates this concept graphically.

For the preceding P-box, assume that the bits are numbered in increasing order of significance (0 being the least significant bit, 7 the most). Then, for example, the input of 00 will correspond to 00. In hexadecimal (using big-endian notation), the input 01 would correspond to 20, and 33 would correspond to B8.

A few things to note about P-boxes: They aren't as random as S-boxes — there is a one-to-one correspondence of bits from the input to the output. P-boxes also take a lot less space to specify than S-boxes: The 8-bit P-box could be written out in very little space. A 16-bit P-box could be written as a list of 16 numbers, but it would require a list of 65,536 numbers to fully specify a 16-bit S-box.

However, technically speaking, P-boxes are S-boxes, just with a more compact form. This is because they are simply a mapping of input values to output values and can be represented as a simple lookup table, such as an S-box. The P-box representation is merely a shortcut, albeit a very handy one.

If we look at any of the previously mentioned structures, though, we can see that they should not be used alone. A trivial cipher can be obtained by just using an S-box on an input, or a P-box, or even XORing each input byte with a fixed number. None of these techniques provides adequate security, though: The first two allow anyone with knowledge of the S-box or P-box to immediately decrypt a message, and with a simple XOR, anyone who knows the particular value of one byte in both plaintext and ciphertext could immediately derive the key.

For these reasons, I will use the above concept of a product cipher to combine each of these concepts — bitwise operations, S-boxes, and P-boxes — to create a very complicated structure. We won't limit ourselves to just these particular operations and boxes, but the ones explained so far represent the core of what is used in most modern cryptographic algorithms.

Figure 4-3. A simple graphical representation of an 8-bit P-box. Note that bits 4 and 6 are passed straight through.

Figure 4-4. Skipjack's Rule A shift register.

Another tool used in the construction of ciphers is a shift register. Look at Figure 4-4, one of two shift registers in Skipjack (called Rule A and Rule B), for an example of how a shift register operates.

Typically, a shift register works by taking the input and splitting it into several portions; thus, in this case, w = w₁ || w₂ || w₃ || w₄ || is our input. Then, the circuit is iterated several times. In this diagram, G represents a permutation operation. Thus, after one round through the algorithm, w₂ will get the permutation of w₁;w₃ will be the XOR of the old w₂, the counter, and the old w₁; and w₄ will get the old value of w₃; while w₁ gets the old value of w₄. This iteration is repeated many times (in Skipjack, it iterates eight times in two different locations).

Shift registers are meant to mimic the way many circuits and machines were designed to work, by churning the data in steps. These are also designed with parallelism in mind: While one piece of circuitry is performing one part of the computation, another can be computing with a different part of the data, to be used in following steps.

There is a need for a cipher that is easy enough for you to easily implement and see results of various techniques, while still being complicated enough to be useful. For that, we shall create a cipher call EASY1 in this section. We'll use it in later chapters to demonstrate some of the methods of cryptanalysis.

EASY1 is a 36-bit block cipher, with an 18-bit key. EASY1 works by splitting its input into 6-bit segments, running them through S-boxes, concatenating the results back together, permuting them, and then XORing the results with the key. The key is just copied side-by-side to become a 36-bit key (both the "left half" and "right half" of the cipher bits are XORed with the same key).

We will use various numbers of rounds at different times, usually low numbers.

The 6-bit S-boxes in EASY1 are all the same:

[16, 42, 28, 3, 26, 0, 31, 46, 27, 14, 49, 62, 37, 56, 23, 6, 40, 48, 53, 8,
20, 25, 33, 1, 2, 63, 15, 34, 55, 21, 39, 57, 54, 45, 47, 13, 7, 44, 61, 9,
60, 32, 22, 29, 52, 19, 12, 50, 5, 51, 11, 18, 59, 41, 36, 30, 17, 38, 10, 4,
                               58, 43, 35, 24]

This is represented in the more compact, array form: The first element is the substitution for 0, the second for 1, and so forth. Hence, an input of 0 is replaced by 16, 1 by 42, and so on. The P-box is a large, 36-bit P-box, represented by

[24, 5, 15, 23, 14, 32, 19, 18, 26, 17, 6, 12, 34, 9, 8, 20, 28, 0, 2, 21, 29,
           11, 33, 22, 30, 31, 1, 25, 3, 35, 16, 13, 27, 7, 10, 4]

Our goal with EASY1 is that it should be easy to understand and fast to derive keys without the use of cryptanalysis (so answers can be verified).

I'll provide some quick code to perform EASY1.

##########################################
# S-box function
##########################################

def sbox(x):
  return s[x]


##########################################
# P-box function
##########################################

def pbox(x):
  # if the texts are more than 32 bits,
  # then we have to use longs
  y = 0l

  # For each bit to be shuffled
  for i in range(len(p)):

   # If the original bit position
   # is a 1, then make the result
   # bit position have a 1

   if (x & (1l << i)) != 0:
    y = y^(1l << p[i])

return y

##########################################
# Takes 36-bit to six 6-bit values
# and vice-versa
##########################################
def demux(x):
  y =[]
  for i in range(0,6):
    y.append((x >> (i * 6)) & 0x3f)

  return y



def mux(x):
  y = 0l
  for i in range(0,6):
    y = y ^ (x[i] << (i * 6))

  return y

##########################################
# Key mixing
##########################################

def mix(p, k):
  v = []
  key = demux(k)
  for i in range(0,6):
    v.append(p[i] ^ key[i])

  return v

##########################################
# Round function
##########################################

def round(p,k):
  u = []

  # Calculate the S-boxes
  for x in demux(p):
    u.append(sbox(x))

  # Run through the P-box
  v = demux(pbox(mux(u)))

  # XOR in the key
  w = mix(v,k)

  # Glue back together, return
  return mux(w)

##########################################
# Encryption
##########################################

def encrypt(p, rounds):
  x = p
  for i in range(rounds):
    x = round(x, key)

  return x

##########################################
# Opposite of the round function
##########################################

def unround(c, k):
  x = demux(c)

u = mix(x, k)
  v = demux(apbox(mux(u)))
  w = []
  for s in v:
   w.append(asbox(s))

  return mux(w)


##########################################
# Decryption function
##########################################

def decrypt(c, k):
  x = c
  for i in range(rounds):
   x = deround(x, key)

  return x

The key schedule produces, from a 64-bit key, a set of 16 keys (K₁, K₂, ..., K₁₆) using the following method:

We then have 16 48-bit round keys, K₁, K₂, ..., K₁₆.

The DES round function consists of four operations, applied in succession:

The final result from the P-box is then given as the output. Figure 4-7 shows a diagram of DES's round function.

The S-boxes in the third step are the most critical part of the cipher. The rest of DES is fairly straightforward and predictable; thus, a very large part of the security of DES rests in the values of the S-boxes.

An ever-growing flaw with DES is its limited key strength, as already mentioned. Despite this, the algorithm was widely used for decades, and few debilitating weaknesses were found in the algorithm. In order to combat the key weakness but prevent hardware and software manufacturers from having to completely change products that utilize DES, a way to extend the life was proposed in the form of triple DES (or, more commonly written, 3DES).

The 3DES method is fairly similar to how it sounds: We essentially run the cryptographic algorithm three times, each time with a potentially different key. We don't just encrypt three times on one end and decrypt three times on the other end, though. Instead, we encrypt and decrypt plaintext P (and corresponding ciphertext C) with three keys, K₁, K₂, and K₃ (in that order), by computing

Encryption :C = Encrypt_K3 (Decrypt_K2 (Encrypt_K1 (P)))

Decryption :P = Decrypt_K1 (Encrypt_K2 (Decrypt_K3 (C)))

Figure 4-7. DES 32-bit round function.

Hence, 3DES is sometimes referred to as DES-EDE (for "Encrypt–Decrypt– Encrypt").

There are a few notes to make here. We have three keys, so wouldn't we have a key of length 56 × 3 = 168 bits? The answer is — sometimes, but not usually.

In most implementations of 3DES, there is a 112-bit key; we let K₁ and K₂ be distinct keys, and K₃ = K₁. The official specification also allows for two additional modes: using three distinct keys (for a full 168-bit key) and having all three keys be the same. Note that if all three keys are the same, then the first two operations of the encryption cancel each other out, as do the final two of the decryption, which creates the standard DES ciphering scheme. This allows software and hardware made for 3DES to also be easily converted back to the original DES as well (although it will be slower because of the wasted time of encrypting and decrypting with no end result).

Many different variants of DES have been proposed. An interesting one is meant to make an exhaustive key search (by trying all possible 56-bit keys) much harder, while not increasing the complexity of the original algorithm at all. DESX uses the exact same algorithm as DES above but involves extra steps called whitening.

Essentially, if we have a DES function using a key k on a plaintext P, we can, for example, write our ciphertextas

C = DES_k(P)

To whiten DES, we take two additional keys of 64 bits each, say, k₂ and k₃, and XOR them to the plaintext and ciphertext, respectively:

C = k₃ ⊉ DES_k(P ⊉ k₂)

The XOR operation used is where the "X" in "DESX" comes from.

The security of this is actually more than it appears at first glance: Adding these XORs does not appear to make the cipher less secure and could possibly increase the virtual key to be 56 + 64 + 64 = 184 bits, instead of the standard 56 bits. In addition, it is trivial to take a normal algorithm that calculates a DES ciphertext and modify it for DESX: Simply XOR the plaintext once before running the algorithm, and XOR the ciphertext afterwards.

This covers the basic workings of DES, although I don't explicitly state the values of the S-boxes and P-boxes. This information is readily available in the specification and in many books.

Rather than use a larger, complicated S-box, a simple function is used in FEAL so that it could be implemented in a few standard computer instructions without requiring large lookup tables. The S-box is called the S-function, defined as a function of three variables: x, y, and δ. Here, x and y are byte values, while δ is a single bit that changes depending on which round the S-function occurs in.

We define S (x, y, δ) as

S (x, y, δ) = rot2(x +y +δ) mod 256

Figure 4-8. FEAL's encryption structure.

The "mod 256" portion indicates that we need to do simple byte arithmetic. The "rot2" function indicates taking its argument, in this case an 8-bit number, and shifting all of its bits (as seen in its most significant bit form) to the left by two places, with the most significant 2 bits (shifted out on the left) being rotated back in to the least significant bits (on the right). For example:

rot2(00101011) = 10101100

A sample implementation of the S-function, including the rotation function, is shown in Listing 4-6.

##########################################
# The rot2 function - helper for the S-function
##########################################

def rot2(x):
     r = (x < 2) & 0xff # Calculate the left shift, removing extra bits
     r = r^(x >>6)        # OR in the leftmost two bits onto the right
     return r

##########################################
# The FEAL S-function
##########################################

def sbox(x, y, delta):
     return rot2((x + y + delta) & 0xff)

The f_K function is a helper function that churns the key to create various subkeys.

Here, the inputs to the key generating function, denoted α and β, are 32-bit quantities, split into four 8-bit quantities. Operations are then done with 8-bit arithmetic, probably since, when FEAL was designed, it was much faster than 32-bit arithmetic, and the 8-bit results are recombined into the 32-bit result.

The f-function is the actual round function, acting as the heart of its Feistel structure. It takes as input two 32-bit values (α and β), and produces a 32-bit result.

To implement these nine steps, we first need to define a few helper functions, to split the 32-bit block into four 8-bit parts (demux) and to recombine 8-bit parts into a single 32-bit block (mux). These are very similar to those used in the SPN cipher above, EASY1. In Python, we can use the code in Listing 4-7.

##########################################
# Splits a 32-bit block into four 8-bit values
# and vice-versa
##########################################

def demux(x):
    # Create an array of size four to store
    # the result
    y = []
    # Calculate each part in turn
    for i in range(0,4):

# They are numbered left to right, 0 to 3
        # But still in MSB order

        y.append((x>> ((3 - i) * 8)) & 0xff)
    return y

def mux(x):
    # Initialize result to zero
    y = 0

    # The input, x, is an array of 8-bit values
    for c in x:

      # Combine each 8-bit value using OR
        y = (y <<8) ^ c

    return y

Now that we have all of the helper functions for FEAL, we can define the FEAL main round function, as shown in Listing 4-8.

##########################################
# Feal round function, f
##########################################

def f(alpha, beta):
    # Split alpha and beta
    a = demux(alpha)
    b = demux(beta)

    # Make the output four 8-bit values
    fs = [0,0,0,0]

    # Calculate each 8-bit value
    fs[1] = a[1] ^ b[0] ^ a[0]
    fs[2] = a[2] ^ b[1] ^ a[3]
    fs[1] = sbox(fs[1], fs[2], 1)
    fs[2] = sbox(fs[2], fs[1], 0)
    fs[0] = sbox(a[0], fs[1], 0)
    fs[3] = sbox(a[3], fs[2], 1)

    # Return the 32-bit result
    return mux(fs)

The key scheduling algorithm for FEAL is meant to split up a 64-bit key into various derived subparts (based on the f_K key scheduling function), for use in the main round function of FEAL.

In Python, we can implement this fairly easily, as shown in Listing 4-9.

##########################################
# FEAL key generating function
##########################################

def fk(alpha, beta):
    # Split alpha and beta
    a = demux(alpha)
    b = demux(beta)

    # Express output as four 8-bit values
    fs = [0,0,0,0]
    # Calculate the four 8-bit values
    fs[1] = sbox(a[0] ^ a[1], a[2] ^ a[3] ^ b[0], 1)
    fs[2] = sbox(a[2] ^ a[3], fs[1] ^ b[1], 0)
    fs[0] = sbox(a[0], fs[1] ^ b[2], 0)
    fs[3] = sbox(a[3], fs[2] ^ b[3], 1)

    return mux(fs)

Although we will get into more detailed cryptanalysis of FEAL later, there are a few things to note.

It's easy to see that FEAL is almost more complicated than DES: It takes more space to explain and requires more bits and pieces. To give FEAL some credit, most of the operations are indeed very fast: They usually operate on a small number of bits, so that they can be implemented in one machine code instruction.

Schneier refers to the subkeys, generated from the main key, as 18 32-bit keys: P₁, P₂, ..., P₁₈. The key scheduling algorithm also calculates the S-box, since its values are completely determined by the key itself.

Blowfish Key Scheduling. The P-values and S-box values for the main encryption are calculated based on an input key (of up to a length of 448 bits) and the hexadecimal digits of π.

This will require a total of 521 iterations in order to compute all values.

The algorithm is based on the Feistel structure, with a total of 16 rounds. The key to the algorithm, as mentioned above, is that the algorithm is kept very simple: For each round, only three XORs, two additions, and four S-box lookups are required.

Blowfish Encryption Algorithm. The basic cryptographic algorithm operates on a 64-bit input and produces a 64-bit output. The following shows the encryption portion. To obtain the decryption code, simply replace P_i in the following with P_19−i (with P₁₇ and P₁₈ at the end being replaced with P₂ and P₁, respectively):

The output is the block obtained by recombining L₁₇ and R₁₇. This main round procedure is shown in Figure 4-9.

The core of the algorithm is, as with all Feistel structures, in the round function.

Blowfish Round Function. In this case, the round function (f in the algorithm) works on a 32-bit argument and produces a 32-bit output by the following method:

This round function has a few interesting properties. Notably, which S-boxes are chosen depends on the data themselves: so that the data dictate their own encryption. [This is because the split plaintext (a, b, c, and d) is used to choose the S-boxes.]

The other important note about Blowfish is that it requires 521 encryptions using its own encryption algorithm before it can produce a single block of output. Therefore, encrypting a single block would take very long because of the long setup time. It really only becomes moderately fast to use Blowfish when encrypting at least several hundred blocks (meaning thousands of bits); otherwise, the setup time will dominate the total encryption and decryption times. Luckily, we need to compute the key values and S-boxes only once.

The Rijndael encryption algorithm essentially consists of four basic operations, applied in succession to each other, and looped multiple times:

The AddRoundKey is the only portion of the algorithm dependent on the current round number and the key.

Using the above four pieces, we can specify the Rijndael encryption algorithm.

Figure 4-10. A state associated with a 128-bit block size Rijndael, such as in AES. If the state is a 128-bit value, then it it is split into the matrix by breaking it down:S_0,0 || S_0,1 || S_0,2 || S_0,3 || S_1,0 || S_1,1 || S_1,2 || S_1,3 || S_2,0 || S_2,1 || S_2,2 || S_2,3 || S_3,0 || S_3,1 || S_3,2 || S_3,3.

Rijndael Encryption Algorithm. Assume that there are r rounds (r is dependent on the key size), and that the plaintext has been loaded into the state.

I'll now describe the four sections in a bit more detail. For a more thorough treatment, see References [2] and [7]. The following examples use the details in the AES for a 128-bit block size.

SubBytes

The SubBytes operation essentially functions as an 8-bit S-box, applied to each 8-bit value of the state, as shown in Figure 4-11.

Figure 4-11. The Rijndael SubBytes operation.

The S-box can be represented in several ways. The normal S-box implementation, with a fixed lookup table, is shown in Figure 4-2. The way I often show it is, if I define the 8-bit input a to be written as a₇ || a₆ || ··· || a₀ and b to be written similarly, then

where the × operator means matrix multiplication. If this is confusing, it is fairly easy, and often faster, to just use the lookup-table representation of the S-box.

MixColumns

The MixColumns operation is the most complicated part of the AES algorithm.

Although I won't go into the nitty-gritty of the mathematics of multiplication over GF(2⁸)(the finite field of size 2⁸, also written as Z₂ 8), in the case of AES, this essentially means that we will multiply two 8-bit numbers, and take the remainder modulo 283 (which is 100011011 in binary), using binary XOR long

Figure 4-12. The Rijndael ShiftRows operation.

division, not normal arithmetic. This is the same as doing normal division, except that instead of successively subtracting, we use binary XOR. Also, while in normal subtraction, we only subtract if we are dividing a smaller number into a larger number at each stage, whereas with XOR, we only divide if they have the same number of binary digits (so either number can be greater). So that we don't confuse this with normal arithmetic multiplication, I will denote the operation as • (as done in the specification [7]).

For example, I will show how to do this with the AES example in Reference [7], calculating 87 • 131 (or, 01010111 • 10000011). We first multiply the two numbers as usual, obtaining 11,397, or 1010110111001. We then perform the long division to obtain the remainder when divided by 10011011:

For the MixColumns operation, we are going to take each column and perform a matrix multiplication, where the multiplication is the • operation shown above. The operation will be

where the a_i,c entries on the right are the old column entries, the b_i,c entries on the left are new column entries, and the ⊗ operator means to perform matrix multiplication with the • operator and XOR instead of addition. We can specify this less abstractly as

b_{0, c} = (2 • a_{0, c}) ⊉ (3 • a_{1, c}) ⊉ a_{2, c} ⊉ a_{3, c}

b_{1, c} = a_{0, c} ⊉ (2 •a_{1, c}) ⊉ (3 • a_{2, c}) ⊉ a_{3, c}

b_{2, c} = a_{0, c} ⊉ a_{1, c} ⊉ (2 •a_{2, c}) ⊉ (3 • a_{3, c})

b_{3, c} = (3 • a_{0, c}) ⊉ a_{1, c} ⊉ a_{2, c} ⊉ (2 •a_{3, c})

This operation will be performed for each column, that is, for c = 1, 2, 3, and 4.

The MixColumns operation is shown graphically in Figure 4-13.

Figure 4-13. The Rijndael MixColumns operation.

Decryption of Rijndael is very similar to encryption: It simply involves doing the operations in reverse (with a reverse key schedule) and using inverse operations for SubBytes, MixColumns, and ShiftRows — these operations are called, surprisingly enough, InvSubBytes, InvMixColumns, and InvShiftRows, respectively.

The use of these inverse functions leads to the following algorithm for decryption:

Rijndael Decryption Algorithm. Assume that there are r rounds (r is dependent on the key size) and that the ciphertext is loaded into the state.

Figure 4-14. The Rijndael AddRoundKey operation.

The most important thing to note is that the keys must be submitted in reverse order.

It is also important to note that the key expansion is changed slightly, as I show in Section 4.9.3.

The inverse operations are fairly easy to derive from the normal ones: We simply construct InvShiftRows by shifting in the opposite direction the appropriate number of times. We construct InvSubBytes by inverting the S-box used (either with the inverse matrix or the inverse of the table). And finally, the InvMixColumns transformation is found by using the following matrix for the multiplication step:

The key expansion step computes the key schedule for use in either encryption or decryption.

Rijndael computes its sizes in terms of 32-bit words. Therefore, in this case, a 128-bit block cipher would have a block size denoted as N_b of 4. The key size is denoted as N_k in a similar manner, so that, for example, a 192-bit key is denoted with N_k = 6. The number of rounds is denoted as r.

Two functions need to be explained in order to describe the key expansion. The SubWord function takes a 32-bit argument, splits it into four 8-bit bytes, computes the S-box transformation from SubBytes on each 8-bit value, and concatenates them back together. The RotWord function takes a 32-bit argument, splits it into four 8-bit bytes, and then rotates left cyclically, replacing each 8-bit value in the word with the 8-bit value that was on the right. Specifically, it computes

RotWord (a₃ || a₂ || a₁ || a₀) = a₂ || a₁ || a₀ || a₃

Finally, there is a constant matrix that is used, denoted as Rcon. The values of Rcon can be calculated fairly easily using the finite field multiplication operation •. Essentially, the values are calculated as

Rcon (i) = 2ⁱ⁻¹ || 0 || 0 || 0

where each of the four parts is an 8-bit number and a member of Rijndael's finite field. Owing to this fact, 2ⁱ⁻¹ must be calculated using the • multiplication operator [calculating the previous result times (•) 2], and not normal multiplication. The first few values of 2ⁱ⁻¹ are straightforward (starting at i = 1): 1, 2, 4, 8, 16, 32, 64, 128. When we get to 256, though, we need to start using the finite field modulo. Therefore, the next few values are 27, 54, 108, and so on. Table 4-5 shows the required values.

Rijndael is a modern cipher. Since it was created in the late 1990's, after many of the standard cryptanalytic techniques that I discuss in this book were known, it was tested against these techniques. The algorithm was tuned so that it was susceptible to none of the techniques, as they were known at the time.

The normal method is normally called electronic codebook (ECB). It simply means that each block of plaintext is used as the normal input to the block cipher, and the output of the cipher becomes the block of ciphertext, just as we would expect. Hence, for each block of plaintext, P, we calculate a block of ciphertext by simply applying

C = Encrypt (P)

Figure 4-15. A picture of a cat in a filing cabinet, demonstrating the preserved structure present in ECB.

However, there are some issues that can easily arise using a cipher in ECB mode. For example, a lot of the structure of the original data will be preserved, because identical plaintext blocks will always encrypt to identical ciphertext blocks. Figure 4-15 shows how this can occur. In this figure, we encrypt every grayscale (8-bit) pixel (padded with 15 bytes of zeros) with AES in ECB mode, and then take the first byte of the output block as the new grayscale value. (This same method is also used for the CBC example in the next section.)^[51]

In general, when identical plaintext blocks always encrypt to identical ciphertext blocks, there is the potential for a problem with block replay : Knowing an important plaintext–ciphertext pair, even without knowing the key, someone can repeatedly send the known ciphertext.

For example, assume that we have a very simple automatic teller machine (ATM), which communicates with a bank to verify if a particular individual is authorized to withdraw cash. We would hope that, at the very least, this communication between the ATM and the bank is encrypted. We might naively implement the above scenario in a simple message from the ATM:

ATM: Encrypt_K ("Name: John Smith, Account: 12345, Amount: $20")

(Assume that the bank sends back a message saying, "OK, funds withdrawn," or "Sorry, insufficient funds.") The above means simply to send the text message, encrypted with the key K. If the encryption scheme merely represented this as an ASCII message and performed an algorithm, such as AES, using the key K, we might think we are safe, since anyone listening in on the transaction will only see something random, such as

ATM: CF A2 1E C5 AF 67 2D AC 7A E1 0D 3B 2F ...

However, someone could do something sinister even with this. For example, someone listening in on this conversation might simply want to replay the above packet, sending it to the bank. Unless additional security measures are in place, the bank will think that the user is making several more ATM withdrawals, which could eventually drain the victim's bank account.

Even though the ATM used strong encryption to communicate with the bank, it was still susceptible to a block replay attack. Luckily, there are methods to help prevent this attack.

One of the most fundamental ideas of combatting the block replay problem is to make the output of each block depend on the values of the previous blocks. This will make it so that anyone listening to any block in the middle will not be able to repeat that one block over and over again at a later date.

However, simply chaining together the outputs like this still leaves a flaw: It does not prevent block replay of the first block (or the first several blocks, if they are all replayed). A common strategy to fight this is to add an initialization vector (the IV, and sometimes called the "salt") to the algorithm. Essentially, this is a random number that is combined with the first block, usually by XORing them together. The IV must also be specified somehow, by sending it to the other party or having a common scheme for picking them.

Using both of these strategies together results in the simple method called cipher-block chaining (CBC). The method I will describe is taken from Reference [9]. It essentially makes each block dependent on the previous block (with the first block dependent also on the initialization vector). Figure 4-16 shows how this eliminates block replay attacks by ensuring that the same plaintext blocks will be encrypted differently.

CBC Encryption. The following describes the basic CBC method, as described in Reference [9]. The method uses a 64-bit block size for plaintext, ciphertext, and the initialization vector (since the reference originally assumes that DES is used, although any cipher can be used in CBC mode). To adapt it for other ciphers, simply change this to the relevant block size, and use the appropriate algorithm.

Figure 4-16. A picture of a cat in a filing cabinet. Unlike ECB, CBC obliterates much of the underlying structure.

Decryption in CBC is equally simple.

CBC Decryption. The biggest restriction is that the two users must share the IV or the first block will not be comprehensible to the receiver.

There are other issues facing cryptography in addition to block replay. One is padding, or adding additional bits to the end of plaintext so that it is a multiple of the block size. This necessity potentially adds small weakness: We know the last few bits of plaintext if we know the padding scheme. Many ciphers use padding either as all zeros or ones, some other pattern, or perhaps just random bits.

However, the decrypting party needs to know how long the real message is so that any extra padding is thrown away. In some systems, the sending party may not know exactly how long the message is in advance (e.g., it may not have enough buffers to store an entire message of maximum length). In this case, it becomes difficult for the receiving party to know when the message has stopped if padding is used.

In both of these cases, the alternative to using a standard block cipher is to use a stream cipher — one that operates a bit at a time rather than a block at a time. We are mostly concerned with block ciphers in this book, but I shall discuss how block ciphers can be turned into stream ciphers, so that they can operate on one bit at a time (and, therefore, not require padding for any length).

Cipher feedback (CFB) mode is one way to turn any block cipher into a stream cipher, where the stream can consist of any number of bits, for example, it could be a bit stream cipher, a byte stream cipher, or a smaller block size cipher. The following construction is taken from Reference [3].

Assume we are implementing an s-bit CFB mode (with output in chunks of s bits). The only requirement is that s is between 1 and the block size.

CFB works by first encrypting input blocks (the first is an IV) with the key. Then, the "top" (most significant)s bits are extracted from this output, and XORed with the next s bits of the plaintext to produce the ciphertext. These bits of the ciphertext are then sent to the receiver.

At this point, the ciphertext bits are then fed back into the input block, hence the term cipher feedback. The input block is shifted left by s bits, and the ciphertext bits are put in on the right (least significant side). The process is then run again with this new input block.

Output feedback (OFB) mode is very similar to the cipher feedback mode just discussed, and they are often confused.

OFB starts out the same: We have an IV as our initial input block, which we encrypt with the key. Again, we use the most significant bits to XOR against the bits to be output. The result of this XOR is sent out as ciphertext.

Now, the difference is here. Before, we fed back in the ciphertext bits (after XORing with the output).

Instead, we feed back in the output bits of the encryption, before XORing with our plaintext (the result of encrypting the input block). These bits are fed into the bottom of the input block by shifting the block to the right and shifting in the new bits — hence the term output feedback.

The primary difference between these two modes is that the CFB is dependent on the plaintext to create the keystream (the series of bits that are XORed with the plaintext in a stream cipher). With OFB, the keystream is only dependent on the IV and the key itself.

An advantage of using OFB is that if a transmission error occurs, the error will not propagate beyond that corrupted block. None of the following blocks will be damaged by the error; thus, the receiver can recover. With CFB, since the ciphertext is directly put into the input block, the receiving end's incorrect ciphertext value would then be forever sullying the future decrypted bits.

Ciphers can also be operated in counter (CTR) mode, which can also be used to convert them to a stream cipher [3].

A series of counters is used, say, C₀, C₁, and so on. These counters are normally just increments of one another, hence the term counter. The first counter, C₀, should normally be a number that is difficult to guess.

The ciphertext for a given set of plaintext bits is then obtained as follows:

The result of the last step is then the ciphertext bits. For the next batch of plaintext bits, encrypt the next counter, and so forth.

Skipjack's encryption algorithm works fairly simply. There are two rules used in different rounds for a total of 32 rounds.

The plaintext is split into four parts (each being a 16-bit value):

Figure 4-17. Skipjack Rule A.

Both rules rely on a permutation, usually written as G. The exact nature of G depends on the round k (since the key mixing is done in the G permutation), so it can also be written as G^k.

Skipjack Rule A. Rule A follows a simple cyclical structure. Note that the counter is incremented every round.

Figure 4-17 shows this process.

Skipjack Rule B. Rule B works similarly to Rule A.

Figure 4-18 shows Rule B.

Figure 4-18. Skipjack Rule B.

Decryption of a Skipjack ciphertext is fairly straightforward: Every operation from above is reversible, including the G permutation. The rules are replaced with two new rules: A ⁻¹ and B ⁻¹. The decryption is performed by running Rule B⁻¹ eight times, followed by Rule A⁻¹ eight times, Rule B⁻¹ eight times again, and finally Rule A⁻¹ eight times.

Please note that the counter needs to run backwards. The keys are also submitted in reverse order k = 31, 30, ..., 0. That is, we start knowing the values for k = 32 (this corresponds to the ciphertext) and calculate the values for k = 0 (this corresponds to the plaintext).

Skipjack Rule A⁻¹. Rule A⁻¹ follows a similar structure to Rule A of the encryption.

Skipjack Rule B⁻¹. Rule B⁻¹ works similarly to Rule B.

The above encryption and decryption relied on functions called the G and G⁻¹ permutations. See Figures 4-19 and 4-20 for their structure.

The F-function is simply an 8-bit S-box. I won't show it here, but it can be viewed in the specifications [17].

Checksums are very simple measurements of ciphers. Typically, they are implemented with simple arithmetic or bitwise operators, usually addition or XOR.

For example, to calculate an 8-bit additive checksum of a series of bytes, simply add together the bytes and calculate the result modulo 256. For an XOR-based checksum, simply use the bitwise XOR on each of the bytes, which will return an 8-bit value.

Other checksums use similar methods. The key thing to note here is that they are not made for security. They are designed to check for simple errors, such as transmission or transcription errors. Their simple implementation on processors in very few instructions allows them to be used often in communications protocols.

It is fairly easy to defeat a checksum if it is used for security: Either simply modify the checksum itself, or modify a single portion of the message with the appropriate value to make the checksum come out correctly. For example, with an 8-bit XOR checksum, it is necessary to change just one byte to manipulate the checksum to be whatever is desired. Take the current checksum, XOR it with the desired checksum, and XOR this value with any byte in the message. The new message will now have the desired checksum.

A cyclic redundancy check (CRC) is a bit-centric method of error checking that is more robust than normal checksums against many types of errors, but is a tad more difficult to implement.

A CRC takes the original message and does bitwise (XOR-based) long division of it by a fixed, known polynomial. The remainder after the division is then transmitted, which the receiving end can easily verify by also dividing by the fixed polynomial.

CRCs vary in size, with the remainders having bit sizes between 5 and 32 being the most common.

For example, we can calculate a 5-bit CRC of the binary message 011011011 with the 6-bit divisor 101101:

The remainder above is the binary number 11000 (24 in decimal).

MD5 [12] is a message digest algorithm (so named because it was the fifth in a series). It outputs a 128-bit number from any number of bits as input (including zero).

MD5 works fairly simply. First, the input is padded so that its length is equal to 448 modulo 512 (meaning it is 448 + 512 ×n bits long, for any integer n greater than or equal to 0). Then, a 64-bit number representing its length is added to the end of this (or, if the length is more than can be represented in a 64-bit number, then the lower 64 bits of its length). This is appended as the lower-order 32 bits first, and then the upper 32 bits (i.e., in LSB order).

MD5 operates on a 128-bit buffer at a time, split into four 32-bit words, A, B, C, and D. Their initial values are shown in Table 4-6.

Four functions are used in the MD5 computation, one for each major round:

f (x, y, z) = (x &y) | ((¬x) &z)

g (x, y, z) = (x &z) | (y &(¬z))

h (x, y, z) = x ⊉ y ⊉ z

i (x, y, z) = y ⊉ (x | (¬z))

Each of the four portions uses one of these functions 16 times, churning through the data in a fairly twisty manner. At each step of the 64 steps, an

operation is performed using one of the above functions, followed by a rotation of the bytes:

a = b + ((a +F (b, c, d) + X_k+ T_i) ≪ s)

where F represents the f-function (Steps 0–15), the g-function (Steps 16–31), the h-function (Steps 32–47), and the i-function (Steps 48–63). The X_k-value represents the portion of the message block that we are pulling from. The T_i-value actually represents a value of the sine function, defined to be (from i = 1, ..., 64)

T_i = 2³² × abs(sin(i))

Here, we assume that i is the input to the sine function, in radians. (Recall that 2 π radians is the same as 360°.) Finally, we circularly shift left (or rotate left) by different values at each step, represented by the ≪ operation.

After this, we rotate the values:

a′ = d, b′ = a, c′ = b, d′ = c

The values with the prime () indicate the new values to be assigned.

After the 64 steps are completed, the new values for a, b, c, and d, are added into the working hash buffer (A, B, C, D). Then, the next block is loaded, and the process is run again.

See Figure 4-21 for a graphical representation of this.

Finally, the new values are arithmetically added back into the old values (with 32-bit arithmetic):

A = A + a, B = B + b, C = C + c, D = D + d

When the last block is processed, the MD5 signature is the final value of (A, B, C, D).

The Secure Hash Algorithm 1 (SHA-1) [10] is a hashing algorithm specified by NIST that outputs a 160-bit hash.

The following description is based on References [16] and [18].

Figure 4-21. Basic round of MD5. Here, the "

" operator represents arithmetic addition, modulo 2³² (i.e., 32-bit addition).

SHA-1 takes the input as 512-bit blocks and further splits them into 16 32-bit words, labeled m₀ through m₁₅. The words are expanded into 80 such words by the following equation, for i = 16, ..., 79:

m_i = (m_i−3 ⊉ m_i−8 ⊉ m_i−14 ⊉ m_i−16) ≪ 1

where the ≪ 1 operation rotates the bits, circularly, left by 1.

The initial values of (a₀, b₀, c₀, d₀, e₀) and (A, B, C, D, E) are

(67452301, efcdab89, 98badcfe, 10325476, c3d2e1f0)

The (A, B, C, D, E) values will represent the hash in the end. For now, we will calculate the (a, b, c, d, e) values and eventually add them when finished processing this block.

There are 80 rounds, for i = 1, ...,80:

a_i = (a_i−1 ≪ 5) + f_i (b_i−1, c_i−1, d_i−1) + e_i−1 + m_i−1 + k_i

b_i = a_i−1

c_i = b_i−1 ≪ 30

d_i = c_i−1

e_i = d_i−1

The f_i functions above change depending on the round:

i = 0, ..., 19 : f_i (x, y, z) = (x & y) | (¬x) & z)

i = 20, ..., 39 : f_i (x, y, z) = x ⊉ y ⊉ z

i = 40, ..., 59 : f_i (x, y, z) = (x & y) | (x &z) |(y &z)

i = 60, ..., 79 : f_i (x, y, z) = x ⊉ y ⊉ z

The k_i values change depending on the round:

i = 0, ..., 19 : k_i = 5a 82 79 99

i = 20, ..., 39 : k_i = 6e d9 eb a1

i = 40, ..., 59 : k_i = 8f 1b bc dc

i = 60, ..., 79 : k_i = ca 62 c1 d6

After we have processed all 80 rounds for the current block, we add the round values (using 32-bit arithmetic) to the ongoing hash values (A = A +a, B = B +b, C = C +c, D = D +d, and E = E +e) and start processing the next block.

Both SHA-1 and MD5 have other "relatives," such as MD4 (similar to MD5, but with a less thorough, and therefore faster, digesting function). However, I shall not discuss them further.

Even a true random number generator can have a certain flaw: Certain numbers are generated more often than others. For example, although flipping a coin is a fairly random process, there is a very slight, measurable difference in the output numbers generated by the coin toss. This can be due to any number of factors, such as wind, flipping style, and the relative weight of the two sides of the coin. For example, if a coin is flipped 100 times, it may turn out that on average, we can expect heads to occur about 49 times but tails to occur 51 times (with probabilities 0.49 and 0.51, respectively).

This is an example of bias : the characteristic of a process to favor one outcome more often than others, even if that process is truly random.

There are ways to reduce bias, typically by combining several bits to produce one bit, or by combining several sources of randomness with each other. For example, we can simply XOR several bits from different random sources to obtain a new random bit. With the coin example, we will assume that tails is a 0, and heads is a 1. If we take two coin flips, we get a 0 if we have two tails in a row, or two heads in a row, giving us a probability of

The probability of a 1 is therefore 1 − 0.5002 = 0.4998. Both probabilities are much closer to 1/2, giving us a bit that has much less bias in its output (since a purely random coin flip would have a probability of 1/2 for both heads and tails).

Of all of the various types of pseudorandom number generators out there, a decent and popular choice is the linear congruential random number generator [6]. This is a random number generator that gives a sequence of numbers from numbers of the form

X ← (a ×X + c) mod m

This gives a sequence of numbers dependent on integers a, c, m, and the seed, which is the initial value (X₀) of the series.

This series is called "linear congruential" because it is based on the fact that the next number is linearly related to the next, modulo m.

Knuth [6] gives some guidance to reduce predictability and bias in this series:

Further guidance on several of these points, as well as how to implement a linear congruential random number generator without floating point arithmetic, can be found in Reference [6].