# Tag Info

24

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

15

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

12

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

11

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

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

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

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

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

6

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

6

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

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

4

Well, the data structure of a compressed data is whatever the decompression algorithm needs to be able to reconstruct the original data (assuming a lossless compression method; it's an approximation of the original data if we're talking about a lossy compression method). That might not be the answer you're looking for; you might be looking for details on ...

4

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

4

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

4

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

4

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

4

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

4

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

4

Using generic homomorphic encryption the answer for all three is essentially yes. Although 3. in general is probably mainly of theoretical interest as it would be impractically slow. For simply compressed data this is simple since compression should not do anything to hide the data. Just decompress, do the operation and possibly compress the result if ...

3

Read about the CRIME and BREACH attacks. They are the classic example where compression before encryption can leak information about the input. The length of the compressed data leaks information about the contents of the data itself. See also http://security.stackexchange.com/q/19911/971 and http://security.stackexchange.com/q/20406/971 and http://...

3

The answer depends on how you would layer the encryption on top of the existing protocol. If you implemented your own Skype client, you could deal with compression issues yourself. That might allow you to use format preserving encryption, perhaps on the compressed data stream and not the audio itself. However, you would need to be careful – speech ...

3

For cryptographic hash functions we usually want to avoid collisions as much as possible (and even more we want to avoid any way to get from the output back to the preimage). So what you want certainly is not a cryptographic hash function, but something else. On the first look, something like a CRC (cyclic redundancy check) could fit your bill. These have ...

3

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

3

When using symmetric encryption is it important to compress the data first? No, not really (unless you're concerned with bandwidth usage). On the other hand, compressing the message can leak data (for example, how compressible the data is). Could it be the case for some ciphers but not for others? No, or at least, not for any cipher that we would ...

3

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

3

It is better to compress before encrypting. Any proven block cipher will reduce the data to a pseudo-random sequence of bytes that will typically yield little to no compression gain at all. Additionally, encrypting compressed data can potentially also carry the added benefit of making statistical analysis harder (though this of course does depend on the ...

3

TL;DR: The zlib output is at least as unique as the SHA-256 output. Compression libraries like zlib have to encode the data in such a way that it is recoverably, which implies that they can not reduce the uncertainity (entropy) of the data. Because of this logic, the entropy of the encoded hash has to be the same as the one of the hash. Now as hashes tend ...

2

You can use Rabin's fingerprints for your case

2

Actually, it appears that we can do a bit better by using an unbalanced RSA key; that is, one composed of two primes of different sizes. For example, suppose we have a 512 bit p and a 1536 bit q; to generate a key, we can select a random 512 bit prime p, and then for q, we search for a prime in the range $(C/p, (C+2^k)/p)$ (where $C$ is our 2048 bit ...

2

If you have known plaintext, namely one input file that is known in its entirety, this is trivial to break. So I'll explore methods that might lead to a break, if you don't know what's in the input file that was compressed. I suggest that you start by analyzing the DEFLATE stream format carefully (see also these handy notes). This will probably help you ...

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