What is wrong with XOR encryption with secure PRNG?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.