2
$\begingroup$

I'm a computer engineer and I've met hash functions theoretically speaking in "algorithms and data structure" and then in several applications (like databases, operating systems, computer architecture etc).

But I was wondering if there's some general theory about these functions and, specifically, if there's a general way to build such functions.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ There is a cryptographic theory, but it has no relevance to practice. In practice people just come up with functions and claim that they are OK. Functions which need to be cryptographically secure also have to withstand attack attempts by the community; but there is no theoretical guarantee that they are secure. There is just hope. $\endgroup$ – Yuval Filmus Oct 23 '15 at 12:21
  • $\begingroup$ Perhaps you'd be interested in properties which we would like these hash functions to have, for example $k$-wise independence and cryptographic notions of security. But these only make sense for keyed hash, whereas many applications of hash functions use a fixed key. $\endgroup$ – Yuval Filmus Oct 23 '15 at 12:22
  • $\begingroup$ The only theory i know is related to this "methods" that the people claims "to be ok", i know about the properties of the cryptographic hash too (one-way property is one of them). In general i was wondering if there's some kind of "theory for the design", just to make an example let's say you want to design an heuristic algorithm, combinatorical algorithm theory in general tells you about what you need to consider, as example in simulated annealing you need to define the "neighbour" of a given point in order to transition between a state or another. Is there something to keep for hash too? $\endgroup$ – user8469759 Oct 23 '15 at 12:34
  • 1
    $\begingroup$ Or should i probably post a specific problem? $\endgroup$ – user8469759 Oct 23 '15 at 12:34
  • 1
    $\begingroup$ Practically speaking, people design hash functions and other attempt to attack them and usually fail. If you want to use a hash function I strongly suggest that you use one "off-the-shelf". Don't try to design one on your own. $\endgroup$ – Yuval Filmus Oct 23 '15 at 12:40
3
$\begingroup$

There is a general cryptographic theory of provably secure hash functions. There are several inequivalent notions of security. Hash functions are a cryptographic primitive, and the goal of cryptography is to explore relations between different primitives – can one primitive be constructed using the other.

All of this, however, has no relevance on hash functions practically used, for various reasons. Practically, hash functions come in two flavors: cryptographically secure and not cryptographically secure. There isn't really any theory regarding the construction of both types. Cryptographically secure hash functions are constructed according to various and changing heuristic principles, but their strength lies in the community trying to break them and failing. Non-secure hash functions have other properties, and successful one have emerged from practice.

Don't construct your own hash function. If you attempt to construct a cryptographically secure hash function, you will probably fail unless you're an expert. Constructing a non-secure hash function is less harmful, but still, existing ones are probably better than one you would come up with.

If you want a hash function with a particular integer range $[a,b]$ (as indicated in the comments), there are two basic options:

  1. If your function doesn't need to be cryptographically secure, you can use the formula $h \pmod{b-a+1} + a$, where $h$ is a general-purpose hash function. The range of $h$ should be large compared to $b-a+1$, unless $b-a+1$ happens to divide the range of $h$.

  2. If your function does need to be cryptographically secure, you have to be more careful. In that case I suggest you ask a question on the dedicated crypto stackexchange site.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

A hash function is any function that can be used to map data of arbitrary size to data of fixed size.

So basically a hash function is just like a mathematical function that transforms one set of values to another.

The most useful set of Hash functions are the Cryptographic Hash Functions

They are widely used in Password Salting, Data Integrity a a LOT of another applications etc.

The reason they are used in many many many applications are because they are essentially One-Way. Once they are made, it is difficult to reverse them.

Avalanche Effect

On theoretical foundation, which is the foundation of such One Way Hash Functions (And probably what you're looking for) is the Avalanche Effect.

The effect ensures that, H(x) is very very different than H(x+1)

Eg:

Avalanche Effect

The more this effect, the harder it is is reverse a hash.

YOu might also be interested in this

|cite|improve this answer
$\endgroup$
  • $\begingroup$ An affine hash function $h(x) = ax+b$ also satisfies your property but isn't hard to invert. $\endgroup$ – Yuval Filmus Oct 24 '15 at 8:26
1
$\begingroup$

For searching, you want a hash function that distributes the input data for a particular case with no (or little) collisions. If you know the data beforehand, you can construct a perfect hash function for that data. Useful if you are searching for a fixed set of keys, mostly.

If you don't know the data beforehand, you are restricted to work on some distribution of the input data and try to find a hash function that flattens that distribution to something uniform (since frequent hash values will tend to give collisions). Fun really starts the moment your potential input data is a very large set has a complex distribution (think English words as used in everyday text as a sample of the set of all possible strings), of which you select a small sample for each particular run (say the words used in this question and its answers, which has a particular extra twist as the word usage here isn't exactly everyday). Plus you want a simple function, that is fast to compute on the available hardware (a slow function negates the advantages of hashing).

Add the problem of algorithmic attacks, i.e., an attacker who knows the hash function shouldn't be able to feed it a large number of keys that collide, thus fouling up the hash search.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

Since practical applications must be empirically driven, this paper uses Genetic Programming to ensure a more uniform distribution of hash vales: Repairing and Optimizing Hadoop

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.