Welcome to the resource topic for 2018/108
Title:
Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains
Authors: F. Betül Durak, 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 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.
ePrint: https://eprint.iacr.org/2018/108
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .