4
$\begingroup$

According to wikipedia, a hash maps digital data of arbitrary size to digital data of fixed size.

For all practical measures, a hash is a unique signature of a big chunk of data. But there is such a thing as a collision free hash, I "heard".

Other than being able to decompress back, arguably the main difference between compressing and hashing is precisely that collision factor - but what if the hash has no collisions?

Why exactly can't we "just" get that "perfect" hash and use it as a compressing method instead? Wouldn't it be able to generate way smaller files?

I see how I must be just missing something, so it's just my way of trying to understand what's the underlying difference between hashing and compressing! :)

$\endgroup$
  • $\begingroup$ hashing = irreversible, compression = reversible. Also note: If you could "decompress" a hash you'd have severly broken modern crypto and may be able to do really bad things with that knowledge. Collision free hashing is only possible as long as you hash shorter or equally long string as your "compressed" string. Otherwise the pigeonhole principle would apply. $\endgroup$ – SEJPM Sep 18 '15 at 19:10
  • 2
    $\begingroup$ While a perfect hash has no collisions, it as a fixed set of inputs. Essentially you're creating a lookup table in algorithm form. $\endgroup$ – CodesInChaos Sep 18 '15 at 19:24
  • $\begingroup$ Well, it's clear I couldn't express myself yet again... Yeah, I linked to perfect hash functions, I didn't know they have a limited set of inputs but - even still - it would be nice if it could be reversible. Maybe a better question would then be: What makes a collision free hash irreversible? $\endgroup$ – cregox Sep 18 '15 at 19:27
  • 4
    $\begingroup$ If you believe in fairy tales, there's always Jan Sloot $\endgroup$ – Maarten Bodewes Sep 18 '15 at 20:31
  • $\begingroup$ @MaartenBodewes never heard of it. Amusing! :) $\endgroup$ – cregox Sep 18 '15 at 20:52
6
$\begingroup$

Mathematically speaking, there is no such thing as a collision-free hash. Practically speaking, there is.

Cryptographic hash functions in good standing have no known collisions. That's one of their defining properties. They do have collisions, but there isn't enough computing power on Earth (if not in the whole universe) to find one, given current mathematical knowledge. A SHA-1 value is 160 bits, so we know that there exists a pair of 161-bit strings that have the same hash, but the best-known techniques to find one are out of range of current computing power (not out of range of imaginable computing power, though, which is why we're moving away from SHA-1).

Intuitively speaking, if it's hard to find collisions for a hash, the hash is hard to inverse. If there was a known algorithm to invert a hash, then at some point the algorithm would have to decide which of the possible preimages to go for, and we could run it with both decisions to find a collision.

It is possible to use a hash as a compression function. But since there is no way to calculate the original text from the hash, this compression method can only be used when the original text is available. Sounds useless? Not quite. In fact, that's one the basic reasons to use hashes! Cryptographic hashes are used when there are two storage or communication mechanisms, one that's secure but supports only a small volume of data, another that's insecure but supports a large volume of data. Store the hash on the small, secure storage and the actual data on the large, insecure storage. Then, when you need the file, retrieve the data, retrieve the hash, and check the hash. In this way, the secure storage mechanism uses the hash as a compression function; the decompression function makes use of the insecure storage, but guarantees the security of the outcome. (You'll not that something is lost, however: if the insecure storage is corrupted, this will be detected, but cannot be corrected. The “decompression” mechanism guarantees integrity (if you get the data back, it's the right data) but not availability (you might not be able to get the data back).)

Seen another way, a cryptographic hash can be used as a compression mechanism, but this requires that each time a new file is stored, the decompression function is somehow modified to remember the original file content. This is clearly impractical, but it is of theoretical interest — this basically describes a random oracle, which is a sort of idealized version of a cryptographic hash.

A perfect hash is a different kind of beast: it is mathematically collision-free, but it achieves that by restricting the possible inputs to a finite (usually small) subset of all possible inputs. The decompression function for a perfect hash is usually stored as a table from hash values to the corresponding original data (for example using an array if the hash values are small integers).

$\endgroup$
  • $\begingroup$ This is by far the most complete answer and you got it I was not asking about perfect hashes... But, if anyone is wondering the exact same thing I was when I asked this question, you may have better luck following through the comments and the chat I had with Alan Wolfe there on the first answer since that's where he helped me solving my original intent. :) $\endgroup$ – cregox Sep 21 '15 at 12:10
  • 1
    $\begingroup$ @Cawas If you think that chat has the best answer, please write it up as a self-contained answer here (or edit Alan Wolfe's answer if it's almost what you wanted). Inactive chatrooms are eventually deleted. $\endgroup$ – Gilles Sep 21 '15 at 13:46
  • $\begingroup$ Don't you mean archived? I've seem very old chatrooms with very little activity... But I did plan to write up a self contained answer eventually. Let my head sleep over it for a few nights first! ;P $\endgroup$ – cregox Sep 21 '15 at 14:30
4
$\begingroup$

A perfect hash function computes unique indexes for a predefined finite set of possible inputs. Typically such a function is used to implement a hash table. It is then not necessary to worry about collisions. Normally the set of possible inputs is small and known, such that it is also possible to invert the function (i.e., given the index one can find the input).

Example: If you have the set of strings

("Hello World", "A quick brown fox", "A lazy dog")

then for example the function counting the occurences of character l in a string would be a perfect hash function for those strings, as it would map the strings to indexes as follows:

"Hello World" -> 3
"A quick brown fox" -> 0
"A lazy dog" -> 1

So you can somehow use this function for compression. However there are a number of problems:

1) A first potential problem is that in order to decompress you must know the perfect hash function and the set of possible strings. So if you store '3' in a file you also have to store somewhere the fact that '3' corresponds to "Hello World". This approach can however make sense if you have a fixed set of inputs that you use for many files.

2) You will only have a compression if you have a small set of large inputs. E.g., if the set of possible inputs is {"a","b",...,"z"}, then the resulting indexes (hashes) will be like {1,...,26} an no compression takes place. So this hashing is not suited for general purpose compression.

