Complexity of ECB and OFB

Question

What is the complexity of ECB in terms of Time and Memory?

and also in OFB? I can't find it in the internet, so I decided to ask it in here.

Answer 1

Well, assuming that you have a fixed block cipher (that is, you don't change the block cipher as the length of the message increases), then given a message of length $N$:

• Both ECB and OFB take $O(N)$ time for both encryption and decryption.
• Both ECB and OFB take $O(1)$ space in addition to the space to hold the encrypted/decrypted message (which is $O(N)$).

Answer 2

As noted by poncho, both ECB and OFB encryption (and decryption) require $O(n)$ time and $O(1)$ additional space (excluding the input and output, which may be modeled as unseekable streams).

These hold both in the average and in the worst case, and it's worth noting that the complexities approach their asymptotes very quickly; typically, the time complexity of both ECB and OFB (and all other common block cipher modes) is $a + \lceil n \rceil b$ for any $n > 0$, where $n$ is the length of the message in cipher blocks and $a$ and $b$ are constants. Similarly, the additional working space usage is also typically constant for all $n > 0$.

The differences between these modes show up in other features, not in time/space complexity:

• ECB mode encryption is embarrassingly parallel; OFB is almost entirely sequential.
• Most of the computation in OFB mode can be done before the (plaintext or ciphertext) input is available, provided that there's sufficient space to buffer the results, since it only depends on key and initialization vector. This does not hold for ECB mode.
• OFB mode only uses the block cipher in one direction, both when encrypting and when decrypting messages; ECB mode requires a two-way block cipher implementation.
• ECB mode is insecure, leaking information about repeated blocks in the plaintext; OFB, if used properly, fully preserves message confidentiality.
• If the same key is used for multiple messages, OFB mode requires a unique IV / nonce for each; ECB does not — and cannot — use an IV, and is just as (in)secure for multiple messages as for just one.
• Both ECB and OFB mode are malleable, but in different ways: OFB allows an adversary to flip arbitrary bits, while ECB allows them to swap arbitrary blocks. Neither provides message authentication.

In practice, the latter three properties, which concern security, override the first three which are about performance. Thus, if you want your messages to be fully confidential, you should not use ECB mode; if you want them to be safe from tampering too, you should not use either mode alone. (However, OFB is fine if combined with a MAC.)

I'd also like to note that there's a block cipher mode that combines most of the advantages of both ECB and OFB as listed above: CTR mode. It's as parallelizable as ECB, as precomputable as OFB, only uses the block cipher in one direction and provides full confidentiality. It does require an IV / nonce for multiple messages (like all modes that provide full confidentiality), and does not provide message authentication (but a MAC can be applied to the ciphertext to provide that).

The main risk for CTR mode is the same as for OFB (and stream ciphers like RC4, too): if the same key and IV (or an IV equal to any intermediate cipher input) are ever used for two messages, confidentiality may be compromised.