What is a good way to generate a one time pad, and is this a good way? [duplicate]

Question

Is there a good/better/best way to generate a one time pad? I would like to only utilize about 40 characters (a-z, 0-9, .,!-).

What I have come up with is perhaps not the BEST way, but seems to fill my needs. It essentially works this way:

Initialize:

1) Generate a random seed using the MS RNGCryptoServiceProvider service

2) Populate an array with a base of all of the characters I use

3) Perform a "switch" based on the random number of the 1st character and the random number (base 40) character in the array after this character

4) Pause a random amount of time determined by yet another random seed call (1-5ms)

5) Get a new seed

6) Perform a "switch" based on the random number of the 2nd character and the random number (base 40) character in the array after this character

7) Continue until all characters are swapped, generating a new random seed at every iteration, switch, etc.

8) Repeat the process 5,000 (adjustable) times

Generate lines:

9) Repeat steps 3-8 10,000 (adjustable) times

10) Write the line to a secure location (either on-screen, encrypted thumb drive, etc.)

11) Using the previous array-based line, repeat steps 3-8 for however many times/lines I want.

This has the residency of reusing old/new seeding (i.e. seeding upon itself) for the switches. I know there are holes in this, but for the actual generation aspect, I figure I can define how many loops per cycle can be run (if a user want to go crazy, they can do 100-millions of switches per line, and can adjust the starting point to between 100-millions). More seems better, but to what end is up to the user.

I will put this out there - my machine runs extremely fast with the Intel CPRNG on the chip. I KNOW this is/can be a security hazard, but I am wondering, just for the generation algorithm, does this seem to be a good way to generate OTP pads? As there is a whole host of other security problems that can be either added to the list or removed judiciously, I am just asking - how much do you need to make an OTP pad, and would the above work?

Thanks in advance, and I will correct anything anyone has questions about.

Answer 1

