11.1 What types of attacks are addressed by message authentication?
11.2 What two levels of functionality comprise a message authentication or digital signature mechanism?
11.3 What are some approaches to producing message authentication?
11.4 When a combination of symmetric encryption and an error control code is used for message authentication, in what order must the two functions be performed?
11.5 What is a message authentication code?
11.6 What is the difference between a message authentication code and a one-way hash function?
11.7 In what ways can a hash value be secured so as to provide message authentication?
11.8 Is it necessary to recover the secret key in order to attack a MAC algorithm?
11.9 What characteristics are needed in a secure hash function?
11.10 What is the difference between weak and strong collision resistance?
11.11 What is the role of a compression function in a hash function?
Problems
11.1 If F is an error-detection function, either internal or external use (Figure 11.2) will provide error-detection capability. If any bit of the transmitted message is altered, this will be reflected in a mismatch of the received FCS and the calculated FCS, whether the FCS function is performed inside or outside the encryption function. Some codes also provide an error-correction capability. Depending on the nature of the function, if one or a small number of bits is altered in transit, the error-correction code contains sufficient redundant information to determine the errored bit or bits and correct them. Clearly, an error-correction code will provide error correction capability when used external to the encryption function. Will it also provide this capability if used internal to the encryption function?
11.2 The data authentication algorithm, described in Section 11.3, can be defined as using the cipher block chaining (CBC) mode of operation of DES with an initialization vector of zero (Figure 11.6). Show that the same result can be produced using the cipher feedback mode.
11.3 The high-speed transport protocol XTP (Xpress Transfer Protocol) uses a 32-bit checksum function defined as the concatenation of two 16-bit functions: XOR and RXOR, defined in Section 11.4 as "two simple hash functions" and illustrated in Figure 11.7.
a. Will this checksum detect all errors caused by an odd number of error bits? Explain.
b. Will this checksum detect all errors caused by an even number of error bits? If not, characterize
the error patterns that will cause the checksum to fail.
c. Comment on the effectiveness of this function for use as a hash function for authentication.
11.4
a. Consider the Davies and Price hash code scheme described in Section 11.4 and assume that
DES is used as the encryption algorithm:
Hi = Hi1+ E(Mi, Hi1)
and recall the complementarity property of DES (Problem 3.14): If Y = E(K, X), then Y' = E(K', X').
Use this property to show how a message consisting of blocks M1, M2,..., MN can be altered
without altering its hash code.
b. Show that a similar attack will succeed against the scheme proposed inM [ EYE88]:
Hi = Mi+ E(Hi1, Mi)
a. Consider the following hash function. Messages are in the form of a sequence of decimal
numbers, M = (a1, a2,..., ai). The hash value h is calculated as
the requirements for a hash function listed in Section 11.4? Explain your answer.
b. Repeat part (a) for the hash function
11.6 It is possible to use a hash function to construct a block cipher with a structure similar to DES. Because a hash function is one way and a block cipher must be reversible (to decrypt), how is it possible?
11.7 Now consider the opposite problem: using an encryption algorithm to construct a one-way hash function.
Consider using RSA with a known key. Then process a message consisting of a sequence of blocks as
follows: Encrypt the first block, XOR the result with the second block and encrypt again, etc. Show that this scheme is not secure by solving the following problem. Given a two-block message B1, B2, and its hash RSAH(B1, B2) = RSA(RSA (B1)+ B2)
Given an arbitrary block C1, choose C2 so that RSAH(C1, C2) = RSAH(B1, B2). Thus, the hash function does not satisfy weak collision resistance.
11.8 Suppose H(m) is a collision resistant hash function that maps a message of arbitrary bit length into an- bit hash value. Is it true that, for all messages x, x' with x != x', we have H(x) != H(x')? Explain your answer.
