Paper published in a book (Scientific congresses, symposiums and conference proceedings)
Cryptanalysis of Feistel Networks with Secret Round Functions
BIRYUKOV, Alex; LEURENT, Gaëtan; PERRIN, Léo Paul
2016In Dunkelman, Orr; Keliher, Liam (Eds.) Selected Areas in Cryptography -- SAC 2015, 21st International Conference, Sackville, NB, Canada, August 12-14, 2015, Revised Selected Papers
Peer reviewed
 

Files


Full Text
draft.pdf
Author preprint (418.11 kB)
Request a copy

All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
Feistel Network; Yoyo; Guess-and-Determine
Abstract :
[en] Generic distinguishers against Feistel Network with up to 5 rounds exist in the regular setting and up to 6 rounds in a multi-key setting. We present new cryptanalyses against Feistel Networks with 5, 6 and 7 rounds which are not simply distinguishers but actually recover completely the unknown Feistel functions. When an exclusive-or is used to combine the output of the round function with the other branch, we use the so-called \textit{yoyo game} which we improved using a heuristic based on particular cycle structures. The complexity of a complete recovery is equivalent to $\bigO(2^{2n})$ encryptions where $n$ is the branch size. This attack can be used against 6- and 7-round Feistel Networks in time respectively $\bigO(2^{n2^{n-1}+2n})$ and $\bigO(2^{n2^{n}+2n})$. However when modular addition is used, this attack does not work. In this case, we use an optimized guess-and-determine strategy to attack 5 rounds with complexity $\bigO(2^{n2^{3n/4}})$. Our results are, to the best of our knowledge, the first recovery attacks against generic 5-, 6- and 7-round Feistel Networks.
Disciplines :
Computer science
Author, co-author :
BIRYUKOV, Alex ;  University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
LEURENT, Gaëtan ;  Inria
PERRIN, Léo Paul ;  University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
External co-authors :
yes
Language :
English
Title :
Cryptanalysis of Feistel Networks with Secret Round Functions
Publication date :
March 2016
Event name :
Selected Areas in Cryptography -- SAC 2015
Event place :
Sackville, Canada
Event date :
August 12-14, 2015
Audience :
International
Main work title :
Selected Areas in Cryptography -- SAC 2015, 21st International Conference, Sackville, NB, Canada, August 12-14, 2015, Revised Selected Papers
Editor :
Dunkelman, Orr
Keliher, Liam
Publisher :
Springer International Publishing
Collection name :
Security and Cryptology, 8781
Pages :
102-121
Peer reviewed :
Peer reviewed
FnR Project :
FNR4009992 - Applied Cryptography For The Internet Of Things, 2012 (01/07/2013-30/06/2016) - Alex Biryukov
Available on ORBilu :
since 27 October 2015

Statistics


Number of views
202 (5 by Unilu)
Number of downloads
0 (0 by Unilu)

Scopus citations®
 
29
Scopus citations®
without self-citations
26

Bibliography


Similar publications



Contact ORBilu