1
$\begingroup$

What are the security vulnerabilities of the XOR operator in the following scenario:

  • The Key, The Cyphertext and the Plaintext are the same size in bits.
  • The Key is only used once and it's secret
  • The Plaintext is only used once and it's secret
  • Hence the Cyphertext is only used once, but it's public
  • Only the Cyphertext, and hence the size of the key is known to the adversary

However:

  • The Key was generated by a pseudorandom number generator
  • The Plaintext (which is a private key to something else) was also generated by a pseudorandom number generator

Therefore neither the key nor the plaintext is fully random, vulnerable to frequency attacks.




So I don't care about practical issues, like the difficulty of key sharing. I only care about security issues.

We can identify that this setup can be vulnerable to frequency analysis and such described here:


  • But are there other vulnerabilities besides the pseudo-random nature of the key and the plaintext?
  • If both the key and the plaintext were truly random, would this provide perfect secrecy?
$\endgroup$
  • 1
    $\begingroup$ The output of a PRF is most certainly not vulnerable to frequency analysis - the linked answer that "describes" it does not mention anything about PRFs or frequency analysis. $\endgroup$ – Ella Rose Jun 16 '17 at 15:30
  • $\begingroup$ If you have C = P xor K, and the key is as long as the plaintext, then what you have is a one-time pad. With all the associated theoretical advantages and practical issues. Like distributing the key and making sure you only use it once. $\endgroup$ – ilkkachu Jun 16 '17 at 15:39
1
$\begingroup$

What you basically have is a binary additive stream cipher, using your pseudorandom number generator as the keystream generator. Used properly (i.e. in such a way that the same keystream is never used twice), the security of such a cipher depends entirely on the strength of the pseudorandom number generator.

If the output of the generator cannot be practically distinguished from a stream of truly random bits without knowing the seed of the generator, and if the seed itself is chosen randomly from a large enough space to make brute force testing of all possible seeds impractical, then such a cipher is indeed secure (in the sense of protecting the confidentiality of the plaintext; note that such XOR-based ciphers are generally malleable, and thus vulnerable to active tampering attacks).

Unfortunately, most pseudorandom number generators are not designed to remain indistinguishable from random even to a deliberate attacker; a typical PRNG's output only looks random to a casual observer, but can be easily distinguished from random if you know how the generator works. Algorithms that are designed to resist such distinguishing attempts are generally described as CSPRNGs, or simply as stream ciphers.

If the keystream were truly random, then what you have would be a one-time pad, and would therefore indeed provide perfect secrecy (but still be malleable). The randomness of the plaintext does not matter here — the whole point of perfect secrecy (and its computational variant, semantic security) is that a cipher with perfect secrecy will reveal no information about the plaintext whatsoever (except for its length), no matter what the plaintext may be or how it's chosen.

That said, if you intend to use the plaintext as the key to another cipher, then it certainly should be generated in such a way as to make it impractical to guess (even using massive amounts of computing power to test possible guesses). Otherwise an attacker could just ignore your XOR stream cipher / one-time pad entirely, and simply try to guess the key to the other cipher directly.

$\endgroup$
  • $\begingroup$ What does malleability mean in the context of a one-time pad? If I said in the OP that the cyphertext and the key are only used ONCE, does malleability matter then? $\endgroup$ – cryptonoob400 Jun 17 '17 at 13:52
  • 1
    $\begingroup$ @cryptonoob400: Malleability means that a middle-man attacker who intercepts the ciphertext in transit can modify it in ways that cannot be detected by the recipient, and which modify the plaintext in some (more or less predictable) way. Specifically, with an XOR cipher, flipping any bit of the ciphertext will flip the corresponding bit of the plaintext. This attack works regardless of how the keystream is generated, even if it's a truly random one-time pad. $\endgroup$ – Ilmari Karonen Jun 17 '17 at 13:56
  • $\begingroup$ Yes but why should I care about that, it does not reveal any information about the plaintext, and this sounds just like a practical problem of communication , not a security problem. $\endgroup$ – cryptonoob400 Jun 17 '17 at 15:11
  • $\begingroup$ It depends. If the attacker could, say, replace your encrypted key with their own, then that would be a problem, wouldn't you think? (With just the XOR bit-flip attack, that's not actually possible in general, unless the attacker already knows your encrypted key anyway. Unless, of course, the message carrying the key also contains enough other data that the attacker does know that they can, say, bit-flip a message like "Please use this new key, which belongs to me, cryptonoob400: ABCDEFGHIJKLMNOP" into "Please use the key AAAAAAAAAAAAAAAA and ignore this garbage: ABCDEFGHIJKLMNOP".) $\endgroup$ – Ilmari Karonen Jun 17 '17 at 17:07
0
$\begingroup$

I think this scenario described has perfect secrecy (but not semantic security), provided the PRNGs are cryptographically secure and generate high-enough entropy keys that are not feasibly predictable, and the message is also a random number (private key) with the same entropy/security as the key.

Example: If the private key is k-bits long in terms of character length, and the message is k-bits long (both with k-bits of entropy/security), resulting in a ciphertext that also is k-bits long (where no padding scheme was used), then the potential "ciphertext space" would be ${2^n}$ where ${k(2)=n}$, and the ciphertext space is equal to ${2^k * 2^k = 2^n}$, where the potential keyspace ${2^k}$ is the square root of the ciphertext space ${2^n}$ (and similarly the message space is ${2^k}$ which is the square root of the ciphertext space).

Conclusion: This means that that there at least an additional ${2^k-1}$ possible ciphertexts identical to yours that could exist but have different keys and messages as inputs into the XOR calculation where ${AnotherMessage \oplus AnotherKey = SameCiphertext}$.

On that basis, an attacker could arrive at one of those matches but not be sure which of them is the correct pairing from ${2^k}$ of them (aside from scenarios such as accessing a cryptocurrency wallet where a decryption oracle (blockchain) uses a public generator point (like a public plaintext value) that can verify the guessed private key produces the desired public key (as unique coordinates on an elliptic curve) where there could be a balance in the address which likely would indicate the correct key was found). Therefore, a stronger security scheme than perfect secrecy in this context would be indistinguishability under adaptive chosen ciphertext attack (IND-CCA2), I believe.

P.S. If the message itself is not communication in any natural language and just a random number (i.e. private key as you stated) then it wouldn't be subject to frequency analysis or malleable, assuming the PRNGs were cryptographically-secure in terms of unpredictability and if sufficient entropy was used to make a brute force search unfeasible.

$\endgroup$
  • $\begingroup$ This system doesn't have perfect secrecy unless the ‘pseudorandom generator’ is in fact a permutation, which is not really a useful pseudorandom generator since usually the premise of a PRG is that its output is larger than its input. If it's not a permutation, then there are some pads it will not generate, and consequently some pads that have zero probability. $\endgroup$ – Squeamish Ossifrage Jun 18 at 23:45

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.