Paper 2018/108
Generic RoundFunctionRecovery 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 formatpreserving 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 roundfunctionrecovery attacks. The best known attack so far is an improvement of MeetInTheMiddle (MITM) attack by Isobe and Shibutani from ASIACRYPT~2013 with optimal data complexity $q=r \frac{N}{2}$ and time complexity $N^{ \frac{r4}{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}{r2}} \right) }$. It crosses the complexity of the improved MITM for $q\sim N\frac{\mathrm{e}^3}{r}2^{r3}$. We also estimate the lowest secure number of rounds depending on $N$ and the security goal. We show that the formatpreservingencryption schemes FF1 and FF3 standardized by NIST and ANSI cannot offer 128bit 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.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. MINOR revision.ACNS 2018
 Keywords
 Feisten Networkgeneric attacks
 Contact author(s)
 durakfbetul @ gmail com
 History
 20180418: revised
 20180130: received
 See all versions
 Short URL
 https://ia.cr/2018/108
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/108, author = {F. Betül Durak and Serge Vaudenay}, title = {Generic RoundFunctionRecovery Attacks for Feistel Networks over Small Domains}, howpublished = {Cryptology ePrint Archive, Paper 2018/108}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/108}}, url = {https://eprint.iacr.org/2018/108} }