Paper 2018/108

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

F. Betül Durak and Serge Vaudenay

Abstract

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 $$ and time complexity $$, where $$ is the round number in FN. We construct an algorithm with a surprisingly better complexity when $$ is too low, based on partial exhaustive search. When the data complexity varies from the optimal to the one of a codebook attack $$, our time complexity can reach $$. It crosses the complexity of the improved MITM for $$. We also estimate the lowest secure number of rounds depending on $$ 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 $$ and $$, respectively (the NIST standard only requires $$), and we improve the results by Durak and Vaudenay from CRYPTO~2017.