Tag Info

Hot answers tagged compression

69

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

45

According to 7-Zip, Use ZipCrypto, if you want to get archive compatible with most of the ZIP archivers. AES-256 provides stronger encryption, but now AES-256 is supported only by 7-Zip, WinZip and some other ZIP archivers. So really there is some balance to be played with. Do you require better security at the sacrifice of compatibility or more ...

21

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

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

18

There is at least one way in which compression can weaken security; it has to do with the fact that essentially all methods of encrypting arbitrarily long message will inevitably leak information about the length of the input. The only way to avoid this leak is to pad all messages to a constant length before encrypting them — but if the messages are ...

16

Well, your definition of entropy is known as Kolmogorov complexity, and it's not so much that it is incorrect, as it is that it is inapplicable to what gzip does. For example, the value $\pi$ can also be generated by a short program; however, if you attempt to compress a 2.2Mbyte sample of the binary expansion, you'll also find that gzip will also not be ...

16

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

13

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

12

Unlike some crypto tasks like encryption+authentication combining compression+encryption have nothing in common/non synergies, so combining them into one algorithm offers no advantages. In practice this means you first compress your data, and then encrypt it, because encrypted data is uncompressable. That way you cleanly separated the separate concerns, and ...

10

Daniel J. Bernstein mentioned your way of compressing RSA public keys in his paper "A secure public-key signature system with extremely fast verification". The naive way you outline roughly doubles the work for each extra bit. If there were a better method which did not run very slowly then it could be repurposed as a factoring algorithm. So if it were ...

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

Technically, if you use a cryptographically secure encryption algorithm with a fresh random key in a confidentiality mode such as (full block) CFB, you don't have to worry about the redundancy of the plain text, since the cipher + mode combination is supposed to be secure even if significant parts of the plain text are known to the adversary. If the cipher +...

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

8

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

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

Short answer: “No”. The latest research shows that compression actually harms security. "Reducing redundancy" is an outdated concept from the late 20th century. The intuition was that if our ciphers turned out to be weak, we might avoid a practical loss of confidentiality by giving attackers less information to work with. For example, in the following ...

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

Compressing the data increases the security a number of ways. It reduces an attacker's ability to affect the decrypted output by flipping ciphertext bits. It removes regular patterns in plaintext (it might create other regular patterns, but they aren't directly the plaintext). There are a number of attacks on OpenPGP that are thwarted by compression. Most ...

6

Also any twin-encryption algo-s around?: by which I mean, suppose I have 2 data strings (alphanumeric only, say for now) -- Using them both, and an algo, I produce the encrypted output - I take in a pair, and produce a pair. The procedure is algo-based and not key-based. One fundamental fact (or perhaps I should say "assumption") in cryptography is that you ...

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

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

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

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

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

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

Yes, a ciphertext of a bulk encryption algorithm normally should not be compressible to less than the plaintext size¹ (at least, if the compression function does not know the encryption key), other than in some corner cases which will occur only with negligible probability (like you hitting the one plaintext which will encrypt to the all-zero-string). ¹Of ...

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