7
$\begingroup$

If I want to generate a few one-time pads, is it OK to just read required number of bytes from /dev/urandom without weakening information-theoretical security?

$\endgroup$
9
$\begingroup$

/dev/urandom is only computationally secure, so you won't get information-theoretical security for your OTP if you draw it from /dev/urandom. If you're happy with computational security, you might as well use a stream cipher instead of a OTP. Stream ciphers are much easier to use securely than OTPs.

On Linux /dev/random aims for information-theoretical security, but in exchange you typically get pretty bad performance. How well it achieves that goal is practice is unclear, since it relies on entropy estimators for its entropy sources, and that's error prone. (I think on BSD /dev/random is equivalent to /dev/urandom because they don't care about information-theoretical security)

$\endgroup$
  • $\begingroup$ One additional thing to note is that if the CPU has RDRAND/RDSEED, Linux /dev/urandom should get enough hardware randomness and be even information theoretically secure if the implementation is good. $\endgroup$ – otus May 3 '16 at 11:29
  • $\begingroup$ And what are the options on BSD? $\endgroup$ – assp1r1n3 May 3 '16 at 11:29
  • $\begingroup$ @otusRDRAND is only computationally secure. Only RDSEED aims of information theoretical security. $\endgroup$ – CodesInChaos May 3 '16 at 11:31
  • $\begingroup$ @CodesInChaos, true, RDSEED if you want to be absolutely sure. (In practice /dev/urandom does not operate fast enough that RDRAND should resort to entropy stretching.) $\endgroup$ – otus May 3 '16 at 11:34
  • $\begingroup$ @assp1r1n3 Buy a hardware RNG. Or RDSEED from your application, if your CPU supports that instruction (AFAIK few do). $\endgroup$ – CodesInChaos May 3 '16 at 11:50
3
$\begingroup$

You're never going to release this, right?

If so, it doesn't matter. Use a pseudorandom stream from /dev/urandom and "pretend" that it's truly random for the sake of learning about the concepts involved.

$\endgroup$
3
$\begingroup$

If you want the encryption to be information-theoretically secure, then you need an information-theoretically secure RNG. And therein lies the problem—how do you establish that a given RNG is information-theoretically secure? Science may say that there are some types of events that are physically unpredictable, but that by itself is insufficient to get a secure RNG. For example, the attacker might still be able to eavesdrop on your RNG's output, in which case you get no security from it.

Basically, when you shoot for "perfect" information-theoretic security it's not enough to point at a candidate physical process, you still have to address a bunch of difficult issues like:

  • The RNG doesn't leak its output to parties other than its user;
  • The RNG doesn't allow its output to be influenced by malicious parties.
  • The RNG's randomness extractor or "conditioning" mechanism truly produces full-entropy uniform output;
  • The RNG's measurements of the noise source don't introduce any biases that the RNG doesn't account for;
  • The entropy rate assumed for the noise source isn't an overestimate;
  • The RNG can produce entropy at a sufficient bit rate to support your application;
  • The RNG doesn't have silent failure modes where it produces low-entropy outputs that go undetected;
  • etc.

The security proof for one-time pads gets to handwave all of these issues away by just assuming that you have a truly secret and unlimited source of truly random keys at little or no cost. So that's another set of reasons why information-theoretic security is impractical, beyond the better-known key length, key exchange and key reuse issues.

$\endgroup$
  • $\begingroup$ Your hand waving criticism is unfounded. The OP is only talking of a 'few' one time pads. You do not need 'unlimited' random numbers. With the prevalence of Rasberries, Arduinos and PICs, megabytes of true random numbers are easily available following a few simple on line designs. And an Arduino might only cost you £2. Further, understand that the proven use case for OTPs is for simple messages of 100's of characters, not hiding a 2 hr porn film. $\endgroup$ – Paul Uszak Oct 13 '16 at 21:23
1
$\begingroup$

Short answer: @Stephan Touset's answer is of course correct: if this is just for your learning, then it doesn't matter, use whatever's convenient. Anything that's not this should be fine:

enter image description here

*Mandatory XKCD


The longer answer is that philosophers like to debate whether "truly random", as you put it, actually exists, and if it does, does it apply to computers?. Fortunately for us, "randomness" isn't actually relevant to cryptography; what matters is "unpredictableness". This may sound like I'm nit-picking, but it's an important difference. The XKCD example above is in fact 100% random since it was chosen by a fair dice roll, unfortunately when we say "random" we usually mean "unpredictable".

The question you should be asking is: "how unpredictable is /dev/random vs random.org?". The answer is that in order to predict your /dev/random output, an attacker basically has to have kernel-level access to your machine, while predicting your random.org output simply requires an attacker to be able to view your network traffic (or the sever-side logs at random.org).


The much longer answer is that /dev/random is widely considered "good enough" for commercial cryptographic use provided that the OS and hardware are configured properly. (I'll assume Linux here, but the arguments for /dev/random are similar for other *nixes).

Check out the list of commercial cryptographic modules that the US govervment has given FIPS 140-2 certification to. Do a ctrl+f for "linux" ... 477 hits as of writing, (almost) all of those will be build on top of /dev/random.

Now, that doesn't mean that /dev/random is automatically good, like any RNG, it's only as good as its seed (or in this case, entropy pool). So to get FIPS certification for a cypto module using /dev/random, you have to demonstrate that the linux kernel has sufficiently unpredictable entropy sources, timing of spinning magnetic disks and timing of network packets will do if you can prove that there is a high enough volume of network activity from multiple different sources. You also have to prove that your crypto module will never ask for randomness early in the boot sequence before the kernel has had a chance to gather a properly unpredictable seed. And a few other things.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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