EUROCRYPT 2024
Partial Sums Meet FFT: Improved Attack on 6-Round AES
README
Title: "Partial Sums Meet FFT: Improved Attack on 6-Round AES" Implementation: Shibam Ghosh Published At: "Eurocrypt 2024" Full Version: "https://eprint.iacr.org/2023/1659"
This repository contains the implementation of the key recovery attacks presented in our paper:
-Partial Sums Meet FFT: Improved Attack on 6-Round AES, Orr Dunkelman, Shibam Ghosh, Nathan Keller, Gaetan Leurent, Avichai Marmor, Victor Mollimard.
To compare with the previous best-known attacks against 6-round AES, we also implement the Partial-Sum Technique proposed by Ferguson et al. and FFT-based attack proposed by Todo et al.
Table of contents
Generic Structure
The implementation of the attacks is primarily on the 6-round AES cipher. However, to test the results quickly and understanding, the same attack algorithms are also implemented on small-scale AES. This small-scale version of AES was proposed by Murphy et al. in FSE 2005. The location of the ciphers in the repository is as follows:
The root directory includes a highly optimized implementation of the Fast Hadamard Transformation, developed in FFHT. It is important to mention that in our scenario, we utilize the Hadamard Transformation, which belongs to a broader category, called Fourier Transformations. Therefore, we specifically employ FHT (Fast Hadamard Transformation). However, for the sake of consistency with literature on 'FFT-based attacks', we refer to it as FFT (Fast Fourier Transformation) instead of FHT (Fast Hadamard Transformation).
Each attack directory contains a makefile.
Requirements
GCC >= 11.4
AES-NI (For AES Oracle only, the attack does not need AES-NI).
Attacks On AES
The directory for AES contains the implementations of the following attacks
-
Basic Attack contains the implementation of the basic attack on AES that we proposed in Algorithm 3 of our paper.
-
Low Memory Variants contains the implementation of the low memory variant of the basic attack on AES that we proposed in Algorithm 4 of our paper.
-
Low Memory Variants Without Packing contains the implementation of the low memory variant of the basic attack (Algorithm 4) on AES, without packing multiple FFTs in 64-bit words.
-
Partial Sum Technique contains the implementation of the Partial-Sum Technique proposed by Ferguson et al., on AES.
-
FFT-based Attack contains the implementation of the FFT-based attack proposed by Todo et al. on AES.
Each of the above directories contains a makefile and a main.c file. In main.c, we generate random plaintexts and key for the oracle. The AES oracle is given in utility. For this, we use AES-NI instruction set. Finally, the table below details the specifications of the AWS instances used in our attack, along with their respective running times. All instances were sourced from the US-east-2 region (Ohio). For an in-depth discussion on the selection of instances and the conducted experiments, please refer to Section 3.5 of the full version of our paper.
| Attack | AWS Instance | RAM | vCPUs | Running Time |
|---|---|---|---|---|
| Partial Sum + FFT (Algorithm 3) | m6i.32xlarge | 512 GB | 128 | 90 minutes |
| Partial Sum + FFT (Algorithm 4) | m6i.32xlarge | 512 GB | 128 | 48 minutes |
| Partial Sum + FFT (Algorithm 4 without packing) | m6i.32xlarge | 512 GB | 128 | 92 minutes |
| Partial Sum | m6i.32xlarge | 512 GB | 128 | 4859 minutes |
| FFT-based | r6i.32xlarge | 1024 GB | 128 | 3120 minutes |
Attacks On small AES
In addition to the attack on AES, we also implement the attacks on small-scale AES in the directory small AES. It contains the implementations of the following attacks
-
Basic Attack contains the implementation of the basic attack on small-scale AES that we proposed in Algorithm 3 of our paper.
-
Low Memory Variants contains the implementation of the low memory variant of the basic attack on small-scale AES that we proposed in Algorithm 4 of our paper.
-
Low Memory Variants Without Packing contains the implementation of the low memory variant of the basic attack (Algorithm 4) on small-scale AES, without packing multiple FFTs in 64-bit words.
-
Partial Sum Technique contains the implementation of the Partial-Sum Technique.
-
FFT-based Attack contains the implementation of the FFT-based attack.
Each of the above directories contains a makefile and a main.c file. In main.c, we generate random plaintexts and keys for the oracle. The implementation of small-scale AES is given in utility.