7 ms·

Are there any methods of generating randomness on common platforms — Linux (raw or VM), Windows, MacOS — that are suitable for use as a cryptographic one-time p

Are there any methods of generating randomness on common platforms — Linux (raw or VM), Windows, MacOS — that are suitable for use as a cryptographic one-time pad? The definition of this library function seems to suggest that it’s suitable: > librandombytes aims for the following stringent randomness goal: no feasible computation will ever be able to tell the difference between the output bytes and true randomness (independent uniformly distributed random bytes). However my understanding is that PRNGs are not a suitable source of randomness for one time pads; that this would reduce OTP encryption to being something like an ad hoc stream cipher. So some implementations that might look random wouldn’t actually provide a suitable bitstream for this purpose: the bits in the output would be correlated, if in a complex, cryptographically obscure way. (But bits in a one-find pad should all be entirely random and uncorrelated.) Is that accurate? Do modern PCs have an efficient way to produce meaningful amounts of true stochastic random data suitable for use with OTP encryption (such as the RDRAND instruction)? What are some good abstractions for producing a stream of random data suitable for use with OTP cryptography? Edit: this is a question for the sake of curiosity. I realize that practical systems have many threat vectors and that OTP is not a panacea, or even necessarily an improvement.

tptacek 4y ago
"OTP cryptography" is for the most part not a thing. If you were running a spy ring and literally giving each of your agents a paper pad with numbers on them, you could print them from `getrandom` output; the `getrandom` bytes wouldn't be how that system was attacked.
- e12e 4y ago
  Iirc NATO used a one time pad codebook for ship communication - but I suspect these days it would only be a fallback in case there's a need to use open radio or similar for signaling?
- jcrites 4y ago
  This is an intellectual question for curiosity’s sake. I realize that an OTP encryption system will not be a practical improvement for communication compared to e.g. the Signal protocol, which is easier to use and provides a number of other advantageous properties; or something like TLS. (If you could securely exchange one time pad material, then you could also more easily exchange asymmetric keys) I realize that actual systems have a large number of threat vectors, and that the encryption protocol itself is unlikely to be the primary risk. Nevertheless, I’m curious: if one decides to implement digital encryption using one time pads, what is the most practical source of suitable randomness? And have communication protocols been designed for OTP, or would your best bet be to layer it on top of something like Signal or TLS? It seems that you probably need to exchange at least some metadata along with each message describing, e.g., the message size and starting offset into the pad material - metadata that you’d want to protect with encryption, and I don’t see a very straightforward way to protect it using OTP. On reflection, this probably only has relevance for government or military communications that might need to remain secure for longer than 50 years. Perhaps the use-case is something like an aircraft carrier, submarine, or other large, critical vehicle or facility, that receives OTP material by delivery of a hard drive protected by considerable physical security. Critical communication from these vehicles/infrastructure would remain protected against future cryptographic attacks - e.g., if an algorithmic vulnerability is discovered, or there’s a breakthrough in quantum or traditional computing that renders today’s encryption vulnerable within the next few decades — the OTP-protected message content remains protected. (Even if intercepted, recorded, and attacked decades later) Yes, I agree that the practical applications are limited… The questions are an exercise for curiosity’s sake: if you’re going to employ OTP encryption, then …
  - tptacek 4y ago
    To achieve the "theoretical" unbreakability that keeps one time pads perennially in the discussion, you need a true random source of bits: a (sufficiently bias-free) measurable natural process to sample. That's what makes OTPs unbreakable: there's no structure anywhere to attack. To achieve practical unbreakability, you just need your bits to be indistinguishable from random. You can take a relatively small number of unguessable bits and then run them through the Blake2-based LRNG algorithm to spool out a practically unlimited number of "random" bits. Theoretically you can attack Blake2 and the LRNG system; there could be some vulnerability there. In practice, this would be a deeply shitty setting to try to cryptanalyze anything, even if Blake2 was broken, which it isn't. If you are going to go through the trouble of literally distributing physical pads to all the counterparties, though, you might as well just generate true random numbers.
    - Vecr 4y ago
      The problem with true random is that you might screw up your avalanche diode circuit (or whatever) in a way that makes it random, but not uniformly distributed. It might also pick up EM from somewhere and not "really" be random all the way. By the time you add all the whitening and that sort of thing to make those problems go away I'm not sure how the information theory proofs hold up. Probably what you would want to do is keep the physical random number generator in a fine-mesh Faraday cage in a controlled environment, and run statistical tests for a while before generating your pads. The rng-tools package on Linux has a test tool. Make sure you disconnect the test wires before generating the pads though!
      - tptacek 4y ago
        I don't think you can verify the safety of a one-time pad with statistical tests.
      - josephg 4y ago
        > By the time you add all the whitening and that sort of thing to make those problems go away I'm not sure how the information theory proofs hold up. Why wouldn't the information theory proofs hold up? Fun puzzle: Suppose I give you coin you can flip with some bias (weight). Maybe 75% of coin flips are heads. Maybe its 65%. You don't know. You want to generate a sequence of bits with uniform randomness (exactly 50%). Without first sampling the coin & calculating the bias, how do you generate the uniform sequence of bits? The answer to that puzzle would probably work fine for your theoretical one time pad. Also, in practice I suspect most of the obvious ways your random noise circuit could be broken could be detected using statistical methods. You can't use math to prove a random number generator is truly random. But you can certainly detect a lot of common failure modes of "random" number sources.
