1
$\begingroup$

I understand that there are three main security requirements for hash functions, pre-image resistance, second pre-image resistance and collision resistance.

I need to write about a hash function that allows the user to identify if the original hashed items are identical, but I am a little confused to which security feature this falls under. I understand that its best that no hashed items create the same digest, but in this case its a requirement.

Would this fall under pre-image resistance, since often this is when the random salt is added? Or simple collision resistance? As collision resistance stops hashed values from equaling the same value.

I am a little confused since I do not want different inputs equaling the same output, only identical ones.

$\endgroup$
3
$\begingroup$

I do not want different inputs equalling the same output, only identical ones.

That is pretty much the definition of collision resistance:

a hash function H is collision resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b such that H(a) = H(b), and a ≠ b.

Of course, no hash function can guarantee that the same hash values means the same input. Consider the case where you are hashing files up to 2 gb into 256-bit hash strings. So there are $2^{8000000000}$ possible inputs and only $2^{256}$ possible outputs. Many many possible files will map to each hash string.

So you can never guarantee that identical hashes means identical inputs, but you can rest easy that with a good cryptographic hash function, it is computationally infeasible for an attacker to build two inputs with the same hash (collision resistance), or to take a given input and find a second input with the same hash value (second pre-image resistance).

$\endgroup$
1
$\begingroup$

The property you're thinking of is just that of being a mathematical function: if $x = y$ then $f(x) = f(y)$.

Computer folk, who often work with faux "functions" (scare quotes; routine or procedure would be better words) that don't have this property, sometimes refer to true mathematical functions as deterministic functions. With the recent popularity of functional programming, you also see them called pure functions.

You mention salting, which is a mechanism for achieving what's often more technically called randomized or probabilistic hashing. In theoretical treatments randomized hashing is often modeled as picking a deterministic hash function at random from a large family of randomly picked deterministic hash functions. But in practice randomized hashing is generally implemented by feeding diverse random salts into the same deterministic hash function along with the message.

The cryptographic hash functions in most common use like SHA-256, SHA-3 and Blake2 are all deterministic, so they trivially meet your requirement.

$\endgroup$
1
$\begingroup$

Well, lets go over it (formula's taken from here):

1st pre-image resistance: For a given $h$ in the output space of the hash function, it is hard to find any message $x$ with $H(x) = h$.

That's not it, as you will only store hashes created over some specific data, the value $h$ cannot be just any value, it is created over some file data. I presume that an adversary cannot just put any hash value in your database without providing a file.

2nd pre-image resistance: For a given message $x_1$ it is hard to find a second message $x_2 \neq x_1$ with $H(x_1) = H(x_2)$.

Well, that's it really. You have a specific file and you don't want to have another file have the same hash.

You still cannot do this for data using MD5 and SHA-1 unless that data was structured specially for this purpose. If you have a file that was not specifically created or altered then you will not find a collision using the currently known attacks.

Collision resistance: It is hard to find a pair of messages $x_1 \neq x_2$ with $H(x_1) = H(x_2)$.

This comes into the picture if an adversary can inject values in your file database. Say the adversary has a collision then somebody can load a file with the data $x_1$ that created the collision to your file system. You would not notice any change from the hash if it would be replaced by $x_2$.

As there are collisions known for MD5 and SHA-1 they are completely vulnerable to this attack. You can just upload a file containing the data required for the collision.

With MD5 it is even easy to create these collisions, using any kind of data as starting value. For SHA-1 you could use one of the demo PDF's, but creating a collision yourself will require a lot of computing power.


Generally salts are not used when comparing files, so I take that part out of the question if you don't mind.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.