0

This question already has an answer here:

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.

marked as duplicate by Deer Hunter, TildalWave, Matthew, Rory Alsop Feb 9 '16 at 13:44

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • How high of security do you need (how high of risk are you assuming)? And how long does this OTP last? For example once securely transmitted does it store the string that after x minutes is considered void? – RB4 Feb 8 '16 at 23:42
  • A question asking how to implement cryptography would likely be better received at crypto.stackexchange.com. – cremefraiche Feb 9 '16 at 0:47
2

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.

  • 2
    The answer is in the last few paragraphs (starting from "So, for practical purposes..."). The rest is an unwanted lecture on a topic the OP is already familiar with. I'd suggest removing the first 3/4 of the text and keeping the actual answer; or moving the preamble to the bottom as an appendix. – lorenzog Feb 9 '16 at 8:56
  • @lorenzog Maybe, but I enjoyed a lot reading it. – vulkanino Feb 9 '16 at 10:58
  • I would consider this the answer I was looking for... I am not looking for a perfect OTP generator, just one that is "random enough" to actually be useful. As to the actual usage of one, it is more academic in nature (versus encrypting actual lines of documents). My reasoning was this (and I might not have been too clear): Using the randomness generated via RNGCryptoServiceProvider, and rotating the character set 1,000's of times per line, is this, in practical purposes, useful. I consider that it is. – JustWondering Feb 11 '16 at 0:09
1

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.

  • 1
    I mostly like this answer, except the part where /dev/urandom is asserted as an ok bar. If the random bits are coming from a process which stretches them, you have a stream cipher, not a OTP. (edit suggested, pending.) – Adam Shostack Feb 9 '16 at 0:47
  • 1
    Just had to point out, /dev/urandom is a pseudo random number generator. It is considered cryptographically secure because it is constantly reseeded from environmental noise, but there is a pseudo random number generator in its pipeline. – Lie Ryan Feb 9 '16 at 0:48
  • @AdamShostack Yeah, /dev/urandom is on the low side of the "true randomness" scale. It's probably good enough since it tries to keep its output restricted to how much true entropy it has, but that mechanism can fail. My favorite method is quantum randomness. – PyRulez Feb 9 '16 at 1:37
  • @AdamShostack (Computer can produce true randomness though. See en.wikipedia.org/wiki/…) – PyRulez Feb 9 '16 at 1:37
  • 1
    @pyrulez that a computer can have random effects does not lead to /dev/urandom is good enough for a OTP. Here's a thought experiment: how much can you draw from urandom for a OTP? Since urandom won't stop, when do you know you're getting remixed output? – Adam Shostack Feb 9 '16 at 1:58

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