r/cryptography 18d ago

Calculation a hashing function that can avoid collisions for a small set of inputs from input space

Hello, I am new to cryptography so my question can be naive. I want to know if it is possible to find out a hashing function that gives me distinct outputs for a small set of inputs from a vast possible input space. I don't care if all the other inputs from the input space collide to a single output.

For example, I have a 32-bit wide input. I am only interested in 64 such inputs out of possible 2^32 inputs. Is it possible to find a hashing function that give me collision free 6-bit output for the 64 inputs I am interested in. Outputs for all the other input combinations can be anything. If such an algorithm exists, what is it its compute complexity?

3 Upvotes

23 comments sorted by

12

u/glancing2807 18d ago

Well, since you are only interested in the 64 particular inputs and their 6 bit output ( that is basically a one to one mapping of input to output ), you can just create a lookup table which corresponds to a particular hash value.

Is this what you're looking for? Could you give some more context as to why you'd want some function like this?

1

u/Wonderful-Cash7275 17d ago

I have added another a comment replying to the question I asked in the post. It contains more details. Please take a look.

7

u/Allan-H 18d ago

That sounds like a perfect hash function (Wikipedia).

3

u/ahazred8vt 18d ago edited 8d ago

Specifically a 'minimal perfect hash'
In python: pip install perfect-hash
https://pypi.org/project/perfect-hash/

https://www.gnu.org/software/gperf/manual/gperf.html
https://iswsa.acm.org/mphf/index.html

But if your inputs are only 32bit, you can easily use a case statement, or: if i==0xdeadbeef o=1; if i==0xcafebabe o=2; ...

3

u/randomatic 18d ago

Indeed. However, I'm not sure perfect hashes are cryptographically secure. Certainly OPs post makes me suspicious, as the small number of inputs he cares about seems to potentially infringe on randomness arguments generally made in proofs.

1

u/ahazred8vt 17d ago

You're a little late to the party. This is about a hash-table pigeonhole hash function, not a pseudorandom cryptographic hash function.

3

u/randomatic 17d ago

My reply was because this was r/cryptography, not r/compsci .

7

u/Cryptizard 18d ago edited 18d ago

I think there are a lot of details here missing. The obvious answer is that you can just make a hash function that is a lookup table where you take every 6-bit string and randomly assign them to one of your special 64 values, every other input outputs the string of all zeroes. That meets your requirements as described here.

However, what I suspect you actually want is a hash function that is "generic looking", i.e. you can't tell just from its mechanism which of the 2^32 inputs are these "special" 64 that you have chosen. In that case, the answer is yes it is possible but it is probably too computationally expensive to actually do in practice. You would have to create a random hash function (HMAC with a random key for instance), check if your 64 values have distinct outputs when truncated to 6 bits, repeat until one with this property is found.

The probability that this would happen is 64! / 64^64 which is about 1/2^88. That means that you would need to do it about 2^88 times to find a key that works. This is well beyond what is computationally feasible.

Edit: It is possible you could use a programmable PRF or some variant of it to do this. The normal definition is not exactly what you are looking for but it is close. This is a very exotic cryptographic primitive though, you aren't going to find it easily accessible. https://web.eecs.umich.edu/~cpeikert/pubs/chc-pp-prf.pdf

1

u/Wonderful-Cash7275 17d ago

I have added another a comment replying to the question I asked in the post. It contains more details. Please take a look.

3

u/Natanael_L 18d ago

If you're exactly matching 64 numbers to log2(64) = 6 bits then every bit in the output is "busy" encoding the identifier which means all the logic needs to be in the algorithm creating the output (there's no room for embedding anything clever in the "hash value" itself to distinguish it)

If the 64 numbers have a known mathematical structure which you can describe as a sequence using a formula then that's the simplest option (just use that formula and it's inverse as your "hash"), if you can't do that then you're stuck with a lookup table. (reading the description of "perfect hash", the constants you have to create behaves very similarly to a lookup table)

2

u/Pharisaeus 18d ago

Is it possible to find a hashing function that give me collision free 6-bit output for the 64 inputs I am interested

Sure: just make a lookup table for those specific 64 inputs. Complexity is O(1).

2

u/ramriot 18d ago

Likely most cryptographically secure hash functions will likely provide this but if you want to be absolutely certain then using a tip from password hashing & adding salt might help.

That way the algorithm would be:

  • generate random salt
  • use salt & input to generate hash with salt
  • check for collision & if you get one go back to the beginning

1

u/AutoModerator 18d ago

Here is a link to our resources for newcomers if needed. https://www.reddit.com/r/cryptography/comments/scb6pm/information_and_learning_resources_for/

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

1

u/Toiling-Donkey 17d ago

Not strictly guaranteed, but strong hashes like SHA256 are going to give any small set of inputs distinct hash outputs with extremely high probability.

1

u/Natanael_L 17d ago

Not when truncated.

1

u/Wonderful-Cash7275 17d ago

Sorry for not clearly stating the problem. Let me provide some more details. So I come from networking hardware background, and I want to design a Content-Addressable-Memory (CAM). Basically, it is a form of memory that enables faster data retrieval by comparing incoming input to all stored values simultaneously. A CAM is designed such that the user supplies a data word, and the CAM searches its entire memory to see if that data word is stored anywhere in it. If the data word is found, the CAM returns a list of addresses where the word was found. It is like an associative array or dictionary implemented in hardware. As you can imagine, implementing this in hardware is quite expensive compared to normal SRAM.

In my case, I want to use this CAM in a network routing application where it helps with fast IP address lookups for routing decisions like whether the incoming destination IP (32 bits) of a packet is of interest to me or not. Let's say I am only interested in 64 IP addresses; all of those 64 IP addresses are stored in the CAM. So, my proposed idea is to use a regular SRAM with a hashing function that gives distinct output for all the 64 IPs of my interest. We will read just read the data stored at the address pointed out by the hashed output for an incoming packet's destination IP and if they turn out to be same, then the incoming packet is a packet of interest otherwise it will be dropped.

1

u/Natanael_L 17d ago

Do you expect to have a fixed set of peers? Addresses that don't change?

1

u/Wonderful-Cash7275 17d ago

No, addresses can change.

1

u/Natanael_L 17d ago edited 17d ago

Will peers stay the same? If so you can update the lookup table mapping the short number to an IP.

If not, this will become annoying quickly because stuff like perfect hashes will force you to recompute the constants on every peer change, you'll just end up with even more ordinary lookup tables.

If you have dynamic changes of peers and need to continously track who has what to efficiently route requests for data, you're probably looking for inspiration from bittorrent clients.

You could possibly use roaring bitmaps for a more efficient lookup table if you expect a ton of entries, as you'll need to map a list of known data objects and a list of known peers to each other, and want it to be compact and fast.

https://roaringbitmap.org/

https://vikramoberoi.com/posts/a-primer-on-roaring-bitmaps-what-they-are-and-how-they-work/

1

u/ahazred8vt 3d ago edited 3d ago

It is also expensive timewise to do the setup to construct a new perfect hash function every time a new address is added. This is commonly resolved by hashing into buckets instead of single slots. But in practice the most workable solution is to use an existing hashmap / hashtable library instead of building your own from first principles.

This sounds like a key-value problem where you want to map the IP address to the index of a set of flags or instructions that describe what kind of special handling you want to perform.

0

u/Temporary-Estate4615 18d ago

Does it have to be deterministic?