The Advanced Encryption Standard, or AES, is one of the most widely-used encryption algorithms in the world, with applications ranging from secure web browsing to wireless networks. Since its introduction in 1998, numerous researchers have pored over its design looking for security flaws. Recently, an international team led by researchers from Nanyang Technological University, Singapore (NTU Singapore) has found a way to attack a reduced-strength variant of AES. Although standard AES remains secure, this discovery is an important milestone for researchers seeking to probe the security of this important algorithm.
AES is typically used as an encryption algorithm, allowing two parties to use a shared secret code to exchange messages securely. A different but closely-related way to use AES is as a “hash function”, which accepts any digital document and generates a fixed-length summary, or hash. For a hash function to be considered secure, it must be a one-way operation: generating the hash of a document must be straightforward, but finding a document matching a given hash must be so computationally difficult as to be practically impossible.
From left to right: Dr Zhenzhen Bao and Assistant Professor Jian Guo
It was this hash function mode of AES that the NTU researchers and their colleagues sought to challenge. The team was led by Assistant Professor Jian Guo and Presidential Postdoctoral Fellow Dr Zhenzhen Bao, two mathematicians working at NTU’s School of Physical and Mathematical Sciences. It also included researchers from Tsinghua University, the Beijing University of Technology, and the Institute of Information Engineering in China.
“For an algorithm like AES, there is no way to prove mathematically that it is absolutely secure. Our confidence in its security relies on researchers continuously looking for weaknesses, and not yet finding a fatal flaw,” says Prof. Guo, who has been working on cryptanalysis research for 15 years.
Prof. Guo and his colleagues sought to reverse the AES hash function by using a Meet in the Middle (MITM) preimage attack, a technique that had been invented relatively recently, in 2008. The MITM preimage attack is powerful but has a drawback: in order to use it against a given hash function, a cryptanalyst has to select a set of parameters known as an “attack configuration”. With a poorly-chosen attack configuration, the MITM attack loses most of its effectiveness, but good attack configurations are difficult to find because there are too many choices.
To get around this problem, the researchers turned to a technique called mixed-integer linear programming, which translates the problem of choosing an attack configuration into a set of linear inequalities. By solving these inequalities, the most efficient possible MITM attack configuration can be derived.
The team then applied their method to AES-128 (a commonly used form of AES that works on blocks of 128 bits under a 128-bit secret key), in a reduced-strength “8-round” configuration. Normally, the AES-128 algorithm consists of 10 rounds, meaning 10 repetitions of a more basic cryptographic function, with each successive round making the algorithm more secure. Security researchers commonly test their ideas against cryptographic algorithms with fewer rounds, hoping to learn lessons that can be later applied to the full-strength algorithm.
“Previous researchers had only shown successful attacks on the fundamental security properties of 7-round AES-128, despite tremendous efforts over more than 20 years,” explains Prof. Guo. “Our team is the first to demonstrate an attack on 8-round AES-128, which is a quantum leap.”
With the combination of the MITM preimage technique and mixed-integer linear programming, Prof. Guo and his colleagues demonstrated that a hash generated by 8-round AES-128 can be reversed more efficiently than a brute-force search. Their results are due to be presented in Eurocrypt, a flagship conference in the cryptography field, in October 2021.
The newly developed technique is not yet powerful enough to tackle the standard 10-round form of AES-128. However, this research has unearthed fresh insights into the properties of AES. Prof. Guo and his colleagues hope to follow up their work by extending this attack to even more rounds of AES-128, and to other important encryption algorithms that use a similar design strategy similar to AES.