Use rdrand instruction to reduce the cost of randomness in rlwe about rlwekex HOT 5 CLOSED

RdRand is unsafe and hard to use properly. It's best to just use system randomness sources (/dev/urandom or arc4random() in most cases).

from rlwekex.

The link you provide is about incorrect use of rdrand with bogus __asm() code and second-hand gossip. We could argue endlessly about the entropy in linux when restarting the same vm image over and over. I tried to provide a simple 6 lines of code in a comment about the way to quickly get randomness. The way this RLWE implementation get randomness hides the true speed of RLWE where the sampling stage can be made in less than a few microseconds. Anyway, since more than 90% of the randomness that RLWE sampling does fetch is not used, the exact source of entropy is not the main algorithmic issue,

from rlwekex.

It's funny that you called the asm "bogus", because it's pulled from an Intel programmer's manual.

We don't need to gossip about the proper way to do randomness - using RdRand in userspace (and in crypto code, no less) is just wrong.

Anyway, since more than 90% of the randomness that RLWE sampling does fetch is not used, the exact source of entropy is not the main algorithmic issue

I don't understand what this means or how it's relevant.

from rlwekex.

Maybe it is not worth debating on that aspect "rdrand or not". Maybe the right approach could be to provide a RND_CTX* to the API entry points, with a buffer already filled with the randomness necessary for the algorithm. There are 2 major impacts hidden by the cost of gathering randomness :

-1- RLWE key exchange can be made faster than ECC key exchange. Most is hidden into the randomness gathering overheads.

-2- only 5 kbytes of randomness is needed, the remaining being used in "dead code" which compares 192-bit fixed-precision numbers and hope that the 140 least-significant bits would have an influence along the decisions in the code (maybe once in 1,000,000 key exchanges). There must be an other algorithmic way to build gaussian randomness which does not include that much waste.

from rlwekex.

I've just checked in a patch that adds a RAND_CTX and passes it in to the sample and crossround algorithms. So far I've only rewrapped the existing PRNGs with this new context, I have not added rdrand. This makes a small (~2%) improvement for the AES PRNG.

As for your second point, Boutoukoat, about chopping off the randomness generation after a certain point (like you discuss in issue #7), my coauthors and I are not yet certain if it is okay from a theoretical perspective to chop that off, we are still thinking about it.

from rlwekex.