Would a compression algorithm that randomly shifts stuff around every iteration be TLS/crypto-safe?

This randomization would prevent the same byte sequence from appearing twice in a row, thus making it harder to figure out the key and stuff. Altho I don't have any crypto knowledge...

Note that it would only apply to the compression step. The decompression step would always produce the same output when given the same input.

  • $\begingroup$ How would the decompression step reverse the randomness? Do you have to pass the randomness from the compressor to the decompresser in a way that the attacker can see? $\endgroup$ – Mike Ounsworth Mar 11 '16 at 13:47
  • $\begingroup$ I honestly think that designing the compression algorithm so it concentrates only on compressing data will be more beneficial, and if You want crypto-safe just use any already proven PRGs from any known stream cipher and just xor the compressed data with pseudorandom sequence. $\endgroup$ – Filip Franik Mar 11 '16 at 13:51
  • $\begingroup$ @FilipFranik so now the PRNG's seed is a private key, you've just invented a cipher. How do you securely get that private key to the decryptor / decompressor? $\endgroup$ – Mike Ounsworth Mar 11 '16 at 14:08
  • $\begingroup$ @MikeOunsworth the same "unmentioned" way SoniEx2 was planning to deliver it in hes/hers original design. Most probably using human readable password passed through KDF. $\endgroup$ – Filip Franik Mar 11 '16 at 14:14
  • $\begingroup$ What means "crypto-safe" for you? $\endgroup$ – Paŭlo Ebermann Mar 11 '16 at 14:56

... a compression algorithm that randomly shifts stuff around ...

This is a contradiction in terms, surely? The extent to which any block of data can be compressed is directly related to the entropy of this data. The more predictable the data is, the lower its entropy and the more compressible it becomes.

If you apply random transformations to your data, you are increasing its entropy and making it less compressible. This defeats the purpose of your compression algorithm. Ultimately, you will end up with data that is indistinguishable from random noise, making it completely incompressible.


The way I see this, any randomization you do at the compression end. you'll have to undo at the decompression end. This means that no matter how clever you are with the design of the cipher (and let's be clear: you are designing a cipher), you'll need some chunk of data that serves as a private key (ie you can't decrypt / decompress the data without it and the attacker can't learn it). The problem you'll face is how to get both ends to agree on a key in a way that an eavesdropping attacker doesn't learn it. There are ways to do that - for example the Diffie-Hellman Key Agreement Protocol, or using public key encryption to send the key over - but I would not recommend implementing this yourself.

This is starting to sound more and more like you're reinventing SSL / TLS, so why not compress your file and then encrypt / send it using a stock TLS library like openssl?

  • 2
    $\begingroup$ "so why not compress your file and then encrypt / send it using a stock TLS library like openssl" This is not a good idea... SSL/TLS optionally includes compression of the plaintext before encryption. The problem you open yourself to active attacks such as BREACH or C.R.I.M.E which are some of the most efficient attacks on SSL/TLS. $\endgroup$ – Alexandre Yamajako Mar 11 '16 at 15:17
  • $\begingroup$ @AlexandreYamajako The SSL/TLS compression option was in my experience not used much, partly because session-wide selection is imprecise, even before CRIME made it unsafe to use at all. OpenSSL for example can easily be compiled to exclude it. BREACH attacks HTTP compression instead and can be defended by compressing (even precompressing) entities with no possible attacker input, like the megabytes of CSS and script libraries most websites want to shove down my browser nowadays; this also allows skipping entities where recompression would be useless, like jpeg and mp3. $\endgroup$ – dave_thompson_085 Mar 13 '16 at 5:03

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.