loeg 4y ago
> this would reduce OTP encryption to being something like an ad hoc stream cipher. What do you think a stream cipher is? CTR-mode stream ciphers are just a PRF stream (which a CSPRNG provides) XOR'd with your data, and maybe concatenated with a MAC. If your PRNG generates the same output twice, your OTP is hosed. Your CTR-mode is also hosed. So, a CSPRNG must not produce the same output twice. Also, what Thomas said. OTP is not a thing.
- lxgr 4y ago
  > CTR-mode stream ciphers are just a PRF stream Not exactly a pseudorandom function, but a pseudorandom permutation. This matters as soon as you start approaching the birthday bound: https://crypto.stackexchange.com/questions/59738/what-are-the-risks-of-using-ctr-mode-with-64-bit-blocks https://crypto.stackexchange.com/questions/59738/what-are-th...
lxgr 4y ago
> the bits in the output would be correlated, if in a complex, cryptographically obscure way. Yes – but by definition, no feasible computation would be able to detect the correlation; and if nobody can detect that it's there, it does not matter.
GoblinSlayer 4y ago
Secrecy is temporary, you only need encryption algorithm to protect your data until its expiration date. For AES-128, the key can be recovered with a computational complexity of 2^126.1 using the biclique attack. If you can do such computation fast enough, you will be able to read much secret data.
gnramires 4y ago
> However my understanding is that PRNGs are not a suitable source of randomness for one time pads A PRNG (Pseudorandom Number Generator) can have varying levels of (1) Quality, and (2) Adversarial resistance (both are closely related of course). Quality generally can be estimated by quantities like period, correlations and some other measures; there are tools that can give useful measures of quality. Adversarial resistance needs serious cryptanalysis (not just passing randomness tests), preferably relying on well known constructions (like hash functions constructions). When a PRNG is made with (2) in mind, it's usually called a CSPRNG (Cryptographically Secure PRNG). DJB here is presenting a CSPRNG: > This makes the randombytes() output suitable for use in applications ranging from simulations to cryptography Daniel is a well known cryptographer and this seems to reuse linux kernel and OpenSSL primitives, so I assume it's fine here to use for any cryptographic applications. Note that one-time pad is a very inefficient cryptography. Generally in cryptography you don't want to roll your own algorithm except for study/research purposes (the famous adage "Don't roll your own crypto") -- just use something like OpenSSL or libsodium.

tptacek 4y ago

"OTP cryptography" is for the most part not a thing. If you were running a spy ring and literally giving each of your agents a paper pad with numbers on them, you could print them from `getrandom` output; the `getrandom` bytes wouldn't be how that system was attacked.

