Choosing a block cipher mode of operation

25/10/2022 · 17 min read · cybersecurity cryptography encryption blockcipher aes cryptauditor  ·
Share on:

Translations

Overview

In this article, I propose to give you some guidance in choosing the mode of operation for a block cipher. The aim here is to highlight the essential elements to know which mode to use, taking into account security properties as well as performance criteria, and in particular with the help of a little tool I have developed for this purpose.

Cryptography and encryption are widespread in the digital world we live in. For example, 85.8% of websites now use the Hypertext Transfer Protocol Secure (HTTPS) by default to exchange data. In this context, numerous algorithms exist, and it is sometimes difficult to choose which one to deploy, especially when using proprietary solutions not disclosing much technical information. A recurring deal is the choice of block cipher modes of operation. First, we will take a brief look at what cryptography and block ciphers are. Then we will look at the main general properties of the associated modes of operation and what these modes do. We will conclude with a comparison of these modes.

Cryptography is the set of techniques used to protect data in order to ensure its confidentiality (information cannot be read by an unauthorized person), integrity (information cannot be modified by an unauthorized person), authenticity (information is attributed to its legitimate author) or non-repudiation (information cannot be denied by its author). Cryptography includes encryption, which ensures data confidentiality by using an algorithm called cipher to make data incomprehensible, producing a ciphertext using an encryption key. Decryption performs the opposite operation, i.e. retrieving the plaintext from the ciphetext.

Encryption can be either symmetrical, where the same key is used to encrypt and decrypt data, or asymmetrical, where a so-called public key (because it’s shared) is used for encryption and another so-called private key (because it’s kept secret) is used for decryption. Symmetrical encryption is generally more efficient than asymmetrical encryption, but the challenge with symmetrical encryption lies in sharing the encryption key. This is why the two types often coexist, where asymmetric encryption is used to encrypt the exchange of a symmetric encryption key used to encrypt the rest of the data to be exchanged.

Symmetric encryption
Symmetric encryption

Asymmetric encryption
Asymmetric encryption

There are two main families of symmetrical encryption: block ciphers and stream ciphers. Block ciphers involve cutting the plaintext into blocks of generally fixed size, while stream ciphers consists in processing the data bit by bit without cutting it.

Simplified view of a block cipher
Simplified view of a block cipher

Simplified view of a stream cipher
Simplified view of a stream cipher

There are several block cipher algorithms: Advanced Encryption Standard (AES), Data Encryption Standard (DES), 3DES, International Data Encryption Algorithm (IDEA), Blowfish, Twofish, RC5, etc. Block ciphers offer many modes of operation, and it can be difficult to decide which mode to use on top of the algorithm and key length.

I am now going to explain the main properties of the modes of operation here, so that you can better understand how they differ in practice.

Some modes of operations guarantee data confidentiality through encryption only: this is known as Confidentiality Only.
Some modes of operation also offer data integrity and authenticity through authentication: this is known as Authenticated Encryption (AE). AE is based on the use of a Message Authentication Code (MAC), a code or tag calculated from an encryption key and an algorithm. The MAC is then used to check whether the data has been modified, and to confirm that it comes from the sender. For AE, the MAC is either:

  • calculated and then encrypted with the plaintext to produce the ciphertext (known as MAC-then-Encrypt or MtE);
  • calculated from the ciphertext which is produced after encrypting the plaintext (known as Encrypt-then-MAC or EtM);
  • calculated separately from the ciphertext (known as Encrypt-and-MAC or E&M).

It is also possible to transmit additional unencrypted data in addition to the encrypted data (the ciphertext), and to authenticate both the additional data and the ciphertext using a MAC. This is known as Authenticated Encryption with Associated Data (AEAD). This can be useful if some of the data does not need to or cannot be encrypted during transmission, but you still want to have the integrity relying on the whole set of data. In the AE context, the MAC is calculated according to different modes (close to MtE, EtM or E&M), which we will explore below.
To give you a more concrete example, when performing AEAD via Galois/Counter Mode (GCM) to encrypt and authenticate data with the IPsec ESP protocol, the Security Parameter Index or SPI (used to identify IPsec flows relating to negotiated cryptographic parameters) acts as the additional data for AEAD.

