From 0f79e3f3d95fd8f04e3893e50c9f27b9e04c2c7e Mon Sep 17 00:00:00 2001 From: Raimo Niskanen Date: Thu, 13 Sep 2018 15:26:24 +0200 Subject: Use long period counter for crypto_aes Conflicts: lib/crypto/doc/src/crypto.xml lib/crypto/src/crypto.erl --- lib/crypto/doc/src/crypto.xml | 110 +++++++++++++++++++++++++++--- lib/crypto/src/crypto.erl | 147 +++++++++++++++++++++++++++-------------- lib/stdlib/src/rand.erl | 18 ++++- lib/stdlib/test/rand_SUITE.erl | 43 ++++++++---- 4 files changed, 246 insertions(+), 72 deletions(-) diff --git a/lib/crypto/doc/src/crypto.xml b/lib/crypto/doc/src/crypto.xml index 3fd99be5b6..c21aec50fe 100644 --- a/lib/crypto/doc/src/crypto.xml +++ b/lib/crypto/doc/src/crypto.xml @@ -1,4 +1,3 @@ - @@ -905,7 +904,8 @@ _FloatValue = rand:uniform(). % [0.0; 1.0[

Creates state object for random number generation, - 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 rand:seed/1 and rand_seed_alg_s/1. @@ -916,12 +916,6 @@ _FloatValue = rand:uniform(). % [0.0; 1.0[ may raise exception error:low_entropy in case the random generator failed due to lack of secure "randomness".

-

- The cache size can be changed from its default value using the - - crypto app's - configuration parameter rand_cache_size. -

Example

 _ = crypto:rand_seed_alg(crypto_cache),
@@ -930,6 +924,34 @@ _FloatValue = rand:uniform().     % [0.0; 1.0[
+ + rand_seed_alg(Alg, Seed) -> rand:state() + Strong random number generation plugin state + + Alg = crypto_aes + + + +

+ Creates a state object for + random number generation, + in order to generate cryptographically unpredictable random numbers, + and saves it in the process dictionary before returning it as well. + See also + rand_seed_alg_s/2. +

+

Example

+ 
+_ = 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
+
+ + + rand_seed_alg_s(Alg) -> rand:state() Strong random number generation plugin state @@ -967,6 +989,12 @@ _FloatValue = rand:uniform(). % [0.0; 1.0[ crypto app's configuration parameter rand_cache_size.

+

+ When using the state object from this function the + rand functions using it + may throw exception low_entropy in case the random generator + failed due to lack of secure "randomness". +

The state returned from this function cannot be used @@ -988,6 +1016,72 @@ _FloatValue = rand:uniform(). % [0.0; 1.0[ + + rand_seed_alg_s(Alg, Seed) -> rand:state() + Strong random number generation plugin state + + Alg = crypto_aes + + + +

+ Creates a state object for + random number generation, + in order to generate cryptographically unpredictable random numbers. + See also + rand_seed_alg/1. +

+

+ To get a long period the Xoroshiro928 generator from the + rand + 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. +

+

+ 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. +

+ + +

+ If you need cryptographically strong random numbers use + rand_seed_alg_s/1 + with Alg =:= crypto or Alg =:= crypto_cache. +

+ + +

+ If you need to be able to repeat the sequence use this function. +

+ + +

+ If you do not need the statistical quality of this function, + there are faster algorithms in the + rand + module. +

+ + +

+ Thanks to the used generator the state object supports the + rand:jump/0,1 + function with distance 2^512. +

+

+ Numbers are generated in batches and cached for speed reasons. + The cache size can be changed from its default value using the + + crypto app's + configuration parameter rand_cache_size. +

+ + + diff --git a/lib/crypto/src/crypto.erl b/lib/crypto/src/crypto.erl index bbdc8c6fc6..8fe52a6cd2 100644 --- a/lib/crypto/src/crypto.erl +++ b/lib/crypto/src/crypto.erl @@ -31,8 +31,8 @@ -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]). @@ -93,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}). @@ -672,39 +674,62 @@ 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, BytesPerWord = (CacheBits + 7) div 8, GenBytes = ((rand_cache_size() + (2*BytesPerWord - 1)) div BytesPerWord) * BytesPerWord, - {#{ type => crypto_cache, - bits => CacheBits, - next => fun ?MODULE:rand_cache_plugin_next/1}, - {CacheBits, GenBytes, <<>>}}; -rand_seed_alg_s({crypto_aes,Seed}) -> + {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), - NN = [0,0,0,0], - {#{ type => crypto_aes, - bits => ?CRYPTO_AES_BITS, - next => fun ?MODULE:rand_plugin_aes_next/1, - jump => fun ?MODULE:rand_plugin_aes_jump/1}, - {Key,GenWords,NN}}. + {F,Count} = longcount_seed(Seed), + {Key,GenWords,F,Count}. rand_cache_size() -> DefaultCacheSize = 1024, @@ -745,44 +770,68 @@ rand_cache_plugin_next({CacheBits, GenBytes, Cache}) -> -dialyzer({no_improper_lists, rand_plugin_aes_next/1}). rand_plugin_aes_next([V|Cache]) -> {V,Cache}; -rand_plugin_aes_next({Key,GenWords,NN}) -> - {Cleartext,NewNN} = aes_cleartext(<<>>, NN, GenWords), +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,NewNN}), + [V|Cache] = aes_cache(Encrypted, {Key,GenWords,F,Count,NewCount}), {V,Cache}. -%% A jump advances the counter 2^64 steps; the the number -%% of cached random values has to be subtracted -%% for the jump to be correct. --dialyzer({no_improper_lists, rand_plugin_aes_jump/1}). +%% 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}) -> - rand_plugin_aes_jump(Alg, Cache, 0). + {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(Alg, [_|Cache], J) -> - rand_plugin_aes_jump(Alg, Cache, J + 1); -rand_plugin_aes_jump(Alg, {Key,GenWords,NN}, J) -> - {Alg, {Key,GenWords,long32_add(NN, (1 bsl 64) - J)}}. +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) -> + <> = + 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). -long32_add([], _) -> []; -long32_add([X|N], Cy) -> - Y = X + Cy, - if - Y < 0; 1 bsl 32 =< Y -> - [(Y band ((1 bsl 32) - 1))|long32_add(N, Y bsr 32)]; - true -> - [Y|N] - end. %% Build binary with counter values to cache -aes_cleartext(Cleartext, NN, 0) -> - {Cleartext,NN}; -aes_cleartext(Cleartext, [A,B,C,D] = NN, GenWords) -> +aes_cleartext(Cleartext, _F, Count, 0) -> + {Cleartext,Count}; +aes_cleartext(Cleartext, F, Count, GenWords) -> + {{S0,S1}, NewCount} = longcount_next(Count), aes_cleartext( - <>, - long32_add(NN, 1), - GenWords - 1). + <>, + F, NewCount, GenWords - 1). %% Parse and cache encrypted counter values aka random numbers -dialyzer({no_improper_lists, aes_cache/2}). diff --git a/lib/stdlib/src/rand.erl b/lib/stdlib/src/rand.erl index fdf9709633..9854c778a1 100644 --- a/lib/stdlib/src/rand.erl +++ b/lib/stdlib/src/rand.erl @@ -1,7 +1,7 @@ %% %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2015-2017. All Rights Reserved. +%% Copyright Ericsson AB 2015-2018. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. @@ -37,6 +37,7 @@ %% Test, dev and internal -export([exro928_jump_2pow512/1, exro928_jump_2pow20/1, + exro928_seed/1, exro928_next/1, exro928_next_state/1, format_jumpconst58/1, seed58/2]). %% Debug @@ -948,6 +949,9 @@ exs1024_jump({L, RL}, AS, JL, J, N, TN) -> -opaque exro928_state() :: {list(uint58()), list(uint58())}. +-spec exro928_seed( + list(uint58()) | integer() | {integer(), integer(), integer()}) -> + exro928_state(). exro928_seed(L) when is_list(L) -> {seed58_nz(16, L), []}; exro928_seed(X) when is_integer(X) -> @@ -979,7 +983,15 @@ exro928ss_next({[S15,S0|Ss], Rs}) -> exro928ss_next({[S15], Rs}) -> exro928ss_next({[S15|lists:reverse(Rs)], []}). +-spec exro928_next(exro928_state()) -> {{uint58(),uint58()}, exro928_state()}. +exro928_next({[S15,S0|Ss], Rs}) -> + SR = exro928_next_state(Ss, Rs, S15, S0), + {{S15,S0}, SR}; +exro928_next({[S15], Rs}) -> + exro928_next({[S15|lists:reverse(Rs)], []}). + %% Just update the state +-spec exro928_next_state(exro928_state()) -> exro928_state(). exro928_next_state({[S15,S0|Ss], Rs}) -> exro928_next_state(Ss, Rs, S15, S0); exro928_next_state({[S15], Rs}) -> @@ -1013,6 +1025,7 @@ exro928ss_uniform(Range, {Alg, SR}) -> exro928_jump({Alg, SR}) -> {Alg,exro928_jump_2pow512(SR)}. +-spec exro928_jump_2pow512(exro928_state()) -> exro928_state(). exro928_jump_2pow512(SR) -> polyjump( SR, fun exro928_next_state/1, @@ -1026,6 +1039,7 @@ exro928_jump_2pow512(SR) -> 16#7B7C4CC049C536E, 16#431801F9DB3AF2C, 16#41A1504ACD83F24, 16#6C41DCF2F867D7F]). +-spec exro928_jump_2pow20(exro928_state()) -> exro928_state(). exro928_jump_2pow20(SR) -> polyjump( SR, fun exro928_next_state/1, @@ -1209,6 +1223,7 @@ seed_nz(N, [S|Ss], M, NZ) -> %% Splitmix seeders, lowest bits of SplitMix64, zeros skipped %% ===================================================================== +-spec seed58(non_neg_integer(), uint64()) -> list(uint58()). seed58(0, _X) -> []; seed58(N, X) -> @@ -1224,6 +1239,7 @@ seed58(X_0) -> {Z,X} end. +-spec seed64(non_neg_integer(), uint64()) -> list(uint64()). seed64(0, _X) -> []; seed64(N, X) -> diff --git a/lib/stdlib/test/rand_SUITE.erl b/lib/stdlib/test/rand_SUITE.erl index c46e370dd5..4cb1c0b13d 100644 --- a/lib/stdlib/test/rand_SUITE.erl +++ b/lib/stdlib/test/rand_SUITE.erl @@ -1101,7 +1101,7 @@ measure_1(RangeFun, Fun, Alg, TMark) -> crypto_aes -> {rand, crypto:rand_seed_alg( - {crypto_aes,crypto:strong_rand_bytes(256)})}; + crypto_aes, crypto:strong_rand_bytes(256))}; random -> {random, random:seed(os:timestamp()), get(random_seed)}; _ -> @@ -1250,20 +1250,31 @@ gen_jump_p3(_, _, Acc) -> lists:reverse(Acc). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% short_jump(Config) when is_list(Config) -> - State_0 = {#{bits := Bits},_} = rand:seed(exro928ss, 4711), + Seed = erlang:system_time(), + short_jump( + rand:seed_s(exro928ss, Seed), + fun ({Alg,AlgState}) -> + {Alg,rand:exro928_jump_2pow20(AlgState)} + end), + short_jump( + crypto:rand_seed_alg_s(crypto_aes, integer_to_list(Seed)), + fun ({Alg,AlgState}) -> + {Alg,crypto:rand_plugin_aes_jump_2pow20(AlgState)} + end), + ok. + +short_jump({#{bits := Bits},_} = State_0, Jump2Pow20) -> Range = 1 bsl Bits, + State_1 = repeat(7, Range, State_0), %% - State_1a = repeat(1 bsl 20, Range, State_0), - State_1b = exro928_jump_2pow20(State_0), - check(17, Range, State_1a, State_1b), + State_2a = repeat(1 bsl 20, Range, State_1), + State_2b = Jump2Pow20(State_1), + check(17, Range, State_2a, State_2b), %% - {_,State_2a} = rand:uniform_s(Range, State_1a), - State_3a = exro928_jump_2pow20(State_2a), - State_3b = repeat((1 bsl 20) + 1, Range, State_1b), - check(17, Range, State_3a, State_3b). - -exro928_jump_2pow20({Alg, AlgState}) -> - {Alg,rand:exro928_jump_2pow20(AlgState)}. + {_,State_3a} = rand:uniform_s(Range, State_2a), + State_4a = Jump2Pow20(State_3a), + State_4b = repeat((1 bsl 20) + 1, Range, State_2b), + check(17, Range, State_4a, State_4b). repeat(0, _Range, State) -> State; @@ -1275,8 +1286,12 @@ check(0, _Range, _StateA, _StateB) -> ok; check(N, Range, StateA, StateB) -> {V,NewStateA} = rand:uniform_s(Range, StateA), - {V,NewStateB} = rand:uniform_s(Range, StateB), - check(N - 1, Range, NewStateA, NewStateB). + case rand:uniform_s(Range, StateB) of + {V,NewStateB} -> + check(N - 1, Range, NewStateA, NewStateB); + {Wrong,_} -> + ct:fail({Wrong,neq,V,for,N}) + end. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% Data -- cgit v1.2.3