e12e 4y ago
Iirc NATO used a one time pad codebook for ship communication - but I suspect these days it would only be a fallback in case there's a need to use open radio or similar for signaling?
jcrites 4y ago
This is an intellectual question for curiosity’s sake. I realize that an OTP encryption system will not be a practical improvement for communication compared to e.g. the Signal protocol, which is easier to use and provides a number of other advantageous properties; or something like TLS. (If you could securely exchange one time pad material, then you could also more easily exchange asymmetric keys) I realize that actual systems have a large number of threat vectors, and that the encryption protocol itself is unlikely to be the primary risk. Nevertheless, I’m curious: if one decides to implement digital encryption using one time pads, what is the most practical source of suitable randomness? And have communication protocols been designed for OTP, or would your best bet be to layer it on top of something like Signal or TLS? It seems that you probably need to exchange at least some metadata along with each message describing, e.g., the message size and starting offset into the pad material - metadata that you’d want to protect with encryption, and I don’t see a very straightforward way to protect it using OTP. On reflection, this probably only has relevance for government or military communications that might need to remain secure for longer than 50 years. Perhaps the use-case is something like an aircraft carrier, submarine, or other large, critical vehicle or facility, that receives OTP material by delivery of a hard drive protected by considerable physical security. Critical communication from these vehicles/infrastructure would remain protected against future cryptographic attacks - e.g., if an algorithmic vulnerability is discovered, or there’s a breakthrough in quantum or traditional computing that renders today’s encryption vulnerable within the next few decades — the OTP-protected message content remains protected. (Even if intercepted, recorded, and attacked decades later) Yes, I agree that the practical applications are limited… The questions are an exercise for curiosity’s sake: if you’re going to employ OTP encryption, then …
- tptacek 4y ago
  To achieve the "theoretical" unbreakability that keeps one time pads perennially in the discussion, you need a true random source of bits: a (sufficiently bias-free) measurable natural process to sample. That's what makes OTPs unbreakable: there's no structure anywhere to attack. To achieve practical unbreakability, you just need your bits to be indistinguishable from random. You can take a relatively small number of unguessable bits and then run them through the Blake2-based LRNG algorithm to spool out a practically unlimited number of "random" bits. Theoretically you can attack Blake2 and the LRNG system; there could be some vulnerability there. In practice, this would be a deeply shitty setting to try to cryptanalyze anything, even if Blake2 was broken, which it isn't. If you are going to go through the trouble of literally distributing physical pads to all the counterparties, though, you might as well just generate true random numbers.
  - Vecr 4y ago
    The problem with true random is that you might screw up your avalanche diode circuit (or whatever) in a way that makes it random, but not uniformly distributed. It might also pick up EM from somewhere and not "really" be random all the way. By the time you add all the whitening and that sort of thing to make those problems go away I'm not sure how the information theory proofs hold up. Probably what you would want to do is keep the physical random number generator in a fine-mesh Faraday cage in a controlled environment, and run statistical tests for a while before generating your pads. The rng-tools package on Linux has a test tool. Make sure you disconnect the test wires before generating the pads though!
    - tptacek 4y ago
      I don't think you can verify the safety of a one-time pad with statistical tests.
    - josephg 4y ago
      > By the time you add all the whitening and that sort of thing to make those problems go away I'm not sure how the information theory proofs hold up. Why wouldn't the information theory proofs hold up? Fun puzzle: Suppose I give you coin you can flip with some bias (weight). Maybe 75% of coin flips are heads. Maybe its 65%. You don't know. You want to generate a sequence of bits with uniform randomness (exactly 50%). Without first sampling the coin & calculating the bias, how do you generate the uniform sequence of bits? The answer to that puzzle would probably work fine for your theoretical one time pad. Also, in practice I suspect most of the obvious ways your random noise circuit could be broken could be detected using statistical methods. You can't use math to prove a random number generator is truly random. But you can certainly detect a lot of common failure modes of "random" number sources.

loeg 4y ago

> this would reduce OTP encryption to being something like an ad hoc stream cipher. What do you think a stream cipher is? CTR-mode stream ciphers are just a PRF stream (which a CSPRNG provides) XOR'd with your data, and maybe concatenated with a MAC. If your PRNG generates the same output twice, your OTP is hosed. Your CTR-mode is also hosed. So, a CSPRNG must not produce the same output twice. Also, what Thomas said. OTP is not a thing.

lxgr 4y ago
> CTR-mode stream ciphers are just a PRF stream Not exactly a pseudorandom function, but a pseudorandom permutation. This matters as soon as you start approaching the birthday bound: https://crypto.stackexchange.com/questions/59738/what-are-the-risks-of-using-ctr-mode-with-64-bit-blocks https://crypto.stackexchange.com/questions/59738/what-are-th...

lxgr 4y ago

> the bits in the output would be correlated, if in a complex, cryptographically obscure way. Yes – but by definition, no feasible computation would be able to detect the correlation; and if nobody can detect that it's there, it does not matter.

GoblinSlayer 4y ago

Secrecy is temporary, you only need encryption algorithm to protect your data until its expiration date. For AES-128, the key can be recovered with a computational complexity of 2^126.1 using the biclique attack. If you can do such computation fast enough, you will be able to read much secret data.

gnramires 4y ago

> However my understanding is that PRNGs are not a suitable source of randomness for one time pads A PRNG (Pseudorandom Number Generator) can have varying levels of (1) Quality, and (2) Adversarial resistance (both are closely related of course). Quality generally can be estimated by quantities like period, correlations and some other measures; there are tools that can give useful measures of quality. Adversarial resistance needs serious cryptanalysis (not just passing randomness tests), preferably relying on well known constructions (like hash functions constructions). When a PRNG is made with (2) in mind, it's usually called a CSPRNG (Cryptographically Secure PRNG). DJB here is presenting a CSPRNG: > This makes the randombytes() output suitable for use in applications ranging from simulations to cryptography Daniel is a well known cryptographer and this seems to reuse linux kernel and OpenSSL primitives, so I assume it's fine here to use for any cryptographic applications. Note that one-time pad is a very inefficient cryptography. Generally in cryptography you don't want to roll your own algorithm except for study/research purposes (the famous adage "Don't roll your own crypto") -- just use something like OpenSSL or libsodium.