0

I'm building a URL-shortening tool. For an arbitrary link, I need to produce a fixed-length slug which will index the full URL in a database. For prettiness reasons, I'd like to keep the slug reasonably short (8 alphanumerical characters seems reasonable).

It seems obvious to me that using a hash function with output to hex is an easy way of generating such a slug without having to worry about collisions. I am not expecting more than a million links to ever be posted (it's not a public tool), so I don't need anything like the kind of collision resistance a normal hashing algorithm would provide. Unfortunately, the hash values tend to be rather long - even MD5 uses 32 hex characters (I also don't know how to square this with the fact that it produces a 128 bit value and 16^32 is much bigger than that).

Suppose I took some collision-resistant hash function like SHA-512, and I take the 128 character output:

ddaf35a193617abacc417349ae20413112e6fa4e89a97ea20a9eeee64b55d39a2192992a274fc1a836ba3c23a3feebbd454d4423643ce80e2a9ac94fa54ca49f

and truncate it to just eight:

ddaf35a

I have two (probably naive) questions:

  1. Why does the 512 bit digest take 128 hex characters and not log_{16}(512)? Or, the other way round, can I cram 16^8 bits of entropy into eight hex characters (or any short alphanumeric string)?
  2. Assuming 1. is something obvious I don't see, does truncating a 128 character hash to 8 characters behave "like an 8-character hash function"? In other words, other than accounting for the reduced size of the hash space, are collisions more likely than you would expect from a hash function with a digest of that length?
8
  • 3
    "Why does the 512 bit digest take 128 hex characters" - I have the feeling that you don't understand what hex means. 1 hex character represents 4 bit (2^4=16), i.e. 2 hex characters represent 8 bit (a byte) and 128 hex characters represent 128*4 = 512 bit. *"can I cram 16^8 bits of entropy into eight hex characters" - 16^8 is 32 bit. 8 hex characters are 8*4 = 32 bit. So - yes. Commented Apr 14, 2021 at 16:58
  • @SteffenUllrich That's a great way to explain it. I've seen this explained many different ways, but that's probably the most concise and succinct explanation I've ever seen.
    – mti2935
    Commented Apr 14, 2021 at 17:01
  • @SteffenUllrich I now remember there are 2^512 512-bit numbers, not 512 of them. Oops :( Commented Apr 14, 2021 at 17:02
  • 2
    "... does truncating a 128 character hash to 8 characters behave "like an 8-character hash function"?" - Yes. Does this answer your question? How bad is it to truncate a hash?, Secure way to shorten a hash. Commented Apr 14, 2021 at 17:03
  • @SteffenUllrich Yes, it certainly answers the on-topic part of my question. Thank you! My earlier misunderstanding might imply I need to do something different (and it certainly looks like conventional URL shorteners do). Commented Apr 14, 2021 at 17:10

0

Browse other questions tagged .