Cutting data into blocks forces modes of operation to add data in order to properly carry out the logical XOR (Exclusive OR) operations, which are performed bit by bit. Elements subject to XOR must be of the same size. Adding data in this case is called padding. Some modes of operation do away with this by generating a key sequence or keystream, which can be used as in bit-by-bit stream ciphers, where each block no longer has to be the same size as the element it faces in order to be encrypted. The block cipher then becomes a stream cipher, even if the data is initially split into blocks. This is interesting because padding lengthens the size of the ciphertext compared with the original plaintext, and has introduced attacks such as the Padding Oracle attack.

A cipher is said streamable or online cipher if it is able to process a message block by block, leaving out the already processed blocks. Otherwise, the entire plaintext must be stored before starting the cipher. Such a property makes receiving, storing, encrypting/decrypting and sending faster.

If the produced ciphertext may happen to be the same given several identical plaintexts, we are facing determinism. If the produced ciphertext is different for each identical plaintext, this is called probabilism. It is preferable to have a probabilistic mode of operation in order to resist various attacks that would weaken the robustness of the encryption. Probabilism is generally made possible in block ciphers by inserting of random, pseudo-random or at least unpredictable data, through the use of Initialization Vector or IV (a sequence of bits that must be random or pseudo-random), or through the use of nonce (an IV used only once, generally random or pseudo-random).

Random read access is the ability to decrypt a block of a ciphertext at random without having to decrypt other blocks of the ciphertext. This can be useful for flexible data access, for instance, whenever you want to decrypt some specific data on a hard disk without decrypting the whole disk!

An error on a bit of ciphertext (e.g. during transmission) can have a different impact depending on the mode of operation. Indeed, depending on the level of inter-dependency between the ciphertext blocks, the error can then propagate during decryption. It should be noted that with AEAD, any error in a bit of the ciphertext will systematically invalidate the decryption result due to the MAC check.

Parallelism is the ability to simultaneously perform encryption or decryption operations on blocks independently of other blocks. This obviously saves considerable time, making the modes of operation more efficient.

I propose here to compare 10 modes of operation for block ciphers. Note that there are other modes that I won’t describe here. I am deliberately offering a textual description here, as nice diagrams can easily be found on the Web.

  • Electronic Codebook (ECB): each plaintext block is associated with the encryption key via the encryption algorithm to produce a ciphertext block independently of the other blocks.
  • Cipher Block Chaining (CBC): each plaintext block is associated with the preceding ciphertext block via a XOR operation, then associated with the encryption key via the encryption algorithm to produce a single ciphertext block. The first block of plaintext is associated with an IV via an XOR operation.
  • Cipher Feedback (CFB): each produced ciphertext block is associated with the encryption key via the encryption algorithm, then the result is associated with the next plaintext block via a XOR operation. The first plaintext block is associated, via a XOR operation, with the result of the association of the encryption key and an IV via the encryption algorithm. CFB does not require padding and is therefore turns a block cipher into a stream cipher.
  • Output Feedback (OFB): each ciphertext block is produced by associating the plaintext with a keystream created from the association of the encryption key and an IV via the encryption algorithm. The OFB mode then turns a block cipher into a stream cipher.
  • Counter (CTR): each ciphertext block is produced independently of the other blocks by associating the plaintext with a keystream. This keystream is created by associating, via the encryption algorithm, the encryption key and the concatenation of a nonce and a counter which is incremented for each block. The CTR mode also turns a block cipher into a stream cipher.
  • Counter with cipher block chaining message authentication code (CCM): uses CTR mode as a stream cipher and CBC-MAC mode (similar to CBC mode for block ciphers) to produce a MAC for authentication. CCM is an AE mode, and more precisely an MtE-type AEAD mode.
  • Galois/Counter Mode (GCM): uses CTR mode (except that counters are initially associated with an IV) as stream cipher. A Wegman-Carter variant is added to produce a MAC: this is a XOR operation between the result of associating the first counter value and the encryption key via the encryption algorithm and the result of a hash function called GHASH. GHASH is a polynomial multiplication from additional data and using the ciphertext blocks as coefficients of the polynomial, followed by a XOR operation with the concatenation of the values of the length of additional data and those of the ciphertext. To put it simply, GCM is an AE mode and, more precisely, an AEAD mode of type EtM.
  • Encrypt-then-authenticate-then-translate (EAX): uses CTR mode as stream cipher and One-key MAC mode (OMAC, similar to CBC-MAC) to produce a MAC for authentication. EAX is an AE mode, and more precisely an EtM-type AEAD mode.
  • Synthetic Initialization Vector (SIV): produces a block cipher and a MAC. The MAC is produced via a pseudorandom function (PRF, in this case CMAC-AES) from the encryption key and the plaintext concatenated with the nonce (which allows the nonce to be used twice). The ciphertext is produced by an encryption algorithm (in this case AES-CTR) from the plaintext, a second encryption key and the MAC. SIV is an AE mode, and more specifically an MtE-type AEAD mode.
  • Offset codebook (OCB): each plaintext block is first associated with an offset (a value determined from the encryption key and a nonce incremented for each block) via a XOR operation. Next, the result is associated with the encryption key via an encryption algorithm, and then again with the offset via a XOR operation. A MAC is generated for authentication from the plaintext blocks, which are associated via a XOR operation, then the result is associated with the encryption key via the encryption algorithm. OCB is an stream cipher based AE mode, and its OCB2 version is more precisely a stream cipher AEAD mode.

