8 - Cryptographic Hash Functions

Question 1

Applications of hash functions

Answer 1

• Hash tables
• Checking integrity
• File comparison for searching
• Cryptography

Question 2

Requirements of crypto hash function H

Answer 2

• Input of H is of any length
• H output has fixed short length and is called the hash value
• H(x) is relatively easy to compute
• Random inputs should result in uniformly distributed outputs
• Small changes should be likely to produce a change in output

One-way / preimage resistance:
- For h, unfeasible to find x H(x) = h

Weak collision resistance/second preimage:
- For x, unfeasible to find y where H(x) = H(y)

Strong collision resistance
- Unfeasible to find ANY pair x and y where H(x) = H(y)
( Can pick both inputs, rather than given one in weak)

Question 3

If a hash function is not one-way…

Answer 3

A hacker could find the message that has the message digest and then present the message as being signed by Bob

Question 4

For all files of 1MB and a 256bits output, can we assign a unique hash to everything

Answer 4

No. The number of possible files is much bigger than the output size.

Some hashes would not be unique.

Question 5

Collisions in hashing

Answer 5

two inputs hashing to the same output

Typically, collisions WILL happen.
- Require that collisions should be hard to find so that brute force takes too long and theres no other better method.

Question 6

Possible attack if H is not weak collision resistant

Answer 6

• message x with sig s
• find another y with H(x) = H(y)
• y with sig s passed as though genuinely signed

Question 7

Possible attack if H not strong collision resistant. (Birthday Attack!)

Answer 7

• Several versions of valid x and fraudulent doc y until H(x)=H(y)
• Sign x to get s
• Substitute in y with sig. s

Question 8

Birthday Attack

Answer 8

• n bit output hash
• find H(x)=H(y)
• approximately 0.5 success after hashing ~2^*(n/2) inputs

Hash should be 160 (2^80 computaitons for brute force) bits min but more commonly 256bits

Question 9

Recommended Hash functions

Answer 9

SHA-2: SHA-256 and SHA-512

SHA-3 also exists

Question 10

Breaking a hash function

Answer 10

Are there methods for finding collisions significantly quicker than brute force

MD5, RIPEMD-160 and SHA-1 have been broken this way

Question 11

Applications of hash functions

Answer 11

• Digital signatures
• PAssword storage
• Blockchain
• Proof of work
• Message auth codes
• Creating Keys

Question 12

When storing passwords, why is a salt necessary?

Answer 12

To mitigate using pre-computed lookup tables by concatenating in a “salt” value before submitting a password.

Unique salt per user