3
$\begingroup$

One time pad required a truly random key. Why canwt it be a psudo-random key? For example, if the key distribution is that for each bit the probability to get 1 is 0.6 and the probability to get 0 is 0.4, and the eavesdropper knows it, how can he decrypt the message (assuming that the key length is at least as big as the message length)? Thank you

$\endgroup$
5
$\begingroup$

For an OTP to provide perfect secrecy it is required that the key stream is indeed purely random. A pure OTP is largely a theoretical construct because it is almost impossible to generate a key stream that is provably random. Any kind of information on the key stream may leak information on the plaintext, which means it is not perfectly secure. Practical OTP's that provide close to perfect secrecy on the other hand are, on the other hand, relatively common, see the comment from Paul below my answer.

Note that leaking information does not necessarily mean decryption; for instance if I encrypt the same message twice with a block cipher you won't know the input, but you can tell that the same message was encrypted because the resulting ciphertext blocks are identical. Any kind of information about the plaintext is enough for perfect secrecy to be broken.


Of course it is perfectly possible to use a pseudo random stream while maintaining practical security. Basically, this is what a stream cipher or block cipher in stream mode (e.g. CTR mode) does. However pseudo random streams indicate that there is some kind of mathematical relationship between the bits of the key stream. And this could be exploited by an attacker. The fact that such a relationship exists in itself is enough to break perfect secrecy.

There are obviously secure stream ciphers right now. We can however not prove them secure. So we cannot guarantee that they won't be broken in the future. Hence the perfect security premise doesn't hold, so they do not represent OTPs. Fortunately, if they are secure enough they don't need to.


It is possible to use a PRNG to create a practically secure key stream. PRNG and stream ciphers are closely related. Stream ciphers however have been especially designed to provide this functionality; they have advantages with regards to the API (treating the input key as key, having an explicit IV) and efficiency.

Beware that some random functions in programming applications may have implementations of PRNG's that are definitely not suitable for this kind of functionality. The shenanigans around "SHA1PRNG" in Java / Android should provide enough of a warning to anyone.


Way TL;DR: use a secure stream cipher

$\endgroup$
  • $\begingroup$ Theoretical - as in when it was extensively used by the CIA, NSA, Mossad, OSS, KGB, FSB, SOE, French intelligence, German (East & West) intelligence, Cuba, North Korea, numbers stations and every other security service in the known Universe over the last 100 years? Or theoretical as in when it's increasingly used for quantum key distribution in Europe, China, USA and geostationary orbit? $\endgroup$ – Paul Uszak Oct 31 '17 at 11:59
  • $\begingroup$ I'm looking at what a construct is, atoms are a construct? $\endgroup$ – daniel Oct 31 '17 at 12:35
  • 1
    $\begingroup$ This answer implies that no hardware random number generators exists. Or that all things are deterministic and that there is no free will. (and that we should just use TLS with appropriate sized keys of today) $\endgroup$ – daniel Oct 31 '17 at 12:57
  • $\begingroup$ @MaartenBodewes is no problem. My skeptical snake eyes are caused by you saying that a real OTP can't exist because its almost impossible to get a TRN, but then you must use a TRN in your alternative to seed the secure stream cipher. crypto.stackexchange.com/a/44253/6417 has some formal methods from possibly the NSA to make good TRNs $\endgroup$ – daniel Oct 31 '17 at 14:46
  • $\begingroup$ @daniel The provably secure TRN is only required to get a theoretical secure OTP. For a practical OTP or for generating a key for the stream cipher: just use any practically secure TRN - there are plenty of those around. $\endgroup$ – Maarten Bodewes Oct 31 '17 at 17:03
1
$\begingroup$

Most of it is by definition, use a key twice, or use a pseudo random number as the key, its no longer a one time pad (because that's not how its defined).

Why would an encryption technique be weaker than a one time pad if it used a pseudo random number?
Because with unlimited computational power (or my be with some other trickery) you could work out the seed for the PRNG.

Why would an encryption technique be weaker than a one time pad if it used a non uniformly distributed random number?
Because it would leak some information, that might not mean it is a piece of cake to break it (depending on the type of messages, the length, if they are repeated) but it does mean some other things. The cipher text of a plain text message would also not be uniformly distributed so it could then be identified (a steganography problem).
If I told you the plain text was going to be all ones or all zeros, and the key was biased like you described, it would only take about 5 bits of the cipher before I could guess with some confidence what the plain text was. I think this is related to Indistinguishability under chosen-plaintext attack

$\endgroup$
0
$\begingroup$

For these kind of intuitions, it typically helps to think about the extremes. What if you had a key that was always all-ones, with probability 1? What if you improve it a little bit, and use a key that, for every bit, has a 0.01 chance of it being a zero? What if it's 0.1?

Given the above, it appears to be benefitial to use a key that gets closer to uniform - the closer you get, the more it adds 'noise' to the plaintext.

$\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.