Week 5: Hash Functions

Question 1

What does a cryptographic hash do?

Answer 1

A cryptographic hash maps a string into a new shorter string.

Question 2

What are some applications of Hash Functions?

Answer 2

• Secure password storage.
• Integrity Checks
• Fingerprinting

Question 3

What is an Ideal Cryptographic Hash?

Answer 3

Input: Arbitrary-length string
Output: Fixed length string
Each repeated input gives same output as before. Each output is unique.

Question 4

What are the Security Properties of a Hash Function?

Answer 4

1. Pre-image resistance
2. Second pre-image resistance.
3. Collision resistance.

Question 5

In Hash Functions, what is Pre-image resistance?

Answer 5

Given hash [h(x)], it should be hard to find a message [x] that produces that hash [h(x)].

Given h(x), hard to find x.

Question 6

In Hash Functions, what is Second pre-image resistance?

Answer 6

Given message [x1], it should be hard to find another message [x2] that produces same hash.

Given x1, h(x1) hard to find x2 where h(x1) == h(x2)

Question 7

In Hash Functions, what is Collision resistance?

Answer 7

It should be hard to find any two messages x1, x2 that produce same hash.

Hard to find any messages x1, x2 where h(x1) == h(x2)

Question 8

Given a hash length, how many messages do you need to look through to have collision?

Answer 8

Collision will occur after 2^(k/2) attempts. Where k is hash key length.

Question 9

How does Merkle-Damgard Construction work?

Answer 9

1. Initial Value and first message block is fed into compression function.
2. Output from 1 and second message block is fed into compression function.
   …
   Final output is the hash.

Question 10

How does a SHA-1 Compression Function work?

Answer 10

1. Pads input message if necessary.
2. Split input message into 32 bit chunks.
3. Start with 5 input constants (IV) and modify each through bitwise operations as you loop through chunks.
4. Output final (32*5) 160 bit message.