is it possible to extract a "hint hash" of some kind from another hash?

Question

I'm a web developer starting to dip into cryptography so please bare with me on this...

Let's say I have a collection of hashes that were generated from some common data i.e. changes to multiple records. Is there a way that I could generate a secondary hash from the main hash and compare it to the other hashes based on how the main hash was generated. For example...

plain text             | hash      | hint hash
----------------------------------------------
"USER:123:fName:Alice" | 92eb5ff.. | 3cd24
"USER:123:fName:alice!"| 1c77753.. | 3cd24
"USER:456:fName:Bob"   | fee6ae2.. | 7d28e
"USER:456:fName:bob!"  | 7775315.. | 7d28e
"USER:789:fName:Carl"  | fec3ad7.. | 75315

Notice how all hashes are unique but the hint hashes match up to the record IDs they are hashed from. So if I generated these hashes based on the plain text and some key i.e. genHash(plainText, keyText). If you only had the hashes, you could associate which hashes are related to each other by their hint hashes only. So if I only had the hashes, I could still find their associations with a couple getHintHash(hash) calls...

Table of hashes:

hash      
---------
92eb5ff.. 
1c77753..
fee6ae2..
7775315.. 
fec3ad7..

Table of hashes with hint hashes:

hash      | hint hash
----------------------
92eb5ff.. | 3cd24
1c77753.. | 3cd24
fee6ae2.. | 7d28e
7775315.. | 7d28e
fec3ad7.. | 75315

Now I have the relationships between the unique hashes without exposing the plain text that generated them. Is this possible? Remember, the hashing function got the plaintext and a key that the "hint hash" could be based off of...

genHash("USER:123:fName:Alice", "USER:123") -> 92eb5ff..

Answer 1

You want a scheme where, given only the hash values, you can compute whether two hashes refer to the same user or not. This is a rather complex question, so it has a rather complex answer. First, let's make sure we all agree on terms:

Def'n: Hash:

A hash function is any function that can be used to map data of arbitrary size to data of fixed size. [wikipedia/Hash_Function]

For example, initials are a perfectly valid hash function (John Smith --> JS, Christina Secretmessagewriter --> CS), although it's no good for cryptography because it doesn't do much in the way of hiding.

Def'n Cryptographic Hash:

A cryptographic hash function is a mathematical algorithm that maps data of arbitrary size to a bit string of a fixed size (a hash function) which is designed to also be one-way function, that is, a function which is infeasible to invert. [wikipedia/Cryptographic_Hash_Function]

If you click on "one-way function" and go far enough down the rabbit hole you'll find out that cryptographic hashes have to be indistinguishable from random, meaning that if I gave you two hashes, there is no way to gain any sort of information whatsoever about whether the two inputs are related (another googlable term for this is "avalanche effect").

So, by definition, what you want is at odds with the very idea of a cryptographic hash function - the goal of which is to prevent any information leakage.

---

Depending how much you care about information leakage, the answer can go on.

What you are asking for is to embed the hash hint inside the overall hash in such a way that it can be extracted again. There's no real security here because if you can do it, so can an attacker who knows your system, but let's explore it anyway.

One way to accomplish this would be to hash the USER:123 and fName:Alice parts separately and concatenate them to make your overall hash. Your "hash hint" is then just the first half of your overall hash (or first N chars if you use different size hashes). It meets the requirement that getHintHash(hash) will extract the hash hint from the overall hash, and it allows you to corrolate related record together without actually exposing the plaintext.

You could do something more complex by inventing your own non-cryptographic hash function that spreads the hint out over the massage rather than sticking it on the front (maybe through some clever math or using a trick from the stenography bag of tricks), but it's not clear what that gains you.

At the end of the day, you might gain some security-through-obscurity and you might be able to compress your hash a little smaller, but it's really equivalent to concatenating two hashes.

Answer 2

I am not clear from your post if GetHintHash is a data retrieval operation or a pure computation function.

If you are asking, "Can I design a data storage system which includes hint hashes that can be retrieved from storage via a function named GetHintHash(hash) which will allow me to retrieve records that are related?" then yes, obviously, you have just described such a system.

If you are asking, "Can I write a function that will tell me if two hashes were derived from similar cleartext, given no other data other than the two hashes?" The answer is NO, unless your hash function sucks. You are asking for the converse of the bolded bullet below:

The ideal cryptographic hash function has four main properties:

• it is quick to compute the hash value for any given message

• it is infeasible to generate a message from its hash value except by trying all possible messages

• a small change to a message should change the hash value so extensively that the new hash value appears uncorrelated with the old hash value

• it is infeasible to find two different messages with the same hash value

(source: Wikipedia)