In the realm of computer science, it’s hard to go too far without encountering hashing or hash functions. The concept appears throughout security, from encryption to password storage to crypto, and more generally whenever large or complex data must be efficiently mapped to a smaller, fixed-size set. Hashing makes the process of looking for data much faster for a computer than performing a search and can be incredibly powerful when mastered. [Malte] did some investigation into hash functions and seems to have found a method called Fibonacci hashing that not only seems to have been largely forgotten but which speeds up this lookup process even further.
In a typical hashing operation, the data is transformed in some way, with part of this new value used to store it in a specific location. That second step is often done with an integer modulo function. But the problem with any hashing operation is that two different pieces of data end up with the same value after the modulo operation is performed, resulting in these two different pieces of data being placed at the same point. The Fibonacci hash, on the other hand, uses the golden ratio rather than the modulo function to map the final location of the data, resulting in many fewer instances of collisions like these while also being much faster. It also appears to do a better job of using the smaller fixed-size set more evenly as a consequence of being based around Fibonacci numbers, just as long as the input data doesn’t have a large number of Fibonacci numbers themselves.
Going through the math that [Malte] goes over in his paper shows that, at least as far as performing the mapping part of a hash function, the Fibonacci hash performs much better than integer modulo. Some of the comments mention that it’s a specific type of a more general method called multiplicative hashing. For those using hash functions in their code it might be worth taking a look at either way, and [Malte] admits to not knowing everything about this branch of computer science as well but still goes into an incredible amount of depth about this specific method. If you’re more of a newcomer to this topic, take a look at this person who put an enormous bounty on a bitcoin wallet which shows why reverse-hashing is so hard.
“…just as long as the input data doesn’t have a large number of Fibonacci numbers themselves…”
Given that the Fibonacci Sequence–meaning Fibonacci numbers, of course–appears so regularly and is so pervasive in the physical–and mathematical–world, this could prove highly problematic.
Exactly a feature I do NOT want in a (cryptographic) hash function. I want slow and secure. Without a doubt this has still very interesting uses as the author implied. E.g. maybe searching distributed hash tables.
The linked article kinda explains this – this is a good “hash” function for mapping a large set to a small set, but not a cryptographic hash, which is often what we mean. This confusion in terms is probably why it’s been ignored.
No, for a cryptographic hash fonction, you need it to be fast and secure. Not slow. Because hashing is omnipresent in signature and integrity control, if they are slow, they risk to slow your entire system, specially if they are used at low level.
If you need slowness in hashing, e.g. for password hashing, then use deficated algorithms such as Argon2 or even bcrypt.
I don’t think you want a password hash to be slow (at least not algorithmically slow). Fundamentally the entire time you’re computing a hash, it’s a security vulnerability to some degree. If you intentionally slow it down by randomly adding waits to defeat like, glitching/power consumption attacks that’s one thing, but if there are a ton of steps I’m not sure that doesn’t make it less secure fundamentally.
You need a slow hashing function (and seeds) for passwords in order to mitigate against generation of rainbow tables/ brute force matching against a stolen password database.
Most tasks that use hash functions are not cryptography nor do they need a cryptographic hash. As with any algorithm you use one that is appropriate for the task.
As someone for whom this is terra icognita I appreciate the long and detailed by local standards introduction to the topic of hashing. Now I can be slightly more informed when I read my next introduction. :)