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.
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.Sign up to join this community
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$:
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:
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.