If cryptographic hashes are completely unique, could they theoretically be used to transfer data? [duplicate]

Question

I know it sounds ridiculous, but hear me out. We know that good hashing algorithms would generate hashes that are pretty much unique. If, in the future, we create a perfect (or just really near perfect) algorithm, could those hashes be used to represent larger chunks of data in a totally unique way? If they truly were unique and determined entirely by the file, could a powerful enough machine work backwards and reconstruct the file?

Now, this is a bit of a stretch from what we currently know, but I'd think it might be possible. Quantum computers can perform many different tasks at once, and we know that they pose a significant threat to modern forms of encryption because of this ability. While that isn't exactly the same thing as guessing every possible file that could've produced a particular hash, but I'd imagine there might be a way to make the process more efficient.

Maybe you get a hash that's a couple kilobytes long, allowing for billions of different input types. Combine that with a computer capable of generating and testing every possible input simultaneously and you'd be able to send tons of information in a couple kilobytes of transmission.

I'm not asking if it's possible to do with our current technology, as I'm fairly sure it isn't. I just want to know if the process of hashing a file could (in theory) support it.

Answer 1

No.

They can be used to identify data you've stored elsewhere. For example, you can probably find a preimage under MD5 for 6f5902ac237024bdd0c176cb93063dc4 by searching the web, and it might even be meaningful English text. And you probably won't find more than one preimage.

This is the idea of content-addressed storage, which is widely used, e.g. by Tarsnap—although it would be a mistake to use MD5 or SHA-1 for content-addressed storage, because collisions are readily available to anyone who wants them, which have hilarious effects on systems doing just that.

But even if you had a practical preimage attack on MD5—say, an array of quantum computers large enough to run Grover's algorithm—it would give you a preimage, but not necessarily (and probably not) the preimage I have in mind that you'll find with a web search. Instead, it would probably give you 128 or 192 or so bits of gibberish. And if you ran it for longer it would probably give you many such blocks of gibberish, long before finding anything that resembles English text.

If the messages you want to transmit cover only a small subset of all bit strings, and are structured with a distribution you know something about, you could invent a better compression scheme for it. Maybe if there are few enough messages with convenient enough structure, you could compress them into 128 bits. This depends on specific information about the distribution of messages, and it depends on having no more than $2^{128}$ pigeons to stuff into holes.

But a preimage-resistant cryptographic hash function like MD5 would be about the stupidest compression scheme imaginable, because not only was it designed without knowledge of your distribution of messages, but it goes to great lengths to obscure the original message and to make ‘decompression’ as hard as it can so that the best way is to guess a possible original message and check it.

Answer 2

Taking your interesting suggestion piece wise:-

pretty much unique

Unfortunately that's not quite right. In a hash of width n bits, collisions occur around $2^{n/2}$ attempts. We're starting to see real world examples of these collisions with the SHA1 hash. It started with the SHAttered demonstration and now there are others linked to in Mx. Ossifrage's answer. Think of it as the birthday problem, or when you put too many pigeons into too few holes.

work backwards and reconstruct the file

The raison d'être for a cryptographic hash is that it is very very very hard to determine the input to the hash from it's output. Whilst it is not inconceivable that a sufficiently powerful computer might be able to invert the hash, the collision problem would still cause uncertainty of the input data. And currently there aren't any quantum computers yet that do productive work. So until they are built, we can't say with 100% confidence that they are possible without some fundamental issue surfacing. That quantum mechanics stuff is quite pesky.

a couple kilobytes long, allowing for billions of different input types

A 16384 bit hash is large. Even without exceeding the block width, it's not billions of possible inputs. It's $2^{16384}$. That's $10^{5000}$ give or take a few billion trillions. Which you'd then have to computationally invert to recover the original data. There are some answers around here estimating the effort and resources required to brute force a 128 bit key, and they use units of lakes and universes. Mankind is only performing 8 million terra hashes /s in the Bitcoin network. That's only $10^{18}$.

Unless of course Ivan Verykleverkov develops a simple inversion algorithm for hashes. But then you simply just fall into the pigeon hole problem for data longer than your block width and or the birthday problem for shorter data. There's just a lot of collisioning.

So I don't think that this data storage method is entirely useful, or physically practical. Or sensible.

Answer 3

Only unique if you do not do it too often

The answer to the question becomes obvious when we give it the complete phrasing.

We know that good hashing algorithms would generate hashes that are pretty much unique, as long as we do not use on too many possible inputs.

You left out the bit that I have highlighted. That last bit is why hashes work and are "pretty much unique", but that is completely negated if you use too many different inputs. Then they are not "pretty much unique" any more but will appear many times. This is known as hash collisions.

So how bad would the collision problem be? Let us make a few assumptions.

1. Assume a clear-text message of 1024 bits. With a 7-bit alphabet, this allows us to send a message slightly longer than the max length of a Twitter message.
2. Assume a 256 bit hash. This corresponds to a compression ratio of 400%.
3. Assume that hashes distribute themselves uniformly, that is to say that every hash has an equal probability to appear as a result.
4. Assume we hash every possible message that can be sent with 1024 bits.

The issue you face here is that once you are done, every hash will appear $2^{1024-256} = 2^{768} \approx 10^{231}$ times.

The number of particles in the known observable universe is less than $ 10^{81}$

So... this is what happens:

