3
$\begingroup$

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?

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ "…XORing two ciphertexts together will give clues to the structure of the plaintext inside." How? Most block ciphers aren't reducible to XOR operations. $\endgroup$
    – Melab
    Jan 18, 2015 at 21:37
  • $\begingroup$ @Melab: Only if the blocks are identical, and that's the reason why I didn't upvote this answer. $\endgroup$
    – Nova
    Jan 18, 2015 at 22:26
  • $\begingroup$ @Nova Many practical applications involve messages with identical blocks of plaintext. For example, DNS requests or ARP packets are identical except for a few bytes each. $\endgroup$ Jan 18, 2015 at 23:26
  • $\begingroup$ @Melab XOR is a bitwise equality test at it's heart, and that's all it's doing here. Blocks of zeros in the XOR operation show that the corresponding plaintext blocks are identical. $\endgroup$ Jan 18, 2015 at 23:28
-1
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ But his analysis is NOT correct. He says his scheme "Does not fall prey to the problems that reusing a key plagues stream ciphers with," but it doesn't: reusing a key still breaks security, even if it's not as spectacular as getting the whole keystream back. $\endgroup$ Jan 14, 2015 at 16:50
  • $\begingroup$ @MrNerdHair: But only in a very small manner. XORing both ciphertexts would give him the XOR of two block cipher encrypted plaintext. An attack on this would have to break the block cipher itself. The only real problem would be for identical plaintext blocks at the same position. I think he/she is aware of this problem, but I can't say for sure. $\endgroup$
    – Nova
    Jan 14, 2015 at 20:29
  • $\begingroup$ No, XORing two ciphertexts tells you which blocks in the plaintext are identical. That's a huge break. $\endgroup$ Jan 14, 2015 at 20:31
  • $\begingroup$ @MrNerdHair: Only with identical original keys. And that's the same for stream ciphers, so we still have the same security like stream ciphers. $\endgroup$
    – Nova
    Jan 14, 2015 at 22:05
  • $\begingroup$ The first point of the OP's analysis of his new algorithm says that it "does not fall prey to the problems that reusing a key plagues stream ciphers with." The whole point of the exercise was to be able to reuse keys, which, just like stream ciphers, it fails at. $\endgroup$ Jan 15, 2015 at 5:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.