Combining a keystream generator with a block cipher

Question

I understand that:

• A stream cipher's security is diluted if the same key is used more than once. This is fixed by using an additional initialization vector in the keystream's computation.
• A block cipher run in the most simple way, electronic codebook mode, has negligible security due to pattern preservation. This is avoided by using cipher-block chaining or another mode of operation.

Consider that using a keystream generator like in stream ciphers to produce a string of keys for encipher individual blocks of a message with a block cipher:

• Does not fall prey to the problems that reusing a key plagues stream ciphers with because of the avalanche effect present in block ciphers.
• Does away with the need to use more complicated modes of operations in a block cipher due to each block being encrypted with a different key.

Is this analysis correct? Are there implementations like this that are already out there?

Answer 1

Under your scheme, the keystream generated by the stream cipher will be the same for each message enciphered with the same key. While your scheme does not encrypt identical blocks of plaintext in the same message to the same value, it does encrypt identical blocks of plaintext in different messages to the same value, meaning that XORing two ciphertexts together will give clues to the structure of the plaintext inside. This can quickly become relevant when used, for example, in a network protocol, because the sorts of structured data computers like to exchange with each other frequently include significant repeated or predetermined segments.

Completely beside the issue of whether your scheme provides confidentiality, it can't replace using "complicated" block cipher modes of operation, because its performance would be abysmal. It's not obvious from the definition of a block cipher, but there is a reason that all the popular block cipher modes of operation vary what they do with the plaintext or what they do with the ciphertext but never get inventive with what they do with the key. In block ciphers, a significant amount of computation is put into expanding the key into a "key schedule," or list of the subkeys that will be used in each round of the cipher. Once the key schedule has been calculated, subsequent blocks can re-use the same data if the key hasn't changed, meaning that encrypting 1,000 blocks with a single key is much, much faster than encrypting them to different keys. If you wanted to change the key for each block, you'd have to re-do the key schedule operation each time, and that would suck.

Finally, a note on IVs. An external source of entropy, in the form of an IV, is required for probabilistic encryption schemes. Probabilistic encryption guarantees that the same message encrypted twice will not produce the same ciphertext, and that property is needed to assure semantic security. However, semantic security is a very strong requirement, and while using deterministic encryption (for example, by calculating an IV deterministically as I suggest in the comments on Maarten's answer) means you won't have semantic security, for many applications it's good enough. Consider implementing strong encryption on a microcontroller, where entropy is scarce and available sources are easily tampered with: deterministic encryption will leak that you've encrypted the same thing twice, but that's usually much more acceptable than courting the spectre of a full-blown break if someone somehow manages to poison your PRNG.

Answer 2

Yes, your analysis is right. Don't know why Maarten Bodewes - owlstead says something else. This doesn't mean that your scheme is secure or the best idea.

Every plaintext block will be encrypted with a new, pseudo random key. If the bit generation of the stream cipher is secure then there's no known way to get the original password without brute forcing it.

All in all you just use a stream cipher, but not with the common XOR operation to combine the key and the plaintext, but with a block cipher. You will still have all the security properties of a stream cipher, at least if the block cipher is still "secure". Even if the block cipher is broken it's still very hard to break the encrypted block because there's only one block encrypted with the particular key.

But what happens if the key generation is broken? The attacker has to have known plaintext blocks and the appropiate ciphertext blocks. With a secure block cipher, it's still only possible with brute force to get the key - and then he or she only has one part of the key stream of the stream cipher. (This only holds for "normal" breaks. If the stream cipher starts to output the same known key for every block, then all hope is lost.)

What happens if you reuse the key? Every identical plaintext block at the same position (index of the block position) will be encrypted to the same ciphertext. If the plaintext block itself or the position in the whole plaintext changes, then the output block will change completely (because of the avalanche effect of the block cipher). Changing the position of the block changes the key used to encrypt the block, and there's no (assailable) correlation in the output of two instances (with different keys) of a (secure) block cipher, regardless of the used plaintext. If only the plaintext itself changes by one bit, then you will still have no (assailable) correlation. The use of a block cipher defies this attacks on the whole cipher, even if the same original key was used.

Timing or power attacks could be a problem for this scheme. You do the key setup of the block cipher not only one time (like in a normal block cipher mode), but as often as the amount of plaintext blocks. Attacks on this have much higher hopes for a success.

But be warned, you still have some problems of the typical stream cipher. For example the same plaintext encrypted with the same key will still lead to the same output. Your scheme doesn't change this, and you still need to use different keys every time you want to encrypt a message - the same way you have to do it for a normal stream cipher. Changing one bit of the output message will destroy the whole plaintext block. It's still advisable to just use a normal encryption mode with a block cipher - as the other answers already mention, it's still faster, esier and maybe more secure to do this than inventing your own scheme.