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.

  • $\begingroup$ Actually, most block cipher modes of operation have $O(n)$ time complexity (where $n$ is the input size) ... and I wouldn't use any bulk encryption system which has a larger one. (Smaller than $O(n)$ is not possible.) $\endgroup$ – Paŭlo Ebermann May 16 '12 at 22:56

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)$).
  • $\begingroup$ what is O? Big-O notation? $\endgroup$ – goldroger May 3 '12 at 16:16
  • $\begingroup$ ah, I see the space is the memory.. how to explain that thing? :D $\endgroup$ – goldroger May 3 '12 at 16:29
  • 1
    $\begingroup$ Big-O notation is the standard way of expressing asymptotic behavior (such as time and memory complexity). What $O(N)$ effectively means is that there is the time taken is a linear function of the message size; encrypting a message twice as long will take twice as long. What $O(1)$ means is that the algorithms use a constant amount of space; no matter how long the message is, ECB and OFB will take no more than $c$ bytes of memory (for some value of $c$). $\endgroup$ – poncho May 3 '12 at 16:38

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.


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.