Jeff Phillips, Code Siren, LLC
28 August 2023 - Cryptography
Introduction
The Advanced Encryption Standard (AES)
[1] is a widely adopted encryption algorithm crucial in securing digital communications, sensitive data, and information systems. AES-256, the most robust variant of AES, has become the gold standard for cryptographic security. In this Polynom article, we delve into the captivating history of AES, tracing its origins, development, and the significant milestones that have shaped its prominence in encryption.
In cryptography, a key length is the number of bits in a key used by a cryptographic algorithm. The key length determines the upper bound on an algorithm's security because brute-force attacks can violate the security of all algorithms. For example, if a key is 128 bits long, there are 2^128 possible keys. An attacker must try an average of 2^128 keys to crack the encryption. This is a vast number, and it is not feasible for classical computers to attempt this many keys.
2
128 = 340,282,366,920,938,463,463,374,607,431,768,211,456
Generally, the longer the key length, the more secure the encryption. However, other factors can also affect the security of an encryption scheme, such as the algorithm's quality and implementation.
A symmetric-key algorithm is a cryptographic algorithm that uses the same key for encryption and decryption. This means that the sender and receiver of a message must share the same key to communicate securely. Symmetric-key algorithms are generally faster and more efficient than asymmetric-key algorithms, but they also require that the key be shared securely.
In September 1997, the National Institute of Standards and Technology (NIST) published the final request for candidate nominations for the Advanced Encryption Standard (AES). The minimum functional requirements for AES candidates included support for 128-bit block lengths and key lengths of 128, 192, and 256 bits. Although an early draft of the requirements had also called for support for block sizes of 192 and 256 bits, this requirement was dropped later. However, some submitters chose to retain variable block lengths in their designs, as the request for proposals indicated that such extra functionality would be favorably received.
The Need for a New Encryption Standard
The Data Encryption Standard (DES) was the predominant encryption algorithm in the late 20th century. However, DES’s limitations became apparent as technology advanced, particularly its vulnerability to brute-force attacks. The rise of powerful computers and increased computational capabilities made it feasible for attackers to crack DES-encrypted data within a reasonable timeframe.
To address these security concerns, the NIST initiated a competition in 1997
[2] to develop a new encryption standard. The competition aimed to select a new encryption algorithm to replace DES and serve as the new cornerstone of cybersecurity.
The competition aimed to select a new encryption algorithm to replace DES and serve as the new encryption standard. The competition invited submissions from cryptographic experts and organizations worldwide, encouraging the development of innovative encryption algorithms that offered enhanced security, efficiency, and flexibility.
Unlike the previous competition processes (e.g., DES, SHA-1, and DSA), NIST announced that the AES selection process would be open to all. Anyone could submit a candidate cipher, and each submission would be considered on its merits. NIST would not perform any security or efficiency evaluations but would invite the cryptography community to mount attacks via cryptanalysis of the different candidates. Anyone interested could also evaluate implementation costs.
All results could be sent to NIST as public comments for publication on the NIST AES website or be submitted for presentation at AES conferences. NIST would collect these contributions and use them as the basis for their selection. NIST would then motivate their choices in evaluation reports.
The competition attracted a significant number of submissions, each presenting unique approaches to encryption. The submitted algorithms underwent a thorough evaluation by the cryptographic community and rigorous analysis to assess their strength against various attacks. The evaluation process included security, performance, implementation feasibility, and resistance against known cryptanalysis techniques.
Cryptanalysis involves analyzing the encryption algorithm to discover potential vulnerabilities and weaknesses attackers could exploit.
The Rijndael Algorithm
After several years of careful evaluation and analysis, NIST announced the selection of the Rijndael algorithm
[3] as the new encryption standard. The Rijndael algorithm, developed by Belgian cryptographers Joan Daemen and Vincent Rijmen, showcased exceptional security properties and demonstrated the potential for high-performance implementations against established competitors.
The Rijndael algorithm was the surprise winner of the new Advanced Encryption Standard (AES) contest for the United States. Joan Daemen and Vincent Rijmen designed it and beat competing algorithms from RSA, IBM, Counterpane Systems, and an English/Israeli/Danish team.
Selecting Rijndael as the Advanced Encryption Standard (AES)
[4] marked a significant milestone in encryption history. AES addressed the shortcomings of DES, offering a range of key sizes, including the robust AES-256 variant with its 256-bit key length. AES-256 substantially improved security, making it highly resistant to brute-force attacks and significantly enhancing the confidentiality and integrity of encrypted data.
The transition from DES to AES represented a critical advancement in cryptographic security. AES quickly gained global recognition and acceptance, becoming the encryption algorithm of choice for governments, organizations, and industries worldwide. Its adoption facilitated secure data transmission, protected financial transactions, and ensured the confidentiality of sensitive information across various domains.
Some unique features of Rijndael’s design:
⦁ Block cipher design: AES-256 encrypts data in blocks of 128 bits.
⦁ 14 rounds of encryption: This process makes breaking it difficult by brute-force attacks.
⦁ Wide range of applications: AES-256 is well-suited for a wide range of applications, from protecting data in transit to storing data on disk.
⦁ 256-bit key: the largest size available in the AES family.
Selection of AES
After a five-year evaluation, NIST selected the Rijndael algorithm as the new encryption standard. Rijndael is a block cipher that offers strong security, efficiency, and flexibility. It is also relatively easy to implement, making it a good choice for various applications.
A block cipher is a cryptographic algorithm operating on fixed-length groups of bits called blocks. Block ciphers are elementary building blocks for many cryptographic protocols. The ciphers are ubiquitous in storing and exchanging data; where applicable, data is secured and authenticated via encryption.
Block ciphers use blocks as an unvarying transformation. Even secure block ciphers are suitable for encrypting only a single block at a time using a fixed key. However, block ciphers are often used with other cryptographic primitives, such as modes of operation, to encrypt more significant amounts of data.
AES is a block cipher, meaning it encrypts data in fixed-sized blocks. In the case of AES, the block size is 128 bits or 16 bytes. This means that AES can only encrypt data that is a multiple of 128 bits in length. Stream ciphers, on the other hand, encrypt data one bit at a time. AES uses a substitution-permutation network (SPN) to transform the input data into the encrypted output. The SPN is a series of linked mathematical operations consisting of several rounds, each of which consists of two steps:
⦁ Substitution: This step replaces each block of bits with a new block of bits, according to a lookup table. The lookup table is typically a non-linear function, which means that a slight change in the input block can result in a significant change in the output block.
⦁ Permutation: This step rearranges the bits in the block. The permutation is typically a linear function, which means that the order of the bits in the input block is preserved in the output block.
The substitution and permutation steps are repeated several times, depending on the block cipher algorithm. For example, AES encryption consists of 14 rounds of processing for 256-bit keys.
The AES Algorithm has Four Main Components:
1) Round keys: These are the keys used to encrypt the data. The round keys are derived from the original key using a key schedule algorithm.
2) Substitution: This replaces each data byte with another byte according to a lookup table.
3) Shift rows: This is the process of shifting the rows of the data by a certain number of positions.
4) Mix columns: This is the process of multiplying the columns of the data by a matrix.
The Key Expansion: The first step is to expand the user-supplied key into a series of round keys. This is done using a series of mathematical operations that ensure that the round keys differ from each other and the original key.
Each processing round includes one single-byte-based substitution step, a row-wise permutation step, a column-wise mixing step, and the addition of the round key. The order in which these four steps are executed differs for encryption and decryption.
The Rounds: The next step is to perform a series of rounds on the input data. Each round consists of four steps:
? SubBytes: This step replaces each byte in a non-linear substitution step where each state array is swapped with another byte according to a lookup table.
Figure: S-box table SubByte for each byte in the state array
? ShiftRows: This step cyclically shifts the rows of the state array by a certain number of positions. The state array is a 2-dimensional array of 16 bytes representing the intermediate ciphertext during the encryption or decryption. The ShiftRows operation is performed on the rows of the state array, and it does not affect the columns of the state array.
? MixColumns: This step mixes the columns of the state using a series of mathematical operations. The MixColumn operation is performed by multiplying each column of the state array by a fixed matrix.
Figure: S-box table after the MixColumns operation is performed in the state array
? AddRoundKey: This step XORs (exclusive-or) the state with the current round key. XOR is a binary operation, meaning that it takes two binary inputs and produces a binary output
The Final Round: This excludes the MixColumns step.
The Inverse Key Expansion: The final step is to reverse the key expansion process to recover the original key.
Each processing round includes one single-byte-based substitution step, a column-wise mixing step, a row-wise permutation step, and the addition of the round key. The order in which these steps are executed differs for encryption and decryption.
A 128-bit input block is arranged in a 4-by-4 array of bytes called the state array. The input block's first four bytes occupy the state array's first column; the next four occupy the second column, and so on. This arrangement of the input block allows AES to perform efficient and secure encryption.
Combined with the multiple rounds of processing, these cryptographic operations introduce nonlinearity, confusion, and diffusion into the encryption process. These properties make it challenging for attackers to analyze the encrypted data and extract meaningful information without possessing the correct key.
Source: John Savard[5]
Robustness and Security
Avalanche Effect: AES-256 exhibits the avalanche effect, which means that even a slight change in the input or key results in a significant change in the output. This property ensures that slight modifications in the plaintext or key lead to substantial differences in the ciphertext, making it challenging for attackers to infer any information about the original data or key from the encrypted output.
Confusion and Diffusion: AES-256 incorporates the principles of confusion and diffusion. Confusion refers to making the relationship between the plain and ciphertext as complex as possible. Diffusion ensures that the influence of each bit of the plaintext spreads throughout the entire ciphertext, providing a high level of randomness and making it difficult to deduce any patterns or relationships.
Round Structure: AES-256 employs a specific number of rounds determined by the key size. Each round consists of a set of transformations that are applied sequentially to the input data. The multiple rounds ensure thorough encryption, enhancing the encrypted data's complexity and security.
Subkey Generation: AES-256 utilizes a key schedule algorithm to generate a set of subkeys for each round. These subkeys are derived from the original encryption key and play a crucial role in encryption and decryption. The subkey generation process enhances the security of AES-256 by introducing additional randomness and key-dependent transformations.
Security Analysis: AES-256 has been subjected to extensive security analysis by the cryptographic community. Researchers and cryptanalysts have scrutinized the algorithm to identify potential vulnerabilities and weaknesses. The fact that no practical attacks have been successful against AES-256 itself reinforces its security and demonstrates its resistance to various cryptanalytic techniques.
Hardware and Software Implementations: AES-256 has been implemented in various hardware and software platforms, ensuring compatibility and availability across different systems and devices. Implementations of AES-256 have been optimized to achieve efficient encryption and decryption operations while maintaining the highest level of security.
Standardization and Trust: AES-256 is a standardized encryption algorithm, meaning it has undergone a rigorous evaluation and approval process by reputable organizations such as NIST, CRYPTREC, NESSIE, and the US NSA. The standardization process instills trust in the algorithm, as it ensures that AES-256 adheres to recognized security standards and has been thoroughly evaluated by experts in the field.
AES Adoption and Global Recognition
Following its selection as the new encryption standard, AES gained widespread recognition and acceptance by governments, organizations, and industries worldwide. The adoption of AES was driven by its versatility, efficiency, and superior security compared to its predecessors. AES was suitable for protecting classified government information and found applications in securing data transmission, protecting financial transactions, and safeguarding sensitive corporate and personal data.
The standardized nature of AES also played a significant role in its adoption. Establishing a single, widely accepted encryption algorithm eliminated interoperability issues and simplified the implementation process across different systems and platforms. This standardization allowed for seamless integration of AES into a diverse range of applications and protocols.
Moreover, the open and transparent nature of the AES selection process contributed to its credibility and trustworthiness. The rigorous evaluation and scrutiny undertaken by the cryptographic community, including government agencies, academic institutions, and industry experts, ensured that AES was thoroughly vetted and analyzed for potential vulnerabilities. This collaborative approach and the involvement of various stakeholders fostered confidence in the security and reliability of AES.
As a result of its robust security and widespread adoption, AES became the de facto encryption algorithm for numerous critical applications and industries. Government agencies, financial institutions, healthcare providers, and telecommunications companies, among others, relied on AES to protect sensitive data and ensure the privacy and integrity of their communications and transactions.
The versatility of AES also allowed for its integration into a wide range of technologies and platforms. It was the foundation for securing virtual private networks (VPNs), wireless networks, web communications (HTTPS), file encryption, and storage encryption. AES's efficient performance and robust security guarantees made it a preferred choice for protecting data in transit and at rest.
AES-256 in Modern Cryptography
AES-256 is widely implemented in numerous cryptographic protocols and systems in the contemporary digital landscape. It is the foundation for securing virtual private networks (VPNs), wireless networks, web communications (HTTPS), file encryption, and storage encryption. The broad adoption of AES-256 is attributed to its balance between security and performance, allowing for efficient encryption and decryption operations without compromising data confidentiality.
Future Developments and Challenges
While AES-256 remains unbroken, the evolution of technology introduces new challenges to cryptographic security. For instance, quantum computing could render most encryption algorithms obsolete by breaking their underlying mathematical foundations. In anticipation of this future threat, programmers, researchers, and cryptologists at Code Siren, LLC are actively exploring post-quantum cryptographic algorithms that can withstand attacks from quantum computers. Developing and standardizing quantum-resistant algorithms will be crucial to ensuring secure communication in the quantum-powered world.
Conclusion
AES is a critical component of information security. It is essential for protecting sensitive data and ensuring the confidentiality of information. The future of AES is bright, as most post-quantum cryptography suites include AES-256. AES is a well-established algorithm with a proven track record of security. It will likely remain the lightweight, de facto encryption standard for many years.
In summary, AES is a secure, efficient, and flexible encryption algorithm widely used to protect sensitive data and information systems. AES is a critical component of information security, and it will likely remain the de facto encryption standard for many years.
Read Other Blogs