Score:13

What is wrong with XOR encryption with secure PRNG?

in flag

Suppose I want to encrypt a message with a password.

Couldn't I just XOR the bytes with bytes from a cryptographically secure pseudorandom number generator (CSPRNG) with seed being the password, or a hash of it? I can't see anything wrong with this.

Or are CSPRNG so slow that more complex encryption schemes are necessary?

us flag
Similar question here: https://crypto.stackexchange.com/questions/35809/whats-wrong-with-xor-encryption-with-hash-and-an-iterated-salt?rq=1
fraxinus avatar
sa flag
You almost invented the CTR (Counter) mode of cipher operation
Score:22
in flag

The bytes that you XOR with the message to get the ciphertext are called the key stream. It is secure to create a key stream using a CSPRNG yes, a cryptographically secure pseudo-random number generator and a static seed.

However, there are practical issues if you use your system's CSPRNG:

  • it may decide to (re-)seed occasionally;
  • the algorithm may change over time or between systems;
  • the way random bytes are extracted may change (it may e.g. decide to align on words).

So you have to be sure that the CSPRNG operation is cast in stone before you'd use it to encrypt something. In the worst case random data is included to seed your cipher in which case the data is effectively lost. This has happened before when the "SHA1PRNG" of Sun was replaced first by another algorithm and then by OpenSSL random data on Android.

Theoretically speaking, a stream cipher - or block cipher in a stream mode - are both CSPRNG where there is one seed (the combination of key and IV/nonce), a specific algorithm and a prescribed way of retrieving a key stream. So generally the boring answer is to use AES-CTR to create the key stream, and to use AES-GCM - which uses AES-CTR internally - if you require message authentication as well. On systems without hardware acceleration a stream cipher such as ChaCha20 could be used instead.

Slightly less boring, you can also build a stream cipher out of a hash function by using counter mode. Preferably you'd use a MAC construction such as HMAC for that. Actually, most CSPRNG's that systems provide are not much more than that - but as stated, they are usually designed to provide random data, not deterministic data. And yes, generally these algorithms are slower than a dedicated stream cipher or hardware accelerated block cipher - they are more complex rather than less complex.

in flag
I'd consider a PRNG deterministic by definition. I.e. “your system's CSPRNG” is not in fact a CSPRNG at all, but rather a random source augmented with a CSPRNG.
Maarten Bodewes avatar
in flag
Or a CSPRNG augmented with a random source, yes. Most often you get them bundled together - which is fine as long as you just use them to get random(-ized) numbers from a limited source of entropy.
Score:16
in flag

Yes, you can; it's called a stream cipher. It can be viewed as an approximation of a one-time pad, where you don't have enough entropy available to generate an OTP key (which must be the same length as the plaintext), but do have enough to seed a PRNG.

Generic vulnerabilities of stream ciphers, independent of the choice of keystream-generation algorithm, are:

  • Reused key attack. If you have access to two encrypted messages, you can XOR those two messages to get the XOR of the two plaintext messages. This answer nicely illustrates how this can be insecure. To avoid this attack, never reuse your passwords, and make sure your key-generating hash function has adequate collision resistance.
  • Bit-flipping attack. Suppose that an attacker intercepts one of your encrypted message, and while she doesn't know the full message, she does somehow know that the digit 1 appears at a particular position in it, which is encoded in the ciphertext as 0x2A. Changing that byte to 0x22 (= 0x2A ^ ('1' ^ '9')) will change that 1 to a 9 in the plaintext, and the “I owe you \$100” you sent is received as “I owe you \$900”. This attack can be mitigated by including a MAC with your message to detect alterations.
za flag
lets say the attacker knows that the last part of your encrypted cookie is `is_admin=0` :-)
Joshua avatar
cn flag
@hanshenrik: Fun fact. I have a cookie that acts like that. But if you change is_admin to 1 you only fool the javascript. The server isn't fooled.
Score:6
kr flag