A one-time pad is an encryption mechanism consisting of combining a stream of key material with the data to encrypt, using a reversible operation; this combination can be very simple, and even doable by hand (without a computer), and still retain security as long as the key material (the "pad") is as long as the data to encrypt, and is never reused (that's the "one-time" part).

Security is relative to how much the key material is unpredictable to attackers. The mathematical beauty of the OTP is that there is no upper bound for that: you can reach information-theoretic security, i.e. achieve perfect protection against computationally unbounded adversaries. Well, you might. Things can become a bit unclear once we begin using infinities.

"True" randomness can be defined as that which cannot be predicted by any attacker. It is unclear whether true randomness can exist at all:

• Right now, physicists work under some assumptions, one of which being that there is an unavoidable level of incertitude in where things are and how fast they go. This is Heisenberg's uncertainty principle. While this interpretation of the real world has been very successful for the last century, and allowed many stupendous technological advances (including the computer you are using to read these lines), it still is a theory in the strong sense of the term: it is "true" as long as it works well at predicting behaviour of physical systems. Whether Heisenberg's principle is fundamental, or a mere illusion due to our imperfect analysis of some underlying mechanism, remains to be seen.

  In a sense, Heisenberg's principle guarantees us existence of randomness only through the usual Argument by Authority: many very smart people with blindingly white lab coats say so. But not all were convinced. Famously, Albert Einstein, one of the smartest physicists to date, was unconvinced, and expressed so in his famous quote: "God does not play dice with the universe". Of course, we can retort that for all his smartness, Albert has been dead for more than 60 years, but that's a rather feeble argument.

• Maybe more importantly, in the case of OTP, the supposed randomness has been measured, since it became the very macroscopic object that is the OTP. What matters for security is how much that pad is not known to the attacker, but since the pad has been used, it has existed in the tangible, human-sized world, e.g. as a piece of paper with printed ink. This is bound to leave some traces. For instance, if you printed it with a common printer, then remains of the data may linger in the printer memory. If you wrote it down with a ball pen, the pressure of the pen may have let a readable depression in the paper sheet below the one you were writing on. If you burned the paper down in the chimney, the carbonated remains might still leak some information (I saw that one in a MacGyver episode, but it turns out to be a real thing as well).

  Thus, in a quest to True Randomness, we must not only defeat Albert Einstein, but also Sherlock Holmes. Physics may come at our rescue, this time the second law of thermodynamics, which can be interpreted as the assertion that information really gets lost over time. Thus, physicist are ready to agree that if we got an unpredictable piece of data at some point, then we may hope to completely suppress it, so that it won't be uncovered by an inquisitive adversary. Possibly.

• Even if we obtain really random events, in the sense explained above, these events may still be biased. In any practical setup for OTP, the key stream must be uniformly random, so there is a need for some unbiasing. Unfortunately, generic unbiasing mechanisms (namely, hash functions) are "normal" cryptographic objects, which live in the computationally bounded world of security. We do not know how to make a hash function that would still fulfil its unbiasing role even against a computationally unbounded attacker.

  (We can make perfect unbiasing if we know the exact distribution of the source random data from which we want to remove any bias. But since we do not even know whether random sources really exist, pinpointing that distribution could be hard.)

Fortunately, there is no practical need to reach absolute unpredictability. This is because computationally unbounded attackers are mythological (in the true sense of the term: we make stories about them, but we have never undeniably met one). The points above may seem excessive in their nitpicking, but that's nothing with regards to how utterly unrealistic an unbounded attacker is. Infinity is kind of big; remember that.

So, for practical purposes, you just need randomness which is unpredictable by actual attackers, not mythical ones. This means that a cryptographically strong PRNG will be sufficient. It won't deter God, if He wants to spy on you. But He already can (because omniscience), so what would be the point anyway ? You create an RNGCryptoServiceProvider instance -- so, just use it. Once it is created, it will happily spew megabytes of data at a high rate. There is no need to add random delays or any other ritual dancing step.

Programming is the art of not goofing up, and yet there is plenty of room for that. For instance, a CSPRNG like RNGCryptoServiceProvider, or /dev/urandom on Linux systems, produces bytes, which are values in the 0..255 range. Extracting random characters out of these bytes can be done correctly, or poorly. If you have an alphabet of 40 signs, then you could imagine that you just need an Euclidian division of each byte value by 40 and keep the remainder (the '%' operator in C#, 'mod' in VB.NET). While this would produce only values between 0 and 39, these would be biased, even if the source random bytes are not. This is because 256 is not a multiple of 40; thus, remainders 0 to 35 would be somewhat more probable than remainders 36 to 39.

The correct way to generate random values in the 0..39 range from source bytes in the 0..255 range is to use a rejection method. When you want to get a new random integer in the 0..39 range:

1. Obtain the next random byte x.
2. If x < 240, then return x mod 40.
3. Otherwise, loop to 1.

In other words, you must discard some possible input values, and get additional bytes when such a value occurs.

As a final note, one-time pads are grossly impractical and cumbersome. They were used in the pre-computer era because there was nothing better at that time. But now they are mostly an historical curiosity, and a mathematical concept for reasoning about infinities.

Answer 2

Sorry, but no. The OTP needs really really random numbers. Like, /dev/random random or better (see this). If your random number generator has "pseudo" anywhere in its name, OTP won't work.

If you want to use pseudo-random numbers to transmit a message, lookup Block cipher.

The thing to keep in mind with OTP is that if a stream is even partially truly random, that isn't good enough. If you have 100 bytes of true entropy, but you algorithm generates a 150 byte key, that attacker get 50 bytes of your info (the other 100 bytes (or more) was probably redundancies in English or whatever you where encoding, which they can fill in themselves).

OTP is practical in limited circumstances (when it does work though, it is beautiful and awesome). For an idea for an easy OTP is to break, the Russians used OTP, but didn't have quite random enough keys, and so the U.S. was able to break it. This was before the internet.

Deer hunter's comment is useful.