# Correctly generating cryptographically secure pseudorandom numbers (in C)?

I am learning about cryptography, purely for my own interest. As part of that, I am implementing a simple toolset in C.

Naturally, I need to generate random numbers to create the pad, and they need to be cryptographically strong. I know about rand(), but from what I can tell it is not strong.

Is there a standard algorithm (or library) that I should be looking at to accomplish this?

-
So you want a stream cipher? –  CodesInChaos Apr 11 '12 at 19:39
I don't think so. I am looking for a CSPRNG that I can use in C. Just wondering if there is a standard for this. –  Tom Scrace Apr 11 '12 at 22:55
When you use a PRNG to generate a stream of bytes that you XOR with the plaintext to form ciphertext, that's a stream cipher (just like RC4). That is NOT a one-time pad. –  David Schwartz Apr 12 '12 at 9:22
Oh. Thanks David. Maybe I have misunderstood something here. So, you're saying that the defining feature of the one time pad is that the random bytes of the key are generated by some true source of randomness, as opposed to a PRNG? –  Tom Scrace Apr 12 '12 at 12:30
Essentially, yes. The difference between a one-time pad and a stream cipher is, essentially, that a one-time pad has a key that's the same size as the data encrypted while a stream cipher has a key size that is independent of the plaintext size. As soon as you hook an XOR engine up to a PRNG, it's not a one-time pad. A one-time pad has to hook the XOR engine to the key. –  David Schwartz Apr 13 '12 at 1:51

Short answer: Don't do this. The security proof for the One Time Pad requires the use of a True Random Bit Generator. The best you can find on a typical multipurpose system without dedicated hardware support for a TRBG is a Cryptographically Secure Random Bit Generator. The difference is that CSRBG is typically a deterministic algorithm that is seeded with good quality entropy the system is able to collect from various states and events. Because of this, using it for generating an OTP would in fact be no more secure than using a black box stream cipher for generating the key stream.

However, for the sake of argument, let's suppose you are implementing an OTP on a *nix based multipurpose system. What is the best you can hope for?

• The key will have to be as long as the message and will have to contain random bits, each with full entropy. This means that the key will have to be stored externally after generation. There will be no way of regenerating the exact same key, except by storing it, transferring it over a secure channel and reloading it. If there is any way at all to regenerate the same key stream from a more compact seed or key (even in theory), it is by definition not an OTP.
• /dev/urandom is no better than using a stream cipher. It is unblocking exactly because it is based on an algorithm that generates the output from a small seed. In principle, /dev/random should be implemented to return full entropy bits (which is why it is blocking - it always waits for enough entropy to be generated), but, firstly, there is no guarantee that it estimates the entropy of its input correctly, and, secondly, that it manages to extract that entropy in a completely unbiased manner. In fact, if the extraction is accomplished by e.g. hashing the entropy input, it is even highly unlikely that the extracted entropy will be completely unbiased. It will at best be good enough for all practical purposes, but that doesn't include using it for an OTP.
-
Thanks for this Henrick. I know that it's not going to be a truly secure one time pad, but I am only doing this for my own education, and as a bit of fun. Do you know if there is a generally accepted CSRBG C library or algorithm that I should be looking at? Thanks. –  Tom Scrace Apr 11 '12 at 19:10
I think the generally accepted way is to use the platform specific recommended CSRBG that is provided by the OS, at least if you are using modern versions of Windows, Linux or MacOSX. However, if you just want to start with something fairly simple that is easily implemented in C, you could always take a look at the RC4 algorithm. –  Henrick Hellström Apr 11 '12 at 19:44
Thanks again Henrick. I am looking into the PRNG in RC4. Do you know if /dev/random is generally considered to be cryptographically strong? –  Tom Scrace Apr 11 '12 at 21:51
I guess the quality of /dev/random/ is generally considered to be highly version dependent. –  Henrick Hellström Apr 12 '12 at 0:52
Thanks Henrick. I have ended up going with /dev/random and it seems to work pretty well. This is on OS X. –  Tom Scrace Apr 12 '12 at 2:55