Is it feasable to combine ECB and CTR block modes of operation?

Question

Both ECB and CTR block modes have advantages over other block modes. They both support parallel encryption and decryption and random reads/writes. Yet both have major disadvantages: (I'm assuming AES block sizes)

• ECB produces repeating patterns for the same 16 bytes of cleartext
• ECB can be shuffled in 16 byte blocks, which results in the cleartext to become shuffled the same way
• CTR xors the clear text to an encrypted nonce+counter. If nonce and key are reused, you can create an XOR key for encrypting/decrypting any AES-CTR encrypted file/message which uses the same key and nonce (This is mainly useful when you can encrypt data, but not read the key/nonce back from the HW AES)

Combining ECB and CTR (By first encrypting the data with ECB,then the ciphertext with CTR) will still allow parallel encryption/decryption and random reads/writes. Yet if you shuffle the blocks, the blocks that changed locations are completely broken. Plus you can't just create an xor key using the same key/nonce, as the data is then still encrypted with a different key. This will also double the key size.

My question is: Does this block mode exist? What are the main problems with an block mode like this?

EDIT: The keys for both encryptions are different, which makes it unlikely that both the ECB and the counter encryption produces the same ciphertext.

Answer 1

Yet if you shuffle the blocks, the blocks that changed locations are completely broken.

This may be true, but you'd have to define what you have achieved if you do. What you are trying to do here is to change the error propagation of the mode of encryption. ECB however has very limited error propagation; it only extends to one block. If you change one bit then the whole output changes. But if your input may have a high amount of possible values, then the change won't be detected. Now you could introduce a crib, a known plaintext, but you'd still have to create yet another pass of e.g. a cryptographically secure hash to protect all the blocks using only one crib.

Error propagation was once an important topic for block ciphers. Nowadays however we tend to rely on CRC's or schemes like PAR2 to avoid damaged (cipher)text. And we tend to rely on message authentication codes (MAC's) to create cryptographically secure authentication tags. Finally we have schemes such as OCB and GCM that provide 1 to 1.5 pass authenticated encryption, making your scheme rather inefficient.

Plus you can't just create an xor key using the same key/nonce, as the data is then still encrypted with a different key. This will also double the key size.

Encrypting twice often does not double the key size due to meet in the middle attacks. You'd have to prove that this is the case.

But given the inefficiency and only partial error propagation and ineffective authentication, I don't think you'd have to delve into that topic.

Answer 2

I agree with @Maarten Bodewes answer, especially in the fact that

Encrypting twice often does not double the key size due to meet in the middle attacks. You'd have to prove that this is the case.

However, if I understand the question correctly you want to combine ECB with CTR because you are afraid that a repeated nonce+key pair will destroy the security guarantees of CTR. Hence, I think your goal is something like nonce misuse-resistance. Roughly speaking, a misuse-resistant mode of operation achieves a decent level of security even if it is use in wrong way (an example is SIV [1]). The provable security guarantees for CTR mode (see [2] for example) do not hold if a nonce is repeated under the same key.

What are the main problems with an block mode like this?

As you have mentioned, encryption in ECB mode becomes deterministic when more than a single block is encrypted under the same key. This is really bad from a security point of view, since it means that an adversary will recognize if the same plaintext is encrypted multiple times. Moreover, ECB is not secure against chosen-plaintext adversaries, i.e. it does not achieve IND-CPA. I assume that your goal is IND-CPA, since this is the common security notation that a confidentiality only scheme should achieve. CTR mode with a nonce as initialization vector (IV) achieves IND-CPA as long as the intermediate counter values do not overlap. In any IND-CPA secure encryption scheme the IV is used to randomize the encryption scheme.

Now, if you are afraid that CTR is used incorrectly and a pair (nonce,key) is repeated I don't see how ECB should help you, because ECB cannot withstand active chosen-plaintext attacks. In any way, your proposed mode of operation will not "double" the security level.

[1]: Rogaway, P., & Shrimpton, T. (2007). The SIV mode of operation for deterministic authenticated-encryption (key wrap) and misuse-resistant nonce-based authenticated-encryption. http://www.cs.ucdavis.edu/~rogaway/papers/siv.pdf

[2]: Bellare, Mihir, et al. "A concrete security treatment of symmetric encryption." http://web.cs.ucdavis.edu/~rogaway/papers/sym-enc.pdf