Abstract
Differential cryptanalysis is a method of attacking iterated mappings which has been applied with varying success to a number of product ciphers and hash functions [1, 3]. The attack is based on predicting a series of differences ΔY 1, ΔY 2,..., ΔY, known as a characteristic Ω. Partial information about the key can be derived when the differences are correctly predicted. The probability of a given characteristic Ω correctly predicting differences is derived from the XOR tables associated with the iterated mapping.
Even though differential cryptanalysis has been applied successfully to a number of specific iterated mappings such as DES, FEAL and LOKI, the effectiveness of the attack against an arbitrary iterated mapping has not been considered. In this paper we derive the exact distribution of characteristics in XOR tables, and determine an upper bound on the probability of the most likely characteristic Ω in a product cipher constructed from randomly selected S-boxes that are bijective mappings. From this upper bound we are then able to construct product ciphers for which all characteristics Ω occur with low probability.
The Current employer of the author is the Distributed System Technology Center (DSTC), Brisbane, Australia.
Chapter PDF
Similar content being viewed by others
References
E. Biham and A. Shamir. Differential cryptanalysis of DES-like cryptosystems. Journal of Cryptology, 4(1):3–72, 1991.
E. Biham and A. Shamir. Differential cryptanalysis of the full 16-round DES. Technical Report 708, Technion, Israel Institute of Technology, Haifa. Israel, 1991.
E. Biham and A. Shamir. Differential cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and LUCIFER. Advances in Cryptology, CRYPTO 91, Lecture Notes in Computer Science, vol. 576, J. Feigenbaum ed., Springer-Verlag, pages 156–171, 1992.
L. P. Brown, J. Pieprzyk, and J. Seberry. LOKI-a cryptographic primitive for authentication and secrecy applications. Advances in Cryptology, A USCRYPT 90, Lecture Notes in Computer Science, vol. 453, J. Seberry and J. Pieprzyk eds., Springer-Verlag, pages 229–236, 1990.
T. Cusick and M. Wood. The REDOC-II cryptosystem. Advances in Cryptology, CRYPTO 90, Lecture Notes in Computer Science, vol. 537, A. J. Menezes and S. A. Vanstone ed., Springer-Verlag, pages 545–563, 1991.
H. Feistel. Cryptography and computer privacy. Scientific American, 228(5):15–23, 1973.
J. Gordon and H. Retkin. Are big S-boxes best? In T. Beth, editor, Cryptography, proceedings, Burg Feuerstein, pages 257–262, 1982.
M. Hall. Combinatorial Theory. Blaisdell Publishing Company, 1967.
J. B. Kam and G. I. Davida. A structured design of substitution-permutation encryption networks. IEEE Transactions on Computers, 28(10):747–753, 1979.
X. Lai. On the design and security of block ciphers. ETH Series in Information Processing, editor J. Massey, Hartung-Gorre Verlag Konstanz, 1992.
X. Lai, J. Massey, and S. Murphy. Markov ciphers and differential analysis. In Advances in Cryptology, EUROCRYPT 91, Lecture Notes in Computer Science, vol. 547, D. W. Davies ed., Springer-Verlag, pages 17–38, 1991.
X. Lai and J. L. Massey. A proposal for a new block encryption standard. In Advances in Cryptology, EUROCRYPT 90, Lecture Notes in Computer Science, vol. 473, I. B. Damgård ed., Springer-Verlag, pages 389–404, 1991.
R. Merkle. Fast software encryption functions. Advances in Cryptology, CRYPTO 90, Lecture Notes in Computer Science, vol. 537, A. J. Menezes and S. A. Vanstone ed., Springer-Verlag, pages 476–501, 1991.
L. J. O’Connor. Enumerating nondegenerate permutations. Advances in Cryptology, EUROCRYPT 91, Lecture Notes in Computer Science, vol. 547, D. W. Davies ed., Springer-Verlag, pages 368–377, 1991.
E. M. Reingold, J. Nievergeld, and N. Deo. Combinatorial Algorithms: Theory and Practice. Prentice-Hall, 1976.
C. E. Shannon. Communication theory of secrecy systems. Bell System Technical Journal, 28:656–175, 1949.
A. Shimizu and S. Miyaguchi. Fast data encipherment algorithm FEAL. Advances in Cryptology, EUROCRYPT 87, Lecture Notes in Computer Science, vol. 304, D. Chaum and W. L. Price eds., Springer-Verlag, pages 267–278, 1988.
N. J. A. Sloane. Error correcting codes and cryptography, part 1. Cryptologia, 6(2):128–153, 1982.
A. Sorkin. LUCIFER: a cryptographic algorithm. Cryptologia, 8(1):22–35, 1984.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
O’Connor, L. (1994). On the Distribution of Characteristics in Bijective Mappings. In: Helleseth, T. (eds) Advances in Cryptology — EUROCRYPT ’93. EUROCRYPT 1993. Lecture Notes in Computer Science, vol 765. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48285-7_31
Download citation
DOI: https://doi.org/10.1007/3-540-48285-7_31
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57600-6
Online ISBN: 978-3-540-48285-7
eBook Packages: Springer Book Archive