Question

One of the earlier applications of cryptographic hash functions was the storage

of passwords for user authentication in computer systems. With this method, a
password is hashed after its input and is compared to the stored (hashed) reference
password. People realized early that it is sufficient to only store the hashed versions
of the passwords.

1. Assume you are a hacker and you got access to the hashed password list. Of
course, you would like to recover the passwords from the list in order to impersonate
some of the users. Discuss which of the three attacks below allow this.
Exactly describe the consequences of each of the attacks:
Attack A: You can break the one-way property of h.
Attack B: You can find second preimages for h.
Attack C: You can find collisions for h.
2. Why is this technique of storing hashed passwords often extended by the use
of a so-called salt? (A salt is a random value appended to the password before
hashing. Together with the hash, the value of the salt is stored in the list of hashed
passwords.) Are the attacks above affected by this technique?
3. Is a hash function with an output length of 80 bit sufficient for this application?

Answer 1

There are three attacks that could allow a hacker to recover passwords from hashed password lists - Attack A: breaking the one-way property of the hash function, Attack B: finding second preimages, and Attack C: finding collisions. Using a salt, which is a random value appended to the password before hashing, can greatly reduce the impact of these attacks. An 80-bit hash function output length is not considered sufficient for storing hashed passwords.

Step-by-step explanation:

1. Attack A: Breaking the one-way property of the hash function would allow the hacker to recover the passwords from the hashed password list. Essentially, this means finding the original input that resulted in a specific hash value. This attack would have significant consequences as it would compromise the security of the system and allow the hacker to impersonate users.

Attack B: Finding second preimages for the hash function would also enable the hacker to recover the passwords. A second preimage is a different input that produces the same hash value as the original input. This attack would have similar consequences as Attack A, as the hacker would be able to impersonate users.

Attack C: Finding collisions for the hash function means finding two different inputs that produce the same hash value. While this attack may not directly help the hacker recover the original passwords, it can still have serious consequences. The hacker could use the collisions to log in as different users without needing to know their actual passwords.

2. The technique of using a salt involves appending a random value to the password before hashing it. This salt value is stored together with the hashed password. By using salts, the impact of a precomputed table attack is greatly reduced. This is because each password would have a different salt, resulting in a unique hash value even for the same passwords. Therefore, attacks A, B, and C would be affected by the use of salts, making it harder for hackers to recover the passwords.

3. The security of a hash function is dependent on its output length. Generally, a longer output length provides better security against attacks. An 80-bit hash function output length would not be considered sufficient for storing hashed passwords. As computational power increases, it becomes easier for attackers to brute force or use other techniques to crack shorter hash function output lengths.

Answer 2

Answer & Explanation:

1.

_Attack A: One way property of hash means that we can't find the input string if given the hash value. The calculation of hash from input string is possible but it is not possible to calculate the input string when given the hash. If the hash function is properly created to have one-way property then there is no way of finding the exact input string. So this attack won't work as the one-way property of hash function can't be broken if hash function is properly created.

_Attack B: Suppose h() is the hash function. And h(x) = m where x is the string and m is the hash. Then trying to find another string y such that h(y) = m is called finding out the second pre-image of the hash.

Although we can't know the exact initial string for sure, we can by using brute force method find out a second pre-image.

This attack will take a very long time. It has the time complexity of
`2^(n)` . It requires the attacker to have an idea about the kind of passwords that might be used and then brute force all of them to find string that has the same hash. Each try will have a chance of 1/
`2^(n)` to succeed.

Rainbow attack using rainbow table is often used for such brute force attack. This comprises a rainbow table which contains passwords and their pre-hashed values.

Therefore, it is not possible to determine the second preimages of h so easily.

_Attack C: Collisions refer to finding out m and m' without knowing any of them. Finding out collisions is easier than finding preimages. This is because after finding out
`2^(n)` pairs of input/output. The probability of two of them having the same output or hash becomes very high. The disadvantage is that we can't decide which user's hash to break. However if I do not care about a particular user but want to get as many passwords as possible, then this method is the most feasible.

It has time complexity of
`2^(n)` /2.

Hence, this is the attack which has most success rate in this scenario.

2.

The brute force way of finding out the password usually involves using a rainbow attack. It comprises a rainbow table with millions of passwords and their hashes already computed. By matching that table against the database, the password can be recovered.

Therefore it is often preferred to salt the password. It means we add some random text to the password before calculating the hash.

The salts are usually long strings. Although users usually do not select long passwords, so a rainbow table with hashes of smaller passwords is feasible. But once salt is used, the rainbow table must accommodate for the salt also. This makes it difficult computationally. Although password might be found in the rainbow table. The salt can be anything and thus, make brute force a LOT more difficult computationally.

Therefore salt is preferred to be added to passwords before computing their hash value.

3.

A hash output length of 80 means there can be exactly
`2^(80)` different hash values. This means there is at least one collision if
`2^(80)`+1 random strings are hashed because
`2^(80)` values are used to accommodate all the possible strings. It is not hard with today's computation power do match against more than this many strings. And doing so, increases the probability of exposing a probable password of an user.

Hence, 80 is not a very secure value for the hash length.