CryptoRand
Fast and efficient cryptographically strong versions of several Enum functions that rely on :rand uniform functions for randomness.
By default, the :rand functions operate in pseudo-random number generator (PRNG) mode, and hence are not cryptographically secure. To achieve cryptographically strong pseudo-random number generation (CSPRNG) versions, :crypto.rand_seed can be used to force :rand functions into a CSPRNG mode; however, the performance of the Enum functions under CSPRNG is approximately 10 times slower than under PRNG. This module provides functions that are faster than corresponding Enum functions when operating in CSPRNG mode.
TOC
Installation
Add crypto_rand to mix.exs dependencies:
def deps, do:
[ {:crypto_rand, "~> 1.0.0"} ]
Efficiency
The source code for the :rand module indicates that at least 55 random bits are required to generate values using :rand functions. So, for example, the call :rand.uniform(2), which returns a value of either 1 or 2, consumes 55 bits of randomness, even though only 1 bit is actually needed to chose between two values.
PRNG methods are sufficiently fast that this inefficient use of randomness is negligible. CSPRNG methods, however, are much slower, and the inefficiency is easily detected. For example, the time (in seconds) required to generate 1 million random integers using :rand.uniform(8) with PRNG vs CSPRNG yields:
PRNG: 0.218
CSPRNG: 2.566
The timing is, of course, system dependent. But it’s the relative timing that is of interest. Running :rand.uniform/1 under CSPRNG is much slower than PRNG.
Consider the inefficient use of randomness in the above example. At least 53.8 MB of randomness was used to generate the one million integers in the range 1..8; yet since each integer in theory only needs 3 bits to be determined, only 2.9 MB of randomness was actually needed. The remaining 50.9 MB were effectively wasted. That’s a usage efficiency ratio of around 5%.
CryptoRand implements a strategy that maximizes the effective use of CSRPNG generated bytes. For example, to generate random integers in the range 1..8, the function CryptoRand.uniform(8) uses 3 bits of randomness per call. The time (in seconds) required to generate 1 million CSPRNG random integers as above is:
CryptoRand: 0.647
Though slower than :rand.uniform/1 under PRNG, CryptoRand.uniform/1 is significantly faster than the equivalent use of :rand.uniform/1 under CSPRNG.
Random Bytes
All CryptoRand functions take a final, rand_bytes argument to specify a function of the form (non_negative_integer) -> binary() that returns an input integer number of bytes as a binary. The optional argument defaults to :cryto.strong_rand_bytes/1 and can omitted. However, any suitable function can be substituted for generating bytes, allowing for deterministic testings as well as substituting any random byte generating function of choice.
Process Dictionary
For efficiency, CryptoRand stores values in the process dictionary. This is consistent with the default behavior of :rand. CryptoRand stores unprocessed bytes generated using rand_bytes under the key :crypto_rand_bytes and parameters needed for generating uniform values in the range 1..max under the key :crypto_rand_max. These entries can be removed using CryptoRand.clear/0.
Tests
The test suite contains deterministic tests of correctness, non-deterministic histogram tests for validating CryptoRand implementation in the face of randomness, and timing tests for rough comparison to existing solutions.
Deterministic
To run the deterministic tests:
> mix test --trace
Non-Deterministic
The non-deterministic tests use CryptoRand functions to create histograms which should exhibit uniform behaviour. The histograms are validated using a simple chi-square test. However, the very nature of chi-square testing means these tests are subject to potential failure even if the underlying implementation is correct. So an occasional failure of a histogram chi-square tests does not mean the implementation is necessarily wrong. For this reason, these tests are put in a separate file that does not automatically get run with the standard mix test command.
To run the histogram tests:
> mix test --trace test/histogram.exs
The histogram tests include module tags for testing particular CryptoRand functions. The tags are random, shuffle, take_random, and uniform. For example, to run the CryptoRand.shuffle/1 histogram tests:
> mix test --trace test/histogram.exs --only shuffle
Timing
The timing tests compare CryptoRand implementation to various existing implementations. These tests are, of course, system dependent; but it is the resulting relative timings that are of interest. Also note these timing tests do not assert expected behavior, and as such don’t either pass or fail. For this reason, these tests are put in a separate file that does not automatically get run with the standard mix test command.
To run the timing tests:
> mix test test/timing.exs
The timing tests include module tags for timing particular CryptoRand functions. The tags are random, shuffle, take_random, uniform and uniform_list. For example, to run the CryptoRand.shuffle/1 timing tests:
> mix test test/timing.exs --only shuffle
The following provides example timings.
Select random element: CryptoRand.random/1 vs :Enum.random/1:
250000 random elements from enumerable 1..12
rand.uniform (PRNG) : 0.111963
rand.uniform (CSPRNG) : 0.735606
CryptoRand : 0.34594
250000 random elements from list len 12
rand.uniform (PRNG) : 0.736724
rand.uniform (CSPRNG) : 7.786567
CryptoRand : 0.297439
Shuffle enumerable: CryptoRand.shuffle/1 vs :Enum.shuffle/1:
250000 shuffles of enumerable 1..12
rand.uniform (PRNG) : 0.827411
rand.uniform (CSPRNG) : 9.516535
CryptoRand : 2.285146
250000 shuffles of list len 12
rand.uniform (PRNG) : 0.796975
rand.uniform (CSPRNG) : 9.318896
CryptoRand : 2.121225
Take random elements: CryptoRand.take_random/2 vs :Enum.take_random/2:
100000 trials of take_random 5 elements from enumerable 1..26
rand.uniform (PRNG) : 0.711783
rand.uniform (CSPRNG) : 7.060916
CryptoRand : 0.680446
100000 trials of take_random 5 elements from list len 26
rand.uniform (PRNG) : 0.734776
rand.uniform (CSPRNG) : 7.020736
CryptoRand : 0.572719
CryptoRand.uniform/1 vs :rand.uniform/1:
1000000 uniform ints in range 1..25
rand.uniform (PRNG) : 0.22094
rand.uniform (CSPRNG) : 2.583177
CryptoRand : 1.056496
Generate uniform int lists: :rand.uniform/1 vs CryptoRand.uniform_list/1:
100000 lists of size 20 with uniform ints from 1..21
rand.uniform (PRNG) : 0.384218
rand.uniform (CSPRNG) : 5.614058
CryptoRand : 1.026913
String Processing
Unlike Enum, CryptoRand isn’t contextually constrained to enumerables. Each of the functions CryptoRand.random/1, CryptoRand.shuffle/1 and CryptoRand.take_random/1 operate on Elixir String.t().
Caveat Emptor
The development of CryptoRand was initially in support of functionality needed for the Puid and RandomPassword libraries. Neither of these libraries required operating on enumerables with a large number of elements. Ensure suitability for your needs before adopting CryptoRand into your projects.