24 ms·
Hash functions are supposed to be fast, though. (If you need something slow like a keystretching function, you iterate a hash function, and you pick the number
by geofft 11y ago
Hash functions are supposed to be fast, though. (If you need something slow like a keystretching function, you iterate a hash function, and you pick the number of iterations based on wall clock time on a representative machine.) BLAKE2 is competitive with MD5 and way, way more secure, for instance: https://blake2.net/ https://blake2.net/
- masklinn 11y ago> Hash functions are supposed to be fast, though. First, apparently that was unclear and I left it unspecified so note that my mention was intended about general hash functions (as you'd use in a hash table, which could easily bottleneck a benchmark without its developer realising it) not specifically cryptographic ones. Second, so are number generators and more or less everything else (aside from KDFs), the issue is none of these are only supposed to be fast, and while they should be as fast it's usually more important that they're good, yet the incentive for language developer is to ignore good (whatever that is for the domain) and focus solely on fast. That is what my comment was about.
- paulmd 11y agoCheck out Random123, an implementation of counter-based random number generators. It won best-of-conference at the ACM Supercomputing '11 conference. Basically the idea is that you have a seed which is used as an encryption key, and then you encrypt a counter value to produce an output. Using the next counter value represents the second output from the generator, and so forth. Different seeds produce different output sequences. If you accept that the encryption algorithm works properly, then the output is uncorrelated for a given counter sequence or seed sequence (although seed sequences are slightly less random than counter sequences). You don't need to store state, and you can seek to an arbitrary position in the PRNG stream in O(1) time simply by recomputing the output for the desired counter value. For non-cryptographic applications, you can derive the seed value from some unique property of your dataset (eg id number of an item being operated upon) and then you don't even need to explicitly store the key value. On AES-NI compatible hardware the cryptographically strong varients outperform even crushable PRNGs like Mersenne Twister. These are a fantastic choice where you have that acceleration. Your computer is built to do it really fast, and this lets you utilize that. They also offer non-cryptographic but crush-resistant variants that roughly double that performance. These algorithms parallelize really well and those advantages are even more significant on GPUs, where memory is at a premium and cryptographic acceleration is usually not available. http://www.thesalmons.org/john/random123/papers/random123sc11.pdf http://www.thesalmons.org/john/random123/papers/random123sc1... http://www.thesalmons.org/john/random123/releases/1.06/docs/ http://www.thesalmons.org/john/random123/releases/1.06/docs/
- altern 11y agoSomewhat off-topic I guess, but aren't PRNG, hashing and (symmetric) encryption in some sense all the same thing? If you have some magic, keyed mixing function that permutes a block of data without leaking information about the key, it seems like you can implement any of the three operations. In oversimplified pseudo-code: def encrypt(data, key): counter = 0 for block in data: yield block ^ mix(counter, key) counter += 1 def generate(key): counter = 0 while True: yield mix(counter, key) counter += 1 def hash(data, key): state = 0 for block in data: state = block ^ mix(state, key) return state And similarly, if you have any one of those functions you can implement the rest. Xor with an unpredictable stream of numbers is a good encryption method, encrypting a string of zeroes should give you unpredictable random numbers and the hash can be used as the mix function when implementing the others, etc.
- paulmd 11y agoThey're all kind of the same idea. As you note, each has some magic mixing function to get some output that's (hopefully) entirely uncorrelated to your input, but the specifics are a bit different. When you encrypt something, the output is the same size as the input. The key is not mutated. You have to be able to go the other way if you know the key (for symmetric encryption). When you hash something, the input is variable but the output length is fixed. Typically this is one-way - you should not be able to reconstruct the input for a given output. When you have a stateful PRNG you get a fixed-length output but you have some internal state that gets changed with every call. So its inputs are generate(state) and you yield output and newstate. Going the other way is possible in theory but not typical. The state for PRNGs is usually larger than the amount of output yielded, sometimes by quite a lot. E.g. Mersenne Twister has about 2.5 KB of state but yields only 32 bits of output per iteration. You generally want to store newstate every time, because setting them up is often expensive (MT takes a lot of calls before it's fully initialized and providing good randomness) and iterating through N-1 steps every time can take a very long time in a long-running program. Usually you want PRNGs to be fast (but strongly random), but encryption and hashing should sometimes be slow (eg to protect passwords in a DB, or as a proof-of-work as in Bitcoin/Hashcash). It all depends on what role you're using them in. You can sorta compose them into each other - like you can make a stateful PRNG by doing a hash on some internal state and then mixing some of it back into the state (eg like RDRAND). Or by encrypting a counter with a seed to make a PRNG (like Random123). Here be dragons, though - there's nothing guaranteeing your hand-rolled encryption algorithm will actually resist an attack, or whatever. So stay with a known, tested implementation.
- geofft 11y agoAh, that makes more sense, but I'm also used to cryptographically-secure hashes being used as general-purpose hashes. :) https://www.131002.net/siphash/ https://www.131002.net/siphash/