Abstract
By considering the role of non-linear approximations in lin- ear cryptanalysis we obtain a generalization of Matsui’s linear crypta- nalytic techniques. This approach allows the cryptanalyst greater flexibil- ity in mounting a linear cryptanalytic attack and we demonstrate the effectiveness of our non-linear techniques with some simple attacks on LOKI91. These attacks potentially allow for the recovery of seven addi- tional bits of key information with less than 1/4 of the plaintext that is required using current linear cryptanalytic methods.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
L. Brown and M. Kwan and J. Pieprzyk and J. Seberry. Improving resistance to differential cryptanalysis and the redesign of LOKI. In H. Imai and R.L. Rivest and T. Matsumoto, editors, Advances in Cryptology — AsiaCrypt’ 91, Lecture Notes in Computer Science 453, Springer-Verlag (1993), 36–50.
H. Feistel. Cryptography and computer privacy. Scientific American, 228(5):15–23, 1973.
C. Harpes and G.G. Kramer and J.L. Massey. A generalization of linear cryptanalysis and the applicability of Matsui’s piling-up lemma. In L.C. Guillou and J.J. Quisquater, editors, Advances in Cryptology — Eurocrypt’ 95, Lecture Notes in Computer Science 921, Springer-Verlag (1995), 24–38.
B.S. Kaliski and M.J.B. Robshaw. Linear cryptanalysis using multiple approximations. In Y.G. Desmedt, editor, Advances in Cryptology — Crypto’ 94, Lecture Notes in Computer Science 839, Springer-Verlag (1994), 26–39.
B.S. Kaliski and M.J.B. Robshaw. Linear cryptanalysis using multiple approximations and FEAL. In B. Preneel, editor, Fast Software Encryption, Lecture Notes in Computer Science 1008, Springer Verlag (1995), 249–264.
S.K. Langford and M.E. Hellman. Differential-linear cryptanalysis. In Y.G. Desmedt, editor, Advances in Cryptology — Crypto’ 94, Lecture Notes in Computer Science 839, Springer Verlag (1994), 17–25.
M. Matsui. Linear cryptanalysis method for DES cipher. In T. Helleseth, editor, Advances in Cryptology — Eurocrypt’ 93, Lecture Notes in Computer Science 765, Springer-Verlag (1994), 386–397.
M. Matsui. The first experimental cryptanalysis of the Data Encryption Standard. In Y.G. Desmedt, editor, Advances in Cryptology — Crypto’ 94, Lecture Notes in Computer Science 839, Springer-Verlag (1994), 1–11.
National Institute of Standards and Technology (NIST). FIPS Publication 46-2: Data Encryption Standard. December 30, 1993.
K. Nyberg. Differentially uniform mappings for cryptography. In T. Helleseth, editor, Advances in Cryptology — Eurocrypt’ 93, Lecture Notes in Computer Science 765, Springer-Verlag (1994), 55–64.
K. Nyberg. Linear approximation of block ciphers. In A. De Santis, editor, Advances in Cryptology — Eurocrypt’ 94, Lecture Notes in Computer Science 950, Springer-Verlag (1995), 439–444.
K. Nyberg and L.R. Knudsen. Provable security against a differential attack. The Journal of Cryptology, 8(1):27–38, 1995.
L. O’Connor. Properties of linear approximation tables. In B. Preneel, editor, Fast Software Encryption, Lecture Notes in Computer Science 1008, Springer Verlag (1995), 131–136.
K. Ohta and K. Aoki. Linear cryptanalysis of the Fast Data Encipherment Algorithm. In Y. Desmedt, editor, Advances in Cryptology — Crypto’ 94, Lecture Notes in Computer Science 839, Springer-Verlag (1994) 12–16.
I. Schaumüller-Bichl. Cryptanalysis of the Data Encryption Standard by a method of formal coding. In T. Beth, editor, Cryptography, Proc. Burg Feuerstein 1982, Springer-Verlag (1983), 235–255.
T. Tokita and T. Sorimachi and M. Matsui. Linear Cryptanalysis of LOKI and s 2DES. In J. Pieprzyk and R. Safavi-Naini, editors, Advances in Cryptology — Asiacrypt’ 94, Lecture Notes in Computer Science 917, Springer-Verlag (1995), 293–303.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Knudsen, L.R., Robshaw, M.J.B. (1996). Non-Linear Approximations in Linear Cryptanalysis. In: Maurer, U. (eds) Advances in Cryptology — EUROCRYPT ’96. EUROCRYPT 1996. Lecture Notes in Computer Science, vol 1070. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-68339-9_20
Download citation
DOI: https://doi.org/10.1007/3-540-68339-9_20
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61186-8
Online ISBN: 978-3-540-68339-1
eBook Packages: Springer Book Archive