3) Mapping every input to the same fixed size index may not be the best idea for compression. General purpose compression functions like Huffman coding also consider the probability of occurence of the different strings, and then strings that occur more often are mapped to shorter sequences than very rare strings, which gives a better compression ratio.

PS: Your question is not really a cryptography question, as perfect hash functions for hash tables are not cryptographic hash functions.

$\endgroup$
  • $\begingroup$ Well, at least this example I could really understand. Is this what everyone else were trying to tell me about indexing? I don't see, however, how in this example it would be collision free. "World Hello" is a collision. I'm not really asking about "perfect hashes", I just assumed they would be an example of a hash without collisions, as I hoped was clear by the whole of my question. :( $\endgroup$ – cregox Sep 19 '15 at 11:44
  • $\begingroup$ A hash without collisions is called a perfect hash, and is only possible if you hash fewer items than the size of your hash output. $\endgroup$ – Alan Wolfe Sep 19 '15 at 13:43
  • 1
    $\begingroup$ @Cawas: You can only avoid collisions for a given predefined set of possible inputs. In my example, "World Hello" is not in the set, so you are not supposed to use it as an input. If you do not properly restrict the set of possible inputs, e.g. you allow strings of any size, then you will have collisions. If you have more possible inputs than possible resulting indexes, then obviously some inputs will map to the same index. $\endgroup$ – Chris Sep 19 '15 at 18:34
  • $\begingroup$ This means the so called perfect hashes were a terrible example to use for what I had in mind! I was picturing there could be a at least a theoretical hash with no collision, given it restricts the input file size or something... Didn't think it was something that completely restricted the data input. My bad again! $\endgroup$ – cregox Sep 19 '15 at 18:42
2
$\begingroup$

Using a perfect hash in this case is essentially the same as using an index. For a perfect hash to work, both the compressor and decompressor have to know the $N$ possible things that might be "compressed" in the data.

You are better off giving them each a number in $[0,N)$, and using $log_2N$ bits as your "compressed data".

This is better than a perfect hash because it uses the minimum number of information possible (perhaps not true with a perfect hash), and doesn't give any more information about the contents than a hash does.

The only way a perfect hash would be better would be if you didn't want other people knowing how many possible items there were. The hash comes from a larger number space, so people can't very easily see if there are only 5 items, or 500 million items.

$\endgroup$
  • $\begingroup$ This makes very little sense... I believe compressing isn't about indexing at all, although I can see where you're coming from and I wouldn't know - maybe you're right. Even so, I don't think the only way to make lossless compression is through indexing. And even still if it is the only way possible to compress data, it would still not explain it. No collision means there's nothing else the hash could ever be coming from, so there must be 1 and only 1 link back somehow. $\endgroup$ – cregox Sep 18 '15 at 20:56
  • $\begingroup$ What I'm saying is that a perfect hash is something where when you hash $N$ specific items, you don't get collisions. If you add another item, you may or may not get a collision so you are stuck with those specific $N$ items for the perfect hash you have. If compression is your goal, you'd want to use the smallest representation of the "compressed" data that is possible, so at that point you should use $0..N-1$ to ensure minimal size. BTW a "perfect minimal hash" is equivalent to doing this indexing, but is more difficult to find one versus just a perfect hash. $\endgroup$ – Alan Wolfe Sep 18 '15 at 21:05
  • $\begingroup$ furthermore, the only way for the person on the other end to "decompress" your data would be for them to also know the $N$ items and the hashes for each of those items. $\endgroup$ – Alan Wolfe Sep 18 '15 at 21:05
  • 1
    $\begingroup$ i think you are missing one point, that if you have a hash without collisions, the name of that is "perfect hashing", and the only way to do it requires that you hash fewer items than the number of unique outputs your hash function can give. If you have a hash function that spits out an 8 bit hash (0 to 255), it is possible to have a perfect hash, so long as you hash 256 items or fewer. If you hash 257 items or more, there is no way to have a perfect hash, because you will have collisions. All the unique outputs are used up after 256 items, so 257 has to re-use one. $\endgroup$ – Alan Wolfe Sep 19 '15 at 18:43
  • 1
    $\begingroup$ Sort of. A hash takes an input of any size and makes an output of some fixed size. It also has the property that it's one way (not reversible), that the output is well distributed even if the input isn't, and that small changes in input give large changes in input (avalanche effect aka chaos theory). Compression takes things of arbitrary size and outputs something else of an arbitrary size which is smaller, and the process is reversible. Small changes in input don't necessarily mean large changes in output. $\endgroup$ – Alan Wolfe Sep 19 '15 at 20:02
-1
$\begingroup$

If you have enough computing power to crack a hash, you can send big files over the internet almost instantly, reducing the need for expensive and powerful network infrastructure, you would have to crack it faster than it takes to download the file to be worth it at least time wise, it may be physically, economically and technologically inefficient or even impossible to have a smartphone/computer the same size and price you have but fast enough to be able to crack hashes like a supercomputer can, or even every supercomputer on earth and universe combined can't. If you find a way to crack hashes instantly with a portable quantum computer for example, then it would be a good way to reduce network load and make the internet almost instantaneous or you can find a way in the middle that you would be able to compress files using more than a hash, perhaps a hash and many parameters in a text file, to guide the cracking algorithm the right way, in password cracking for example it takes a very long time to bruteforce a password when you have absolutely no information about the length or character set of the password, but if only you had the length and character set of the password it would significantly reduce the time used to crack the hash.The same thing could be done with larger files/information.Here is a small example :

Hash and parameters : sha1: 19f054f1f448ff152f1d586be39a56f179fe80c9 Lowercase letters only : yes Words in a dictionary : yes Length : 13

Result : stackexchange

$\endgroup$
  • 1
    $\begingroup$ By the pigeon hole principle this obviously does not work. $\endgroup$ – Maeher Jul 29 at 18:41
  • $\begingroup$ @Maeher I had a quick look on this mathematical principle because I am not really familiar with it, and I don't get why it would not work, I assume you are talking about hash collisions, two different inputs generating the same hash, this could still be circumvented. $\endgroup$ – imagnu Jul 29 at 20:21

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.