Tag Info

70

No, there is no way to compress (or hash or encrypt or whatever) a 5 MB file into a 32 byte hash and then reconstruct the original file just from the hash alone. This is simply because there are many more possible 5 MB files than there are 32 byte hashes. This means that, whatever hashing or compression or other algorithm you use, it must map many ...

34

I think you're misinterpreting the source. The source says the TRNGs "rely" on compression (a cryptographic hash would be the compression function, or possibly some simpler function to increase throughput). The random data isn't insecure after compression, it's insecure before compression. Why? When you roll dice there's an equal probability of it ...

23

OK, there seems to be some confusion with regards to terminology, so let's try to clean that up. I'll try and define things myself, but also provide the more formal Wikipedia definitions. Encryption. Encryption usually is the process of concealing information solely based on the secrecy of some smaller value, which is called "a key" most of the time. Modern ...

21

Neither: Encrypting first and then compressing does not work. Compressing first can leak information about plaintext content through the ciphertext length, as poncho mentioned in comments to another answer. Specifically, compression allows an attacker who can control parts of the message that is encrypted to reveal things about the other, secret parts, ...

19

No, it's not possible to retrieve the original input of a hash, because the input of a hash can be of almost any size (less than 2'091'752 terabytes). But the hash value is always a fixed length, i.e. a SHA-256 has always a 256-bit value. That's why there are multiple inputs that have the same hashed value, see Pigeonhole-principle. That's also the reason ...

19

The decompression of compressed-then-encrypted data is not possible without the decryption key, at least for compression and encryption schemes independent of each other. We can make a theoretical argument for that: compression schemes compress only a small portion of possible plaintexts (that happen to be the ones where compression is used in practice), and ...

15

So I'm trying to find a method of encryption that not only obfuscates text, but also compresses the result. For example, if I encrypted ninechars, the ideal result would be less than nine characters. Even without encryption, it's not possible for a reversible data compression scheme to shorten all of its inputs. This can be easily proven using the ...

10

