Basic XOR cipher for longer messages

Question

How much effective strength is the following adding to a basic 512 bit XOR cipher?

Private Key = Key0 consists of 512 randomly generated bits. This key is never used to encrypt or decrypt anything.

Plain Text Message needs to be encrypted.

1. Generate unique random 16 byte salt for this particular message.

2. Salt Key0 and run through SHA512 hash to make Key1.

3. XOR first block with Key1.

4. Run Key1 (unsalted here and in all other blocks) through SHA512 to create Key2.

5. XOR second block with Key2.

6. Continue until entire message has been encrypted.

7. Store salt + cipher text.

   Since every single block of every single message is encrypted with a different key, barring the same salt getting randomly generated more than once and hashing collisions, it should avoid the repeating pattern. Also, submitting a string of binary 0's would only reveal the salted hash of the key, so it would be useless on other messages. Would it be feasible to brute force the hash of the key to retrieve the actual key?

Answer 1

What you are essentially trying to do is build a pseudorandom number generator (with salt + Key0 as the seed) and use the output of it as a key stream to construct a stream cipher. Some comments:

1. Consider that if the first block is all 0, then all subsequent keys can be recovered. This follows from the fact that the first block is XOR-ed with Key1, and Key1 XOR 0 = Key1. If Key1 is known it can be passed to SHA512 to produce Key2 and so forth.
2. This is not a contrived scenario, even if the first block is not all 0, suppose it is some sort of header data where k bits are known. Those k bits can now be XORed against the first cipher text block to recover k bits of Key1. The search space is now reduced to 2^(512-k).
3. (Cryptographic) Hash functions in general only provide guarantees that they can't be inverted (given H(m) you can't find m) and are collision resistant (it is hard to find m' != m such that H(m) == H(m'). They say nothing about providing output that is indistinguishable from random, which is required of a cryptographically secure pseudorandom number generator.

Assuming a random oracle model (so point 3 can be disregarded and the output of a hash is treated as true random) and a uniformly random plaintext you would have security of 512 bits. I very much doubt however that this is the case, though it is hard to put an exact number on the security of the scheme. My recommendation is to use a well studied stream cipher seeded with random.