000264826 001__ 264826
000264826 005__ 20190619220211.0
000264826 037__ $$aREP_WORK
000264826 245__ $$aGeneric Round-Function-Recovery Attacks for Feistel Networks over Small Domains
000264826 260__ $$bePrint
000264826 269__ $$a2018
000264826 260__ $$c2018
000264826 300__ $$a24
000264826 336__ $$aReports
000264826 500__ $$aPublished on ePrint.
000264826 520__ $$aFeistel 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.
000264826 6531_ $$aFeistel Network, generic attacks
000264826 700__ $$g286852$$aDurak, Fatma Betül$$0251314
000264826 700__ $$0241950$$aVaudenay, Serge$$g131602
000264826 8560_ $$ffatih.balli@epfl.ch
000264826 8564_ $$uhttps://infoscience.epfl.ch/record/264826/files/2018-108.pdf$$s617934
000264826 909C0 $$xU10433$$pLASEC$$mfatih.balli@epfl.ch$$0252183$$zGrolimund, Raphael
000264826 909CO $$qGLOBAL_SET$$pIC$$preport$$ooai:infoscience.epfl.ch:264826
000264826 960__ $$afatih.balli@epfl.ch
000264826 961__ $$afantin.reichler@epfl.ch
000264826 973__ $$aEPFL$$sPUBLISHED$$rREVIEWED
000264826 980__ $$aREP_WORK
000264826 981__ $$aoverwrite