Generalized differential-linear cryptanalysis of block cipher
DOI:
https://doi.org/10.30837/rt.2021.1.204.01Keywords:
symmetric cryptography, block cipher, differential-linear cryptanalysis, generalized autocorrelation table, security proofAbstract
Differential-linear cryptanalysis of block ciphers was proposed in 1994. It turns out to be more efficient in comparison with (separately) differential and linear cryptanalytic methods, but its scientific substantiation remains the subject of further research. There are several publications devoted to formalization of differential-linear cryptanalysis and clarification of the conditions under which its complexity can be mathematically accurately assessed. However, the problem of the differential-linear cryptanalytic method substantiation remains completely unresolved.
This paper presents first results obtained by the author in the direction of solving this problem. The class of differential-linear attacks on block ciphers is expanded. Namely, both distinguishing attacks and attacks aimed at recovering one bit of information about a key are considered. In this case, no assumptions are made (as in well-known publications) about the possibility of representing the cipher in the form of some two components. Lower bounds of information complexity of these attacks are obtained. The expressions of these bounds depend on the averaged (by keys) values of the elements’ squares of the generalized autocorrelation table of the encryption transformation. In contrast to the known ones, the obtained bounds are not based on any heuristic assumptions about the investigated block ciphers and are valid for a wider class of attacks as compared to the traditional differential-linear attack. Relations between, respectively, differential, linear and differential-linear properties of bijective Boolean mappings are given. In contrast to the well-known works, the matrix form of the relations is used that makes it possible to clarify better their essence and simplify the proofs. A new relation is derived for the elements of the generalized autocorrelation table of the encryption transformation of the product of two block ciphers, which may be useful in further research.
References
Langford S., Hellman M. Differential-linear cryptanalysis // Advanced in Cryptology – Crypto 1994, LNCS. Vol. 839. 1994. P. 17 – 25.
Biham E., Dunkelman O., Keller N. Enhancing differential-linear cryptanalysis // Advanced in Cryptology – ASIACRYPT 2002, LNCS. Vol. 2401. 2002. P. 254 – 266.
Lu J. A methodology for differential-linear cryptanalysis and its applications // Designs, Codes and Cryptography. 2015. Vol. 77. № 1. P. 11 – 48.
Blondeau C., Leander G., Nyberg K. Differential-linear cryptanalysis revisited // J. Cryptology. 2017. Vol. 30. № 3. P. 859 – 888.
Bar-On A., Dunkelman O., Keller N., Weizman A. DLCT: a new tool for differential-linear cryptanalysis // Cryptology ePrint Archive, Report 2019/256. http://eprint.iacr.org/2019/256.
Алексейчук А.Н. Неасимптотические нижние границы информационной сложности статистических атак на симметричные криптосистемы // Кибернетика и системный анализ. 2018. Т. 54. № 1. С. 93 – 104.
Nyberg K. The extended autocorrelation and boomerang tables and links between nonlinearity properties of vectorial Boolean functions // Cryptology ePrint Archive, Report 2019/1381. http://eprint.iacr.org/2019/1381.
Canteuat A., Koelsch L., Li Ch. [et al.] On the differential-linear connectivity table of vectorial Boolean function // CoRR, abs/190807455. 2019.
Lai X., Massey J.L., Murphy S. Markov ciphers and differential cryptanalysis // Advances in Cryptology – EUROCRYPT’91, Proceedings. – Springer Verlag, 1991. P. 17 – 38.
Harpes C., Kramer G.G., Massey J.L. A generalisation of linear cryptoanalysis and the applicability of Matsui’s piling-up lemma // Advances in Cryptology – EUROCRYPT’95, Proceedings. – Springer Verlag, 1995. P. 24 – 38.
Hoeffding W. Probability inequalities for sums of bounded random variables // J. Amer. Statist. Assoc. 1963. Vol. 58. № 301. P. 13 – 30.
Логачев О.А., Сальников А.А., Ященко В.В. Булевы функции в теории кодирования и криптологии. Москва : МЦНМО, 2004. 470 с.
Сачков В.Н. Введение в комбинаторные методы дискретной математики. Москва : Наука, 1982. 384 с.
Daemen J., Govards R., Vandervalle J. Correlation matrices // Fast Software Encryption – FSE’94, LNCS. Vol. 1008. 1994. P. 275 – 285.
Zhang X.-M., Zheng J., Imai H. Relating differential distribution tables to other properties of substitution boxes // Des. Codes Cryptography. 2000. Vol. 19. № 1. P. 45 – 63.
Chabaud F., Vaudenay S. Links between differential and linear cryptanalysis // Advanced in Cryptology – EUROCRYPT’94, LNCS. Vol. 950. 1994. P. 356 – 365.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
