Perfectly random one-time pad for encryption

Question

I need to create a one-time pad to encrypt some data (a few KBs in size). How should I go about generating this one-time pad to avoid all of the pseudo-random problems associated with basic random number generation such as rand()?

Is there an existing, trusted tool or library I can use for this?

Eo

What language / operating system / runtime environment are you using? – Patinated

look here for a couple of good solutions: #3436876 – Cuprum

@Erik, doesn't matter too much. Preferably Windows, though. – Eo

Answer 1

Try Random.ORG. They have various free (and paid) services that generate truly random numbers based on atmospheric noise (or at least that is what they claim to do).

Olsen

As long as you don't mind someone else knowing your super-secret one time pad. And you don't mind your attackers being able to intercept it on the wire. – Mariann

Answer 2

Most modern operating systems have a cryptographically-secure pseudo-random number generator.

For example, Windows has CryptGenRandom. You can access the same stream from .NET by using the RNGCryptoServiceProvider class. From C++, you can access the same stream by using the Microsoft C++ library function rand_s. From Python, it's accessible using the function urandom (see bottom of linked page) in the os module.

Unlike normal PRNGs, CSPRNGs are designed to pass rigorous statistical randomness tests. They're also designed to hold up well under serious attack, even when their initial or running state becomes available to an attacker.

The term "pseudo-random", as used by cryptographers, may be misleading to a non-technical reader. A CSPRNG expands a collection of random values, known as a seed, into a longer sequence of numbers. That sequence is reproducible given the seed, but for any good CSPRNG, a minor change in the seed yields a very different sequence. Therefore, as long as at least some portion of the seed is chosen via an adequately random process, an attacker is unable to predict the resulting sequence - even if the attacker can influence the remainder of the seed.

Numerous important systems, ranging from military communications to the encryption that protects virtually all online transactions, rely on the functionally-equivalent security between "cryptographically-secure pseudo-random" and "random".

EDIT: If you're lucky enough to be working with Intel's Ivy Bridge processor range, you now have another very interesting alternative.

Meuse

Answer 3

You can't generate truly random numbers algorithmically - you need hardware assistance. If you use an algorithm, however secure (such as a cryptographically secure PRNG), you're simply creating a stream cipher based on that PRNG; it's no longer a One Time Pad.

Mariann

@Nick: While using a cryptographically-secure PNRG for a one-time pad is not the same as using a true RNG, the two methods are almost identical in strength. It's not called "cryptographically-secure" for nothing. And I like Steve Bellovin's quote: "I've observed that one-time pads are theoretically unbreakable, but practically very weak. By contrast, conventional ciphers are theoretically breakable, but practically strong." – Meuse

No, they're not 'almost identical in strength'. A real OTP, used properly, is literally unbreakable, since all plaintexts are equally probable. In contrast, a cryptographically secure PRNG has a much more limited state. The OP almost certainly actually wants a conventional cipher - OTPs are very rarely the correct answer - but simply saying "use a PRNG" is bad advice: you're just inventing your own cipher based on the PRNG, and you'd be far better off using an existing cipher. – Mariann

There is no such thing as a guaranteed "real OTP". Security is defined only relative to an attack model. For example, a hardware circuit to produce subverted bits can be built on an integrated circuit a few millimeters square. The most sophisticated hardware random number generator can be subverted by placing such a chip anywhere upstream of where the source of randomness is digitised, say in an output driver chip or even in the cable connecting the RNG to the computer. – Meuse

@RoadWarrior Yes there is. Don't confuse difficulty of implementation or verification with theoretical impossibility. And this is totally irrelevant: whether or not it's practical to achieve a 'true' OTP, using a PRNG is most assuredly not one. – Mariann

The fundamental security of an OTP is based on having a set of numbers where the sequence is completely unpredictable. Regardless of the source of the numbers (a RNG or a PRNG), the unpredictability of the sequence can be compromised by an attacker with sufficient access. My example above highlights subverting an RNG, there's an academic paper that shows a similar method of subverting CryptGenRandom. Hence my use of the word "guaranteed" - both a RNG (real OTP) and a PNRG (pseudo OTP) have no guarantee of producing an uncompromised sequence of random numbers. – Meuse

@RoadWarrior As you say, "completely unpredictable". Random numbers generated from, say, subatomic decay events are completely unpredictable. PRNG outputs are not - they're just impractical to predict, and they can only generate a small subset of the possible random sequences. Yes, you can come up with a way in which any system could be subverted, but an 'OTP' built on a PRNG is fundamentally not an OTP, no subversion required. Put simply: it's only an OTP if the input is entirely random. Subversion of systems is a separate issue from the theoretical strength and nature of the cipher. – Mariann

CSPRNG outputs are completely unpredictable - i.e. can be used as a real OTP - unless the attacker knows the start conditions. So if you make the assumption that your CSPRNG or RNG aren't compromised, both can be used as a real OTP. There may be a theoretical difference, but only if you assume a compromise. – Meuse

@RoadWarrior Argh! No, it's not an OTP! It's a stream cipher made from a PRNG! There is a real, practical difference: You can enumerate every possible PRNG state, and the number of those states are far, far fewer than the number of possible plaintexts. An OTP, in contrast, has as many keystreams as possible plaintexts, so any plaintext is a possible decryption. Please, please just read the Wikipedia article on OTPs (en.wikipedia.org/wiki/One_time_pad) - the entire of the cryptographic community is in disagreement with you. – Mariann

So with an RNG, it takes a billion years to enumerate every state, and with a CSPRNG it takes a million years. The difference is huge, but completely meaningless from any practical viewpoint. When somebody asks for a method to generate an OTP, I think it's perfectly acceptable to supply a method that produces the same practical characteristics as an OTP. – Meuse

@RoadWarrior So your argument is "really big numbers are basically the same"? Please, I beg you, don't ever implement anything in crypto. You're missing the fundamental point: It's only an OTP if all possible plaintexts are equally likely. If it's not, it's a stream cipher, and one which you've ad-hoc invented yourself - and thus almost certainly much less secure than a standard, well-tested cipher. – Mariann

So your argument is that there's a practical difference between a billion years and a million years? A quote from your OTP link: "However, if a modern so-called CSPRNG is used, it can form the basis for an empirically secure stream cipher." – Meuse

@RoadWarrior Of course there is - ask any geologist. It's not going to take a billion years to crack an OTP, though, because every single plaintext of the right length is a possible decoding, so you'd have no way to determine if you'd found the correct one. But my actual argument is that a) It's not an OTP unless all plaintexts are equally probable, and b) you shouldn't invent your own ciphers based on PRNGs, when there are perfectly suitable standard ciphers around. – Mariann