In addition to the answers of "Maarten Bodewes" and "dan04":

Your scheme does not provide any protection of integrity. If you use the same password for different messages, then the 1st byte will be identical in all generated keys, 2nd byte will be again identical in all generated keys, etc. This means, an attacker can replace any byte in the encrypted message with the byte with the same number from another message, and you will not be able to detect if your encrypted message was modified. To do it, the attacked does not even need to know the password. Thus the attacker can change the encrypted message from "Transfer 1000 USD" to "Transfer 5000 USD", and nobody will be able to detect that the encrypted message was modified.

ilkkachu avatar
ws flag
using the same password/key for multiple messages would also be likely to open decryption attacks
kr flag
@ilkkachu: Sure. "dan04" has mentioned it. I see no sense to repeat it.
kr flag
Note that the second bullet-point in dan04's answer is also about integrity. The difference between this one and that one is rather subtle: that one seems more general (since it doesn't depend on having multiple messages), but perhaps there's some situation where this attack is possible but that one is not?
R.. GitHub STOP HELPING ICE avatar
cn flag
Inability to reuse the same keystream is a rather different issue. Even without that, attackers can change the message. They can't substitute another known message but they can flip particular bits, etc. You need authenticated encryption to avoid that.
Joshua avatar
cn flag
And you assume he doesn't have an IV why? (IV would be loaded when seeding the CSPRNG).
kr flag
@Joshua: Good point. I have overlooked "CS" and considered it as normal PRNG. If it is really CS, then even when then same seed (password) is set, 1) the generated sequence on another computer will be different and thus it will be impossible to decrypt the original message; 2) even on the same computer after initializing CSPRNG for decryption the generated sequence can be different (for instance, so works CR PRNG in Java, Class SecureRandom). Thus it can be impossible to decrypt the previously encrypted message. Thus, the scheme in the OP it is even worse.
Score:1
us flag

Your encryption algorithm will perform very poorly in some practical scenarios. For instance, if you encrypt a disk with it, then reading a file from the end of the disk will require the CSPRNG to generate gigabytes / terabytes of random numbers before you get the numbers used to encrypt that file.

Score:0
ss flag

You will have to mix in an element of actual randomness - if you don't seed the generator with random numbers the output will also not be random. The solution you described is vulnerable to:

  1. Dictionary attacks. You can generate hashes for all the seeds for common passwords. Or download it.
  2. Known plaintext attacks. Because your seed is fixed the random stream is fixed. If you know the plaintext of one message, you can now decode all other messages to the same length. Depending on the information you send there might be a lot more plaintext available than you would think (e.g. files have specific markings, for messages language can be more predictable than you would think).

The XOR trick only does confusion and not diffusion and is open to statistical attacks. Even one-time pads with XOR only is partially vulnerable. E.g. for very long messages statistically XOR also leaves 1/256 of your message unencrypted because XOR with 0 doesn't do anything, and 1/256 is inverted because XOR with 0xff is the same as NOT. Again - depending on the information you send 1/256 match might be good enough for the attacker (e.g. if the attack wants to know whether you shared a specific file that they know the context of.)

You might want to salt your RNG with true randomness in addition to the hash. And you need padding to ensure that you don't leak length information.

cn flag
I think you are mistaking the key in use. The question doesn't address, if a static key or some sort of key exchange is used. Of course any randomness within the encryption process needs to be sent to the receiver in some way (sending the IV, key exchange process, etc.). And randomness for keys should be generated by some secure process, if possible.
cn flag
But about your second paragraph, that's simply not true. The XOR with 0 doesn't do anything - but that is exactly the point. The attacker does not know, if that position of the key is XORed with 0 or 1 (looking at single bits). If the key is truly random, uniform, and never repeated, then the attacker can't know which bits of the message are flipped or unchanged. That is the exactly reason, why statistical attacks do not work for OTP.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.