1. You receive a hash.
2. You put it into you magical quantum computer.
3. Your computer reverse calculates the possible inputs.
4. As a result, you get more possible clear-text messages than can even fit in the observable universe.

How can you know which one was sent?

In summary: you cannot know which message was actually sent.

"But what if we..."

You object. You say:

"But I am only interested in meaningful messages, not garbage like VGhpcyBpcyBhY3R1YWxseSBhIG1lYW5pbmdmdWwgdHdlZXQ= !".

Well in that case, if you are happy with for instance limiting yourself to written English, then the number of possible messages drop significantly. According to xkcd: what if, number 34, there are about $2^{154}$ possible meaningful Twitter messages in English₍₁₎. Now the chance of collision is very small, so if you are happy with a fixed compression ratio of 400%, then things are all peachy.

But why would you settle for 400% when you can get up to 900% using plain old compression algorithms, without the need for a magical quantum computer?

"Fine!", you say! "I will decrease the side of my hash!".

So you decrease the size of the hash to 128 bits. Now you have a compression ratio of 800%. However...

$2^{154-128} = 2^{26} \approx 10^{7.8}$

...which is to say that every hash has more than 10 million possible clear-text messages... 10 million possibilities that all make some kind of sense.

And to rub salt in the wound: you are still coming up short on the data rate savings compared to plain old compression.

So in conclusion: yes, you could — hypothetically — use hashes to compress messages. But the compression rate would not be better than when using existing compression algorithms. And you would need a magical quantum computer to be able to use this method.

_{(1) ...precluding using words that do not appear in any dictionary, like curiously spelled names}

Answer 4

Yes, but only in one very specific way - as zero-knowledge identifiers.

First, Paul has already pretty much demolished your idea of using SHA as a replacement for ZIP, so to speak. The simple version is that not being able to reverse the one-way hash is exactly why it's called a one-way hash.

However, there is one way in which they can be used to transfer information. If you have a low-bandwith channel with a large repository of knowledge on both sides, no common indexing mechanism, but need to identify bits.

For example, imagine we settle some other star systems, and each of them gets a full copy of our knowledge. Unfortunately, mission command forgot to give this database of knowledge an index. You can use one-way hashes to (pretty much) uniquely identify a specific piece of data that the other side also has. For example, you could send an information that says "the scientific study identified by the hash XXX has been (dis)proven". Usually, we have better ways to identify data, but if you don't, and you know the receiver has an identical (bit-by-bit identical) copy, a hash is a shorter way to (pretty much) uniquely identify a larger piece of information. Of course, now the other side needs to search all its knowledge for a document that matches this hash, in the process it will generate hashes for (statistically half) the documents, and those hashes now became an index.

So that's a pretty theoretical way. :-)

Answer 5

Imagine a hash algorithm with a length of 1 bit. No matter how clever your (un)hashing algorithm is, it can only ever produce two different files. You need a hash long enough to represent all files you'll want to compress. For all possible files that requires an infinitely long hash.

You're probably implicitly assuming that the unhashing algorithm could find the "most likely" file for each hash. However, in this scenario crypto hash algorithm makes it a Rube-Goldberg machine. Crypto hashes are designed to be completely unbiased and unreversible, so everything they do makes picking "most likely" file harder.

If you take a regular compression algorithm, like Huffman coding, and truncate it to a fixed length, it will be equivalent of a (non-crypto) hash. But it will be much better than unbiased crypto hash: it will be biased towards most likely messages, and it will be trivial to reverse for all possible hashes.

Answer 6

The answer is YES with a big IF.

If the hashing is done with Quantum Hashing, then there is a chance that this can be done.

The explanation of Quantum Hashing is beyond the scope of this question because it is a very experimental subject. I suggest anyone interested on the subject to read an article you will find in Nature.com 's scientific papers.

Yang, Y.-G. et al. Quantum Hash function and its application to privacy amplification in quantum key distribution, pseudo-random number generation and image encryption. Sci. Rep. 6, 19788; doi: 10.1038/srep19788 (2016)

Answer 7

Your question headline asks

If cryptographic hashes are completely unique, could they theoretically be used to transfer data?

And the answer to that question is yes.

But unfortunately, cryptographic hashes are not and cannot be completely unique, so the question is pointless. A cryptographic hash has the property that given one text with hash X, it is for practical purposes impossible to find a second text that also has hash X. But that doesn't mean that there are no other texts with hash X; there are in fact an infinite number of them.

Answer 8

Sadly a hash is a predetermined length, so there are a finite number of unique hashes. But the input string can be infinitely long, so unfortunately that means a single unique hash could be created by an infinite number of different strings.

Even if you could create an algorithm that was able to vet out the nonsense data, for example by looking for a predetermined string in the result, it would require an extremely large amount of processing power to crunch the hashes, or an unrealistically sized rainbow table.

---

HOWEVER! Instead of sending a hash, which is the final result of the string, you can send a seed, which can be used to recreate the string pseudorandomly.

This concept is already utilised in games with randomly generated worlds, such as minecraft. Rather than sending every single block in the world, it sends the original seed (a couple of bytes) it used to generate it in the first place, followed by the changes players have made to it (if any).

For further brain food on this idea, check out the library of babel. Every single possible sentence (or combination of letters) ever, can be found at a certain position in it.

EDIT: However, unfortunately the pointer to that string is as long as or longer than the data itself.