Merge pull request #1857 from RaimoNiskanen/raimo/rand-crypto-xoroshiro928

OTP-14461 - New 'rand' algorithm: Xoroshiro928** also for 'crypto'

Implement a new 'rand' algorithm named 'exro928ss' and a new 'crypto' plugin for 'rand' named 'crypto_aes'.

Both are based on Xoroshiro928** which is derived from Xoroshiro1024** modified to use 58-bit words for performance reasons in the Erlang VM.  Xoroshiro1024** has got the Xoroshiro1024 generator and the StarStar scrambler from the 2018 paper "Scrambled Linear Pseudorandom Number Generators" by David Blackman and Sebastiano Vigna.

This generator and scrambler combination shows no systematic weaknesses in standard statistical tests as TestU01(BigCrush) and PractRand, unlike the previously used * and + scramblers in the 'rand' module that exhibit statistical weaknesses for the lowest bits.

The 'crypto' plugin uses AES-256 as scrambler and the Xoroshiro928 as generator, which gives the same very long period and jump functions as for Xoroshiro928**, but a cryptographically secure scrambler gives absolutely no detectable statistical weaknesses regardless of how the generated numbers are used.

The speed of 'exro928ss' is only about 30-50% slower than the default fast 'rand' algorithm, but the state is roughly the double and it produces about 8 times the garbage per iteration.

The speed of 'crypto_aes' is about half (amortized) that of the default fast 'rand' algorithm which is fast and thanks to doing encryption in batches caching the result.  Hence the state is much larger.

2 files changed, 258 insertions, 37 deletions

diff --git a/lib/crypto/doc/src/crypto.xml b/lib/crypto/doc/src/crypto.xml
index 8c4dc1729a..e9ccd89911 100644
--- a/lib/crypto/doc/src/crypto.xml
+++ b/lib/crypto/doc/src/crypto.xml
@@ -1,4 +1,3 @@
-<?xml version="1.0" encoding="utf-8" ?>
 <!DOCTYPE erlref SYSTEM "erlref.dtd">
 
 <erlref>
