Week 4 Part 1

Question 1

What part of the CIA triad do encryption, hash functions AND MACS ensure?

Answer 1

• Confidentiality: Maintained through Encryption.
• Integrity: Ensured by Hash Functions.
• Authenticity: maintained by MACS

Question 2

How do hash functions ensure integrity?

Answer 2

Alice can verify the integrity of Bob’s message by comparing her computed hash of the message with the hash provided by Bob. If they match, the message has not been altered.

Question 3

Explain a one-way function and a collision-resistant function and give examples.

Answer 3

• One- way function (OWF)
  A function (f) is one-way if:

1. Easy to compute
   
   1. Given x, easy to compute y= f(x) i.e.f an input is given you can find the output
2. Hard to invert:
   
   1. Given y, it is hard to find x s.t. y= f(x)

example: Product of large primes, e.g. 2048-bit, is a OWF, factorisation

• Collision- Resistant Function (CRF)
  A function (f) is CRF if:

1. Collision Difficulty:
   
   1. It is computationally hard to find any two distinct inputs x1 and x2 that produce the same output, where f(x1)=f(x2).

example: The identity function f (x) = x is a CRF.

Question 4

What are the requirements of a hash function?

Answer 4

1. Preimage-Resistance (One-Wayness):
   
   • It’s computationally infeasible to reverse-engineer the original input from its hash output.
2. Second Preimage Resistance (Weak-Collision Resistance):
   
   • Given an input, it’s difficult to find another input with the same hash output.
3. Collision-Resistance (Strong Collision-Resistance):
   
   • It is hard to find two distinct values x′,x such that H(x′) = H(x)
     
     • the adversary chooses the collision
     • find any two values that collides
     • if you satisfy this, you definitely satisfy weak-collision resistance

Question 5

How many times do we need to hash a function to find a collision?

Answer 5

f the output of H is n-bit long, we can always find collisions after hashing at most 2^(n) + 1 distinct messages

Question 6

What are some applications of hash functions?

Answer 6

