What's wrong with XOR encryption with hash and an iterated salt

Question

Suppose you'd use the following algorithm to encrypt a message

1. Let $k$ be the key to encrypt with
   
2. Let $m$ be the message to encrypt
   
3. Split $m$ into groups of 512 bytes
   

Given a hash function with a 512 bit output.
For each 512 bit group in the message:

let $s$ starts at 0

1. let $l = hash(k + s)$
   
2. XOR the current group of the message with $l$
   
3. Append the result from above to the final result.
   
4. Increase $s$ by 1.
   
5. Repeat until there are no more groups in the message

How would one go about breaking such an encryption? If the hash function is well designed then each bit in the input should have a 50% chance of being flipped in the output.

The only predictable relationship between the input and output should be the length of the message. In this case the length of the input and output would always be the same. But is that a security problem? If so, how would one go about exploiting it?

Edit: This question was marked as a possible duplicate. In contrast to the linked question, this question is not concerned with the specifics of the hash function used. This question assumes that the $hash(m) \rightarrow m'$ function is perfect, and given that, if it is a secure method of encryption.

Answer 1

Assuming that:

1. the functions $F_k(s) = {\rm hash}(k + s)$ form a pseudorandom function family (PRF) indexed by the key $k$, and

2. each key is only used to encrypt one message,

then this construction is provably¹ secure against chosen-plaintext attacks.

Being a PRF is not a standard property of a cryptographic hash function, so one cannot just assume that any given secure hash function will satisfy it. A "perfect hash" (i.e. a random oracle) would indeed yield a PRF when used in this manner, but some real-world hash functions might have weaknesses that using them in this way could expose.

Fortunately, however, there's a standard way of converting a hash function into a PRF, called HMAC.² Thus, you could fix this part of your scheme by using ${\rm HMAC}_{\rm hash}(k; s)$ instead of ${\rm hash}(k + s)$. Or just use a hash function that does claim to be a PRF when used this way.³

As for encrypting multiple messages, the problem is that, as cygnusv notes, XORing two ciphertexts encrypted with the same key would cancel out the hash outputs, yielding the XOR of the corresponding plaintexts. If one of the plaintexts is known to the attacker, they can then trivially recover the other.

This limitation would be easily fixed by picking a unique nonce string $n$ for each message and including it in the hash input, e.g. as ${\rm hash}(k + n + s)$ or ${\rm HMAC}_{\rm hash}(k; n + s)$. Of course, the nonce would have to be stored / transmitted alongside the ciphertext, so that it can be decrypted.

(Also, to avoid attacks due to the ambiguity of concatenation, at least two of $k$, $n$ and $s$ should have a a fixed length; otherwise, it would be possible for e.g. $k = \text{"xyz"}$, $n = \text{"123"}$, $s = \text{"4"}$ to yield the same hash input as $k = \text{"xyz"}$, $n = \text{"12"}$, $s = \text{"34"}$ or $k = \text{"xyz1"}$, $n = \text{"23"}$, $s = \text{"4"}$. Or you could simply replace the concatenation with some less ambiguous encoding.)

---

^{1) The proof is essentially the same as that used to prove the IND-CPA security of CTR mode encryption, except that we don't need the PRP/PRF switching lemma since we already have a PRF, and the requirement that only a single message can be encrypted obviously requires some modification to the IND-CPA game to keep it non-trivial. A natural choice would be to allow the adversary online access to the encryption oracle, i.e. the ability to submit individual blocks of plaintext, which the oracle will encrypt as successive parts of a single message stream and immediately return to the adversary.}

^{2) Strictly speaking, the standard security proof of HMAC only applies to certain types of hash functions, known as Merkle-Damgård hashes, and only with certain specific assumptions on their internal operation. That said, most traditional hashes (including SHA-1 and SHA-2) are of the Merkle-Damgård type, and most newer hashes like SHA-3 are explicitly claimed to be secure when used in HMAC, even if they don't use the Merkle-Damgård construction.}

^{3) Off the top of my head, I believe SHA-3 / Keccak effectively makes this claim, via its "flat sponge claim"; of course, if you're using Keccak anyway, it would be even easier to just use its variable-length output, standardized as SHAKE128/256, to generate enough bits to encrypt the whole message from a single hash input.}

Answer 2

There are several possible attacks. Off the top of my head, if an attacker manages to fool you into encrypting a very long message consisting of zeros (00.......00000), then the resulting ciphertext can be used to decrypt all the ciphertexts encrypted with that key. That kind of attack would be a chosen-plaintext attack. That means that your cipher doesn't meet a very weak security notion called "Onewayness under chosen-plaintext attacks" (OW-CPA).

Answer 3

Suppose attacker came to know about length of key and salt and also a set of plaintext that was obtained after XOR operation with the hash obtained then, this scheme is prone to Length extension attack for all hashes that are based on Merkle Damgard construction. MD5, SHA1 and SHA2 all are based on Merkle Damgard contruction and are thus, prone to length extension attack.

Thus, although SHA-512 has huge output size of 64 bytes, length extension attack is still possible.

The use of HMAC-SHA-512 as explained by Ilmari Karonen, is correct method of obtaining the ciphertext. However, as he said, the salt part has really to be unique for every encryption with same password.

Although HMAC-SHA-512 is very strong hash and futuristic collision attack is quite impossible, the use of HMAC further strengthen the XOR cipher. This can be understood by the fact that MD5 and SHA1 hashes are now broken but HMAC-MD5 and HMAC-SHA1 are still strong and quite impossible to break.

If different and unique salt is used everytime to create a PRF stream using a counter as part of the salt using HMAC-SHA-512, then the PRF obtained is quite strong and can be considered as Pseudo One Time PAD to XOR a plaintext.

A sample of this Pseudo One Time PAD can be seen by opening file "Sunny Tiny XOR v2.1.htm" in a browser. After inputting password, Unique Salt and Plaintext to XOR, in the appropriate fields one can obtain the required Pseudo One Time Pad stream by hitting "Show XOR Key" button. One can then test the Randomness quality of the Obtained stream using PRF testers.

Both AES-256 and AES-128 use 16 bytes of output block size and arguably of almost same strength (AES-256 is still not proved to be stronger than AES-128 bit). HMAC-SHA-512 uses 64 byte block using a cryptographically secure hash. This means HMAC-SHA-512 XOR Cipher is many times stronger (not just 4 times) than AES cipher. This is because for every bit output size for the same cipher, the strength doubles. It will not be wrong to say that AES-129 bit block (if possible) is double the strength of AES-128.