Laboratory Exercises: Authentication Functions

Introduction

In this exercise we survey theory and some applications of cryptographic hash functions. We begin our study by analyzing basic properties of hash functions such as "one-wayness" and "collision-resistance". We demonstrate the application of hash functions in the construction of cryptographic puzzles and message authentication codes. Finally, we study the most commonly used construction for hash functions: Merkle-Damgard construction. We show some important security implications (problems) of this construction.

Exercise -

Hash function H(·) generates a representative compact fingerprint (a hash value) of a given piece of information. As such, H(·) has to satisfy the following properties: H(·) is applicable to messages of arbitrary (finite) size, it generates a hash value of a fixed size, and it can be easily (quickly) generated for any message.

In order to be useful in cryptographic applications, a hash function has to satisfy some or all of the following properties:

• One-way property. Hash function H() is one-way if for the given hash value h it is hard to find pre-image x such that H(x) = h.
• Weak-collision resistance (second-preimage resistance). For the fixed preimage x, it is hard to find another preimage y = x such that they hash to the same value, that is, H(y) = H(x).
• Strong-collision resistance. It is hard to ?nd x and y = x such that H(x) = H(y).

It is easy to see that strong-collision resistance implies weak-collision (second-preimage) resistance.

Task 1.1. Cryptographic Hash Functions: Basics

1. Consider all possible 200 bit long inputs to hash function H(·). Assume that H(·) outputs 160 bit hash values. How many input values, on average, hash to each possible output value?

(Hint: Model H(·) as follows. For a given n bit hash value H(x), the probability that the hash value H(y) of a randomly chosen message (preimage) y, equals H(x), is approximately 2-n.)

2. Consider the following hash value obtained by hashing with SHA-1 a single letter of English alphabet: C6 3A E6 DD 4F C9 F9 DD A6 69 70 E8 27 D1 3F 7C 73 FE 84 1C. Find the corresponding letter. Describe your approach. Use CrypTool to accomplish this task.

3. Assume that you succeed in the previous task (you recover the hashed letter). Does you success imply that that SHA-1 hash function does not satisfy one-way property? Explain your answer.

4. Create a new document in CrypTool by clicking on the icon "New". Write some text in the new document. In the main menu, under "Indiv. Procedures" sub-menu select "Hash . Hash Demonstration..." to open "Hash demo" window. Modify text that appears in "Actual document" window and observe what happens with the corresponding hash value. Explain your observation.

Task 1.2. Weak- and Strong-Collision Resistance

1. Consider a hash function that outputs 50 bit long hash values. What is the average workload needed for finding second-preimage with this hash function? Similarly, what is the average workload needed for finding a collision? Express the attack average workload as the average number of hash function evaluations needed for a successful attack.

2. In this task we will introduce a simple security primitive called a cryptographic puzzle. A cryptographic puzzle is used in situations where a server wants to prevent potential clients from "overusing" the service. Thus, before using a service, a client is asked to solve a simple puzzle. If a client attempts to overuse the service, it has to solve a potentially large number of puzzles, which effectively deters the client from overusing the service.

A cryptographic puzzle can be effectively implemented with a hash function as follows. Let C be a random challenge that a server sends to a client upon receiving a request for a service. Then the client is granted the service only if it returns to the server a value R such that the following equation holds:

where X can be any value.

Answer the following questions. What is the average workload of the client? What is the workload of the server; the work required to verify that H(Rk||C) begins with n zeros?

3. Use "Hash demo" window in CrypTool and equation (1) to solve the following cryptographic puzzle: C = Mario Cagalj and n = 7. Provide solution R to the puzzle. What was the required workload?

4. Is the following statement correct or not? Cryptographic puzzle admits a unique solution R. Please explain your answer.

5. Cryptographic hash functions find their application in the construction of efficient digital signatures. Recall, a digital signature procedure prescribes that a hash value of a message is to be signed, instead of signing the message directly. Which property a hash function has to satisfy in order to be useful for the digital signature? Please explain.

6. Use CrypTool to find a collision in the first (most significant) 40 bits of a hash value produced by SHA-1. In main menu, choose "Analysis  Hash  Attack on the Hash Value of the Digital Signature..." and follow instructions therein. Provide messages which collide in the first 40 bits.

