---

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

---

1. Generic Structure
2. Requirements
3. Attack On AES
4. Attacks On small-scale AES
   
   
   
   

---

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:

• Attacks on 6-round AES
• Attacks on 6-round small-scale AES

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.