I will start with all relevant references I found, then tentatively answers the question. Feel free to improve this community wiki. It was originally asked the effort to break PKZIP 2 encryption, described in section 6.1 of the .ZIP File Format Specification (with some refinements in the derived Info-ZIP appnote), assuming a high-entropy password (that is, ...

9

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 ...

9

The way this is usually done is to use a separate compression algorithm, then encrypt the compressed (shorter) message. However, compression has some disadvantages and nowadays its use is discouraged. Compression can leak information about the plaintext, like in CRIME and BREACH attacks on TLS. Arguably it is the protocol that combines the compression and ...

9

You say you want to decompress the data coming from A so B can do incremental backups and recovery. Were A's data not encrypted this would make perfect sense. But A's data is encrypted and that changes everything. Let's think this through. Let's say A compresses its data and then encrypts it. And let's say B could somehow decompress the data from A without ...

8

Let $x\in\mathbb Z/p\mathbb Z$ be the point's first coordinate, and define $z := x^3+ax+b$. We know that there exists a square root $y\in\mathbb Z/p\mathbb Z$ of $z$, i.e. $y^2=z$. Let's assume we have already found such an $y$. Since the order of $(\mathbb Z/p\mathbb Z)^\ast$ is $p-1$, Lagrange's theorem implies $y^p=y\text,$ hence \left(z^{(p+1)/4}\right)...

7

The problem is not with compression and encryption, it is with the protocol that is being used, and the type of data being compressed (or not) prior to encryption. The most damning leaks are on protocols that were either designed to be compressed without encryption, or encrypted without compression. The best example I have is VOIP systems that use a ...

7

For each of the "MD" functions (MD4, MD5, SHA-1, SHA-256, SHA-512, and derivatives), one can view the compression function as a "tilted block cipher": the message block is used as key, and the function encrypts the current state. More formally, if you look at MD5, then there is a block cipher $B$ that takes as inputs a 512-bit key and a 128-bit block. The ...

7

Random data can not be compressed. Good pseudo random data can not be compressed(with generic algorithm). As Paul commented if you use an inefficient encoding such as hexadecimal or Decimal ASCII characters you are using a full 8 bit character to represent less information. Hexadecimal is compressible to 50% and decimal to $\log_2(10)/8$ which is approx 41%....

7

I think it is theoretically possible to have semantically secure encryption that supports decompression of encrypted data (both in lossy and lossless compression settings), but that it will be very inefficient in practice. For a generic approach, one could compress the plaintext, encrypt it using a fully homomorphic encryption scheme, and then decompress ...

6

No, in general you cannot. WinRAR uses AES (128 or 256 depending on version) for encryption, which does not allow key recovery even with know plaintext and ciphertext. It also uses key stretching to derive the encryption key from a password. The algorithm used in newer versions is PBKDF2 with a version dependent iteration count. So a key-guessing attack is ...

6

I think that the answer to this question is a bit more involved than it first seems. The reason is that the compression attacks work when different lengths after compression reveal information about the plaintext. This is of course a huge problem. However, you have to ask the question without compression as well: when does the plaintext size leak information....

6

Are there any algorithms or alternatives to create short signatures. The algorithm does not have neccessarily have to rely on public/private key. Both parties are ment to be secure and can use the same key if neccessary. Absolutely; if you want a public key signature (which, when cryptographers use the term 'signature', that's what they mean), then you can ...

6

The other answers are correct, there is no way to recover data from a hash. From your phrasing, I think that this may be an instance of an X-Y problem: you need very aggressive lossless compression, and hashes plus some way to undo them are the closest thing you know of. Accordingly you might look into an abuse of fractal compression: oversample your ...

6

In data lossless compression we want the data recoverable from the compressed form. This is usually helpful if the entropy is low like text files, so-called zipping. In data lossy compression like JPEG, we still want to get the image (data) but we don't care about the full quality of the image. This can be considered as the original data can be recovered ...

5

A one time pad (OTP) should by definition not have any patterns. An entropy source can have patterns, but an OTP by definition should consist of pure random bits. In general you can create something that is close to a true random number generator by applying a cryptographic hash function over the output of an entropy source. According to NIST you should ...

5

You can use multi-signatures. One example is the BN06 scheme described in the paper: Bellare, Neven - Multi-signatures in the plain public-Key model and a general forking lemma

5

Update: a premise in the former answer did not resist the acid test of experiment. This whole answer was thus very wrong. Thanks to daniel's comment for opening my eyes.

5

Simple information theory shows that this is not possible. For any given hash value, there's an infinite number of files that produce that hash (assuming there's no arbitrary limit on the input length). It's possible(*) to produce a file that produces the same hash, but because information has been discarded, there's no way to say whether or not it's the ...

5

No, this does not make a deterministic authenticated cipher, unless you're using a secret CRC as a MAC. How do you break it? First, find a pair of messages $m = m_1 \mathbin\| m_2$ and $m' = m'_1 \mathbin\| m'_2$ so that $m_i \ne m'_i$ and $\operatorname{CRC}(m) = \operatorname{CRC}(m')$. (Finding collisions in CRCs is not hard.) Then: Query the oracle ...

5

No, there is no way (secure or otherwise) to compress a random $192$ byte value into something smaller; it is impossible to encode $2^{8 \times 192}$ bit possible settings in only 32 bytes (or $191$ bytes, for that matter...) Some exceptions: If those 192 bytes were nonrandom, that is, the vast majority of those 192 bit settings were impossible, you may be ...

4

The sponge construction does not have a compression function in the sense of traditional hash constructions like Merkle–Damgård. Instead, it operates using a permutation function $f$ which "mixes" or "absorbs" the input into the state of the algorithm. Strictly speaking, it does take an input larger than the output it produces, but this function is ...

4

Some cryptographers feel that the ultimate goal for an encryption scheme is semantic security or, even better, perfect security. An encryption scheme that supports de-duplication also allows the backup server -- and the attacker, who we assume steals every backup tape that the server sysadmins send to the off-site backup location -- to detect which parts ...

4

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 ...

Only top voted, non community-wiki answers of a minimum length are eligible