2

I wish to hash something that outputs a collision-free hash, and to use that hash as an id in a database. Using conventional cryptographic hashing (fixed-length) means there is a chance of collision, and that the id might not become unique.

Does such a cryptographic hash exist?

I guess I could always use deterministic asymmetric encryption and encrypt something with the public key, throw away the private key, and use the output as a sort of hash, but anyhow -- was wondering if there are other possibilities.

Basically my problem is this -- I want each username to have a record in my database, but if someone gets a hold of my database, I don't want anyone be to able to read the username from a record. No user will ever know the username of someone else, thereby eliminating the possibility of simply hashing and testing if someone exists in the database.

Improve this question
2
  • 1
    concat a precise date or counter to the hash to avoid the possibility of duplicates.
    – dandavis
    May 7, 2018 at 17:48
  • As @forest already said, you can just use a cryptographic hash for the usernames and reject a username registration if it hashes to an existing one. The chance of a collision is virtually zero and even if there's a collision, it's like a regular username collision. To protect against generic rainbow tables, use the same fixed salt to hash all usernames.
    – Arc
    May 7, 2018 at 18:39

1 Answer 1

Reset to default
4

What you are asking for is a random oracle, a hypothetical ideal hash that cannot create collisions unless the input is larger than the output. Such a hash does not exist in reality, and the best you can get is current cryptographic hashes that make intentionally finding collisions harder. The larger the hash's output, the lower the chance of an unintentional collision. A strong hash like SHA-256 is unlikely to ever collide, even if you were intentionally generating billions of IDs a second.

The chance of a collision is 1 - e-b(b - 1) / 2n, where n is the number of distinct IDs in your set and b is the number of bits in the hash digest. This website explains more about hash collision risks.

If all you want to do is generate a unique pseudorandom ID given a fixed-sized input, you could use a block cipher. The input is the input ID, and the output is the unique, pseudorandom ID. This can be described as H = Ek(ID), and is similar to a block cipher in counter mode. As long as the input and output need only be as large as the block size, there will be no collisions. Note that, unlike a hash, this is reversible and knowledge of the key can be used calculate the original ID.

The block size of the cipher is what determines the input and output sizes. For example, a 64-bit block cipher requires a 64-bit ID as an input, and will output a 64-bit value that can be used in place of your hash. Every distinct 64-bit input will map to a distinct and pseudorandom 64-bit output. The input can be smaller than the block size if it is padded with a constant value, but the output must be used as-is. If input or output is truncated, there will be the risk of running into collisions.

Using a block cipher may not be practical if you are converting usernames into IDs, because a 64-bit block size (for example) can accept at maximum an 8 character username, assuming ASCII. If the input needs to be of variable size, I would urge you to use a hash function. The chance of collisions for a strong ≥160-bit hash is vanishingly small. This is what hashes are designed for.

Improve this answer
4
  • Would not asymmetric encryption accomplish this, and hence be called a random oracle?
    – HelloWorld
    May 6, 2018 at 23:21
  • No. Asymmetric encryption is not hashing. It reversibly encrypts a short string. Furthermore, you can in theory have identical outputs when encrypting with different public keys (since two private keys will decrypt the same ciphertext to different plaintexts).
    – forest
    May 6, 2018 at 23:22
  • 1
    Ah, ok. So it's reversible. I guess my question was not correctly asked. I have no requirement that the output is not reversible (and thus not a hash I guess), only that it may be considered cryptographically secure. Are there other schemes that I may consider?
    – HelloWorld
    May 6, 2018 at 23:26
  • 1
    @HelloWorld A lone block cipher (i.e. one block in ECB mode) will not exhibit collisions for any given key. But, because block ciphers are reversible, an attacker who obtains the database and key would be able to read the username from a record simply by decrypting the encrypted names.
    – forest
    Jan 25, 2019 at 9:35

You must log in to answer this question.

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