• Instead of storing passwords in the clear, one stores H(password)
• Ensuring Software Integrity (that it has not been changed or tampered with
• Timestamping (proving you have discovered a secret earlier without disclosing it)
• Many cryptographic applications:
  
  • Message authentication
  • One-time passwords
  • Digital signatures
  • Commitment schemes
  • Proof of work (Bitcoin)

Question 7

What are some existing hash function and their bits and max message size? and are they secure?

Answer 7

• MD5 (128-bit) (max message size 2^64 bits) (Not secure, Broken!)
• SHA-1 (160-bit) (max message size 2^64 bits)(Not secure, Broken!)
• SHA - 2 (224, 256, 384. 512) (Max message size is 2^64, 2^64, 2^128, and 2^128 bits, respectively)
• SHA-3 (512 bit) (unlimited message size)

Question 8

What can we use to reduce the complexity of finding hash collisions? what would the complexity reduce to?

Answer 8

The Birthday Paradox can be exploited to reduce the complexity of finding hash collisions
- If the fingerprint is n-bit long, brute force attack requires O(2^n) hashes whereas a birthday attack requires O(2^ n/2)

Question 9

How can you perform a birthday attack on a hash function?

Answer 9

Birthday Attack on Hash Functions

1. Choose 2 ^n/2 random messages m1,…..,m 2^n/2
2. Obtain the fingerprint of all of those messages
3. If there is a collision, stop, otherwise go to Step 1

Question 10

Are hash functions deterministic?

Answer 10

yes same input produces the same output

Question 11

Briefly explain the Merkle Damgard construction.

Answer 11

The Merkle-Damgård construction is a framework for building hash functions that process a message in fixed-size blocks, applying a compression function sequentially to produce a final hash value.

Question 12

What are some attacks on hash functions and how to perform them?

Answer 12

• Dictionary attack
• You make a dictionary, you hash many words from the dictionary and then you search in the password column and then compare
  
  • need to store a lot of data
• Compute and store hashes of a list of popular password choices and do a table lookup
  
  • Matches if any means all such users used the password in question
• Rainbow Table Attack
• Rainbow tables trade space for time in attacking hashed passwords
• Involve computing large chains of password hashes
  
  • Hash and reduce approach

Question 13

What is the difference between a dictionary attack and rainbow table attack?

Answer 13

A dictionary attack relies on a list of common words and phrases to guess a password, while a rainbow table attack uses precomputed tables of password-hash pairs to quickly find a match. Both methods aim to discover passwords, but the rainbow table attack is more efficient when dealing with hashed passwords, while a dictionary attack is more general and may work against simpler, common passwords.

Question 14

How do we protect against dictionary and rainbow table attacks?

Answer 14

Add a salt to the password before hashing, store salt andH(password||salt)

Question 15

When using hash functions for integrity of software release (download) which property is the most important?

Answer 15

Weak-collision resistance

Question 16

When comparing the collision resistance strength of SHA-256 and SHA-512 which of the following is correct?

Answer 16

Finding SHA-512 collisions effort is 2^128 times that of SHA-256

• For SHA-256, finding a collision would take roughly 2^128 operations, because 256/2=128.
• For SHA-512, finding a collision would take roughly 2^256 operations, because 512/2 = 256
• Therefore2^256/2^128=2^128

Question 17

A one-way and bijective function f : {0, 1}^n → {0, 1}^n (each input corresponds to one distinct output) was used to construct a hash function H : {0, 1}^2n → {0, 1}^n, where to hash an input m = mL||mR ∈ {0, 1}^2n (i.e. mL and mR are n-bit long each), we compute H(m) = f (mL ⊕ mR) (⊕ denotes XOR). Is H collision-resistant? Justify your answer.

Answer 17

H is not collision-resistant, and not even weakly collision-resistance! ⊕ is commutative and hence for any m = mL||mR where mL does not equal mR, we can easily find a collision in the form m′ = mR||mL. There are other ways to find collisions even when mL = mR.
- basically: because XOR is commutative, meaning a XOR b equals b XOR a , you can reverse the m L and m R and still get the same result when you apply the XOR operation. So if you have a message m that’s made of mL followed by mR, you can create a different message m′ by swapping mL and mR around, and after hashing, both m and m′ will give the same hash value. This is a collision.

Question 18

Choose ALL correct answers from the following: A (non-programmable) random oracle maps different inputs to different random outputs but it always returns the same answer for the same input, Hash functions are deterministic, A hash function that is (strongly) collision-resistant is also weakly collision-resistant. size of the output of a hash function depends on the size of its input.

Answer 18

The only wrong answer is the size of the output of a hash function depends on the size of its input. The size of a hash function is n bits regardless of the size of the message. it can be 1 bit or 100 bits.

Question 19

We have a collision-resistant (and also one-way) hash functionGwhich maps arbitrary-length inputs to n-1 bits long outputs for some fixed number n.

We have usedGto construct another hash functionH whose output is n bits long as follows:

To computeH(M), we proceed as follows:

• If M is exactly n-1 bits long, we computeH(M)=1 || M
• Otherwise, we computeH(M)= 0 ||G(M)

Where || denotes string concatenation. Note that the output of His always n bits long.

Which of the following is correct about the hash function H.Choose only one answer. H is both collision-resistant and one-way H is collision-resistant but not one-way. H is neither collision-resistant nor one-way. H is one-way but not collision-resistant

Answer 19

H is collision resistant but not one way

From what the question is telling us, we can infer that H is collision resistant and one way when its n bits because it is using G(M). However, when its n-1 bits its not using G(M). H is collision resistant because M is unique but not one way because we can reverse the concatenation

Question 20

A user’s password has been hashed without a salt using the (insecure) hash function SHA-1. We managed to learn the last 4 characters of the user’s password which are “rise” We also have information that the concerned password is exactly 8 characters long and it consists of only lower-case English alphabet letters.

The SHA-1 hash of the password (in hexadecimal) is :63e76d7b9e5059006df47479d8b6f78294c74852

What is the user’s full password (as a string without quotes)? (what is the sage code for it?

Answer 20

surprise

import hashlib

The known last 4 characters
last4 = “rise”

Set of characters for the first 4 characters of the password
charset = “abcdefghijklmnopqrstuvwxyz”

Iterate through all possible combinations
for char1 in charset:
for char2 in charset:
for char3 in charset:
for char4 in charset:
# Combine the first 4 characters
first4 = char1 + char2 + char3 + char4
# Combine the full password
password = first4 + last4
# Calculate the SHA-1 hash
sha1_hash = hashlib.sha1(password.encode()).hexdigest()
# Check if the hash matches the one you have
if sha1_hash == “63e76d7b9e5059006df47479d8b6f78294c74852”:
print(f”Found password: {password}”)
break

Question 21

When combining two hash functionH1andH2to construct a hash functionHasH(M) =H1(M) ||H2(M), which statement about the collision resistance ofHis correct, where || denotes string concatenation.Choose only one answer. Both H1 and H2 must be collision-resistant for H to be collision-resistant. Even if both H1 and H2 are collision-resistant, H cannot be collision-resistant. It suffices for either H1 or H2 to be collision-resistant for H to be collision-resistant.

Answer 21

It suffices for either H1 or H2 to be collision-resistant for H to be collision-resistant.
The reason that either H1 or H2 being collision resistant is enough for H to be collision resistant is because if there’s a collision for H1 || H2, it’s also a collision for H1 and H2 and if one of them is collision resistant than its not possible

Question 22

Consider two secure collision-resistant cryptographic hash functions H1and H2whose message digests are 64-bit and 32-bit, respectively. Taking the implication of the birthday paradox into account, which of the following statements is correct.Only choose one answer H1 is twice as collision-resistant as H2. H1 is 2^5 times as collision-resistant as H2. H1 is 2^16 times as collision-resistant as H2. H1 is 2^64 times as collision-resistant as H2.

Answer 22

H1 is 2^16 times as collision-resistant as H2

Given the birthday paradox, for an n-bit hash function, it is considered to have roughly 2^(n/2) resistance against collisions.

• H1 has a 64-bit message digest, so its collision resistance is roughly 2^(64/2) = 2^32.
• H2 has a 32-bit message digest, so its collision resistance is roughly 2^(32/2) = 2^16.

To find out how many times collision-resistant H1 is we divide them: 2^32 / 2^16 which gives us 2^16

H1 is 2^16 times as collision-resistant as H2

Question 23

A system has used an ideal hash function H : {0, 1}∗ → {0, 1}30 that behaves like a random oracle to hash the users’ passwords. Upon login attempt, the user presents his/her password to the system and the system grants access only if H(w) matches the stored user password hash in the password file. Note that a password hash collision with a particular user would mean that those users would be able to login on behalf of each other. An attacker A is attempting to login as the root user (System Administrator) by brute forcing its password. The attacker is not repeating any failed attempts, i.e. it is excluding any previous wrong guesses rejected by the system. How many password guesses A has to try before it can have at least 10% chance (probability 0.1) of succeeding?

Answer 23

For a hash whose output is k-bit long, its output space has 2^k possible outputs.
When k = 30
there are 2^30 possible different passwords to choose from.
In the first attempt, the probability Pr(F1) that the adversary fails is 2^k -1 / 2^k i.e. all but one hash value would fail.
Generalising this to failing after t attempts, the probability Pr(Failt) = 2^k -1 =1- t/2^k.
The probability Pr(Succeed) that A succeeds after t attempts is thus: Pr(Succeed) =
1- Pr(Failt) = t/2^k
Plugging k = 30, in the above,we are looking for the value t such that t / 2^30 ≥ 0.1, i.e. t ≥ 0.1 * 2^30. we have t = 107374183