Hacker News Reader

Comment by DanBlake | Hacker News Reader

Feel free to upload a 5MB file under your narrow restrictions and I will see if I can reduce it with one of the 20 different compression systems available to me.

View on HN

Here you go: https://mikeash.com/tmp/randomfile.bin

If you manage to get that under 5MB by applying any tool which allows recovering the original data, I will be most interested to know how you did it.

Success: compress.sh: #!/bin/bash echo "#!/bin/bash" echo curl $1

./compress.sh https://mikeash.com/tmp/randomfile.bin > randomfile.compressedzomg

/me hides

You're lucky I'm too lazy to edit a byte on the server and then ask you if it still matches.

It would. You would need to change the location of the file

Fine, fine, you're^Wthey're lucky I'm too lazy to make it return new random data each time.

\o/ :D

The larger the random file the _less_ likely you are the successfully compress it.

Everyone here is telling you that you are wrong, and have even clearly demonstrated this through both mathematical reasoning and empirical tests. Quit digging :-)

Quit digging :-)

On that note, sometimes we all get too attached to our own hard-won mistakes. We all need to remember that sometimes we should set aside pride and just say, "Whoops, my reasoning was unclear or I was misinformed, thanks for correcting my misstatent or misunderstanding."

Ooh, the encryption comment I just made reminded me of an example of compression potentially working on encrypted content.

AES-ECB mode will actually compress fairly well for some inputs (the canonical example being a bitmap image). The reason the compression can work? Because the crypto is broken. In the image case you can actually just visually (no maths or anything) see a large amount of the details of the source image.

Yep. Wikipedia uses this example image:

https://upload.wikimedia.org/wikipedia/commons/f/f0/Tux_ecb....

If there is structure in an encrypted file then the encryption is broken. It is mathematically indistinguishable from true random data. No compression algorithm can compress it.

An additional point you need to consider: You can select different models and compression programs (and some programs do do this), but you have to record which one you use in your output. This again increases the size of the output - this means that even a no-op compression algorithm (say cat or cp :D ) results in output that is bigger (you need a initial byte to say you haven't tried to compress).

I think the better approach to what you're claiming is for you to provide an example that is compressed. Just provide the input, the key, the encryption algorithm (AES-GCM for preference, but seriously AES-CBC would work to), and the compression algorithm.

I don't have a handy place to stash 5MB of data publicly, but you can run the following in SBCL (or the equivalent in whatever language you prefer):

    (in-package :cl-user)
    (use-package :ironclad)
    (let ((data (make-array (* 5 1024 1024)
                            :element-type '(unsigned-byte 8)
                            :initial-element (char-code #\X))))
      (encrypt-in-place
       (make-cipher
        :aes
        :key (sb-ext:string-to-octets "YELLOW SUBMARINE")
        :mode :ctr
        :initialization-vector (make-array 16 :element-type '(unsigned-byte 8)))
       data)
      (with-open-file (tmp "/tmp/data" :direction :output
                           :element-type '(unsigned-byte 8))
        (write-sequence data tmp)))

That's a file of 5,242,880 'X' characters, encrypted with the key 'YELLOW SUBMARINE' and an all-zero initialization vector. You will not be able to compress it.

Reply on news.ycombinator.com