@@ -905,7 +904,8 @@ _FloatValue = rand:uniform().     % [0.0; 1.0[</pre>
 	<p>
           Creates state object for
 	  <seealso marker="stdlib:rand">random number generation</seealso>,
-          in order to generate cryptographically strong random numbers.
+          in order to generate cryptographically strong random numbers,
+          and saves it in the process dictionary before returning it as well.
           See also
 	  <seealso marker="stdlib:rand#seed-1">rand:seed/1</seealso> and
 	  <seealso marker="#rand_seed_alg_s-1">rand_seed_alg_s/1</seealso>.
@@ -916,12 +916,6 @@ _FloatValue = rand:uniform().     % [0.0; 1.0[</pre>
 	  may raise exception <c>error:low_entropy</c> in case the random generator
 	  failed due to lack of secure "randomness".
 	</p>
-	<p>
-	  The cache size can be changed from its default value using the
-	  <seealso marker="crypto_app">
-	    crypto app's
-	  </seealso> configuration parameter <c>rand_cache_size</c>.
-	</p>
         <p><em>Example</em></p>
         <pre>
 _ = crypto:rand_seed_alg(crypto_cache),
@@ -931,6 +925,34 @@ _FloatValue = rand:uniform().     % [0.0; 1.0[</pre>
     </func>
 
     <func>
+      <name>rand_seed_alg(Alg, Seed) -> rand:state()</name>
+      <fsummary>Strong random number generation plugin state</fsummary>
+      <type>
+        <v>Alg = crypto_aes</v>
+      </type>
+      <desc>
+	<marker id="rand_seed_alg-2" />
+	<p>
+          Creates a state object for
+	  <seealso marker="stdlib:rand">random number generation</seealso>,
+          in order to generate cryptographically unpredictable random numbers,
+          and saves it in the process dictionary before returning it as well.
+          See also
+	  <seealso marker="#rand_seed_alg_s-2">rand_seed_alg_s/2</seealso>.
+	</p>
+        <p><em>Example</em></p>
+        <pre>
+_ = crypto:rand_seed_alg(crypto_aes, "my seed"),
+IntegerValue = rand:uniform(42), % [1; 42]
+FloatValue = rand:uniform(),     % [0.0; 1.0[
+_ = crypto:rand_seed_alg(crypto_aes, "my seed"),
+IntegerValue = rand:uniform(42), % Same values
+FloatValue = rand:uniform().     % again
+	</pre>
+      </desc>
+    </func>
+
+    <func>
       <name>rand_seed_alg_s(Alg) -> rand:state()</name>
       <fsummary>Strong random number generation plugin state</fsummary>
       <type>
@@ -967,6 +989,12 @@ _FloatValue = rand:uniform().     % [0.0; 1.0[</pre>
 	    crypto app's
 	  </seealso> configuration parameter <c>rand_cache_size</c>.
 	</p>
+	<p>
+	  When using the state object from this function the
+	  <seealso marker="stdlib:rand">rand</seealso> functions using it
+	  may throw exception <c>low_entropy</c> in case the random generator
+	  failed due to lack of secure "randomness".
+	</p>
 	<note>
 	  <p>
 	    The state returned from this function cannot be used
@@ -989,6 +1017,72 @@ _FloatValue = rand:uniform().     % [0.0; 1.0[</pre>
     </func>
 
     <func>
+      <name>rand_seed_alg_s(Alg, Seed) -> rand:state()</name>
+      <fsummary>Strong random number generation plugin state</fsummary>
+      <type>
+        <v>Alg = crypto_aes</v>
+      </type>
+      <desc>
+	<marker id="rand_seed_alg_s-2" />
+	<p>
+          Creates a state object for
+	  <seealso marker="stdlib:rand">random number generation</seealso>,
+          in order to generate cryptographically unpredictable random numbers.
+          See also
+	  <seealso marker="#rand_seed_alg-1">rand_seed_alg/1</seealso>.
+	</p>
+	<p>
+	  To get a long period the Xoroshiro928 generator from the
+	  <seealso marker="stdlib:rand">rand</seealso>
+	  module is used as a counter (with period 2^928 - 1)
+	  and the generator states are scrambled through AES
+	  to create 58-bit pseudo random values.
+	</p>
+	<p>
+	  The result should be statistically completely unpredictable
+	  random values, since the scrambling is cryptographically strong
+	  and the period is ridiculously long.  But the generated numbers
+	  are not to be regarded as cryptographically strong since
+	  there is no re-keying schedule.
+	</p>
+	<list type="bulleted">
+	  <item>
+	    <p>
+	      If you need cryptographically strong random numbers use
+	      <seealso marker="#rand_seed_alg_s-1">rand_seed_alg_s/1</seealso>
+	      with <c>Alg =:= crypto</c> or <c>Alg =:= crypto_cache</c>.
+	    </p>
+	  </item>
+	  <item>
+	    <p>
+	      If you need to be able to repeat the sequence use this function.
+	    </p>
+	  </item>
+	  <item>
+	    <p>
+	      If you do not need the statistical quality of this function,
+	      there are faster algorithms in the
+	      <seealso marker="stdlib:rand">rand</seealso>
+	      module.
+	    </p>
+	  </item>
+	</list>
+	<p>
+	  Thanks to the used generator the state object supports the
+	  <seealso marker="stdlib:rand#jump-0"><c>rand:jump/0,1</c></seealso>
+	  function with distance 2^512.
+	</p>
+	<p>
+	  Numbers are generated in batches and cached for speed reasons.
+	  The cache size can be changed from its default value using the
+	  <seealso marker="crypto_app">
+	    crypto app's
+	  </seealso> configuration parameter <c>rand_cache_size</c>.
+	</p>
+      </desc>
+    </func>
+
+    <func>
       <name name="stream_init" arity="2"/>
       <fsummary></fsummary>
       <desc>
diff --git a/lib/crypto/src/crypto.erl b/lib/crypto/src/crypto.erl
index 2db73c4af0..68c0bcef5e 100644
--- a/lib/crypto/src/crypto.erl
+++ b/lib/crypto/src/crypto.erl
@@ -31,9 +31,10 @@
 -export([cmac/3, cmac/4]).
 -export([poly1305/2]).
 -export([exor/2, strong_rand_bytes/1, mod_pow/3]).
--export([rand_seed/0, rand_seed_alg/1]).
--export([rand_seed_s/0, rand_seed_alg_s/1]).
+-export([rand_seed/0, rand_seed_alg/1, rand_seed_alg/2]).
+-export([rand_seed_s/0, rand_seed_alg_s/1, rand_seed_alg_s/2]).
 -export([rand_plugin_next/1]).
+-export([rand_plugin_aes_next/1, rand_plugin_aes_jump/1]).
 -export([rand_plugin_uniform/1]).
 -export([rand_plugin_uniform/2]).
 -export([rand_cache_plugin_next/1]).
@@ -92,7 +93,9 @@
              ]).
    
 %% Private. For tests.
--export([packed_openssl_version/4, engine_methods_convert_to_bitmask/2, get_test_engine/0]).
+-export([packed_openssl_version/4, engine_methods_convert_to_bitmask/2,
+	 get_test_engine/0]).
+-export([rand_plugin_aes_jump_2pow20/1]).
 
 -deprecated({rand_uniform, 2, next_major_release}).
 
@@ -674,34 +677,73 @@ rand_seed_s() ->
 rand_seed_alg(Alg) ->
     rand:seed(rand_seed_alg_s(Alg)).
 
+-spec rand_seed_alg(Alg :: atom(), Seed :: term()) ->
+                           {rand:alg_handler(),
+                            atom() | rand_cache_seed()}.
+rand_seed_alg(Alg, Seed) ->
+    rand:seed(rand_seed_alg_s(Alg, Seed)).
+
 -define(CRYPTO_CACHE_BITS, 56).
+-define(CRYPTO_AES_BITS, 58).
+
 -spec rand_seed_alg_s(Alg :: atom()) ->
                              {rand:alg_handler(),
                               atom() | rand_cache_seed()}.
-rand_seed_alg_s(?MODULE) ->
-    {#{ type => ?MODULE,
-        bits => 64,
-        next => fun ?MODULE:rand_plugin_next/1,
-        uniform => fun ?MODULE:rand_plugin_uniform/1,
-        uniform_n => fun ?MODULE:rand_plugin_uniform/2},
-     no_seed};
-rand_seed_alg_s(crypto_cache) ->
+rand_seed_alg_s({AlgHandler, _AlgState} = State) when is_map(AlgHandler) ->
+    State;
+rand_seed_alg_s({Alg, AlgState}) when is_atom(Alg) ->
+    {mk_alg_handler(Alg),AlgState};
+ rand_seed_alg_s(Alg) when is_atom(Alg) ->
+    {mk_alg_handler(Alg),mk_alg_state(Alg)}.
+%%
+-spec rand_seed_alg_s(Alg :: atom(), Seed :: term()) ->
+                             {rand:alg_handler(),
+                              atom() | rand_cache_seed()}.
+rand_seed_alg_s(Alg, Seed) when is_atom(Alg) ->
+    {mk_alg_handler(Alg),mk_alg_state({Alg,Seed})}.
+
+mk_alg_handler(?MODULE = Alg) ->
+    #{ type => Alg,
+       bits => 64,
+       next => fun ?MODULE:rand_plugin_next/1,
+       uniform => fun ?MODULE:rand_plugin_uniform/1,
+       uniform_n => fun ?MODULE:rand_plugin_uniform/2};
+mk_alg_handler(crypto_cache = Alg) ->
+    #{ type => Alg,
+       bits => ?CRYPTO_CACHE_BITS,
+       next => fun ?MODULE:rand_cache_plugin_next/1};
+mk_alg_handler(crypto_aes = Alg) ->
+    #{ type => Alg,
+       bits => ?CRYPTO_AES_BITS,
+       next => fun ?MODULE:rand_plugin_aes_next/1,
+       jump => fun ?MODULE:rand_plugin_aes_jump/1}.
+
+mk_alg_state(?MODULE) ->
+    no_seed;
+mk_alg_state(crypto_cache) ->
     CacheBits = ?CRYPTO_CACHE_BITS,
-    EnvCacheSize =
-        application:get_env(
-          crypto, rand_cache_size, CacheBits * 16), % Cache 16 * 8 words
-    Bytes = (CacheBits + 7) div 8,
+    BytesPerWord = (CacheBits + 7) div 8,
+    GenBytes =
+        ((rand_cache_size() + (2*BytesPerWord - 1)) div BytesPerWord)
+        * BytesPerWord,
+    {CacheBits, GenBytes, <<>>};
+mk_alg_state({crypto_aes,Seed}) ->
+    %% 16 byte words (128 bit crypto blocks)
+    GenWords = (rand_cache_size() + 31) div 16,
+    Key = crypto:hash(sha256, Seed),
+    {F,Count} = longcount_seed(Seed),
+    {Key,GenWords,F,Count}.
+
+rand_cache_size() ->
+    DefaultCacheSize = 1024,
     CacheSize =
-        case ((EnvCacheSize + (Bytes - 1)) div Bytes) * Bytes of
-            Sz when is_integer(Sz), Bytes =< Sz ->
-                Sz;
-            _ ->
-                Bytes
-        end,
-    {#{ type => crypto_cache,
-        bits => CacheBits,
-        next => fun ?MODULE:rand_cache_plugin_next/1},
-     {CacheBits, CacheSize, <<>>}}.
+        application:get_env(crypto, rand_cache_size, DefaultCacheSize),
+    if
+        is_integer(CacheSize), 0 =< CacheSize ->
+            CacheSize;
+        true ->
+            DefaultCacheSize
+    end.
 
 rand_plugin_next(Seed) ->
     {bytes_to_integer(strong_rand_range(1 bsl 64)), Seed}.
@@ -712,12 +754,97 @@ rand_plugin_uniform(State) ->
 rand_plugin_uniform(Max, State) ->
     {bytes_to_integer(strong_rand_range(Max)) + 1, State}.
 
-rand_cache_plugin_next({CacheBits, CacheSize, <<>>}) ->
+
+rand_cache_plugin_next({CacheBits, GenBytes, <<>>}) ->
     rand_cache_plugin_next(
-      {CacheBits, CacheSize, strong_rand_bytes(CacheSize)});
-rand_cache_plugin_next({CacheBits, CacheSize, Cache}) ->
+      {CacheBits, GenBytes, strong_rand_bytes(GenBytes)});
+rand_cache_plugin_next({CacheBits, GenBytes, Cache}) ->
     <<I:CacheBits, NewCache/binary>> = Cache,
-    {I, {CacheBits, CacheSize, NewCache}}.
+    {I, {CacheBits, GenBytes, NewCache}}.
+
+
+%% Encrypt 128 bit counter values and use the 58 lowest
+%% encrypted bits as random numbers.
+%%
+%% The 128 bit counter is handled as 4 32 bit words
+%% to avoid bignums.  Generate a bunch of numbers
+%% at the time and cache them.
+%%
+-dialyzer({no_improper_lists, rand_plugin_aes_next/1}).
+rand_plugin_aes_next([V|Cache]) ->
+    {V,Cache};
+rand_plugin_aes_next({Key,GenWords,F,Count}) ->
+    rand_plugin_aes_next(Key, GenWords, F, Count);
+rand_plugin_aes_next({Key,GenWords,F,_JumpBase,Count}) ->
+    rand_plugin_aes_next(Key, GenWords, F, Count).
+%%
+rand_plugin_aes_next(Key, GenWords, F, Count) ->
+    {Cleartext,NewCount} = aes_cleartext(<<>>, F, Count, GenWords),
+    Encrypted = crypto:block_encrypt(aes_ecb, Key, Cleartext),
+    [V|Cache] = aes_cache(Encrypted, {Key,GenWords,F,Count,NewCount}),
+    {V,Cache}.
+
+%% A jump advances the counter 2^512 steps; the jump function
+%% is applied to the jump base and then the number of used
+%% numbers from the cache has to be wasted for the jump to be correct
+%%
+rand_plugin_aes_jump({#{type := crypto_aes} = Alg, Cache}) ->
+    {Alg,rand_plugin_aes_jump(fun longcount_jump/1, 0, Cache)}.
+%% Count cached words and subtract their number from jump
+-dialyzer({no_improper_lists, rand_plugin_aes_jump/3}).
+rand_plugin_aes_jump(Jump, J, [_|Cache]) ->
+    rand_plugin_aes_jump(Jump, J + 1, Cache);
+rand_plugin_aes_jump(Jump, J, {Key,GenWords,F,JumpBase, _Count}) ->
+    rand_plugin_aes_jump(Jump, GenWords - J, Key, GenWords, F, JumpBase);
+rand_plugin_aes_jump(Jump, 0, {Key,GenWords,F,JumpBase}) ->
+    rand_plugin_aes_jump(Jump, 0, Key, GenWords, F, JumpBase).
+%%
+rand_plugin_aes_jump(Jump, Skip, Key, GenWords, F, JumpBase) ->
+    Count = longcount_next_count(Skip, Jump(JumpBase)),
+    {Key,GenWords,F,Count}.
+
+rand_plugin_aes_jump_2pow20(Cache) ->
+    rand_plugin_aes_jump(fun longcount_jump_2pow20/1, 0, Cache).
+
+
+longcount_seed(Seed) ->
+    <<X:64, _:6, F:12, S2:58, S1:58, S0:58>> =
+        crypto:hash(sha256, [Seed,<<"Xoroshiro928">>]),
+    {F,rand:exro928_seed([S0,S1,S2|rand:seed58(13, X)])}.
+
+longcount_next_count(0, Count) ->
+    Count;
+longcount_next_count(N, Count) ->
+    longcount_next_count(N - 1, rand:exro928_next_state(Count)).
+
+longcount_next(Count) ->
+    rand:exro928_next(Count).
+
+longcount_jump(Count) ->
+    rand:exro928_jump_2pow512(Count).
+
+longcount_jump_2pow20(Count) ->
+    rand:exro928_jump_2pow20(Count).
+
+
+%% Build binary with counter values to cache
+aes_cleartext(Cleartext, _F, Count, 0) ->
+    {Cleartext,Count};
+aes_cleartext(Cleartext, F, Count, GenWords) ->
+    {{S0,S1}, NewCount} = longcount_next(Count),
+    aes_cleartext(
+      <<Cleartext/binary, F:12, S1:58, S0:58>>,
+      F, NewCount, GenWords - 1).
+
+%% Parse and cache encrypted counter values aka random numbers
+-dialyzer({no_improper_lists, aes_cache/2}).
+aes_cache(<<>>, Cache) ->
+    Cache;
+aes_cache(
+  <<_:(128 - ?CRYPTO_AES_BITS), V:?CRYPTO_AES_BITS, Encrypted/binary>>,
+  Cache) ->
+    [V|aes_cache(Encrypted, Cache)].
+
 
 strong_rand_range(Range) when is_integer(Range), Range > 0 ->
     BinRange = int_to_bin(Range),