It may not be easy to choose one of these modes just by reading how they work. As you likely noticed, each of these operating modes, depending on their design, has different properties, allowing more security features or better performance. The rest of this article will help you compare these modes and ease your choices.

In this section, we will compare the modes of operation we have described, first with regard to their main properties, then according to their peformances, using a tool I haveve developed.

The following table summarizes the various properties of the main block cipher modes of operation.

ECB CBC CFB OFB CTR CCM GCM EAX SIV OCB
Mode Confidentiality only Confidentiality only Confidentiality only Confidentiality only Confidentiality only AEAD AEAD AEAD AEAD AEAD
Padding required (no stream cipher) Yes Yes No No No No No No No No
Streamable Yes Yes Yes Yes Yes No Yes Yes No Yes
Determinist or Probabilistic Determinist Probabilistic Probabilistic Probabilistic Probabilistic Probabilistic Probabilistic Probabilistic Probabilistic Probabilistic
Random access possible Yes Yes Yes No Yes No Yes (after verifying the MAC) Yes (after verifying the MAC) Yes (after verifying the MAC) Yes
Parallelism possible Encryption and Decryption Decryption only Decryption only No Encryption and Decryption Encryption and Decryption Encryption and Decryption Encryption and Decryption No Encryption and Decryption
Impact of error propagation Average as affecting the current entire block Important as affecting the current entire block and the next blocks Important as affecting the current entire block and the next blocks Low as only affecting the concerned bit Low as only affecting the concerned bit Important as invalidating the MAC Important as invalidating the MAC Important as invalidating the MAC Important as invalidating the MAC Important as invalidating the MAC

To conclude this article, I now bring a comparison of the performance of various modes of operation with a little tool I have developed for this purpose: cryptauditor. This tool uses the PyCryptodome Python library to enable some random data to be encrypted and decrypted using either the AES encryption algorithm with different possible modes, or the Rivest-Shamir-Adleman (RSA) encryption algorithm, according to a random key of a given length. I also extended cryptauditor’s capabilities with the support of more cryptographic techniques like hash function or digital signature algorithms.
With cryptauditor, in order to measure the execution time of the encryption or decryption function, I use the Time library and the perf_counter() counter. I also disable the garbage collector during the measurement to minimize disruption to the results.

Here is an example of how cryptauditor can be used:

$ python3 cryptauditor.py -u us -r 100000 -d 10B -c AES-OFB
Performing 100000 rounds of AES encryption and decryption in OFB mode with a 256-bit random key on 10B of random data
Encryption time: 2.685us
Decryption time: 2.666us

You can also have fun testing all the operating modes for AES in a single command, cryptauditor will then show you the speed ranking:

