Properties for cryptographic hash functions (preimage, second preimage and collision resistant)

Question

While studying computer security at university I have been asked this question:

There are three desirable properties for cryptographic hash functions: Preimage resistant, Second preimage resistant, and Collision-resistant. For each of the following applications of hash functions, explain which of these three properties are needed and which are not.

1) Alice poses to Bob a tough math problem and claims she has solved it. Bob would like to try it himself, but would yet like to be sure that Alice is not bluffing. Therefore, Alice writes down her solution, appends some random bits, computes its hash and tells Bob the hash value (keeping the solution secret). This way, when Bob comes up with the solution himself a few days later, Alice can verify his solution but still be able to prove that she had a solution earlier.

2) Passwords are stored in a password file, in hashed form. To authenticate a user, the password presented by the user is hashed and compared with the stored hash. A user who gains read access to the password file should not be able to log in by this method. (Assume that the mischievous user does not modify the system in any way before trying to log in.)

3) A system administrator, concerned about possible breakins, computes the hash of important system binaries and stores the hash values in a read-only file. A program periodically recomputes the hash values of the files containing the system binaries, and compares them to the stored values. A malicious user who is able to overwrite one of the ``protected'' files should not be able to change the file without detection.

I cannot find an answer, if anyone could help me it would be very kind!

Answer 1

These questions do not concern any mathematical properties of hashing functions, just the requirements of the defender and the abilities of the attackers. This is a pretty common feature for modeling security systems; so it's good to get familiar with it.

1. This one is less clear than the others; but let's assume that there was a finite set of possible solutions, like a multiple choice test; and Bob wants to be sure, later, that Alice wrote down the correct one. In this case, what they need is a collision resistant algorithm. If she could easily find collisions, Alice could simply write down each of the answers, and append arbitrary bits such that they all hashed to the same value.

This isn't just a theoretical risk; it has actually been done: http://www.win.tue.nl/hashclash/Nostradamus/

1. The defender here is the owner of the resource being logged into; he doesn't want to authenticate someone improperly by verifying a hash if the correct plaintext was not presented. The attacker has the hashes, and wants to find any plaintext that'll let him authenticate. That means he needs to find some plaintext that hashes to a particular value--a preimage attack.

2. The system owner wants to make sure that, if the hash of the file matches, that guarantees that the system file is unmodified. In other words, he wants to be sure that only one plaintext corresponds to each hash. The attacker (probably) has access to both the plaintexts and the hashes, but he needs to find a second pre-image for a given hash.

BTW, Alice should consider using a zero-knowledge proof: http://en.wikipedia.org/wiki/Zero-knowledge_proof