Task 1.3. Merkle-Damgard Iterative Construction

The most commonly used construction for hash functions is called the Merkle-Damgard construction. The construction iterates the compression function C defined as follows:

C: {0, 1}ⁿ × {0, 1}^m|→ {0, 1}ⁿ.

The input to the hash function, a message M, is broken into m-bit blocks (e.g., m = 512); the last block is padded if necessary. In each iteration 1 ≤ i ≤ k + 1 the compression function C takes as arguments an m-bit message block Mi and an n-bit chaining variable hi-1 and produces an n-bit chaining variable hi. Note that h0 = IV is set to some predefined initial value. Note also that in the last iteration (i = k + 1) the compression function C takes as arguments an encoding M_k+1 of the length of the message M and the last but one chaining variable h_k. Finally, the value of the last chaining variable h_k+1 represents the hash value of the entire message M.

The most important result on this construction states that if the compression function C is collision-resistant, so is the resulting construction. However, the iterative nature of this construction creates a number of security vulnerabilities.

1. Consider the following two messages formatted into m-bit blocks:

M⁽¹⁾ = M₁||M₂||M₃||M₄

M⁽²⁾ = M₁||M₂||M'₃||M₄.

Assume that blocks M₃ and M'₃ ≠ M₃ collide under the compression function C(·), that is,

C(h₂,M₃) = C(h₂,M'₃) = h₃.

Show that the two messages M⁽¹⁾ and M⁽²⁾ ≠ M⁽¹⁾ collide under the hash function built using the Merkle-Damg°ard construction and the compression function C(·).

2. Consider a hash function H_real(·) that is based on the Merkle-Damgard construction. Assume that we can find a collision for a single iteration of the Merkle-Damgard construction, that is, a collision on the compression function C(·). Due to the birthday paradox, we know that in time √2ⁿ = 2^n/2 we can find two messages M₁ and M'₁ such that

C(h₀,M₁) = C(h₀, M'₁) = h₁.

Again, in 2^n/2 time, we can find another collision, that is two messages M₂ and M'₂ such that

C(h₁,M₂) = C(h₁,M'₂) = h₂.

Answer, what is the total time required to ?nd two collisions?

Consider now the following four messages:

M⁽¹⁾ = M₁||M₂

M⁽²⁾ = M'₁||M₂

M⁽³⁾ = M₁||M'₂

M⁽⁴⁾ = M'₁||M'₂.

What value do the above four messages hash to? What do you observe? What is the total number of collisions that we have found in time 2 × 2^n/2? Contrast this number with the number of collisions that we would be able to find had we used an ideal hash function.

3. A hash function is commonly used as building block for message authentication codes (MACs). Let H_ideal(·) be an ideal hash function. Then, the following construction results in a perfect MAC function H_k(·): H_k(m) = H_ideal(k||m), where k is a secret key. However, if we instantiate the ideal hash function H_ideal(·) with a real one that uses the Merkle-Damgard construction (e.g., SHA-1), the above MAC construction is not secure.

Consider a real hash function H_real(·), a message M of size 248 bits and a secret key k of size 100 bits. Let us assume that the message block in the Merkle-Damgard construction of H_real(·) is 512 bits long. Let us also assume the 64-bit encoding of the length of the message to be hashed. Assume that we calculate the MAC of M as follows:

MAC(M) = H_real(k||M).                                 (2)

Then, the following holds:

where C(·) is the compression function used in H_ideal(·).

Assume now that an attacker knows (intercept) for example, MAC(·) may output a 512-bit MAC, in which case MAC(M) is easily obtainable. The attacker doesn't know the secret key k. The attacker next constructs the following message M':

where X is an arbitrary x-bit message (1 ≤ x ≤ 448).

Your task is to show that the following holds:

What is the implication of the last equation? Is the MAC construction given by equation (2) secure? (Hint: Note that MAC(M), C(·), X, "padding", "length" are all public values (known by the attacker).)

4. Consider the following construction for a MAC function:

MAC(M) = H_real(M||k) .                                                (3)

Is it secure? Contrast this construction to H_real(k||M). (Hint: What could be a problem with the construction given by expression (3) if you would be able to find M and M ≠ M' such that H_real(M) = H_real(M')?)

Attachment:- Authentication Functions Assignment.rar