1 unstable release
Uses old Rust 2015
0.0.0 | Jun 17, 2018 |
---|
#94 in #rng
25KB
415 lines
Overview
What if we could default to attack-resistant random generators without excessive CPU cost? We introduce 'Randen', a new generator with security guarantees; it outperforms MT19937, pcg64_c32, Philox, ISAAC and ChaCha8 in real-world benchmarks. This is made possible by AES hardware acceleration and a large Feistel permutation.
Related work
AES-CTR (encrypting a counter) is a well-known and easy to implement generator. It has two known weaknesses:
-
A known-key distinguisher on 10-round, 128-bit AES https://goo.gl/3xReB9.
-
No forward security/backtracking resistance: compromising the current state lets attackers distinguish prior outputs from random.
NIST 800-90a r1 https://goo.gl/68Fwmv is a standardized generator that ensures backtracking resistance, but is not fast enough for a general-purpose generator (5-10x slower than AES).
Algorithm
The Randen generator is based upon three existing components:
-
Reverie https://eprint.iacr.org/2016/886.pdf is a sponge-like generator that requires a cryptographic permutation. It improves upon "Provably Robust Sponge-Based PRNGs and KDFs" by achieving backtracking resistance with only a single permutation per buffer.
-
Simpira v2 https://eprint.iacr.org/2016/122.pdf constructs up to 1024-bit permutations using an improved Generalized Feistel network with 2-round AES-128 functions. This Feistel block shuffle achieves diffusion sooner and is less vulnerable to sliced-biclique attacks than a Type-2 cyclic shuffle.
-
"New criterion for diffusion property" https://goo.gl/mLXH4f shows that the same kind of improved Feistel block shuffle can be extended to 16 branches, which enables a more efficient 2048-bit permutation.
We combine these by plugging the larger Simpira-like permutation into Reverie.
Performance
The implementation targets x86 (Westmere), POWER 8 and ARM64.
x86 microbenchmark: generating random bits in a tight loop (cpb=cycles per byte, MAD=median absolute deviation):
RNG | cpb | MAD |
---|---|---|
Randen | 1.54 | 0.002 |
pcg64_c32 | 0.78 | 0.003 |
mt19937_64 | 1.79 | 0.001 |
ChaCha8 | 3.02 | 0.003 |
ISAAC | 4.08 | 0.006 |
Philox | 4.70 | 0.003 |
/dev/urandom (ChaCha20) | 15.27 | 0.018 |
BCryptGenRandom (CTR-DRBG) | 16.80 | 0.009 |
x86 real-world benchmark (reservoir sampling):
RNG | cpb | MAD |
---|---|---|
Randen | 2.60 | 0.008 |
pcg64_c32 | 3.03 | 0.009 |
mt19937_64 | 2.82 | 0.009 |
ChaCha8 | 3.75 | 0.008 |
ISAAC | 4.46 | 0.014 |
Philox | 4.95 | 0.009 |
/dev/urandom (ChaCha20) | 13.46 | 0.017 |
BCryptGenRandom (CTR-DRBG) | 16.41 | 0.015 |
Security
Randen is indistinguishable from random and backtracking-resistant. For more details and benchmarks, please see "Randen - fast backtracking-resistant random generator with AES+Feistel+Reverie".
Usage
make && bin/randen_benchmark
Note that the code relies on compiler optimizations. Cycles per byte may increase by factors of 1.6 when compiled with GCC 7.3, and 1.3 with Clang 4.0.1. This can be mitigated by manually unrolling the loops.
Third-party implementations / bindings
Thanks to Frank Denis for making us aware of these third-party implementations or bindings. Note that the algorithm is still under review and subject to change, but please feel free to get in touch or raise an issue and we'll add yours as well.
By | Language | URL |
---|---|---|
Frank Denis | C | https://github.com/jedisct1/randen-rng |
This is not an official Google product.
lib.rs
:
The Randen pseudorandom number generator.
Dependencies
~330–520KB