-
Notifications
You must be signed in to change notification settings - Fork 6
/
Copy pathRNG_engines.txt
1123 lines (1073 loc) · 54 KB
/
RNG_engines.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
*****************************************************************************
0. Contents of this file
*****************************************************************************
0. Contents of this file
1. Quick recommendations for which RNGs to use
2. Quick comparison charts for recommended RNGs
3. Details on the critera used in sections #1 and #2
4. Longer descriptions of recommended RNGs
5. Non-recommended RNGs ("other" RNGs)
6. Naming conventions for RNGs in PractRand
*****************************************************************************
1. Quick recommendations for which RNGs to use
*****************************************************************************
The following RNGs have the broadest appeal among normal users:
hc256
HC-256 is the highest quality recommended RNG and the most
cryptographically secure. Its biggest drawback is slow seeding
time. It's also a little slow and a bit large, but not so much of
either of those as to hinder usability for typical purposes.
sfc64 / sfc32 / sfc16
The sfc* RNGs are the fastest of the recommended RNGs and one of
the smallest. The 32 and 64 bit variants have no known drawbacks,
though the 16 bit variant is considered inadequate for parallel
uses.
chacha
Chacha offers cryptographic security, fast random access, fast
seeding, and easily adjustable security vs speed tradeoffs.
Unfortunately while seeding and random access are fast, generating
random numbers with it at any particular setting ends up being slow
relative to other RNGs of comparable security and quality, at least
with the PractRand implementation (which currently lacks the SIMD
optimizations necesary for high-speed implementations of ChaCha).
efiix64x384 / efiix32x384 / efiix16x384 / efiix8x384
The fastest recommended RNG that qualified for a "future-proof" five
star quality rating. Also the fastest RNG to offer any degree of
cryptographic security. Unfortunately its security rating suffers
from insufficient analysis. Also, it's a bit slow to seed,
particularly on platforms that are not 64 bit.
*****************************************************************************
2. Quick comparison charts for recommended RNGs
*****************************************************************************
This section contains lists of RNG algorithms and variants included in the
PractRand library, rated from 0 to 5 stars on each of several broad criteria.
Each list is restricted to RNGs recommended for a particular purpose; some
RNGs thus appear on multiple lists. You can find descriptions of the
categories that they are rated on in section 3, and descriptions of the
individual RNGs in section 4.
In addition to the things which recommended RNGs are rated on, every
recommended RNG meets a few common requirements:
deterministic
endian-safe (when used correctly)
excellent performance on statistical tests (exception: mt19937)
fast enough for most purposes (exception: sha2_based_pool)
supports serialization
internally uses only integer math (not floating point)
natively operates on 8, 16, 32, or 64 bit integers
natively outputs an integer of the same size it operates on internally
supports seeding from a 64 bit integer
* The following RNGs are recommended for normal use on 64 bit CPUs.
Engine quality speed theory size notes
sfc64 3*** 5***** 1* 32 bytes best speed
jsf64 3*** 5***** 0 32 bytes -
xsm64 4**** 4**** 1* 32 bytes random access
arbee 4**** 4**** 1* 40 bytes entropy pooling
trivium 5***** 1* 2** 48 bytes crypto
efiix64x384 5***** 3*** 1* 3104 bytes crypto
isaac64x256 5***** 2** 2** 4128 bytes crypto
* The following RNGs are recommended for normal use on 32 bit CPUs.
Engine quality speed theory size notes
sfc32 3*** 5***** 0 16 bytes best speed
jsf32 3*** 5***** 0 16 bytes -
xsm32 3*** 4**** 1* 16 bytes random access
chacha(8) 5***** 1* 3*** 124 bytes crypto + random access
efiix32x384 5***** 3*** 0 1552 bytes crypto
isaac32x256 5***** 2** 2** 2064 bytes crypto
mt19937 2** 3*** 4**** 2500 bytes popular
hc256 5***** 2** 3*** 8580 bytes best quality, best crypto
* The following RNGs are recommended for normal use on 16 bit CPUs.
Engine quality speed theory size notes
sfc16 2** 5***** 0 8 bytes fastest RNG & smallest RNG
efiix16x384 5***** 3*** 0 776 bytes -
* The following RNGs are recommended for normal use on 8 bit CPUs.
Engine quality speed theory size notes
efiix8x384 5***** 3*** 0 388 bytes -
(not much variety at 8 bit... if anyone needs more let me know... the 16
bit ones should work acceptably on 8 bit CPUs too though)
Using an RNG of one word size on a CPU of a different word size will incur a
performance penalty, but is otherwise fine.
* Some RNGs allow a user to skip forwards or backwards arbitrarily far in
the output stream efficiently. The following RNGs support that:
Engine quality speed size word other
xsm32 3*** 4**** 16 bytes 32 bit -
xsm64 4**** 4**** 32 bytes 64 bit -
chacha(8) 5***** 1* 124 bytes 32 bit crypto
chacha(12) 5***** 1* 124 bytes 32 bit crypto
chacha(20) 5***** 0 124 bytes 32 bit crypto
salsa(8) 4**** 1* 140 bytes 32 bit crypto
salsa(12) 5***** 0 140 bytes 32 bit crypto
salsa(20) 5***** 0 140 bytes 32 bit crypto
* Some RNGs allow versatile progressive seeding, useful for adapting
information in an irregular or exotic format to serve as a seed or key. The
following RNGs are recommended for that purpose:
Engine quality speed size word other
arbee 4**** 4**** 40 bytes 64 bit* -
sha2_based_pool 5***** 0 302 bytes 8/64* crypto
* Some RNGs are cryptographically secure, making it extraordinarily difficult
for someone to figure out their seed (aka key) or state from examining their
output. The following RNGs are recommended for that purpose:
Engine quality speed size word crypto other
trivium 5***** 1* 48 bytes 64 bit 2** -
chacha(8) 5***** 1* 124 bytes 32 bit 1* random access
chacha(12) 5***** 1* 124 bytes 32 bit 3*** random access
chacha(20) 5***** 0 124 bytes 32 bit 4**** random access
salsa(8) 4**** 1* 140 bytes 32 bit 1* random access
salsa(12) 5***** 0 140 bytes 32 bit 3*** random access
salsa(20) 5***** 0 140 bytes 32 bit 4**** random access
sha2_based_pool 5***** 0 302 bytes 8/64 * 3*** entropy pooling
efiix8x384 5***** 3*** 388 bytes 8 bit 0 -
efiix16x384 5***** 3*** 776 bytes 16 bit 1* -
efiix32x384 5***** 3*** 1552 bytes 32 bit 1* -
efiix64x384 5***** 3*** 3104 bytes 64 bit 1* -
isaac32x256 5***** 2** 2064 bytes 32 bit 2** -
isaac64x256 5***** 2** 4128 bytes 64 bit 2** -
hc256 5***** 2** 8580 bytes 32 bit 5***** -
Non-standard limitations may apply on some low-end, embedded, or exotic hardware
to what sort of RNG algorithms you can use in a cost-effective manner.
1. If multiplication is very costly:
No problem; most of the current recommended RNGs do not use multiplication.
The exceptions are:
xsm32 uses multiplication
xsm64 uses multiplication
mt19937 uses multiplication, but only during seeding
2. If you can not use floating point math:
No problem; none of the current recommended RNGs use floats.
3. If memory is a major constraint:
No problem, just look at the "size" column on the above charts. In
particular sfc, jsf, xsm, arbee, trivium, and chacha are reasonably
small for their quality and feature set.
4. If you can not do integer math except by emulating it on floating point:
That's a problem. All of the PractRand RNGs will tend to be slow on your
hardware.
5. If barrel shifts are not efficient on your hardware:
Not a big problem. Even hardware that lacks native barrel shifts can
generally emulate them at reasonable speeds. If for some reason you want to
avoid all use of barrel shifts anyway, some PractRand recommended RNGs that
avoid barrel shifts include isaac32x256, isaac64x256, mt19937, and Trivium.
6. If integer sizes on your hardware not 8, 16, 32, or 64 bits:
That's a problem. Some of the recommended RNG algorithms could still be
efficient, but they might require a customized implementation to optimize
for your specific architecture.
7. If you need to minimize the number of transistors required to implement the
RNG in hardware:
Trivium, sfc*, and jsf* can all be implemented with very little hardware.
Of those, Trivium offers the highest quality and is the only one of those
to offer any degree of cryptographic security.
Have some other limitation? Let me know about it!
The following RNG algorithms are frozen - they will produce the same results
when used in the same way in all future versions, unless bugs are discovered:
jsf64
jsf32
isaac32x256 (aka "ISAAC")
isaac64x256 (aka "64 bit ISAAC")
mt19937 (aka "The Mersenne Twister")
hc256 (aka "HC-256")
trivium
chacha (aka ChaCha) (for even numbers of rounds only)
salsa (aka Salsa20) (for even numbers of rounds only)
Other recommended RNGs in PractRand may vary from version to version, though
they should stabilize by the time PractRand approaches version 1.0.
*****************************************************************************
3. Details on the critera used in sections #1 and #2
*****************************************************************************
The categories they are rated in on the quick comparison charts include:
quality: (rated from 0 to 5 stars)
Broadly:
1 star - good enough for typical apps & games
2 stars - good enough for almost any* non-parallel purpose today
3 stars - good enough for almost any* purpose today
4 stars - good enough for any* purpose in the next few years
5 stars - good enough for any* purpose
* = excluding cryptographic purposes - that is rated separately
An RNGs quality score is determined as the LOWEST of several subscores.
The subscores are performance on statistical tests, cycle length,
statespace, and how much I trust the algorithm. More specifically...
Empirical Testing:
1 star - must pass 1 GB of PractRand standard
also, must pass TestU01 SmallCrush
2 star - must pass 16 GB of PractRand standard
also, must pass TestU01 SmallCrush
also, must pass gjrand mcp --standard
3 star - must pass 256 GB of PractRand standard
also, must pass TestU01 Crush
also, must pass gjrand mcp --big
4 star - must pass 1 TB of PractRand standard
also, must pass TestU01 Crush & BigCrush
also, must pass gjrand mcp --huge
5 star - must not have any known failures on general-purpose tests
Cycle Length (aka period):
1 star - minimum cycle length of at least 2**40 or
average cycle length of at least 2**45
2 star - minimum cycle length of at least 2**52 or
average cycle length of at least 2**62
3 star - minimum cycle length of at least 2**59 or
average cycle length of at least 2**79
4 star - minimum cycle length of at least 2**64 or
average cycle length of at least 2**104
5 star - minimum cycle length of at least 2**80 or
average cycle length of at least 2**160
Statespace:
1 star - statespace of at least 2**40
2 star - statespace of at least 2**60
3 star - statespace of at least 2**90
4 star - statespace of at least 2**150
5 star - statespace of at least 2**240
Note that this is closely related to cycle length.
Trusted (aka how trustworthy I think they are, aka my analysis):
1 star - not TOO horribly broken
2 star - probably adequate
3 star - mostly trustworthy
4 star - quite solid
5 star - completely solid
Note that this is not entirely independent of other the categories -
I look at everything else when making my judgement. Including
seeding, interstate correlations (primarily assessed by avalanche
testing), possible linear patterns, subcycles, and other issues.
quality subscores for PractRand RNGs
name overall empirical cycle states trusted
jsf32 3 5 4 3 3
jsf64 3 5 5 5 3
sfc16 2 4 2 2 2
sfc32 3 5 4 3 3
sfc64 3 5 5 5 3
xsm32 3 4 4 3 3
xsm64 4 5 5 4 4
arbee 4 5 5 5 4
isaac32x256 5 5 5 5 5
isaac64x256 5 5 5 5 5
efiix8x384 5 5 5 5 5
efiix16x384 5 5 5 5 5
efiix32x384 5 5 5 5 5
efiix64x384 5 5 5 5 5
hc256 5 5 5 5 5
trivium 5 5 5 5 5
sha2_based_pool 5 5? 5 5 5
chacha (8) 5 5 5* 5 5
chacha (12) 5 5 5* 5 5
chacha (20) 5 5 5* 5 5
salsa (8) 4.5 5 5* 5 4.5
salsa (12) 5 5 5* 5 5
salsa (20) 5 5 5* 5 5
mt19937 2 2 5 5 3
* - should be a 4, but I added an optional tweak to make it a 5
explanations for those subscores on some PractRand RNG examples:
jsf32 3 5 4 3 3
empirical: 5 - passes all tests so far (and it has been very well tested)
cycle: 4 - avg ~ 2**127, good enough for any use today but maybe not future-proof
states: 3 - ~ 2**128, hitting a statespace related issue is difficult but possible
trust: 3 - looks good every way I can look at it, but not perfect
jsf64 3 5 5 5 3
empirical: 5 - passes all tests so far
cycle: 5 - avg ~ 2**255, future-proof
states: 5 - ~ 2**256, future-proof
trust: 3 - adding extra bits beyond jsf32 didn't really improve it very much
arbee 4 5 5 5 4
empirical: 5 - passes all tests so far
cycle: 5 - avg ~ 2**319 (min >= 2**64), future-proof
states: 5 - 2**320, future-proof
trust: 4 - better mixed & slightly larger than jsf64, fewer ways I could have missed a flaw
sfc16 (v4) 2 4 2 2 2
empirical: 4 - flaws detectable on EXTREMELY long tests (512 TB on PractRand std)
cycle: 2 - avg ~ 2**63 (min >=2**16), marginal for some uses
states: 2 - 2**64, marginal for some uses today
trust: 2 - apparent pretty decent, but I'm suspicious of it anyway
sfc32 (v4) 3 5 4 3 3
empirical: 5 - passed all tests
cycle: 4 - avg ~ 2**127 (min >=2**32), good enough for today but not future-proof
states: 3 - 2**128, marginal for extreme uses today
trust: 3 - looks decent
sfc64 (v4) 3 5 5 5 3
empirical: 5 - passed all tests
cycle: 5 - avg ~ 2**255 (min >=2**64), future-proof
states: 5 - 2**256, future-proof
trust: 3 - the extra bits over sfc32 didn't help very much
xsm32 3 4 4 3 3
empirical: 4 - passes all output tests so far, though seeding test results are weaker
cycle: 4 - always 2**64, good enough for anything today but not future-proof
states: 3 - 2**95, marginal for some parallel uses today
trust: 3 - the underlying state transition is horrible, but the quality of
the output hashing should be good enough to compensate ; however, in a
worst-case scenario interseed correlations could become significant
xsm64 4 5 5 4 4
empirical: 5 - passes all tests so far
cycle: 5 - always 2**128, future-proof
states: 4 - 2**192, good enough for anything now but not completely future-proof
trust: 4 - the extra bits helped significantly
mt19937 2 2 5 5 3
empirical: 2 - it fails binary rank tests, linear complexity tests,
and a few closely related variants. In practice that means it
fails TestU01 Crush, PractRand at 256 GB, and gjrand at --huge
cycle: 5 - exactly 2**19937-1, way beyond future-proof
states: 5 - exactly 2**19937-1, way beyond future-proof
trust: 3 - the hashing & size seem to be sufficient to handle its
underlieing problems well enough for almost any use; only the excessive
linearity creates problems
hc256 5 5 5 5 5
empirical: 5 - passes all known tests, even those normally not counted
cycle: 5 - average cycle is way beyond future-proof
states: 5 - statespace is way beyond future-proof
trust: 5 - obviously completely trustworthy
chacha (8+) 5 5 5* 5 5
empirical: 5 - passes all known tests, even those normally not counted
cycle: 5* - normally cycle length is 2**68, but I added a tweak to allow 2**100 in some circumstances
states: 5 - future-proof
trust: 5 - trustworthy
salsa (8) 4.5 5 5* 5 4.5
empirical: 5 - passes all tests I've tried
cycle: 5* - normally cycle length is 2**68, but I added a tweak to allow 2**100 in some circumstances
states: 5 - future-proof
trust: 4.5 - trustworthy. pretty much.
salsa (12+) 5 5 5* 5 5
empirical: 5 - passes all known tests, even those normally not counted
cycle: 5* - normally cycle length is 2**68, but I added a tweak to allow 2**100 in some circumstances
states: 5 - future-proof
trust: 5 - trustworthy
quality subscores for some candidates and rejects for PractRand recommended RNGs:
name overall empirical cycle states trusted
vf16 1 4 1 1 2
vf32 3 5 3 3 3
vf64 3 5 5 4 3
vfm32 2 5 2 2 2.5
vfm64 3 5 4 3 3.5
ranrot_alternative8 3 3 5 5 2
ranrot_alternative16 3 5 5 5 3
ranrot_alternative32 3 5 5 5 3
ranrot_alternative64 3 5 5 5 3
sfc16 (v3) 1 2 1 1 1.5
sfc32 (v3) 2 5 3 3 2
sfc64 (v3) 2 5 5 4 2
lcg(32,64) 0 1 0/4 0/2 1
clcg(32,96) 2 4 4/5 2/3 2
quality subscores for some non-PractRand RNG examples:
name overall empirical cycle states trusted
typical libc rand 0 0 0 0 0
rand48 0 0 1/0 1/0 0
ICG, m=2**31-1 0 0 0 0 3.5
RC4 3.5 4 5 5 3.5
KISS93 2 2.5 5 3 2
KISS4691 3 4 5 5 3
explanations for those subscores on non-PractRand RNG examples:
typical libc rand 0 0 0 0 0
empirical: 0 - fails most tests rapidly
cycle: 0 - technically 2**31, but more like 2**17 in practice
states: 0 - technically 2**31, but more like 2**17 in practice
trust: 0 - it has no rightward mixing, 2**17 subcycle
rand48 0 0 1/0 1/0 0
empirical: 0 - fails most tests rapidly
cycle: 1 - technically 2**48, but more like 2**17 in practice
states: 1 - technically 2**48, but more like 2**17 in practice
trust: 0 - it has no rightward mixing, 2**17 subcycle
RC4 3 3 5 5 3.5
empirical: 3 - passes a lot of tests, but fails PractRand after 1 TB
cycle: 5 - more than anyone will ever need
states: 5 - more than anyone will ever need
trust: 3.5 - it looks mostly good... but slightly funky... hard to evaluate
ICG, m=2**31-1 0 0 0 0 3.5
note: too slow to be of any practical use
empirical: 0 - passes a good amount of tests for its size, but that's
not saying much at all
cycle: 0 - adequate for very simple apps, but only barely
states: 0 - so small it guarantees a rapid failure
trust: 3.5 - it looks good... but rather funky... hard to evaluate;
irrelevant anyway for performance reasons and because the cycle length
and state size are both much too small
KISS93 2 3 5 3 2
empirical: 3 - passes a lot of tests, but fails a single subtest of BigCrush and
eventually PractRand at 2TB
cycle: 5 - more than anyone will ever need
states: 3 - fair amount
trust: 2 - very low quality component RNGs make bias likely
detectable; given that one of them is a power of 2 LCG the bias
may only show up on the low bits; also, the general compound
nature makes it underperform in some situations that normal
testing will not detect.
KISS4691 3 4 5 5 3
note: may be mixing naming conventions on KISS?
empirical: 4 - passes BigCrush and PractRand for a long long time,
but eventually fails low bit long range correlation tests
cycle: 5 - more than anyone will ever need
states: 5 - more than anyone will ever need
trust: 3 - low quality component RNGs make bias possibly detectable,
but the weaknesses of each component are sufficiently different
that maybe not; given that one of them is a power of 2 LCG the
bias may only show up on the low bits. Also, the general
compound nature makes it underperform in some environments that
standard testing will not detect; the large statespace of the
MWC component reduces but does not fix this problem.
speed: (rated from 0 to 5 stars)
Broadly:
0 stars - very slow - too slow for normal use
1 star - slow - fast enough for normal use, but only barely
2 stars - medium-slow
3 stars - medium-fast
4 stars - fast
5 stars - very fast
Speed is in arbitrary units. It's a bit subjective since actual
speed will vary with the circumstances in complex ways.
Typically a 1 star difference in speed ratings corresponds to
about a 30% difference in performance.
Also take note of the output size - if an RNG outputs more bits
per call then fewer calls will be necessary for many purposes.
Also take note of the word size - if an RNG is run on a computer
with general purpose registers of a different size than its word
size then it may run slower than expected.
theory: (rated from 0 to 5 stars)
This rating corresponds to how much the RNG or the math it uses
has been studied, how well its properties are known. An RNG with
zero stars in this area has no academic papers published about it,
an unknown number of cycles, and an unknown shortest cycle length
(though predictions are made about the average cycle length of such
RNGs and the probability of finding a short cycle by accident, and
such predictions are generally accurate). An RNG with 5 stars in
this category has numerous academic papers published about it,
fully known cycle lengths, etc. Intermediate numbers of stars
generally represent intermediate amounts of understanding and
attention from academics.
Broadly:
0 stars - everything known about the RNG was determined empirically
or by gut instinct
1 star - some property of the RNG is provable, and/or at least one
paper about the RNG or a closely related RNG has been published
...
5 stars - numerous flaws of the RNG are thoroughly documented
(generally not possible for high quality RNGs)
size: (in bytes)
This is the size in bytes of the RNG implementation. Generally a
larger number means that the RNG has a better statespace size and
cycle length, but is slower to initialize, uses more RAM (though
that's usually not significant on desktops), performs worse in rapid
context switching, etc.
word: (usually either 8, 16, 32, or 64 bit integers)
This is the size of integers that the RNG does math on internally.
Mostly you don't need to worry about this unless you want to. Broadly
an RNG will perform better if its word size is 32 on 32 bit machines,
or 64 on 64 bit machines, etc. It is generally also the size of
integer that the RNG outputs at once.
statespace size
This is the number of meaningfully distinct states the RNG can be in.
This is closely related to the size of the RNG - RNGs with larger sizes
usually have have larger statespaces. Statespace can be an important
factor in suitability of an RNG for high end parallel uses.
See "quality" above for information on how statespace size is factored
in to quality ratings.
minimum cycle length (aka period)
The shortest cycle the RNG possesses. May be impractical to figure
out for chaotic RNGs, in which case it will be listed as 1. RNGs with
small minimum cycles lengths may have a risk of producing the same
number over and over again if you use the wrong seed on them. In
practice this is normally not a significant issue for decent RNGs,
either due to the extreme unlikelyhood of picking a bad seed (in some
cases it may be computationally infeasible to even find a bad seed
deliberately, even with a massive distributed computing project), or
due extreme unlikely of a bad seed even existing (it is believed
that there are no bad seeds for hc256, even though that can't quite
be proven).
See "quality" above for information on how minimum cycle length size is
factored in to quality ratings.
operations used
Generally not important for desktops, but some exotic hardware may have
a hard time with some types of operations.
full word output
Means that the number of random bits produced per call to the RNG is
equal to the size of integers that the RNG operates on internally. All
PractRand recommended RNGs have full word output.
buffering
Means that the RNG produces multiple words at once internally, and stores
them in a buffer until the application wants them.
random access
Means that the RNG can skip forwards or backwards in its output stream
efficiently.
entropy pooling
Means that the RNG can be progressively seeded using irregular integer
sizes, allowing an RNG to be seeded in exotic ways and/or be used as a
hash function.
crypto security
The difficulty a competent attacker would face figuring out the seed
or internal state of an RNG from examining its output. Most RNGs
have a rating of "none" or 0 stars. The more computation and outputs
needed to figure out the internal state, the better. The more people
who have analyzed an RNGs security, the better. The more self-evident
or provable the security, the better.
VERY roughly guidelines:
1 star: analyzed by myself only
2 stars: analyzed by a few probably competent people
3 stars: analyzed by lots and lots and lots of people
+1 star: any two of:
well respected by reviewers
no hint that its security margin might be borderline
studied for more than a decade
+1 star: security is self-evident / trivially provable
multi-cyclic
Multicyclic RNGs have statespaces greater than their minimum cycle
length.
reversible
Reversible RNGs have average cycle lengths that are substantial
fractions of their state spaces. Irreversible RNGs have average
cycle lengths on the rough order of the square root of their
state space.
For multicyclic RNGs with smaller state spaces (say, less than 2**300),
reversibility is a good thing. Past there it is neither good nor bad,
though some people like irreversability in crypto RNGs, on the theory
that even if the RNG state somehow magically gets compromised, at least
the older output might still be secure.
Single-cycle irreversible RNGs are very rare and usually a bad idea.
*****************************************************************************
4. Descriptions of recommended RNGs
*****************************************************************************
The short version is:
sfc16 / sfc32 / sfc64
pros: fast, small
cons: none
hc256
pros: highest quality, strong cryptographic security
cons: large, slow to seed, slow
chacha / salsa
pros: random access, cryptographic security, high quality, fast seeding
cons: slow, particularly if not using a SIMD implementation
efiix8x384 / efiix16x384 / efiix32x384 / efiix64x384
pros: high quality, fast for the quality, marginal cryptographic security
cons: slow to seed
mt19937
pros: well studied, widely used
cons: large, slow to seed, poor quality vs speed
jsf32 / jsf64
pros: fast, small
cons: some bad cycles exist
xsm32 / xsm64
pros: random access, small
cons: requires fast hardware multiplication (i.e. not for low-end embedded platforms)
trivium
pros: small, some cryptographic security, extremely simple hardware implementation, high quality
cons: slow in software
sha2_based_pool
pros: high quality, cryptographic security, entropy pooling
cons: VERY VERY SLOW
arbee
pros: small, fast, entropy pooling
cons: none
isaac32x256 / isaac64x256
pros: some cryptographic security
cons: large, slow, a little slow to seed
The long version is:
small fast RNGs:
Small fast RNGs range from 2 to 5 words in size (16 to 40 bytes on 64 bit
systems), and tend to be the fastest category of RNGs.
jsf32 / jsf64
actual name: unnamed (I called it jsf for Jenkin's Small Fast RNG)
This algorithm is included because it is a good small fast chaotic
RNG and it is better studied that other small fast chaotic RNGs.
This algorithm was written by Bob Jenkins.
--
This small fast RNG is what I use as my baseline for the category
of small fast RNGs.
This small fast RNG has an advantage over most in that a lot of
people have looked at it, and many people have tried their own
custom unpublished RNG tests on it. No biases have been reported in
the ouput of the 32 or 64 bit versions of this. Even versions
scaled down to 16 bits pass most tests.
--
details:
quality subscores (scored from 0 to 5 stars):
empirical: 5 / 5
cycle length: 4 / 5
statespace: 3 / 5
trusted: 3 / 3
overall: 3 / 3
speed: fast
operations used: addition, bitwise, fixed shifts
full word output: yes
buffered: no
random access: no
entropy pooling: no
crypto security: none
minimum cycle: 1
word size: 32 / 64 bit
size: 16 / 32 bytes
statespace: 2**128-4 / 2**256-1
multi-cyclic: yes
reversible: yes
arbee
See arbee under entropy pooling RNGs below.
sfc16 / sfc32 / sfc64
actual name: Small Fast Counting RNG, version 4
This algorithm is included because of its combination of very fast
speed, good statistical properties, small size, and (on larger
word sizes) guaranteed minimum cycle length.
I wrote this algorithm. So I might be prejudiced.
--
This has not been as thoroughly tested as the jsf algorithm, but
on my tests so far it appears superior to jsf in both quality
and speed. It's basically a good small chaotic RNG driven by a
bad smaller linear RNG. The combination gives it the strengths of
each - good chaotic behavior, but enough structure to avoid short
cycles.
--
details:
quality subscores (scored from 0 to 5 stars):
empirical: 5 / 5 / 5
cycle length: 2 / 4 / 5
statespace: 2 / 3 / 5
trusted: 2 / 3 / 3
overall: 2 / 3 / 3
speed: fast
operations used: addition, bitwise, fixed shifts
full word output: yes
buffered: no
random access: no
entropy pooling: no
crypto security: none
minimum cycle: 2**16 / 2**32 / 2**64
word size: 16 / 32 / 64 bit
size: 8 / 16 / 32 bytes
statespace: 2**64 / 2**128 / 2**256
multi-cyclic: yes
reversible: yes
crypto / high quality RNGs:
These RNGs have *very* good statistical properties, and offer some degree
of cryptographic security. They also tend to be slow to seed. All except
trivium and chacha are indirection-based.
isaac32x256 / isaac64x256
actual names: ISAAC, ISAAC64 (Indirection, Shift, Accumulate, Add, Count)
This algorithm is included because of its combination of decent speed
with very good statistical quality. It is also included as an option
for fast cryptography - it is suspected of being less secure than
hc256, but it is also faster than hc256.
This algorithm was written by Bob Jenkins.
--
It's an indirection-based RNG.
--
details:
quality subscores (scored from 0 to 5 stars):
empirical: 5 / 5?
cycle length: 5 / 5
statespace: 5 / 5
trusted: 5 / 5
overall: 5 / 5
speed: medium-slow
operations used: addition, bitwise, fixed shifts, arrays
full word output: yes
buffered: yes
random access: no
entropy pooling: no
crypto security: moderate
minimum cycle: 2**40 / 2**72
word size: 32 / 64 bit
size: 2064 / 4128 bytes
statespace: 2**8296 / 2**16584
multi-cyclic: yes
reversible: yes?
hc256
actual name: HC-256 (not sure what that stands for)
This algorithm is included because it is believed to be quite
cryptographically secure. It is a bit slow and rather heavy-weight,
but it has excellent statistical properties and security.
This RNG uses buffered output, so some calls to it take much longer
than other calls to it.
This algorithm is believed to have no bad cycles.
--
Basically, it's a very large high quality variant of a fibonacci-style
RNG, with a little extra indirection-based stuff added. It's all set
up in a way that looks optimized for provability.
--
details:
quality subscores (scored from 0 to 5 stars):
empirical: 5?
cycle length: 5
statespace: 5
trusted: 5
overall: 5
speed: slow
operations used: addition, bitwise, fixed shifts, arrays
full word output: yes
buffered: yes
random access: no
entropy pooling: no
crypto security: strong
minimum cycle: none (probably no bad cycles)
word size: 32 bit
size: 8580 bytes
statespace: 2**65547
multi-cyclic: yes
reversible: yes?
efiix8x384 / efiix16x384 / efiix32x384 / efiix64x384
actual name: EFIIX stands for Entropy From Iteration, Indirection, Xor, (and addition)
This algorithm is included because of its combination of reasonable
speed with very good statistical quality. It is the fastest of the
cryptographic RNGs included in PractRand, and along with Trivium one
of two that is not buffered.
It appears to be moderately cryptographically secure to me, but that's
not worth much since no real cryptanalysis has been done by third
parties on it.
I wrote this algorithm. So I might be prejudiced.
--
It's another larger-state indirection-based RNG. Scaled down versions
are dramatically higher in quality than scaled down versions of other
indirection-based RNGs I've looked at, but that's not necessarily very
meaningful. I think of it as 384 braided "strands" of state, where for
each output one strand gets shuffled to a randomized position. At the
same time there's something like a small fast RNG that intermixes with
each strand as the strands get reordered.
--
details:
quality subscores (scored from 0 to 5 stars):
empirical: 5 / 5? / 5? / 5?
cycle length: 5 / 5 / 5 / 5
statespace: 5 / 5 / 5 / 5
trusted: 5 / 5 / 5 / 5
overall: 5 / 5 / 5 / 5
speed: medium-slow
operations used: addition, bitwise, fixed shifts, arrays
full word output: yes
buffered: no
random access: no
entropy pooling: no
crypto security: some
minimum cycle: 2**8 / 2**16 / 2**32 / 2**64 (probably no bad cycles)
word size: 8 / 16 / 32 / 64 bit
size: 388 / 776 / 1552 / 3104 bytes
statespace: 2**3104 / 2**6208 / 2**12416 / 2**24832
multi-cyclic: yes
reversible: yes
trivium
This algorithm is included because of its of small size combined
with cryptographic security. It is not as secure as HC-256,
but still offers a significant degree of security.
--
It's basically 3 cyclic buffers operating on individual bits, with
some relatively simple logic connecting the 3. Broadly similar to,
but higher quality than, small fast chaotic RNGs like jsf64. Though
it has a more regular structure than most small fast chaotic RNGs,
and is a lot slower.
This is the only small simple crypto RNG I've seen. Note that it
is very easy to implement in hardware, requiring far fewer
transistors than the other CSPRNGs that PractRand includes. Some
published attacks suggest that the security of its seeding function
is marginal unless you skip the first few outputs.
--
details:
quality subscores (scored from 0 to 5 stars):
empirical: 5?
cycle length: 5
statespace: 5
trusted: 5
overall: 5
speed: quite slow
operations used: bitwise, fixed shifts
full word output: yes
buffered: no
random access: no
entropy pooling: no
crypto security: low (medium if you skip the first few outputs)
minimum cycle: --
word size: 64 bit
size: 48 bytes
statespace: 2**288
multi-cyclic: yes
reversible: yes?
salsa / chacha (variable numbers of rounds)
Actual name for salsa: Salsa20/# (replace # with the number of rounds) aka Snuffle 2005
Actual name for chacha: ChaCha or ChaCha# (replace # with the number of rounds) aka Snuffle 2008
This algorithm is included because of its of support for random
access, its cryptographic security, and its fast seeding.
--
Notes on ChaCha vs Salsa:
ChaCha is basically a more recent version of Salsa.
The chacha version is simpler, faster, smaller, higher quality,
and marginally more secure. The only reason the older salsa
version is included at all is because it has the unambiguous
license statement and eSTREAM certification - chacha is better in
all other ways.
Notes on Salsa/ChaCha speed:
There are two issues that have a big impact on Salsa/ChaCha speed:
1. Number of rounds. Basically a quality setting. Fewer rounds
is faster (but not fast), more rounds is higher quality and more
secure.
* ChaCha ChaCha Salsa Salsa
Rounds quality security quality security
20(default) 5***** 4**** 5***** 4****
12 5***** 3*** 5***** 3***
8 5***** 2** 4**** 1*
6 4**** 0 3*** 0
4 3*** 0 1* 0
It is recommended that only even numbers of rounds be used -
the behavior of odd numbers of rounds is not as well defined.
2. SIMD usage. These algorithms are designed for SIMD. They
work fine in non-SIMD implementations, but they are
significantly faster when using SIMD. My implementation currently
does not use SIMD do to inability to guarantee memory alignment
properly.
--
It looks kinda like a block cypher applied to a counter - the
state transition function is trivial, but the output hashing is
extremely high quality.
The algorithm as defined in the spec has a cycle length of 2*68,
which would limit it to a quality rating of 4 under my rating
scheme. To allow it to meet my requirements for a 5 star
quality rating the implementation included here has an optional
tweak allowing the cycle length to be extended to 2**100. It
still returns the same values for the first 2**68 calls, but
after that instead of starting over at the begining it can allow
carries on the stream position to overflow in to one of the
constants. This non-standard behavior is disabled by default
when seeding with the chacha seeding formats to maximize
compatibility with other chacha implementations, but enabled
when using PractRand-specific seeding options (like autoseeding)
when compatibility should not be an issue. It can also be
manually enabled when using a chacha seeding format.
--
details:
quality subscores (scored from 0 to 5 stars):
empirical: 5 (see above chart relating # of rounds to quality)
cycle length: 5* (depending upon seeding method)
statespace: 5
trusted: 5 (see above chart relating # of rounds to quality)
overall: 5 (see above chart relating # of rounds to quality)
speed: quite slow (faster when using SIMD implementation)
operations used: addition, bitwise, fixed shifts (optimized for SIMD)
full word output: yes
buffered: yes
random access: yes
entropy pooling: no
crypto security: medium-high (see above chart relating # of rounds to quality)
minimum cycle: 2**68 or 2**100
word size: 32 bit (or 128 bit with SIMD)
size: 124 bytes for ChaCha, 136 bytes for Salsa
statespace: 2**384
multi-cyclic: yes
reversible: yes
popular RNGs:
mt19937
This is the Mersenne Twister. It is included because of its popularity -
this RNG is widely used and widely recognized. It also has an unusual
combination of reasonably well understood mathematical properties
(corresponding to its good "theory" rating) with acceptable speed &
statistical properties. So if you want an RNG that has a good theory
rating and doesn't compromise speed or statistical properties too much then
this is a solid choice.
This algorithm has no bad cycles (it is single-cycle), though it does have
equivalents - bad regions within its cycle. This is the only recommended
single-cycle RNG in PractRand.
--
The state transition function is a very low quality large twisted LFSR.
The output function is a relatively complex hashing function to mask
the flaws of the underlieing twisted LFSR. But for some reason the
output hashing function used is also purely linear.
In PractRand it fails only the binary matrix rank test. It looks like it
really ought to flunk my BCFN test, but it doesn't. Testing suggests that
it's ability to pass that test would evaporate if it had a smaller
statesize or slightly weaker output hashing, but is passes consistently,
even when very very large quantities of output are used.
It's test failures suggest that it should be considered low-quality...
but the failures seem oddly brittle, with slight meaningless variations
causing mt19937 to pass them, so I'm not entirely sure how to treat
that.
Technically random access is possible for this algorithm, but the cost
(in memory & cycles) required is sufficiently painful that it's never
done in practice.
update: PractRand 0.91 now includes a binary rank test in the core test
set. With this change, mt19937 now fails PractRand standard after 256
gigabytes. Oddly enough it doesn't just fail matrix sizes over 19937,
it also fails low-bit tests using smaller matrices (12 thousand). I'm
not sure what that means.
--
details:
quality subscores (scored from 0 to 5 stars):
empirical: 2
cycle length: 5
statespace: 5
trusted: 2
overall: 2
speed: medium-slow
operations used: addition,bitwise,fixed shifts,simple arrays, (seeding only:)multiplication
full word output: yes
buffered: yes
random access: no (well... sorta, but not really)
entropy pooling: no
crypto security: none
minimum cycle: 2**19937-1
word size: 32 bit
size: 2500 bytes
statespace: 2**19937-1
multi-cyclic: no
reversible: yes
entropy pooling RNGs:
In PractRand, an entropy pool is an RNG that accepts arbitrary
input and produces as output a stream of pseudo-random numbers
that is effectively an inifinitely long hash of its input. See
RNG_entropy_pools.txt for more information.
arbee
This algorithm is included because of its combination of reasonable
speed, excellent statistical properties, small size, ability to act as
an entropy pool, and guaranteed minimum cycle length. In particular
it is the only entropy pool in PractRand that is small and/or fast.
See RNG_entropy_pools.txt for more information.
Much of this algorithm is heavily based upon jsf64 by Bob Jenkins,
but I adapted it slightly for different purposes than jsf64. So I
might be prejudiced.
--
It's just the 3-rotate version of the 64 bit version of Bob Jenkins small
fast RNG, with a counter added to make short cycles impossible. I also
added some progressive seeding stuff so it can act as a fast entropy pool.
--
details:
quality subscores (scored from 0 to 5 stars):
empirical: 5
cycle length: 5
statespace: 5
trusted: 4
overall: 4
speed: medium-fast
operations used: addition, bitwise, fixed shifts
full word output: yes
buffered: no on output, sort of but not really on input
random access: no
entropy pooling: yes
crypto security: none
minimum cycle: 2**64
word size: 64 bit
size: 40 bytes
statespace: 2**320 (2**256 effective for some purposes)
multi-cyclic: yes
reversible: yes
sha2_based_pool
This is an SHA-2 based entropy mixing pool.
This algorithm was included to be a cryptographically secure
entropy pool. It is also the smallest cryptographically secure
RNG recommended in PractRand at the moment.
--
It's just the SHA2-512 algorithm and some buffers set up to act as
an RNG.
--
details:
quality subscores (scored from 0 to 5 stars):
empirical: 5?
cycle length: 5
statespace: 5
trusted: 5
overall: 5
speed: very very slow (for both output and input)
operations used: addition, bitwise, fixed shifts, simple arrays
buffered: yes
random access: no
entropy pooling: yes
crypto security: moderate
minimum cycle: none (probably no bad cycles)
word size: mix of 8 and 64 bit
size: 308 bytes
multi-cyclic: yes
reversible: no
random access RNGs:
A random access RNG or seekable RNG is an RNG that you can advance or rewind to