2
$\begingroup$

I'm calculating a SHA2 hash of a certain sensitive key value. I need to store files on disk using this hash a directory path prefix. So lets say I hash the key value 150023, I get a 32-byte value which in hex is 64-characters long - quite a long filename.

What's the shortest string I can get of this 32-byte hash, that would have some degree of uniqueness? I could use Base64 but that would be about 40 chars. Should I simply truncate the 32-byte hash value? Would it have frequent collisions if I used similar key values?

Improve this question
$\endgroup$
1
  • $\begingroup$ Why use it as a directory prefix? Directories and files could be renamed by the user. An option might be Alternate Data Streams (if NTFS) so you can store the hash invisible as part of the file itself. However, it will be lost when copied from NTFS to some other file system. $\endgroup$
    – Thomas Weller
    Dec 21, 2013 at 22:33

1 Answer 1

Reset to default
3
$\begingroup$

There are 94 printable ascii characters. Not all of which are valid for file names, however. There should be $64=2^6$ that are valid for file names, so read $6$ bits at a time and map those to one of the $64$ characters that are valid for file names. That would give you $256/6\approx 43$ characters. It will be hard to get much smaller than that.

That process is pretty much base64 anyways, so I'd stick with base64.

Truncation could work depending on your adversary model. What kind of collisions are you worried about? If you are only worried about random collisions, truncation would be fine. If you truncate to $128$ bit outputs, you would expect to see a collision after about $2^{64}$ files. If you are worried about malicious collisions, best to stick with the $\approx 43$ characters of base64.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Beware that standard base64 uses / as part of its character set, which is reserved in most contemporary file systems. Also many file systems (including anything native to Windows) are case insensitive. And the GUI I'm using right now won't allow file tst.txt to be renamed to lpt9 or con. $\endgroup$
    – fgrieu ♦
    Jun 12, 2012 at 5:08
  • 1
    $\begingroup$ @fgrieu: good point. Rather than the original base64, Geotarget probably wants RFC 4648 'base64url' "Base64 with URL and Filename Safe Alphabet". In order to guarantee that a program won't generate a base filename of "con" or some other reserved filename, and to make human-generated filenames such as "readme" usually sort before program-generated filenames, I typically make program-generated filenames start with lowercase 'z'. $\endgroup$
    – David Cary
    Jun 19, 2012 at 13:08
  • $\begingroup$ @mikeazo: (Just adding detail to old but fairly good answer.) $log94(2^{256}) = about 39,1$. Thus it can be estimated that it could be possible to get 40 or less character filenames, if using whole character set (and more complex encoding). 43 is for the most purposes close enough. Also, note that many operating systems allow UTF of latin1 characters in filenames, allowing shorter names. $\endgroup$
    – user4982
    Oct 27, 2013 at 10:31
  • $\begingroup$ For case-insensitive file systems, it's probably best to stick with base 32 or 36, which can be encoded using single-case letters and numbers. In particular, the distinct printable ASCII characters allowed in Windows file names are not quite enough to encode six bits per character: there are 9 reserved characters and 26 equivalent upper/lowercase pairs, leaving only 60 usable characters (including space, which you don't seem to count; also, some file systems may have additional reserved characters). $\endgroup$
    – Ilmari Karonen
    Feb 20, 2014 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.