CSPRNG for everyone! (or Do you hate std::random_device?)

[Duthomhas]

I just wrote a little library to get values from the OS CSPRNG, which is where you should be getting CS random numbers anyway, and what you should be using to seed your PRNGs in <random>.

For example, let's generate 20 random integer values, sorted from smallest to largest:

  #include <algorithm>
  #include <iostream>
  #include <vector>
  #include <duthomhas/csprng.hpp>

  int main()
  {
    duthomhas::CSPRNG rng;

    auto xs = rng( std::vector <int> ( 20 ) );
    std::sort( xs.begin(), xs.end() );

    for (int x : xs) std::cout << x << "\n";
  }

CSPRNG is also a drop-in replacement for the horribly-committee-brained std::random_device (which needs to die), and is perfectly usable to initialize, say, your Mersenne Twister:

  duthomhas::CSPRNG seed;
  std::mt19937 rng( seed.sseq );
  // Hey, no need to discard() anything! :O) 

Check it out here:
https://github.com/Duthomhas/CSPRNG

[helios]

What's wrong with std::random_device?

[mbozzi]

Very nice!

I'm grateful for CSPRNG::sseq....

[Duthomhas]

@helios
Just about everything. Melissa O’Neil has a pretty good summary here http://www.pcg-random.org/posts/cpps-random_device.html

The reality is that it can fail with or without your knowledge for any reason at all. And using it is painful.

C and C++ are crippled by poor random number generation capabilities. Heck, the best we can get from C++’s Standard Library is a Mersenne Twister, which is outmoded and outclassed by years. How often do we (or SO, etc) get questions about std::rand()? That should have died hard at least ten years ago.

Good RN generation is still, frankly, not a feature of modern C++.


Maybe I’ll blog about it and link here.