$ python3 cryptauditor.py -c aes-all -d 100MB -r 10 -u s
Performing 10 rounds of AES encryption and decryption in ECB mode with a 256-bit random key on 100MB of random data
Performing 10 rounds of AES encryption and decryption in CBC mode with a 256-bit random key on 100MB of random data
Performing 10 rounds of AES encryption and decryption in CFB mode with a 256-bit random key on 100MB of random data
Performing 10 rounds of AES encryption and decryption in OFB mode with a 256-bit random key on 100MB of random data
Performing 10 rounds of AES encryption and decryption in CTR mode with a 256-bit random key on 100MB of random data
Performing 10 rounds of AES encryption and decryption in CCM mode with a 256-bit random key on 100MB of random data
Performing 10 rounds of AES encryption and decryption in GCM mode with a 256-bit random key on 100MB of random data
Performing 10 rounds of AES encryption and decryption in EAX mode with a 256-bit random key on 100MB of random data
Performing 10 rounds of AES encryption and decryption in SIV mode with a 256-bit random key on 100MB of random data
Performing 10 rounds of AES encryption and decryption in OCB mode with a 256-bit random key on 100MB of random data
Encryption speed ranking:
1 - AES-ECB (+0.0s)
2 - AES-CTR (+0.109s)
3 - AES-CBC (+0.132s)
4 - AES-OFB (+0.151s)
5 - AES-OCB (+0.182s)
6 - AES-SIV (+0.342s)
7 - AES-EAX (+0.343s)
8 - AES-CCM (+0.345s)
9 - AES-GCM (+0.65s)
10 - AES-CFB (+2.523s)
Decryption speed ranking:
1 - AES-ECB (+0.0s)
2 - AES-CBC (+0.121s)
3 - AES-CTR (+0.13s)
4 - AES-OFB (+0.154s)
5 - AES-OCB (+0.333s)
6 - AES-SIV (+0.358s)
7 - AES-CCM (+0.363s)
8 - AES-EAX (+0.364s)
9 - AES-GCM (+0.669s)
10 - AES-CFB (+2.513s)

Moreover, I would like to recommend 2 other interesting alternative tools that offer similar functionality: CyberChef and openssl (with the speed option).

I measured the performance of the different modes of operation using the AES encryption algorithm with a 256-bit key and for different random data sizes ranging from 1B to 100MB and performing 10000, 100000 or 1000000 executions (in order to produce an average) depending on the size of the data to be processed. The measurements were carried out on a MacBook Pro with an Intel Core i5 2.4 GHz Quad-Core processor with 16 GB memory and running macOS Catalina (version 10.15.7) at the time of the tests. I added RSA to the tests for comparison purposes. Note that RSA has a fairly low limit in terms of plaintext size that can be processed, i.e. the key size (modulus) minus the padding minus the size of the hash function’s fingerprint output.
The ordinates (in logarithmic scale for greater visibility) are the execution time in ms and the abscissas are the size of the data to be encrypted or decrypted in Bytes (B).

Encryption execution time as a function of the plaintext size
Encryption execution time as a function of the plaintext size

Decryption execution time as a function of the plaintext size
Decryption execution time as a function of the plaintext size

Time for a little analysis… But first of all, I would like to appeal to your good skepticism as there are so many parameters that make the results vary, especially the underlying hardware!
One of the first things we can notice is that trends change as the size of the data to be processed increases. Even so, the best performing mode here is ECB. This comes as no surprise, as it is the simplest mode (but also the least secure!) offering Confidentiality Only and that can be parallelized. We can also see that the modes offering AEAD (CCM, GCM, EAX and SIV) naturally take longer to execute than the others, which is expected as they have to perform additional processing due to the authentication part. In particular, we can see that SIV performs poorly for small amounts of data, then falls into line as data size increases. Moreover, OFB and CTR modes offer very interesting performances. Finally, it is confirmed that RSA performs very poorly compared to AES.

I highly invite you to carry out your own tests, and to read other articles relating to this type of study (see the sources at the end of the article).

We are now in a better situation to answer the question: which operating mode should I choose? The answer depends on many criteria, but above all on best practices.

  • Choose a probabilistic mode.
  • Be particularly careful to use random IVs and unique nonces.
  • Study the underlay hardware (is there dedicated hardware for encryption and decryption, such as an Application-Specific Integrated Circuit or ASIC?)
  • Prefer a parallelizable mode.
  • Be careful if random read access is required.
  • Choose a mode without padding.
  • Check whether or not a data authentication function is already provided for your use case; if not, prefer an AEAD mode.
  • With Confidentiality Only modes, prefer a mode with low impact of error propagation.

Generally speaking, the recommended modes are CTR, GCM and OCB.

Translations