Réseau de Feistel | EPFL Graph Search

Un réseau de Feistel est une construction utilisée dans les algorithmes de chiffrement par bloc, nommée d'après le cryptologue d'IBM, Horst Feistel. Elle a été utilisée pour la première fois dans Lucifer et DES. Cette structure offre plusieurs avantages, le chiffrement et le déchiffrement ont une architecture similaire voire identique dans certains cas. L'implémentation matérielle est aussi plus facile avec un tel système même si les choses ont passablement changé depuis la fin des années 1970. Un réseau de Feistel repose sur des principes simples dont des permutations, des substitutions, des échanges de blocs de données et une fonction prenant en entrée une clé intermédiaire à chaque étage. Il est vraisemblable que Feistel ne soit pas le seul inventeur de cette architecture. Durant une conférence, Don Coppersmith a laissé entendre que Bill Notz et Lynn Smith (de l'équipe d'IBM travaillant sur DES) avaient été en grande partie à l'origine du réseau de Feistel tel que nous le connaiss

Breaking the FF3 Format Preserving Encryption

Fatma Betül Durak, Serge Vaudenay

The NIST standard FF3 scheme (also known as BPS scheme) is a tweakable block cipher based on a 8-round Feistel Network. We break it with a practical attack. Our attack exploits the bad domain separation in FF3 design. The attack works with chosen plaintexts and tweaks when the message domain is small. Our FF3 attack requires

O(N^{\frac{11}{6}})

chosen plaintexts with time complexity

N^{5}

, where

N^2

is domain size to the Feistel Network. Due to the bad domain separation in 8-round FF3, we reduced the FF3 attack to an attack on 4-round Feistel Networks. In our generic attack, we reconstruct the entire codebook of 4-round Feistel Network with

N^{\frac{3}{2}} \left( \frac{N}{2} \right)^{\frac{1}{6}}

known plaintexts and time complexity

N^{4}

2017

Breaking The FF3 Format-Preserving Encryption Standard Over Small Domains

Fatma Betül Durak, Serge Vaudenay

The National Institute of Standards and Technology (NIST) recently published a Format-Preserving Encryption standard accepting two Feistel structure based schemes called FF1 and FF3. Particularly, FF3 is a tweakable block cipher based on an 8-round Feistel network. In CCS~2016, Bellare et. al. gave an attack to break FF3 (and FF1) with time and data complexity

O(N^5\log(N))

, which is much larger than the code book (but using many tweaks), where

N^2

is domain size to the Feistel network. In this work, we give a new practical total break attack to the FF3 scheme (also known as BPS scheme). Our FF3 attack requires

O(N^{\frac{11}{6}})

chosen plaintexts with time complexity

O(N^{5})

. Our attack was successfully tested with

N\leq2^9

. It is a slide attack (using two tweaks) that exploits the bad domain separation of the FF3 design. Due to this weakness, we reduced the FF3 attack to an attack on 4-round Feistel network. Biryukov et. al. already gave a 4-round Feistel structure attack in SAC~2015. However, it works with chosen plaintexts and ciphertexts whereas we need a known-plaintext attack. Therefore, we developed a new generic known-plaintext attack to 4-round Feistel network that reconstructs the entire tables for all round functions. It works with

N^{\frac{3}{2}} \left( \frac{N}{2} \right)^{\frac{1}{6}}

known plaintexts and time complexity

O(N^{3})

. Our 4-round attack is simple to extend to five and more rounds with complexity

N^{(r-5)N+o(N)}

. It shows that FF1 with

N=7

and FF3 with

7\leq N\leq10

do not offer a 128-bit security. Finally, we provide an easy and intuitive fix to prevent the FF3 scheme from our

O(N^{5})

attack.

2017

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

Fatma Betül Durak, Serge Vaudenay

Feistel Networks (FN) are now being used massively to encrypt credit card numbers through format-preserving encryption. In our work, we focus on FN with two branches, entirely unknown round functions, modular additions (or other group operations), and when the domain size of a branch (called

N

) is small. We investigate round-function-recovery attacks. The best known attack so far is an improvement of Meet-In-The-Middle (MITM) attack by Isobe and Shibutani from ASIACRYPT~2013 with optimal data complexity

q=r \frac{N}{2}

and time complexity

N^{ \frac{r-4}{2}N + o(N)}

, where

r

is the round number in FN. We construct an algorithm with a surprisingly better complexity when

r

is too low, based on partial exhaustive search. When the data complexity varies from the optimal to the one of a codebook attack

q=N^2

, our time complexity can reach

N^{O \left( N^{1-\frac{1}{r-2}} \right) }

. It crosses the complexity of the improved MITM for

q\sim N\frac{\mathrm{e}^3}{r}2^{r-3}

. We also estimate the lowest secure number of rounds depending on

N

and the security goal. We show that the format-preserving-encryption schemes FF1 and FF3 standardized by NIST and ANSI cannot offer 128-bit security (as they are supposed to) for

N\leq11

and

N\leq17

, respectively (the NIST standard only requires

N \geq 10

), and we improve the results by Durak and Vaudenay from CRYPTO~2017.

2018

Breaking The FF3 Format-Preserving Encryption Standard Over Small Domains

Fatma Betül Durak, Serge Vaudenay

O(N^5\log(N))

, which is much larger than the code book (but using many tweaks), where

N^2

is domain size to the Feistel network. In this work, we give a new practical total break attack to the FF3 scheme (also known as BPS scheme). Our FF3 attack requires

O(N^{\frac{11}{6}})

chosen plaintexts with time complexity

O(N^{5})

. Our attack was successfully tested with

N\leq2^9

N^{\frac{3}{2}} \left( \frac{N}{2} \right)^{\frac{1}{6}}

known plaintexts and time complexity

O(N^{3})

. Our 4-round attack is simple to extend to five and more rounds with complexity

N^{(r-5)N+o(N)}

. It shows that FF1 with

N=7

and FF3 with

7\leq N\leq10

do not offer a 128-bit security. Finally, we provide an easy and intuitive fix to prevent the FF3 scheme from our

O(N^{5})

attack.

2017

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

Fatma Betül Durak, Serge Vaudenay

N

q=r \frac{N}{2}

and time complexity

N^{ \frac{r-4}{2}N + o(N)}

, where

r

is the round number in FN. We construct an algorithm with a surprisingly better complexity when

r

is too low, based on partial exhaustive search. When the data complexity varies from the optimal to the one of a codebook attack

q=N^2

, our time complexity can reach

N^{O \left( N^{1-\frac{1}{r-2}} \right) }

. It crosses the complexity of the improved MITM for

q\sim N\frac{\mathrm{e}^3}{r}2^{r-3}

. We also estimate the lowest secure number of rounds depending on

N

and the security goal. We show that the format-preserving-encryption schemes FF1 and FF3 standardized by NIST and ANSI cannot offer 128-bit security (as they are supposed to) for

N\leq11

and

N\leq17

, respectively (the NIST standard only requires

N \geq 10

), and we improve the results by Durak and Vaudenay from CRYPTO~2017.

2018

Breaking the FF3 Format Preserving Encryption

Fatma Betül Durak, Serge Vaudenay

O(N^{\frac{11}{6}})

chosen plaintexts with time complexity

N^{5}

, where

N^2

N^{\frac{3}{2}} \left( \frac{N}{2} \right)^{\frac{1}{6}}

known plaintexts and time complexity

N^{4}

2017