0

I am taking a SHA256 hash output in hexadecimal (64 hex nibbles), subsequencing it by taking every other character to make it 32 hex nibbles or 128 bits, and formatting it into a UUID string.

This isn't being used for security purposes, mainly as a way to create a deterministic UUID. I've read from a couple sources that truncating SHA256 to 128 bits is still more collision resistant compared to MD5.

My question is, does taking every other hex nibble instead of truncating the first 32 hex nibbles of the SHA256 hash output affect collision probability in any way?

My intuition is that it shouldn't affect collision probability at all, but all sources I've read only discussed the truncation of the first n characters of SHA256 hash, and nothing about subsequencing every other character.

As a note, I also recently learned that UUIDv5 uses SHA1 to create a hash, and then truncates the first 16 bytes to create a reproducible UUID. So I believe the method I am using should produce similar collision safety.

For my purposes, there would be at most 1 billion unique records.

Using the following approximate formula for accidental collision probability:

k^2/2n where:
k is the number of records (1 billion)
n is the number of total possible hashes (2^128).

The probability of collision is: 1.47 x 10^-21. It is low enough that I feel safe that a collision would not occur.

Can anyone confirm or deny this for me?

1

1 Answer 1

0

You can take any 128 bits of the 256 bit output of SHA-256, each bit has 50% chance of being 0 or 1. Just truncating is considered best practice because what you're doing seems "clever" and that is an anti-pattern. See for example the section about truncating the output in the RFC for HMAC.

I am worried that your "unique UUIDs" can be mapped back to their original values because there are just not that many original values. If they're just sequential integers or something, it would be trivial to do. Maybe use HMAC with a secret key instead of straight hash? Or get a review of the entire system design and not this small part?

1
  • Thanks for the response. The "original value" in this case is not a sequential integer, it is a string that is guaranteed to be unique per record. The UUID generated by the the truncated SHA256 is being used as a primary key in a SQL db. The deterministic factor here is required because we need to be able to generate the primary key for a record without hitting the db for some of our use cases. We are not using this for storing passwords, or any sort of sensitive info. Thus, my only concern is for collisions, but it seems that probability is very low. Dec 27, 2022 at 21:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .