Back to the Future with Block Sizes
An analysis of block ciphers and the AES algorithm.
The National Institute of Standards and Technology (NIST) is currently active in the field of cryptography. It is working on both Post-Quantum Cryptography (PQC) and the standardization of the lightweight cipher Ascon. Additionally, it will soon initiate a significant initiative to investigate threshold cryptography, and by the end of 2024, it announced its intention to consider the standardization of a larger block size variant of the AES algorithm.
To better understand this proposal and its relevance, it is essential to explore what a block cipher is and review the history of the AES algorithm.
Explanation of Block Ciphers
A block cipher is a technique used to encrypt data in individual blocks using a secret key. The two most important characteristics of a block cipher are the key size, which determines the number of bits needed to define it, and the block size, which is the amount of data that is encrypted in each application of the cipher.
This concept is commonly introduced to children through letter tables, where, for example, a random permutation can turn the word BAD into the encrypted text MTH. In this case, the second row of the table serves as the key, resulting in a total number of possible combinations that, when calculated, equate to a key size of approximately 88.3 bits. However, the block size in this example is just one letter, even though its key size is considerably large.
Despite this, a small block size can become vulnerable since repetitions of blocks can be detected in lengthy encrypted texts. For instance, the words “HIDE ME” are encrypted as “QNHX EX,” where the repetition of the character X suggests that it could be encrypting the letter E, the most common letter in English. This reveals that even with random messages, block repetitions pose a potential risk for any system employing a block cipher. Due to the birthday paradox, a match between blocks is likely to occur after encrypting only a few.
About AES
AES is a block cipher that has become the backbone of most cryptographic systems worldwide. It was standardized by NIST in 2001, with variable key sizes of 128, 192, and 256 bits, but with a fixed block size of 128 bits. Initially, in the preliminary proposal for AES, NIST had considered blocks of different sizes but ultimately decided to focus solely on 128-bit blocks.
Although this size seemed appropriate in 2001, the reality is that inherent limitations arose due to its size. Systems using AES were constrained to restrict the amount of data that could be encrypted with a single key to 64 gigabytes in its most popular mode, which is below the capacity of many current storage devices. This implies the need to frequently change keys or implement alternative methods of integrating AES.
Since AES is very fast in hardware, it would be ideal to use it to build a hash function, but block ciphers can be insecure if the block size is small. This discrepancy between block size and key size led to a theoretical “attack” on AES with a 256-bit key in 2009.
Conclusion
What NIST announced is an attempt to reexamine what, with the current perspective, could be considered a mistake made in 2001. The standardization of AES should have been carried out with a 256-bit block size variant. If cryptographers had the opportunity to go back in time, they would modify the AES competition to allow for a 256-bit block size.