Prevent hash collisions with HMAC secret as IV

Question

Our organistation would like to hash large file paths to asssign to a specific object. To prevent hash collisions, I thought we can use the same sort of technique as we use to prevent rainbow tables in password hashes. When you hash the value 'sample data' we will first prepend an IV, which will be used as hmac secret to verify the hash.

function makeHash($data,$algo='sha256',$ivKey=null) {
  if(empty($ivKey)) {
	$ivKey = openssl_random_pseudo_bytes(16);
  }

    $result = $ivKey.hash_hmac($algo,$data,$ivKey,true);
	return base64_encode($result);
}

function verifyHash($data,$hash,$algo='sha256') {

  $result = base64_decode($hash);
   $ivKey =  mb_substr($result,0,16,'8bit');
   $dataHash = makeHash($data,$algo,$ivKey);

  return $hash == $dataHash;
}

Usage example:

$hash = makeHash('sample data');
echo $hash;
var_dump(verifyHash('sample data',$hash));
/**
Output:
 I9Kl9Mkq/6ee3xQixrDn3YImRAywz0rhmBBxRjrfRWiGeRuBrIkREirgKBDr8Gzh
 bool(true) 
*/

Would this be a good way to prevent collisions?

Answer 1

Probably not, unless the paths you are trying to protect include a secret large enough to make it impossible to brute force the hash.

The problem is that this will protect against people finding paths by matching against all the possible values. But assuming the paths can be easily guessed, it is probably not enough to prevent brute-forcing a single path at a time. Furthermore, if you have a hierarchic tree and you also hash the roots of a particular branch, then you can first brute force the root, then the first subdirectory ... until you reach the desired end node.

Most of the time people will protect URL's by keeping a map, where a random value of about 64 to 128 bits is mapped to a specific URL (or path). Obviously the map itself must then be kept secure.

You can slightly approve your algorithm by actually using PBKDF2 with a high iteration count. But even with that brute-forcing the path could be doable.

Answer 2

It doesn't sound to me like you're clear on what your security goal is here. Why do you want to "prevent collisions"? What is the risk that you're trying to defend your application from? How do collisions relate to this risk?

When you hash the value 'sample data' we will first prepend an IV, which will be used as hmac secret to verify the hash.

But your code, if I understand it correctly, contradicts your assertion that the IV is "secret"—it's being prepended to the HMAC result, which I presume is being shown to users of the system.

To prevent hash collisions, I thought we can use the same sort of technique as we use to prevent rainbow tables in password hashes.

The technique you describe doesn't make collisions any less likely.

Also the purpose of password salts isn't to prevent collisions, but rather to slow down a password cracker who steals the database. Unique per-entry salts mean that the attacker cannot reuse the work done for attacking one entry to attack any others.

In fact, collisions aren't necessarily a problem! If password entries A and B had different salts and passwords, and we coincidentally had that hash(salt(A), password(A)) = hash(salt(B), password(B)), well, that doesn't imply hash(salt(A), password(A)) = hash(salt(A), password(B)) or any similar "crosstalk" between the entries. So the application would still reject users logging in with the wrong password for their account. And the attacker still has to start the password guesses from different salts.