Upper Bounds for the Security of Several Feistel Networks

Yosuke TODO

doi:10.1587/transfun.E98.A.39

Upper Bounds for the Security of Several Feistel Networks

Yosuke TODO

Full Text Views

0

Cite this

Summary :

In this paper, we deal with upper bounds for the security of some Feistel networks. Such a topic has been discussed since the introduction of Luby-Rackoff construction. The Luby-Rackoff construction is unrealistic because its round functions must be chosen at random from the set of all functions. Knudsen dealt with a more practical construction whose round functions are chosen at random from a family of 2^k randomly chosen functions, and showed an upper bound for the security by demonstrating generic key recovery attacks. However it is still difficult for designers to choose functions randomly. Then, this paper considers the security of some Feistel networks which have more efficient and practical round functions, and such Feistel networks are indeed used by some Feistel ciphers in practice. We show new properties using the relationship between plaintexts and ciphertexts. We propose new generic key recovery attacks by using our properties, and confirm the feasibility by implementing the attack on Feistel ciphers with small block sizes. As a result, we conclude that efficient and practical 6-round Feistel networks are not secure.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E98-A No.1 pp.39-48

Publication Date: 2015/01/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E98.A.39

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category: Symmetric Key Based Cryptography

Authors

Yosuke TODO
NTT Corporation

Keyword

block ciphers, Feistel networks, round functions, key recovery attacks

Cite this

Copy

Yosuke TODO, "Upper Bounds for the Security of Several Feistel Networks" in IEICE TRANSACTIONS on Fundamentals, vol. E98-A, no. 1, pp. 39-48, January 2015, doi: 10.1587/transfun.E98.A.39.
Abstract: In this paper, we deal with upper bounds for the security of some Feistel networks. Such a topic has been discussed since the introduction of Luby-Rackoff construction. The Luby-Rackoff construction is unrealistic because its round functions must be chosen at random from the set of all functions. Knudsen dealt with a more practical construction whose round functions are chosen at random from a family of 2^k randomly chosen functions, and showed an upper bound for the security by demonstrating generic key recovery attacks. However it is still difficult for designers to choose functions randomly. Then, this paper considers the security of some Feistel networks which have more efficient and practical round functions, and such Feistel networks are indeed used by some Feistel ciphers in practice. We show new properties using the relationship between plaintexts and ciphertexts. We propose new generic key recovery attacks by using our properties, and confirm the feasibility by implementing the attack on Feistel ciphers with small block sizes. As a result, we conclude that efficient and practical 6-round Feistel networks are not secure.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E98.A.39/_p

Copy

@ARTICLE{e98-a_1_39,
author={Yosuke TODO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Upper Bounds for the Security of Several Feistel Networks},
year={2015},
volume={E98-A},
number={1},
pages={39-48},
abstract={In this paper, we deal with upper bounds for the security of some Feistel networks. Such a topic has been discussed since the introduction of Luby-Rackoff construction. The Luby-Rackoff construction is unrealistic because its round functions must be chosen at random from the set of all functions. Knudsen dealt with a more practical construction whose round functions are chosen at random from a family of 2^k randomly chosen functions, and showed an upper bound for the security by demonstrating generic key recovery attacks. However it is still difficult for designers to choose functions randomly. Then, this paper considers the security of some Feistel networks which have more efficient and practical round functions, and such Feistel networks are indeed used by some Feistel ciphers in practice. We show new properties using the relationship between plaintexts and ciphertexts. We propose new generic key recovery attacks by using our properties, and confirm the feasibility by implementing the attack on Feistel ciphers with small block sizes. As a result, we conclude that efficient and practical 6-round Feistel networks are not secure.},
keywords={},
doi={10.1587/transfun.E98.A.39},
ISSN={1745-1337},
month={January},}

Copy

TY - JOUR
TI - Upper Bounds for the Security of Several Feistel Networks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 39
EP - 48
AU - Yosuke TODO
PY - 2015
DO - 10.1587/transfun.E98.A.39
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E98-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2015
AB - In this paper, we deal with upper bounds for the security of some Feistel networks. Such a topic has been discussed since the introduction of Luby-Rackoff construction. The Luby-Rackoff construction is unrealistic because its round functions must be chosen at random from the set of all functions. Knudsen dealt with a more practical construction whose round functions are chosen at random from a family of 2^k randomly chosen functions, and showed an upper bound for the security by demonstrating generic key recovery attacks. However it is still difficult for designers to choose functions randomly. Then, this paper considers the security of some Feistel networks which have more efficient and practical round functions, and such Feistel networks are indeed used by some Feistel ciphers in practice. We show new properties using the relationship between plaintexts and ciphertexts. We propose new generic key recovery attacks by using our properties, and confirm the feasibility by implementing the attack on Feistel ciphers with small block sizes. As a result, we conclude that efficient and practical 6-round Feistel networks are not secure.
ER -