11.1 What characteristics are needed in a secure hash function?
Get 11.1 exercise solution
11.2 What is the difference between weak and strong collision resistance?
Get 11.2 exercise solution
11.3 What is the role of a compression function in a hash function?
Get 11.3 exercise solution
11.4 What is the difference between little-endian and big-endian format?
Get 11.4 exercise solution
11.5 What basic arithmetical and logical functions are used in SHA?
Get 11.5 exercise solution
11.6 Describe the set of criteria used by NIST to evaluate SHA-3 candidates.
Get 11.6 exercise solution
11.7 Define the term sponge construction.
Get 11.7 exercise solution
11.8 Briefly describe the internal structure of the iteration function f.
Get 11.8 exercise solution
11.9 List and briefly describe the step functions that comprise the iteration function f.
Get 11.9 exercise solution
Problems
11.1 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.5. 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.
Get 11.1 exercise solution
11.2
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 = Hi-1⊕ E(Mi, Hi-1) 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,c, MN can be altered without altering its hash code. b. Show that a similar attack will succeed against the scheme proposed in [MEYE88]: Hi = Mi⊕ E(Hi-1, Mi)
Get 11.2 exercise solution
11.3
a. Consider the following hash function. Messages are in the form of a sequence of numbers in Zn, M = (a1, a2,cat). The hash value h is calculated as
for some predefined value n. Does this hash function satisfy any of the requirements for a hash function listed in Table 11.1? Explain your answer. b. Repeat part (a) for the hash function
mod n. c. Calculate the hash function of part (b) for M = (189, 632, 900, 722, 349) and n = 989.
Get 11.3 exercise solution
11.4 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?
Get 11.4 exercise solution
11.5 Now consider the opposite problem: using an encryption algorithm to construct a oneway 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.
Get 11.5 exercise solution
11.6 Suppose H(m) is a collision-resistant hash function that maps a message of arbitrary bit length into an n-bit hash value. Is it true that, for all messages x, x′ with x ≠ x′, we have H(x) ≠ H(x′) Explain your answer.
Get 11.6 exercise solution
11.7 In Figure 11.12, it is assumed that an array of 80 64-bit words is available to store the values of Wt, so that they can be precomputed at the beginning of the processing of a block. Now assume that space is at a premium. As an alternative, consider the use of a 16-word circular buffer that is initially loaded with W0 through W15. Design an algorithm that, for each step t, computes the required input value Wt.
Get 11.7 exercise solution
11.8 For SHA-512, show the equations for the values of W16, W17, W18, and W19.
Get 11.8 exercise solution
11.9 State the value of the padding field in SHA-512 if the length of the message is a. 1919 bits b. 1920 bits c. 1921 bits
Get 11.9 exercise solution
11.10 State the value of the length field in SHA-512 if the length of the message is a. 1919 bits b. 1920 bits c. 1921 bits
Get 11.10 exercise solution
11.11 Suppose a1a2a3a4 are the 4 bytes in a 32-bit word. Each ai can be viewed as an integer in the range 0 to 255, represented in binary. In a big-endian architecture, this word represents the integer a1224 + a2216 + a328 + a4 In a little-endian architecture, this word represents the integer a4224 + a3216 + a228 + a1 a. Some hash functions, such as MD5, assume a little-endian architecture. It is important that the message digest be independent of the underlying architecture. Therefore, to perform the modulo 2 addition operation of MD5 or RIPEMD-160 on a big-endian architecture, an adjustment must be made. Suppose X = x1 x2 x3 x4 and Y = y1 y2 y3 y4. Show how the MD5 addition operation (X + Y) would be carried out on a big-endian machine. b. SHA assumes a big-endian architecture. Show how the operation (X + Y) for SHA would be carried out on a little-endian machine.
Get 11.11 exercise solution
11.12 This problem introduces a hash function similar in spirit to SHA that operates on letters instead of binary data. It is called the toy tetragraph hash (tth).6 Given a message consisting of a sequence of letters, tth produces a hash value consisting of four letters. First, tth divides the message into blocks of 16 letters, ignoring spaces, punctuation, and capitalization. If the message length is not divisible by 16, it is padded out with nulls. A four-number running total is maintained that starts out with the value (0, 0, 0, 0); this is input to the compression function for processing the first block. The compression function consists of two rounds.
Round 1 Get the next block of text and arrange it as a row-wise 4 * 4 block of text and covert it to numbers (A = 0, B = 1, etc.). For example, for the block ABCDEFGHIJKLMNOP, we have
Then, add each column mod 26 and add the result to the running total, mod 26. In this example, the running total is (24, 2, 6, 10).
Round 2 Using the matrix from round 1, rotate the first row left by 1, second row left by 2,
third row left by 3, and reverse the order of the fourth row.
In our example:
Now, add each column mod 26 and add the result to the running total. The new running total is (5, 7, 9, 11). This running total is now the input into the first round of the compression function for the next block of text. After the final block is processed, convert the final running total to letters. For example, if the message is ABCDEFGHIJKLMNOP, then the hash is FHJL. a. Draw figures comparable to Figures 11.9 and 11.10 to depict the overall tth logic and the compression function logic. b. Calculate the hash function for the 48-letter message “I leave twenty million dollars to my friendly cousin Bill.” c. To demonstrate the weakness of tth, find a 48-letter block that produces the same hash as that just derived. Hint: Use lots of A’s.
Get 11.12 exercise solution
11.13 For each of the possible capacity values of SHA-3 (Table 11.5), which lanes in the internal 55 state matrix start out as lanes of all zeros?
Get 11.13 exercise solution
11.14 Consider the SHA-3 option with a block size of 1024 bits and assume that each of the lanes in the first message block (P0) has at least one nonzero bit. To start, all of the lanes in the internal state matrix that correspond to the capacity portion of the initial state are all zeros. Show how long it will take before all of these lanes have at least one nonzero bit. Note: Ignore the permutation. That is, keep track of the original zero lanes even after they have changed position in the matrix.
Get 11.14 exercise solution
11.15 Consider the state matrix as illustrated in Figure 11.16a. Now rearrange the rows and columns of the matrix so that L[0, 0] is in the center. Specifically, arrange the columns in the left-to-right order (x = 3, x = 4, x = 0, x = 1, x = 2) and arrange the rows in the top-to-bottom order (y = 2, y = 1, y = 0, y = 4, y = 6). This should give you some insight into the permutation algorithm used for the function and for permuting the rotation constants in the function. Using this rearranged matrix, describe the permutation algorithm.
Get 11.15 exercise solution
11.16 The function only affects L[0, 0]. Section 11.6 states that the changes to L[0, 0] diffuse through u and to all lanes of the state after a single round. a. Show that this is so. b. How long before all of the bit positions in the matrix are affected by the changes to L[0, 0]?
Get 11.16 exercise solution
