DEGENERATE S-BOXES
DOI:
https://doi.org/10.15588/1607-3274-2018-1-15Keywords:
methodology of evaluation of resistance, degenerate substitution, differential indicators, linear indicators.Abstract
Context. S-blocks are one of the main transformations of many ciphers, and the search for S-boxes with improved cryptographic indicesa great deal of attention in the literature of this direction is paid. Thus, it that there are permutations (S-blocks), which should be considered
bad is assumed, i.e. those that are not suitable for building reliable ciphers. On the other hand, one of the directions for improving the design of ciphers, which has been developing recently, with the construction of ciphers is connected, in which S-blocks of random type can be used. There is an important question. Which S-boxes are not suitable for building encryption transformations? In this connection, the study of the properties and features of the formation of S-blocks of degenerate structures, which are interpretations that degrade the cryptographic exponents of ciphers, is becoming increasingly important.
Objective. A study of the properties and features of the formation of permutations of a degenerate type, an estimate of the probability
of their generation with the aid of a random permutation generator. Determination of the characteristics by which degenerate substitutions can distinguished.
Method. Construction of the piecemeal laws of the distribution of the maxima of tables of differential differences and tables of linear
approximations for reduced models of ciphers, using different (degenerate) S-block constructions in them. Determination of the law of
distribution of maxima of XOR tables and shifts of tables of linear approximations of byte permutations.
Results. The ensemble characteristics of the set of byte substitutions are studied. Based on the study of the differential and linear
properties of the reduced models of ciphers, the characteristics by which degenerate substitutions can identified are determined. The probability
of random generation (by choice) of a byte substitution of a degenerate type is determined computationally and experimentally.
Conclusions. The results of the work confirmed that obtaining degenerate byte S-blocks for their random generation is an unlikely event. This means that almost without restrictions in the ciphers, S-blocks can used, generating with the help of the generator of random substitutions. The scientific novelty of the presented results is that the influence of degenerate permutations on the efficiency of encryption
transformations has studied. For the first time it established that, the use of S-blocks generated randomly in ciphers with a very high probability does not lead to a deterioration in the ciphers’ resistance to differential and linear cryptanalysis attacks.
The practical significance of the results of the work seen in the receipt of specific data confirming the main position of the new technique
developed to assess the stability of block symmetric ciphers to attacks of differential and linear cryptanalysis on the independence of cipher
strength indicators from the applied S-blocks, including S-blocks of random type.
References
Dolgov V. I., Lisickaya I. V. Metodologiya ocenki stojkosti
blochnyh simmetrichnyh shifrov k atakam differencial’nogo i
linejnogo kriptoanaliza: monografiya. Har’kov, Izdatel’stvo
“Fort”, 2013, 420 p.
Saier W., Staffelbach O. Nonlinearity criteria for cryptographic
functions, In Advances in Cryptology – EUROCRYPT’89, Lecture
Notes in Computer Science. Springer-Verlag, 1990, Vol. 434,
pp. 549–562.
Pasalic E., Johansson T. Further Results on the Relation between
Nonlinearity and Resiliency for BF, IEEE Trans. on Information
Theory, 2002, Vol. 48, No. 7, July, P. 1825–1834.
Sillan W., Clark A. and Dawson E. An effective genetic algorithm
for finding highly nonlinear Boolean functions, In First
International Conference on Information and Communications
Security, in Lecture Notes in Computer Science, Springer Verlag,
, Number 1334, pp. 149–158. 5. Sillan W., Clark A. and Dawson E. Smart Hill Climbing Finds
Better Boolean Functions, Workshop on Selected Areas in
Cryptography (SAC’97) Workshop Record, 1997, P. 50.
Seberry J., Zhang X. Hadamar Matrices, Bent Functions and
Cryptography, In J. H. Dinitz and D. R. Stinson, editors,
Contemporary Design Theory: A Collection of Surveys, chapter
, John Wiley and Sons, Inc, 1995, pp. 431–559.
Gorbenko I. D., Potij A. V., Izbenko Yu. A. i dr. Issledovanie
analiticheskih i statisticheskih svojstv bulevyh funkcij
kriptoalgoritma Rijndael (FIPS 197), Radiotehnika. Vseukr.
Mejvedomstvenyj nauchno tehnicheskij sbornik, 2004, No. 126,
pp. 132–138.
Pasalic E., Johansson T., Saitra S. et al. New constructions of
resilient and correlation immune Boolean functions achieving
upper bounds of nonlinearity, In Workshop of Coding and
Cryptography, Electronic Notes in Discrete Mathematics. Elsevier,
January 2001.
Sillan W., Clark A. and Dawson E. Heuristic Design of
Cryptographically Strong Balanced Boolean Functions, In
Advances in Cryptology ЕUROCRYPT’98 Springer Verlag LNCS
, 1998, pp. 489–499.
Saity S., Johansson T. Construction of Cryptographically
Important Boolean Functions, In INDOCRYPT 2002, Volume
in Lecture Notes in Computer Science, Springer Verlag,
, pp. 234–245
Lisickaya I. V. Metodologiya ocenki stojkosti blochnyh
simmetrichnyh kriptopreobrazovanij na osnove umen’shenyh
modelej: dis. … doct. tehnich. nauk 05.13.05. Har’kov, 2012,
p.
Dolgov V. I., Kuznecov A. A., Isaev S. A. Differencial’nye svojstva
blochnyh simmetrichnyh shifrov, predstavlennyh na ukrainskij
konkurs, Elektronnoe modelirovanie, 2011, Vol. 33, No. 6,
pp. 81–99.
Kuznecov A. A., Dolgov V. I., Isaev S. A. Linejnye svojstva
blochnyh simmetrichnyh shifrov, predstavlennyh na ukrainskij
konkurs, Prikladnaya Radioelektronika, 2011, Vol. 10, No. 2,
pp. 135–140.
Dolgov V. I., Olejnikov R. V., Bolshakov A. UI. i dr
Kriptograficheskie svojstva umen’shenoj versii shifra «Kalina»,
Prikladnaya Radioelektronika, 2010, Vol.10, No. 3, pp. 135–
Gorbenko I. D., Lisickiy K. E., Denisov D. S. On Ciphers Coming
to a Stationary State of Random Substitution, Universal Journal
of Electrical and Electronic Engineering, 2, pp. 206–215.
DOI. 10.13189/ujeee. 2014.020409.
Lisickij K. E. Dinamicheskie pokazateli prihoda blochnyh shifrov
k sostoyaniyu sluchajnoj podstanovki, Izdatel’stvo dom LAP
LAMBERT Аcademic Publishing, 2014, 60 p. ISBN-13-978-3-
-28919-4.
Dolgov V. I., Lisickaya I. V., Lisickij K. E. Shifry so sluchajnumi
podstanjvkami, Trudy mejvedomstvennoj mejdynarodnoj
nauchno tegnicheskoj konferencii “Komp’uiternoe modelirovanie
v naukoiomkih tehnologiyah”. Har’kov, 28–31 maua 2014 y,
pp. 120–123.
Lisickij K. E. Snova ob optimal’nyh S-blokah, Prikladnaya
radioelektronika, HTURE, 2014, Том. 13, No. 3, pp. 208–212.
Gorbenko I. D., Lisickaya I. V., Lisickij K. E. Utochneonnye
pokazateli prihoda shifrov k sostoyaniyu sluchajnoj podstanovki,
Prikladnaya radioelektronika, 2014, Том. 13, No. 3, pp. 213–
Informacijni tehnologii. Kriptografichnyj zahyst informacii.
Algoritm symmetrichnogo blokovogo peretvorennya: ДСТУ
:2014. Кiev, Derzhspozhyvstandart Ukrainu, 2015, 238 p.
(Nacional’nyj standart Ukrainy).
Lisickaya I. V. Vyrozhdennye podstanovki, Radiotehnika, 2012,
Vyp. 171, pp. 31–38.
Lisickij K. E. On Maxima Distribution of Full Differentials and
Linear Hulls of Block Symmetric Ciphers , I. J. Computer Network
and Information Security, 2014, 1, 11–18 Published Online
November 2013 in MECS (http://www.mecs-press.org/).
DOI: 10.5815/ijcnis. 2014.01.02.
Markku-Juhani O. Saarinen Cryptographic Analysis of All 16-Bit
S-Boxes, Of the series Lecture Notes in Computer Science, 2008,
Volume 7118, pp. 118–133.
Tokareva N. N. Kvadratichnye approksimacii sgecial’nogo vida
dlya cheturehrozryadneh podstanovok v S-blokah, Prikladnaya
diskretnaya matematika, 2008, Vol. 1, No. 1, pp. 50–54.
Heys H. M. A Tutorial on Linear and Differential Cryptanalysis,
CRYPTOLOGIA, 2002, Vol. 26, No. 3, pp. 189–221.
Lisickaya I. V., Kovtun V. V. Ob uchastii S-blokov v formirovanii
maksimal’nyh znachenij linejnyh veroyatnostej blochnyh
simmetrichnyh shifrov, Mejvedomstvennyj nauchno tegnicheskoj
sbornik “Radiotehnika”, 2011, Vyp 166, pp. 17–25.
Lisickaya I. V., Kazimirov A. V. Ob uchastii S-blokov v
formirovanii maksimal’nyh znachenij differencial’nyh
veroyatnostej blochnyh simmetrichnyh shifrov, Proceedings
International Conference SAIT 2011, Kyiv, Ukraine, May 23–28,
, P. 459.
Olejnikov R. V., Oleshko O. I., Lisickij K. E. i dr. Differencial’nye
svojstva podstanovok, Prikladnaya diskretnaya matematika,
, Тom 9, No. 1, pp. 50–54.
Dolgov V. I., Lisickaya I. V., Oleshko O. I. Svojstva tablic linejnyh
approksimacihj sluchajnyh podstanovok, Prikladnaya
Radioelektronika, 2010, No. 3, pp. 334–340.
Downloads
How to Cite
Issue
Section
License
Copyright (c) 2018 K. E. Lisickiy
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
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.
-
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.
