5 ms·

The many flavors of hashing

rurban 4y ago
Thanks for the nice words!
Sniffnoy 4y ago
Since the OP is the author, I have to point out the following mistake: > Related to the "looks random enough" aspect, because the input size is almost always larger than the output (which is fixed size), there are usually an infinite number of inputs for which the output is the same, thus these functions are not surjective. The word you are looking for here is "injective", not "surjective". Edit: As long as I'm pointing out wrong-word errors like this, I should probably also point out that the phrase is "bear with me", not "bare with me".
- jjitz 4y ago
  well, they might also not be surjective :) but I guess we'll probably never know
  - naniwaduni 4y ago
    Homework for Dantzig: show that [cryptographic hash] is surjective?
- ciprian_craciun 4y ago
  Thanks for both corrections, indeed you are right on both accounts.
- jwilk 4y ago
  I hate the terms "injective" and "surjective". It's impossible for me to remember which is which.
  - samatman 4y ago
    The way I remember it is that all three names are based on the image and codomain since the arguments/domain are total. Sur- means 'upon' (sorta) as in sur-la-table, so we know the surjective is upon the entire codomain, hence surjective is the 'at least once' class, leaving injective as the 'at most once' class. Bijective is the invertible one but I've never had problems remembering that and I note that you don't mention it either.
tptacek 4y ago
This article dances around the problem of encrypting small values a bunch. Here's a Rogaway paper on how to do it: https://www.cs.ucdavis.edu/~rogaway/papers/thorp.pdf https://www.cs.ucdavis.edu/~rogaway/papers/thorp.pdf (You do not need to limit yourself to inputs that are multiples of the AES block size). There's another one like this, I forget the name. SHA-2 is just fine, and is usually a saner choice than SHA-3 (if you want to be a crypto-hipster, use Blake2, not SHA-3; it's usually an easier dep to pull in, and more things use it).
zeroimpl 4y ago
The section about signature hashes could use some improvement. Cryptographic hashes have multiple use cases. The main one that comes to mind is basically just secure checksum/integrity hashes where you want to guarantee nobody could force a collision. For this case, all the scary warnings about "don't use these algorithms directly" makes no sense.
- ciprian_craciun 4y ago
  The section on "signature hashes" was kept short on purpose because anything that relates to real cryptography or security use-cases should require at least using a high-quality (as in audited) high-level library (like `libsodium`), and / or doing your real in-depth research, not reading a few paragraphs on a random person's blog. :) For example even in the case you've described "where you want to guarantee nobody could force a collision" my suggestion is to use a keyed algorithm (like Blake3) or a HMAC and choose a different key (if not for each "instance" algorithmically tied to it, at least for each "deployment"). It doesn't solve the brute force, but it might save you from other mistakes related to how you use those hashes (like for example when the attacker might swap or replace two payloads with their hashes).
xzghfat 4y ago
i like it
a_e_k 4y ago
I once had a need for permutation hashing as part of a 2D sampling algorithm. My approach was to compose the hash using only reversible steps (to ensure that it's a permutation), and then use cycle walking to reduce the domain size from a power-of-two down to an arbitrary non-power-of-two size if needed. I published my implementation in the Pseudorandom Permutations section of my "Correlated Multi-Jittered Sampling" tech report: https://graphics.pixar.com/library/MultiJitteredSampling/paper.pdf https://graphics.pixar.com/library/MultiJitteredSampling/pap...
- Piezoid 4y ago
  Other works on reversible / permutation based / mixing hash functions : https://papa.bretmulvey.com/post/124027987928/hash-functions https://papa.bretmulvey.com/post/124027987928/hash-functions https://nullprogram.com/blog/2018/07/31/ https://nullprogram.com/blog/2018/07/31/ https://gist.github.com/lh3/59882d6b96166dfc3d8d https://gist.github.com/lh3/59882d6b96166dfc3d8d

Thanks for the nice words!

Since the OP is the author, I have to point out the following mistake: > Related to the "looks random enough" aspect, because the input size is almost always larger than the output (which is fixed size), there are usually an infinite number of inputs for which the output is the same, thus these functions are not surjective. The word you are looking for here is "injective", not "surjective". Edit: As long as I'm pointing out wrong-word errors like this, I should probably also point out that the phrase is "bear with me", not "bare with me".

jjitz 4y ago
well, they might also not be surjective :) but I guess we'll probably never know
- naniwaduni 4y ago
  Homework for Dantzig: show that [cryptographic hash] is surjective?
ciprian_craciun 4y ago
Thanks for both corrections, indeed you are right on both accounts.
jwilk 4y ago
I hate the terms "injective" and "surjective". It's impossible for me to remember which is which.
- samatman 4y ago
  The way I remember it is that all three names are based on the image and codomain since the arguments/domain are total. Sur- means 'upon' (sorta) as in sur-la-table, so we know the surjective is upon the entire codomain, hence surjective is the 'at least once' class, leaving injective as the 'at most once' class. Bijective is the invertible one but I've never had problems remembering that and I note that you don't mention it either.

tptacek 4y ago

This article dances around the problem of encrypting small values a bunch. Here's a Rogaway paper on how to do it: https://www.cs.ucdavis.edu/~rogaway/papers/thorp.pdf https://www.cs.ucdavis.edu/~rogaway/papers/thorp.pdf (You do not need to limit yourself to inputs that are multiples of the AES block size). There's another one like this, I forget the name. SHA-2 is just fine, and is usually a saner choice than SHA-3 (if you want to be a crypto-hipster, use Blake2, not SHA-3; it's usually an easier dep to pull in, and more things use it).

zeroimpl 4y ago

The section about signature hashes could use some improvement. Cryptographic hashes have multiple use cases. The main one that comes to mind is basically just secure checksum/integrity hashes where you want to guarantee nobody could force a collision. For this case, all the scary warnings about "don't use these algorithms directly" makes no sense.

ciprian_craciun 4y ago
The section on "signature hashes" was kept short on purpose because anything that relates to real cryptography or security use-cases should require at least using a high-quality (as in audited) high-level library (like `libsodium`), and / or doing your real in-depth research, not reading a few paragraphs on a random person's blog. :) For example even in the case you've described "where you want to guarantee nobody could force a collision" my suggestion is to use a keyed algorithm (like Blake3) or a HMAC and choose a different key (if not for each "instance" algorithmically tied to it, at least for each "deployment"). It doesn't solve the brute force, but it might save you from other mistakes related to how you use those hashes (like for example when the attacker might swap or replace two payloads with their hashes).

xzghfat 4y ago

i like it

a_e_k 4y ago

I once had a need for permutation hashing as part of a 2D sampling algorithm. My approach was to compose the hash using only reversible steps (to ensure that it's a permutation), and then use cycle walking to reduce the domain size from a power-of-two down to an arbitrary non-power-of-two size if needed. I published my implementation in the Pseudorandom Permutations section of my "Correlated Multi-Jittered Sampling" tech report: https://graphics.pixar.com/library/MultiJitteredSampling/paper.pdf https://graphics.pixar.com/library/MultiJitteredSampling/pap...

Piezoid 4y ago
Other works on reversible / permutation based / mixing hash functions : https://papa.bretmulvey.com/post/124027987928/hash-functions https://papa.bretmulvey.com/post/124027987928/hash-functions https://nullprogram.com/blog/2018/07/31/ https://nullprogram.com/blog/2018/07/31/ https://gist.github.com/lh3/59882d6b96166dfc3d8d https://gist.github.com/lh3/59882d6b96166dfc3d8d