An simple AES-based random number generator

http://www.caswenson.com/2015_04_26_an_simple_aesbased_random_number_generator

by thursdayb • 11 years ago

13 5 11 years ago

yshalabi• 11 years ago

Why not use SHA-3 for hashing? I thought it can also use AES-NI extensions?

Using the AES-NI instructions seems like it should be more commonly used when you first think of it but the devil is in the details. I tried to use AES-NI for non-crypto hash functions and PRNG a few years ago and ultimately gave up on that approach even though it does work in principle.

The really short version: the AES instructions are too slow for the amount of usable randomness you get out of them. There are simple integer op sequences that exploit fast, multiple ALUs per core to consistently generate more usable randomness per clock cycle. The only "extension" instruction that generates efficient randomness per clock is the CRC instruction, though the output requires some additional processing since it is not intended to appear random.

That said, most popular hash functions can be greatly improved. For my own work I use a family of hash functions I invented a few years ago (really need to put these on github) that are 30-80% faster than Google's equivalent CityHash while having levels of robust randomness that look cryptographic when tested by SMHasher and similar test suites. My first attempts were actually based on AES, which is a cool way to do it and very efficient if you can make it work, but I could not get the required performance.

Though now that I am thinking about it again, I may have an idea on how to maybe fix the performance problem...

unwind• 11 years ago

That's pretty close to doing a Fermat. :) Please post the code, if it's that good there's got to be some interest.

swordswinger12• 11 years ago

Is Go's AES-based hash function supposed to be a cryptographic hash? If so, did they use a standard transform (e.g. Davies-Meyer) for this task or roll their own?

scaramanga• 11 years ago

Turns out that only clmul is needed to produce fast hash functions, even strongly universal ones.

http://arxiv.org/abs/1202.4961

An simple AES-based random number generator

Related Stories