Back to the future with block sizes
The American National Institute for Standards and Technology (NIST) is rather busy on the cryptographic front these days. Not only has it been busy in the area of Post-Quantum Cryptography (PQC), it is also in the process of standardizing the lightweight cipher Ascon, and it is also embarking soon on a major effort to examine threshold cryptography, but in late 2024 it announced that it would be looking at standardizing a larger block size variant of the AES algorithm.
To understand what this proposal is, and why it is important, we need to dig a bit deeper into what a block cipher is, and the history of the AES algorithm.
Chief Academic Officer at Zama.
Block ciphers explained
A block cipher is a mechanism to encrypt single blocks of data using a secret key. The two important characteristics of a block cipher are the number of bits needed to determine the key (the so-called key size) and the size of the data which each application of the block cipher encrypts (the co-called block size).
Children often encounter block ciphers as a first introduction to cryptography by making a table of letters, and then placing a random permutation of the letters underneath them such as
A – B – C – D – E – F – G – H – I – J – K – L – M
T – M- A – H – X – S – C – Q – N – R – P – D -E
So the word BAD would encrypt to the ciphertext MTH. In this example the key is the second row of the table (you need the second row to encrypt and decrypt). This gives a total number of keys of
26 · 25 · 24 ··· 3 · 2 · 1 ≈ 2 88.3
which corresponds to a key size of 88.3 bits. The block size is however only one letter, i.e. something which can be represented in bits. This key size is quite large, if I just gave you an encrypted message of three letters it would be hard to determine the key.
However, because the block size is small it is easy to break in practice, since a large encrypted text will reveal repeats of plaintext blocks. For example the words “HIDE ME” will encrypt to “QNHX EX”, and we can see the repetition of X encrypting E. As we know E is the most likely letter in English this means it is likely that the attacker can guess X encrypts E.
Even if we were encrypting random messages (and not English) this repetition of blocks is a way for an attacker to attack any system which uses the block cipher. Due to the birthday paradox, if we have a block size of b bits, then we expect such a collision to after a few blocks. For the case of our toy cipher this means, for a random message, we expect a collision to occur after about 5 blocks.
AES
AES is a block cipher, which is the workhorse of almost all cryptographic systems in the world today. It was standardized by NIST in 2001, and has a variable key size of 128, 192 and 256 bits, but a fixed block size of 128 bits. This fixing of the block size was not originally on the cards.
In the original preliminary call for AES, NIST proposed having 128, 192 and 256 bit key sizes, with a fixed block size of 128-bits, but with the option for other block sizes.
However, as the process to choose AES progressed, in the official first call in 1997 NIST decided to focus only on 128 bit block sizes. In 2001 this block size seemed alright. After all, it means that for a random message we only expect to output blocks to be identical after ciphertext blocks, or 256 Exabytes.
The problem is that this “seemed alright” was not quite true. AES was actually based on an algorithm called Rijndael (invented by two Belgian mathematicians called Joan Daemen and Vincent Rijmen). In its original design, submitted to NIST, Rijndael had three possible key sizes (128, 192 and 256 bits) and three possible block sizes (128, 192 and 256 bits).
As we just remarked, during the AES process, in order to simplify the competition, NIST decided that it would only focus on 128-bit block sizes. Thus the original Rijndael design was modified to only allow one block size.
Unfortunate consequences
The fact that collisions happen more likely with a smaller block size means that applications needed to limit the number of blocks they could encrypt. This means that we only use a single 128-bit key to encrypt a relatively small amount of data. In practice this limit on the amount one can encrypt with one key becomes blocks, or only 64 Gigabytes (which is less than most harddisks in a laptop these days) , when AES is used in its most popular scenario (called AES-GCM mode). Meaning we need to rekey our ciphers more often, or use another method of calling AES.
Due to AES being super fast in hardware it would be good if we could use AES to construct a hash function (which are very slow normally). One can use block ciphers to construct hash functions, but they are not very secure (or are more complex to construct) unless the block cipher has a big block size (such as 256 bits).
The mismatch between block size and key size for the AES algorithm led to a theoretical “attack” (in a very special situation) on the AES algorithm with 256 bit key size in 2009 due to Biryukov and Khovratovich. Thus AES-256, with its 128-bit block size, was not as good as one would expect. On the other hand using Rijndael with 256-bit key and 256- bit block size would have avoided this “attack”.
Summary
Thus what NIST has announced is to revisit, what in hindsight, was the mistake it made back in 2001. AES should really have been standardized with a 256 bit block size variant.
If cryptographers had a DeLorean time machine they would go back about twenty five years, and modify the AES competition so that the final decision would have allowed AES to be used with a 256-bit block size.
We’ve compiled a list of the best encryption software.
This article was produced as part of TechRadarPro’s Expert Insights channel where we feature the best and brightest minds in the technology industry today. The views expressed here are those of the author and are not necessarily those of TechRadarPro or Future plc. If you are interested in contributing find out more here: https://www.techradar.com/news/submit-your-story-to-techradar-pro
The American National Institute for Standards and Technology (NIST) is rather busy on the cryptographic front these days. Not only has it been busy in the area of Post-Quantum Cryptography (PQC), it is also in the process of standardizing the lightweight cipher Ascon, and it is also embarking soon on…
