6
$\begingroup$

As we know any text, file, byte...in SHA-256 output will be returned as 64 hex length. Is it possible to create cryptography that can do the same thing as SHA-256 but can be reversed, so if we have the output of 64 length of hex number, we can reverse it and get started input like "i love programming"? This will be soo cool way to compress huge text. Is it possible?

$\endgroup$
9
  • 11
    $\begingroup$ This is information-theoretically impossible! $\endgroup$
    – DannyNiu
    Feb 21 at 3:08
  • 3
    $\begingroup$ This would only work if the input has redundant information that is unnecessary for reconstructing it. That's true for all lossless compression algorithms. Also see Kolmogorov complexity $\endgroup$
    – Navin
    Feb 21 at 3:48
  • 1
    $\begingroup$ If this were possible, someone would have already implemented it, because compressing a 10TB file down to a few hundred bytes would be God Damned Amazing and Incredibly Useful. $\endgroup$
    – RonJohn
    Feb 21 at 5:45
  • 3
    $\begingroup$ "This will be soo cool way to compress huge text" -- perpetual motion machines would also be soo cool. $\endgroup$ Feb 21 at 13:22
  • 2
    $\begingroup$ 'Reversible hash' is a contradiction in terms. $\endgroup$
    – user207421
    Feb 22 at 1:26
20
$\begingroup$

Strictly speaking, all hash functions are compressing since the output can be smaller than the input, but I imagine you're asking about compressing data that can later be losslessly decompressed.

This is impossible due to the pigeonhole principle. The fact that the fixed output space of a hash algorithm is smaller than the input space means that there will always be multiple possible inputs for the same output. Even if you could find a preimage (i.e. "reverse" the hash), you would not know if it is the original preimage or just a preimage. If the input size was sufficiently small (smaller than the hash) then it may be possible since you can discard larger preimages and only keep the very finite number of small ones that make sense (e.g. only valid ASCII strings), but then it's not compression.

As an extreme example, imagine a "hash function" with a trivial preimage attack: a 1-bit CRC with the polynomial x + 1 (i.e. an even parity bit). If I give you the output of this function and the output is 1, you will have absolutely no idea what the input was. You can compute an input, but you can't find the input. For a 1-bit hash, half of all possible inputs in the input space map to that same output!


This impossibility is the basis of the popular joke from Schneier Facts:

For Bruce Schneier, SHA-1 is merely a compression algorithm.

$\endgroup$
4
  • 14
    $\begingroup$ The pigeon-hole principle also immediately proves that it's not possible to write a compression algorithm that can guarantee compression of every input by even one bit. There will always be some inputs that result in same-size-or-larger output. $\endgroup$ Feb 21 at 7:20
  • $\begingroup$ There exist systems that use a perfect hash function. Perfect hash are hashing algorithms that are calculated based on fully known inputs (ie. all data that are not known beforehand are invalid to the system) thereby allowing you to calculate a hash function that never collides (there are even C libraries that can calculate this automatically for you). In a perfect hash the pigeonhole principle does not exist by definition. In such a system you should be able to reverse the hashing by generating all possible hashes and storing them in a table/database $\endgroup$
    – slebetman
    Feb 21 at 23:38
  • 2
    $\begingroup$ @slebetman But then it's not compression anymore. $\endgroup$
    – forest
    Feb 21 at 23:42
  • 7
    $\begingroup$ @slebetman In a finite domain of N known values, you can represent any of them by an integer between 1 and N. The process you described using a perfect hash is really just a very complicated way of representing the numbers from 1-N, in order to do that. $\endgroup$
    – Ben
    Feb 22 at 3:32