(I'm still working on a FAQ update about random number generation in C and C++. It really is not that hard to do it right, but there is a lot to learn about it that goes against what has seeped into the general programming community for decades.)

@mbozzi
Yeah! I’m pleased you are pleased.

[mbozzi]

The best we can get from C++’s Standard Library is a Mersenne Twister, which is outmoded and outclassed by years.

RNGs are still mostly black magic to me, even after quite a bit of research. I don't know enough math I guess.

If you don't mind me asking here, what's wrong with the Mersenne Twister? I mean, in what way(s) is it outclassed by newer methods? Besides a way to seed it correctly that's not ridiculous, what should be added or changed to fix the deficiencies?

[Duthomhas]

[updated]

Nothing. It is just old and methods to crack it are well-understood now. And it is relatively slow.

Check out XorShift+ or Xoroshiro128+ for PRNGs that blow MT out of the water.

O’Neil’s PCG is also very nice; it exists because of her frustration over the deficiencies of PRNGs which still dominate software.


I’m trying to finish up the FAQ pages on random number generation, but there is a lot to distill down to something both readable and usable. I’ll definitely post here in the lounge when it is ready.


But the basics are: take a number (the “seed”, if you will), perform some mathematical operations on it, and spit out some collection of the resulting bits as your generated number. Repeat ad infinitum. All pseudo-random number generation works this way. The only difference is the math used.

An LCG is a “linear congruential generator” — a line function with a remainder function tacked on:

    y ≡ mx + b (mod n)

That’s it! (And you can hopefully see why it is easy to crack. Just watch for a few iterations and you can figure out both m and n.)

Smarter generators apply more sophisticated mathematical operations.


A CSPRNG is still a PRNG, except it has special constraints: namely, the mathematical functions applied are significantly more sophisticated, and the initial state comes from an STRNG (which produces whitened TRNG data, also called “entropy”) and may be modified by it regularly as well.

Well, back to working on my blag.

Find it here: http://michael-thomas-greer.com/blog/CSPRNG/

[helios]

I mean, it's (well-?)known that general purpose PRNGs are not cryptographically secure. That there exist vulnerabilities in MT in somewhat irrelevant, since no one uses it in security applications.

Personally, I think MT is rather meh for performance reasons. It has a relatively large internal state (600+ integers) and it updates it completely with a relatively expensive operation every 600 or so generations. For comparison, xorshift128 maintains only 128 bits of state, and an LCG may maintain as few as 32.

[Duthomhas]

Yes, exactly.

There are four classes of RNGs, which fall into the following manifold with the usual initialisms:

             insecure   secure
            ┌────────┐┌────────┐
     pseudo │  PRNG  ││ CSPRNG │
            └────────┘└────────┘
            ┌────────┐┌────────┐
      true  │  TRNG  ││ STRNG  │
            └────────┘└────────┘

Substitute "secure" with "unpredictable" and you get the gist of truth. All the stuff in the standard library is PRNG.

Speed is an implementation issue; but it is not necessarily correlated to the security.


The way it works is this: TRNG is “whitened” into STRNG, which is used as “entropy” to seed and regularly update the internal state of the OS CSPRNG.


And you should pull a seed for your PRNG of choice (secure or insecure) from the OS CSPRNG, then use that. (My library lets you do that easily.)

  duthomhas::CSPRNG seed;
  std::mt19937 rng( seed.sseq );

That properly seeds the entire internal state (all 600+) with data (in contrast to the faux seeding you get from using the time -- which is a terrible seed itself).

Many CSPRNGs you can use for general random number generation are also very quick, perfectly usable in high-performance applications, and are still properly seeded by the OS CSPRNG.

[plexus]

Just because good ol' PRNGs don't fit your application doesn't mean they're bad or shouldn't be used, or should even be removed from the lib.

There are many cases where the security or sophistication of a RNG is irrelevant for the task.
I even use std::rand() at times without even seeding it. Because sometimes it's just not neccessary.

Choose the right tool for a task, not the best. KISS!

[JLBorges]

> Do you hate std::random_device?

No, I don't. The implementations have become quite good for a couple of years now.
(The only black sheep still remaining is the GNU MinGW Library on Windows.)

Microsoft:

Although the ISO C++ Standard does not require random_device to be cryptographically secure, in Visual Studio it is implemented to be cryptographically secure.
https://docs.microsoft.com/en-us/cpp/standard-library/random

GNU (not MinGW):
Uses hardware supported entropy on modern Intel 64 / IA-32 (RDRAND instruction), /dev/urandom otherwise
https://gcc.gnu.org/git/?p=gcc.git;a=blob_plain;f=libstdc%2B%2B-v3/src/c%2B%2B11/random.cc;hb=HEAD

LLVM:
Uses NaCl on platforms where it is available; otherwise /dev/urandom on Unix and clones.
https://github.com/llvm-mirror/libcxx/blob/master/src/random.cpp

The stub for libc++ on windows calls Microsoft's rand_s() which "uses the operating system to generate cryptographically secure random numbers."
https://msdn.microsoft.com/en-us/library/sxtz2fa8.aspx

[Duthomhas]

> No, I don't.
Well, you are not my target audience, then. :>

/end good humor
...
/restart good humor

> The implementations have become quite good for a couple of years now.
Yes, but I take especial issue with the exceptions (lack of guarantee) and with the clunkiness of the design altogether.

That's some good info you put there, though. I'm pleased you mentioned Sodium. (Well, sorta.)

[ZoranV]

Hello, Duthomhas,

I cannot compile (g++ 5.4.0, Code::Blocks 16.01, Linux Mint 18.1) the first example (here: https://github.com/Duthomhas/CSPRNG#c ):

#include <iostream>
#include <duthomhas/csprng.hpp>

int main()
{
  duthomhas::CSPRNG rng;
  std::cout << rng() << "\n";
}

The compiler error message:
main.cpp|31|error: ‘CSPRNG’ is not a member of ‘duthomhas’|

I tried with lowercase duthomhas::csprng rng, as I see there is a class csprng in duthomhas namespace, but then i get:
main.cpp|32|error: ambiguous overload for ‘operator<<’ (operand types are ‘std::ostream {aka std::basic_ostream<char>}’ and ‘duthomhas::csprng’)

Please tell me what am I doing wrong?

[ne555]

when asking about compiler errors post the code that produces that error.
I could managed to get the same message by writting

#include <iostream>
#include <duthomhas/csprng.hpp>

int main()
{
  duthomhas::csprng rng;
  std::cout << rng /*note the lack of parenthesis*/ << "\n";
}

this compiled fine

#include <iostream>
#include <duthomhas/csprng.hpp>

int main()
{
  duthomhas::csprng rng;
  std::cout << rng() << "\n";
}

[ZoranV]

Sorry, ne555, but I still can't make it work.
This is exact text copied from my IDE:

#include <iostream>
#include <duthomhas/csprng.hpp>

int main()
{
  duthomhas::csprng rng();
  std::cout << rng() << "\n";
}

I get:
main.cpp|8|error: ambiguous overload for ‘operator<<’ (operand types are ‘std::ostream {aka std::basic_ostream<char>}’ and ‘duthomhas::csprng’)|

EDIT:
Ah, I see that I added the parentheses to declaration. However, still does not compile:

#include <iostream>
#include <duthomhas/csprng.hpp>

int main()
{
  duthomhas::csprng rng; // parenthesis removed
  std::cout << rng() << "\n";
}

Now I get this:
/home/z/programiranje/code_blocks/TestStaticVar/duthomhas/csprng.hpp|90|undefined reference to `csprng_create'|

[Duthomhas]

Remember that capitalization is significant in C++.

Next, when you compile you must also compile and link csprng.cpp with your program, just as the documentation says https://github.com/Duthomhas/CSPRNG#installing

(That error code means that the linker cannot find the csprng_create() function referenced in duthomhas/csprng.hpp.)

[kbw]

Windows support too, how quaint.

[Ganado]

Is that common practice to have the internal/C version be CAPS, and lowercase if it's C++? So, CSPRNG (void* typedef) is not wrapped in the namespace, because that's the version needed for C, but csprng is? Not saying it's wrong or right (I have no idea), I've just never seen a design like that.

Also is the example in your readme wrong then, since CSPRNG isn't wrapped in the namesapce?

  duthomhas::CSPRNG rng;
  std::cout << rng() << "\n";

[ZoranV]

Thanks, Duthomas,
in Code::Blocks I had to add csprng.hpp to the project (I mistakenly thought that adding the project path to project's search path would be enough) and now it compiles.

However, you said:

Remember that capitalization is significant in C++.

Now I can compile with lowercase csprng:

#include <iostream>
#include <duthomhas/csprng.hpp>

int main()
{
  duthomhas::csprng rng; // csprng in lowercase, unlike in original example
  std::cout << rng() << "\n";

  return 0;
}

, but still not the code shown here: here: https://github.com/Duthomhas/CSPRNG#c (with capital CSPRNG):

#include <iostream>
#include <duthomhas/csprng.hpp>

int main()
{
  duthomhas::CSPRNG rng;
  std::cout << rng() << "\n";

  return 0;
}

Which gives me:
/home/z/programiranje/code_blocks/TestStaticVar/main.cpp|6|error: ‘CSPRNG’ is not a member of ‘duthomhas’|

Did you make mistake in this example, or I still don't do it properly?

[Duthomhas]

kbw wrote:

Windows support too, how quaint.

LOL. I think I need to add BSD support too...

Ganado wrote:

Is that common practice to have the internal/C version be CAPS, and lowercase if it's C++?

ZoranV wrote:

Now I can compile with lowercase csprng:

Hmm, you're right. I’ll have to fix the docs and/or the library.

CSPRNG is a initialism for Cryptographically Secure Pseudo-Random Number Generator, so I made it caps.

Otherwise, there is no such convention. Caps is typically reserved for CPP macros, but otherwise, whether you get caps or not depends entirely on your library writer. The nice thing about using caps in class names is that you can make your variables minuscules but otherwise give it the same kind of name.

Thanks for noticing the error. Give me a couple days to fix it.

[ZoranV]

Okay, Thank you. You might also consider just making an alias in csprng.hpp, so the example will become valid and already working code with lower case won't be broken:

//...
namespace duthomhas
{
  struct csprng
  {
  //...
  };

  typedef csprng CSPRNG;

}