5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The main idea IMO is to make the consequences of nonce reuse less awful; yes, ECB+CTR with different keys achieves this practical goal, and theoretically not weaker than plain CTR; but if nonce is reused, the encryption is not CPA-secure anyway. $\endgroup$ – kludg Oct 12 '16 at 13:00
  • 1
    $\begingroup$ Take a look at XTS mode. It doesn't work as you propose, but it's conceptually similar. $\endgroup$ – CodesInChaos Oct 12 '16 at 13:05
  • 3
    $\begingroup$ One reason why people don't use it is speed. This mode takes 2 block cipher calls per block for encryption and doesn't even yet provide authentication. $\endgroup$ – SEJPM Oct 12 '16 at 14:57
  • $\begingroup$ If you don't mind the patent situation, you could use OCB mode. It's pretty close to what you seem to want, uses only one cipher invocation per block, and actually provides proper authenticated encryption. $\endgroup$ – Ilmari Karonen Oct 12 '16 at 22:25
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I didn't try to create a block mode with extended error propagation. Plus I stated in an edit to my question that we are using two keys here, effectively doubling key size $\endgroup$ – Morten Oct 12 '16 at 12:43
  • $\begingroup$ "ECB can be shuffled in 16 byte blocks, which results in the cleartext to become shuffled the same way" ... describes error propagation. "Plus I stated in an edit to my question that we are using two keys here, effectively doubling key size" ... yeah, but without explaining why it doubles the key strength this is just a loose statement (two key triple DES also doesn't double the key strength...) $\endgroup$ – Maarten Bodewes Oct 12 '16 at 12:54
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What advantage does cipher=plain ^ ECB(counter) have over cipher=ECB(plain ^counter) if block-mode operation would be acceptable, and if the "counter" bits change in a fashion which is orthogonal to any likely changes in the plaintext? Both require essentially the same operations, with the sole exception of having the counter advance differently, but the former will devolve into an xor between two plaintexts if a counter value gets used in two known messages, while the latter would at worst report whether the plaintext blocks match. $\endgroup$ – supercat Apr 11 '18 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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