### STORMGATE078's blog

By STORMGATE078, history, 4 weeks ago, , After reading this, this and this, I think I understand the advantages and disadvantages of hash-based solutions to problems that involve matching strings or objects. But from what I've seen so far, almost all methods that are presented make use of the fact that the characters from the alphabet are allocated linearly (I.e.: val=ch-'a'+1;, where 'val' is the equivalent of the character in decimal format — used in calculating the hash values — , and ch is the char).

What happens if instead of using this linear method of assigning values I create a function that does that randomly (and that still makes use of a prime number and a base)? This function has to be injective and should assign an integer from the range $[1, base-1]$ (where $base$ is chosen at the beginning of the program) to each character from the given alphabet. For example, if α={'a', 'b', 'c'} and base=7, is the following distribution : f('a')=5, f('b')=1, f('c')=6, harder to hack, assuming that it has been chosen randomly at the beginning and the attacker can't reverse engineer it?

Presuming that the generated numbers are truly random (they make use of the chrono clock, the processor cycles or other external source of enthropy), is this approach actually reliable and harder to hack in general?  Comments (8)
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   No, it won't affect the birthday attack at all other than a marginal slowdown from the time it takes to compute your permutation function. As explained in the article you linked to, the birthday attack simply generates a bunch of random strings and checks if the hashes of any two strings match. If you have $H$ possible hashes, the the average number of strings you need to generate in order to have two strings with the same hash is approximately $1.25\sqrt{H}$ regardless of how you generate the hash. This means that if your hash function isn't randomized and your hash values aren't more than 64 bits, you're for sure vulnerable to the birthday attack.Just randomize your hash function properly and you should be safe.