Abstract
Unbalanced Feistel networks F k which are used to construct invertible pseudo-random permutations from kn bits to kn bits using d pseudo-random functions from n bits to (k − l)n bits, k ≥ 2 are studied. We show a new generalized birthday attack on F k , with d ≤ 3k − 3. With 2(k−1)n chosen plaintexts an adversary can distinguish F k (with d = 3k − 3) from a random permutation with high probability. If d < (3k − 3) then fewer plaintexts are required. We also show that for any F k (with d = 2k), any adversary with m chosen plaintext oracle queries, has probability O(m nk/2(k−1)n) of distinguishing F k from a random permutation.
Chapter PDF
References
W. Aiello, R. Venkatesan, Foiling birthday attacks in length-doubling transformations, Eurocrypt 1996, LNCS 1070.
N. Alon, J.H. Spencer, The probabilistic method, John Wiley and Sons, 1992.
FIPS 46, Data Encryption Standard, Federal Information Processing Standards Publication 46, U.S. Department of Commerce/N.I.S.T., National Technical Information Service, Springfield, Virginia, 1977.
D. Coppersmith, Another Birthday attack, Advances in Cryptology, Crypto 1985.
D. Coppersmith, Luby-Rackoff: Four rounds is not enough, IBM Research Report, RC20674, Dec. 96.
M. Girault, R. Cohen, M. Campana, A Generalized birthday attack, Eurocrypt 1988, LNCS 330.
L. Knudsen, X. Lai, B. Preneel, Attacks on fast double block length hash functions, J. of Cryptology, 1998, 11:59–72.
M. Luby, Pseudorandomness and cryptographic applications, Princeton University Press, 1996.
M. Luby and C. Rackoff, How to construct pseudorandom permutations from pseudorandom functions, SIAM J.of Comp., 17, pp.373–386, 1988.
J. Patarin, About Feistel Schemes with Six (or More) Rounds, Proc. Fast Software Encryption, March 1998.
R. Anderson, E. Biham, Two Practical and Provably Secure Block Ciphers: BEAR and LION, 1996 Workshop on Fast Software Encryption.
B. Schneier, J. Kelsey, Unbalanced Feistel Networks and Block-Cipher Design, Fast Software Encryption, Third International Workshop Proceedings (February 1996), Springer-Verlag, 1996, pp. 121–144.
Moni Naor, O. Reingold, On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited, Proc. STOC 97
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jutla, C.S. (1998). Generalized birthday attacks on unbalanced Feistel networks. In: Krawczyk, H. (eds) Advances in Cryptology — CRYPTO '98. CRYPTO 1998. Lecture Notes in Computer Science, vol 1462. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0055728
Download citation
DOI: https://doi.org/10.1007/BFb0055728
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64892-5
Online ISBN: 978-3-540-68462-6
eBook Packages: Springer Book Archive