I have a huge list of MD5 hashes, which takes up quite some space. I wonder whether I would achieve (some) compression by encoding the characters (which are A-F 0-9), with Huffman coding. I made a quick script, and seem to notice that almost every character in the strings (A-F 0-9) has the same frequency in the file of hashes.

So my questions is: will hashes always produce strings with an almost equal letter frequency?

  • $\begingroup$ No, but getting farther away from that requires more output for a given security level. $\hspace{1.41 in}$ $\endgroup$ – user991 May 23 '15 at 10:17
  • 1
    $\begingroup$ If order doesn't matter, you can sort them and then compress the first few bytes, which rarely change between hashes. $\endgroup$ – CodesInChaos May 23 '15 at 11:46
  • $\begingroup$ "by encoding the characters (which are A-F 0-9)", why hexadecimal notation instead of byte-for-byte binary? $\endgroup$ – DannyNiu Sep 26 at 5:48

A cryptographic hash function will produce an output with pseudorandom properties, therefore when expressed in hexadecimal, a list of hash values will have an almost equal number of each character. Pseudorandom data will not compress, as compression looks for patterns. If you had duplicates, compression could reduce the data size.

If you want to compress the list, take your hexadecimal string of 32 characters, and convert it back to ASCII character values, taking up 16 characters. If you need it to be text readable, that can be encoded using Base64 or a variant, which will take 22 to 24 characters.

  • 1
    $\begingroup$ They can be encoded with just 20 characters. $\;$ $\endgroup$ – user991 May 23 '15 at 10:19
  • $\begingroup$ @RickyDemer I have a Base128 encoder I wrote years ago that can get it down to 19! $\endgroup$ – Richie Frame May 23 '15 at 10:22
  • 2
    $\begingroup$ How about a base-256 encoding? $\:$ (aka, not encoded at all) $\;\;\;\;$ $\endgroup$ – user991 May 23 '15 at 10:24
  • $\begingroup$ Actually, any decent compression algorithm will compress hexadecimal MD5s perfectly. By perfectly I mean to ~the theoretical entropy of the file. You'll get a 50% reduction due to byte occupancy. So you don't really need to do anything manually as per your last para., other than gzip it. $\endgroup$ – Paul Uszak Sep 25 at 12:01

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.