10
$\begingroup$
  • If the question was about (current form)

    Reversible cryptographic hash functions

    Then No!

    One-wayness property of the cryptographic secure hash functions will prevent that. Hash functions don't use keys. So if you can reverse, everybody will reverse and there will be no secure hash function at all.

    Besides, mathematically impossible, too; hash functions use arbitrary large inputs to digest a fixed size $\ell$

    $$H:\{0,1\}^* \to \{0,1\}^\ell$$

    Reversibility requires being 1-1 and onto, you cannot reverse a function if it is not 1-1, and clearly, cryptographic hash functions are not 1-1 since the fixed output size. 1-1 is a bad property for cryptographic hash functions and what is described is a permutation.

    This can be seen clearly with Pigeonhole principle; you have a small number of holes for arbitrarily numbered pigeons. Therefore at least one hole will contain more than one pigeon. When you try to map back, which pigeon will you choose? fail!

    Also, the Cryptographic Hash function needs to mangle the inputs to shrink the output and that causes to loss of information by the and operation ($\wedge$) that is not reversible.

    Therefore what you need is just the opposite of what we want from cryptographically secure hash functions. The pre-image will fail!

  • If the question was about (The first revision)

    compressible encryption;

    Then No!

    Encryption schemes unlike hash functions are reversible operations. Therefore the output space must be at least the same as the input space.

    If you want to compress do it before encryption. Then you can decompress after decryption.

    $$c =E_k(compress(m)) \quad \text{ and } m =decompress(D_k(c))$$

    However, note that, the compression before encryption can be problematic as in the CRIME (Compression Ratio Info-leak Made Easy);

    CRIME (Compression Ratio Info-leak Made Easy) is a security exploit against secret web cookies over connections using the HTTPS and SPDY protocols that also use data compression. When used to recover the content of secret authentication cookies, it allows an attacker to perform session hijacking on an authenticated web session, allowing the launching of further attacks. CRIME was assigned CVE-2012-4929.

    The original paper - 2002 - John Kelsey - Compression and Information Leakage of Plaintext

    and the follow-up BREACH

    BREACH (a backronym: Browser Reconnaissance and Exfiltration via Adaptive Compression of Hypertext) is a security exploit against HTTPS when using HTTP compression. BREACH is built based on the CRIME security exploit. BREACH was announced at the August 2013 Black Hat conference by security researchers Angelo Prado, Neal Harris and Yoel Gluck

    Another problem is achieving side-channel free compression as noted by Hola. If there is a side-channel attack possibility one might consider this, too.

    Therefore, if you want to use compression before encryption execute a serious analysis of your decision.

    Ironically, the modern encryption schemes do the reverse (increase the size - a little) due to security. Block/stream ciphers need IV/nonce to achieve Ind-CPA security. The modern mode of encryption methods like AES-GCM and ChaCha20-Poly1305 produces an authentication tag that increases the output size, too.

$\endgroup$
6
  • $\begingroup$ It should be noted that compression before encryption can be problematic, since it generally breaks the security guarantee. $\endgroup$
    – Maeher
    Feb 20 at 18:24
  • $\begingroup$ @Maeher yes, the CRIME attack. Are you also talking about the CPA game where the adversary sends two messages that have the same length, however, the challenger response includes the compression of the randomly selected message? $\endgroup$
    – kelalaka
    Feb 20 at 19:00
  • $\begingroup$ Well written. One associated problem is compression algorithms do not have side channel security. $\endgroup$
    – hola
    Feb 20 at 22:45
  • 1
    $\begingroup$ I don't think this is entirely relevant, since OP is talking about reversing a hash function, not a compressing encryption function. $\endgroup$
    – forest
    Feb 21 at 1:37
  • 1
    $\begingroup$ @forest I've read it like that, you may right. Added that to the top. Thanks for the note. $\endgroup$
    – kelalaka
    Feb 21 at 7:13
-5
$\begingroup$

Yes, it is possible provided you allow for hashes that are not necessarily a fixed length. This is essentially what content based addressing is. The content can be "any text, file, or byte" and it is addressed by a hash of it. For an example of this you can check out IPFS. You can share a short address of a file with someone else and they can decompress that hash back into the original piece of content. This works by maintaining a mapping between these addresses and the content.

While forest says that this is impossible due to the pigeonhole principle when using a fixed size hash output, IPFS gets around this by being able to support an arbitrary number of hash functions which can each have an arbitrary length. By varying the hash function or length you will always be able to find an address that is not currently used.

$\endgroup$
13
  • 3
    $\begingroup$ But that's not compression (think LZSS). That's just encoding. $\endgroup$
    – forest
    Feb 21 at 6:53
  • 4
    $\begingroup$ It isn't clear what you are claiming. The world will probably never need more than 2^252 distinct files, so we can compress any file that we need in the real world to just 256 bits? That is nonsensical, but it sort of seems like that is what you are saying. $\endgroup$ Feb 21 at 13:40
  • 4
    $\begingroup$ @Anonymous If you need to store a copy of the file somewhere else (or any information required for the reconstruction of the file), then it is not compression. Yes, DHT uses hashes. No, DHT is not a form of compression. $\endgroup$
    – forest
    Feb 22 at 3:45
  • 3
    $\begingroup$ @Anonymous Unless that message contains extreme redundancy, you won't be able to store 1 GiB in 64 bytes. And most certainly not recover a 1 GiB preimage given a broken 512-bit (64 byte) hash. $\endgroup$
    – forest
    Feb 22 at 6:50
  • 5
    $\begingroup$ @Anonymous I think you're misunderstanding what compression is. It doesn't matter where the data is stored. The typical definition of compression in this context is use of a reversible algorithm which takes an input and produces an output. If the input is large and redundant, then the output is small and less redundant. It's as simple as that. If you store data in the cloud, that 1 TiB of data hasn't vanished just because you've moved it to another computer. It hasn't been compressed. It just moved. $\endgroup$
    – forest
    Feb 22 at 8:10

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.