Problems
2.1 This problem uses a real-world example of a symmetric cipher, from an old U.S.
Special Forces manual (public domain).The document, filename SpecialForces.pdf, is
available at this book’s Web site.
a. Using the two keys (memory words) cryptographic and network security, encrypt
the following message:
Be at the third pillar from the left outside the lyceum theatre tonight at
seven. If you are distrustful bring two friends.
Make reasonable assumptions about how to treat redundant letters and
excess letters in the memory words and how to treat spaces and punctuation.
Indicate what your assumptions are. Note: The message is from the Sherlock
Holmes novel, The Sign of Four.
b. Decrypt the ciphertext. Show your work.
c. Comment on when it would be appropriate to use this technique and what its
advantages are. Get this solution
2.2 Consider a very simple symmetric block encryption algorithm in which 32-bits blocks
of plaintext are encrypted using a 64-bit key. Encryption is defined as
C (P K0) K1
where C ciphertext, K secret key, K0 leftmost 64 bits of K, K1 rightmost
64 bits of K, bitwise exclusive OR, and is addition mod 264.
a. Show the decryption equation.That is, show the equation for P as a function of C,
K0, and K1.
b. Suppose and adversary has access to two sets of plaintexts and their corresponding
ciphertexts and wishes to determine K.We have the two equations:
C (P K0) K1; C' (P' K0) K1
First, derive an equation in one unknown (e.g., K0). Is it possible to proceed further
to solve for K0? Get this solution
2.3 Perhaps the simplest “serious” symmetric block encryption algorithm is the Tiny
Encryption Algorithm (TEA). TEA operates on 64-bit blocks of plaintext using a
128-bit key. The plaintext is divided into two 32-bit blocks (L0, R0), and the key is
divided into four 32-bit blocks (K0,K1,K2,K3). Encryption involves repeated application
of a pair of rounds, defined as follows for rounds i and i 1:
Li Ri 1
Ri Li 1 F(Ri 1, K0, K1, δ
i)
Li 1 Ri
Ri 1 Li F(Ri, K2, K3, δ
i 1)
where F is defined as
F(M, Kj, Kk, δ
i) ((M 4) Kj) ((M 5) Kk) (M δi)
and where the logical shift of x by y bits is denoted by x y, the logical right shift of
x by y bits is denoted by x y, and δ
i is a sequence of predetermined constants.
a. Comment on the significance and benefit of using the sequence of constants.
b. Illustrate the operation of TEA using a block diagram or flow chart type of
depiction.
c. If only one pair of rounds is used, then the ciphertext consists of the 64-bit
block (L2, R2). For this case, express the decryption algorithm in terms of
equations.
d. Repeat part (c) using an illustration similar to that used for part (b). Get this solution
2.4 Show that Feistel decryption is the inverse of Feistel encryption. Get this solution
2.5 Consider a Feistel cipher composed of 16 rounds with block length 128 bits and key
length 128 bits. Suppose that, for a given k, the key scheduling algorithm determines
values for the first eight round keys, k1, k2, . . ., k8, and then sets
k9 = k8, k10 = k7, k11 = k6, . . ., k16 = k1
Suppose you have a ciphertext c. Explain how, with access to an encryption oracle,
you can decrypt c and determine m using just a single oracle query.This shows that
such a cipher is vulnerable to a chosen plaintext attack. (An encryption oracle can
be thought of as a device that, when given a plaintext, returns the corresponding
ciphertext.The internal details of the device are not known to you, and you cannot
break open the device. You can only gain information from the oracle by making
queries to it and observing its responses.) Get this solution
2.6 For any block cipher, the fact that it is a nonlinear function is crucial to its security.
To see this, suppose that we have a linear block cipher EL that encrypts 128-bit
blocks of plaintext into 128-bit blocks of ciphertext. Let EL(k, m) denote the
encryption of a 128-bit message m under a key k (the actual bit length of k is irrelevant).
Thus,
EL(k, [m1 m2]) EL(k,m1) EL(k,m2) for all 128-bit patterns m1,m2
Describe how, with 128 chosen ciphertexts, an adversary can decrypt any ciphertext
without knowledge of the secret key k. (A “chosen ciphertext” means that an adversary
has the ability to choose a ciphertext and then obtain its decryption. Here, you
have 128 plaintext–ciphertext pairs to work with, and you have the ability to chose
the value of the ciphertexts.) Get this solution
2.7 Suppose you have a true random bit generator where each bit in the generated
stream has the same probability of being a 0 or 1 as any other bit in the stream and
that the bits are not correlated; that is, the bits are generated from identical independent
distribution. However, the bit stream is biased. The probability of a 1 is 0.5 δ
and the probability of a 0 is 0.5 δ, where 0 δ 0.5.A simple deskewing algorithm
is as follows: Examine the bit stream as a sequence of non-overlapping pairs. Discard
all 00 and 11 pairs. Replace each 01 pair with 0 and each 10 pair with 1.
a. What is the probability of occurrence of each pair in the original sequence?
b. What is the probability of occurrence of 0 and 1 in the modified sequence?
c. What is the expected number of input bits to produce x output bits?
d. Suppose that the algorithm uses overlapping successive bit pairs instead of
nonoverlapping successive bit pairs. That is, the first output bit is based on input
bits 1 and 2, the second output bit is based on input bits 2 and 3, and so on.What
can you say about the output bit stream? Get this solution
2.8 Another approach to deskewing is to consider the bit stream as a sequence of
non-overlapping groups of n bits each and output the parity of each group.That is,
if a group contains an odd number of ones, the output is 1; otherwise the output
is 0.
a. Express this operation in terms of a basic Boolean function.
b. Assume, as in the Problem 2.7, that the probability of a 1 is 0.5 δ. If each group
consists of 2 bits, what is the probability of an output of 1?
c. If each group consists of 4 bits, what is the probability of an output of 1?
d. Generalize the result to find the probability of an output of 1 for input groups of
n bits. Get this solution
2.9 What RC4 key value will leave S unchanged during initialization? That is, after the
initial permutation of S, the entries of S will be equal to the values from 0 through 255
in ascending order. Get this solution
2.10 RC4 has a secret internal state which is a permutation of all the possible values of the
vector S and the two indices i and j.
a. Using a straightforward scheme to store the internal state, how many bits are
used?
b. Suppose we think of it from the point of view of how much information is represented
by the state. In that case, we need to determine how may different states there are, then take the log to the base 2 to find out how many bits of information this represents. Using this approach, how many bits would be needed to represent the state? Get this solution
2.11 Alice and Bob agree to communicate privately via e-mail using a scheme based on
RC4, but they want to avoid using a new secret key for each transmission. Alice and
Bob privately agree on a 128-bit key k.To encrypt a message m consisting of a string
of bits, the following procedure is used.
1. Choose a random 80-bit value v
2. Generate the ciphertext c RC4(v 7 k) m
3. Send the bit string (v 7 c)
a. Suppose Alice uses this procedure to send a message m to Bob. Describe how Bob
can recover the message m from (v 7 c) using k.
b. If an adversary observes several values (v1 7 c1), (v2 7 c2), . . . transmitted between
Alice and Bob, how can he/she determine when the same key stream has been
used to encrypt two messages? Get this solution
2.12 With the ECB mode, if there is an error in a block of the transmitted ciphertext, only
the corresponding plaintext block is affected. However, in the CBC mode, this error
propagates. For example, an error in the transmitted C1 (Figure 2.10) obviously corrupts
P1 and P2.
a. Are any blocks beyond P2 affected?
b. Suppose that there is a bit error in the source version of P1. Through how
many ciphertext blocks is this error propagated? What is the effect at the
receiver? Get this solution
2.13 Is it possible to perform encryption operations in parallel on multiple blocks of plaintext
in CBC mode? How about decryption? Get this solution
2.14 Suppose an error occurs in a block of ciphertext on transmission using CBC.What
effect is produced on the recovered plaintext blocks? Get this solution
2.15 CBC-Pad is a block cipher mode of operation used in the RC5 block cipher, but it
could be used in any block cipher. CBC-Pad handles plaintext of any length. The
ciphertext is longer than the plaintext by at most the size of a single block.
Padding is used to assure that the plaintext input is a multiple of the block length.
It is assumed that the original plaintext is an integer number of bytes. This plaintext
is padded at the end by from 1 to bb bytes, where bb equals the block size in
bytes. The pad bytes are all the same and set to a byte that represents the number
of bytes of padding. For example, if there are 8 bytes of padding, each byte has the
bit pattern 00001000.Why not allow zero bytes of padding? That is, if the original
plaintext is an integer multiple of the block size, why not refrain from
padding? Get this solution
2.16 Padding may not always be appropriate. For example, one might wish to store the
encrypted data in the same memory buffer that originally contained the plaintext. In
that case, the ciphertext must be the same length as the original plaintext. A mode for
that purpose is the ciphertext stealing (CTS) mode. Figure 2.13a shows an implementation
of this mode.
a. Explain how it works.
b. Describe how to decrypt Cn 1 and Cn. Get this solution
2.17 Figure 2.13b shows an alternative to CTS for producing ciphertext of equal length to
the plaintext when the plaintext is not an integer multiple of the block size.
a. Explain the algorithm.
b. Explain why CTS is preferable to this approach illustrated in Figure 2.13b. Get this solution
2.18 If a bit error occurs in the transmission of a ciphertext character in 8-bit CFB mode,
how far does the error propagate?
