4
$\begingroup$

Can I use Salsa20 as a good non-cryptographic PRNG with different streams if I reduce the number of rounds to 8 and omit the addition step at the end? I want to omit the final step because I don't want to get all zero outputs.

$\endgroup$
5
$\begingroup$

Reducing the rounds to 8 would give you Salsa20/8, which is not just a fast PRNG operating at 1.88 cycles per byte on Core2Duo, but is still quite cryptographically secure with the best attack requiring approximately 2244 operations. Removing the final addition step would not be good though, as without that, it would be trivial to reverse the function and discover the key and counter given just a single block of known plaintext. You will not get all zero outputs by keeping the addition, so you should keep it.

You could cut the algorithm down to four rounds in order to roughly double the speed while completely sacrificing cryptographic security. Less than four rounds results in incomplete diffusion, leading to biased and non-uniform output. However, it will still be roughly twice as slow as the fastest dedicated non-cryptographic PRNG, XorShift128+ (an LFSR-based PRNG at 0.48 cycles per byte on Kaby Lake).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Some other non-cryptographic algorithms are certainly faster, but they have a smaller state (I need room for a SHA256 hash) and I need streams. There doesn't seem to be much choice other than crypto algorithms if you have these requirements. $\endgroup$ – Thorham Jan 21 '19 at 12:00
  • $\begingroup$ Is 0.48 c/b for a scalar implementation? You can run four XorShift128+ PRNGs in parallel in elements of an AVX2 vector. See AVX/SSE version of xorshift128+ for __m256i xorshift128plus_avx2(struct rngstate256 *sp). 8 SIMD ALU uops per 32 bytes of results => about 12 bytes per cycle, or 0.0833 c/b on SKL / KBL. (I used it in my answer on What's the fastest way to generate a 1 GB text file containing random digits? which does > 8 bytes per cycle of space-separated ASCII decimal digits on SKL.) $\endgroup$ – Peter Cordes Jan 21 '19 at 14:52
  • $\begingroup$ @Thorham: would it work to use a SHA256 hash as the seed for two XorShift128+ PRNGs operating in parallel? If so, 2x 128-bit SIMD vectors will work, and let you generate 2x 64-bit random numbers in parallel. Or use 256-bit vectors to run 4 generators in parallel, requiring twice as much seed data. See my previous comment for C++ and C intrinsics implementations. $\endgroup$ – Peter Cordes Jan 21 '19 at 14:58
  • 2
    $\begingroup$ @PeterCordes, Thorham, xoshiro256**/+ are available too. (They use rotate, not just xor-shifts. May not be as suitable for vector implementations.) Two instances of a 128-bit algorithm seeded like that isn't too different from just truncating SHA-256 output to 128 bits. $\endgroup$ – Future Security Jan 21 '19 at 16:09
  • 1
    $\begingroup$ @FutureSecurity: SSE2 / AVX2 xoshiro256** looks very possible. AVX512 even has SIMD rotates, making it even better. Other SIMD ISAs can emulate it with shift+shift+OR. SIMD integer multiply is not bad for 32-bit integers on Intel CPUs with SSE4.1, but requires extended-precision techniques for 64-bit integer elements (until AVX512), which is why I used xorshift+ instead of *. But xoshiro256** only multiplies by the constants *5 and *9, which are both power-of-2 + 1 so are just left-shift+add. (In a scalar implementation, x86 can do that in one cycle with lea rax, [rbx + rbx*8].) $\endgroup$ – Peter Cordes Jan 21 '19 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.