DEGENERATE S-BOXES

K. E. Lisickiy

Abstract


Context. S-blocks are one of the main transformations of many ciphers, and the search for S-boxes with improved cryptographic indices
a 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.

Keywords


methodology of evaluation of resistance; degenerate substitution; differential indicators; linear indicators.

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.


GOST Style Citations


1. Долгов В. И. Методология оценки стойкости блочных симметричных шифров к атакам дифференциального и линейного криптоанализа: монография / В. И. Долгов, И. В. Лисицкая. – Харьков : Издательство «Форт», 2013. – 420 с.
2. Saier W. Nonlinearity criteria for cryptographic functions /
W. Saier, O. Staffelbach // In Advances in Cryptology. –
EUROCRYPT’89, Lecture Notes in Computer Science, Springer-
Verlag. – 1990. – Vol. 434. – P. 549–562.
3. Pasalic E. Further Results on the Relation between Nonlinearity and Resiliency for BF / E. Pasalic, T. Johansson // IEEE Trans. on Information Theory. – 2002. – Vol. 48, No. 7, July. – P. 1825–1834.
4. Sillan W. An effective genetic algorithm for finding highly
nonlinear Boolean functions / W. Sillan, A. Clark and E. Dawson // In First International Conference on Information and
Communications Security, in Lecture Notes in Computer Science, Springer Verlag. – 1997. – Number 1334. – P. 149–158.
5. Sillan W. Smart Hill Climbing Finds Better Boolean Functions / W. Sillan, A. Clark and E. Dawson // Workshop on Selected Areas in Cryptography (SAC’97) Workshop Record. – 1997. – P. 50.
6. Seberry J. Hadamar Matrices, Bent Functions and Cryptography / J. Seberry and X. Zhang. // In J. H. Dinitz and D. R. Stinson, editors, Contemporary Design Theory: A Collection of Surveys, chapter 11, John Wiley and Sons, Inc. – 1995. – P. 431–559.
7. Исследование аналитических и статистических свойств булевых функций криптоалгоритма Rijndael (FIPS 197) /
[И. Д. Горбенко, А. В. Потий, Ю. А. Избенко и др.] // Радио-
техника. Всеукраинский межведомственный научно-технический сборник. – 2004. – № 126. – С. 132–138.
8. New constructions of resilient and correlation immune Boolean functions achieving upper bounds of nonlinearity / [E. Pasalic, T. Johansson, S. Saitra et al.] // In Workshop of Coding and Cryptography, Electronic Notes in Discrete Mathematics. Elsevier, January 2001.
9. Sillan W. Heuristic Design of Cryptographically Strong Balanced Boolean Functions / W. Sillan, A. Clark and E. Dawson. // In Advances in Cryptology ЕUROCRYPT’98 Springer Verlag LNCS 1403. – 1998. – P. 489–499.
10. Saity S. Construction of Cryptographically Important Boolean Functions / S. Saity and T. Johansson // In INDOCRYPT 2002, Volume 2551 in Lecture Notes in Computer Science, Springer Verlag – 2002.– P. 234–245.
11. Лисицкая И. В. Методология оценки стойкости блочных симметричных криптопреобразований на основе уменьшенных моделей: дис. … докт. техн. наук: 05.13.05 / Лисицкая Ирина Викторовна. – Харьков, 2012. – 293 с.
12. Долгов В. И. Дифференциальные свойства блочных симметричных шифров, представленных на украинский конкурс. / В. И. Долгов, А. А. Кузнецов, С. А. Исаев. // Электронное моделирование. – 2011.– Т. 33, № 6. – С. 81–99.
13 Кузнецов А. А. Линейные свойства блочных симметричных
шифров, представленных на украинский конкурс / А. А. Куз-
нецов, И. В. Лисицкая, С. А. Исаев // Прикладная радиоэлектроника. – 2011. – Т.10, №2 – С. 135–140.
14. Криптографичекие свойства уменьшенной версии шифра
«Калина» / [В. И Долгов, Р. В Олейников, А. Ю. Большаков
и др.] // Прикладная радиоэлектроника. – 2010. – № 3. –
С. 349–354.
15. Gorbenko I. D. On Ciphers Coming to a Stationary State of
Random Substitution / I. D. Gorbenko, K. E. Lisickiy, D. S. Denisov // Universal Journal of Electrical and Electronic Engineering, 2, P. 206–215. DOI. 10.13189/ujeee. 2014.020409.
16. Лисицкий К. Е. Динамические показатели прихода блочных шифров к состоянию случайной подстановки / К. Е. Лисицкий / / Издательский дом LAP LAMBERT Аcademic Publishing, 2014. – 60 с. ISBN-13. 978-3-659-28919-4.
17. Долгов В. И. Шифры со случайными подстановками /
В. И. Долгов, И. В. Лисицкая, К. Е. Лисицкий // Труды между-
народной научно-технической конференции «Компьютерное
моделирование в наукоемких технологиях», Харьков, 28–31
мая 2014 г. – С. 120–123.
18. Лисицкий К. Е. Снова об оптимальных S-блоках / К. Е. Лисицкий // Прикладная радиоэлектроника. – 2014. – Том. 13, № 3.– С. 208–212.
19. Горбенко И. Д. Уточненные показатели прихода шифров к состоянию случайной подстановки / И. Д. Горбенко,
И. В. Лисицкая, К. Е. Лисицкий // Прикладная радиоэлектро-
ника. – 2014. – Том. 13, № 3.– С. 213–216.
20. Інформаційні технології. Криптографічний захист інформації.
Алгоритм симетричного блокового перетворення: ДСТУ
7624:2014. – К. : Держспоживстандарт України, 2015. –
238 с. – (Національний стандарт України).
21. Лисицкая И. В. Вырожденные подстановки / И. В. Лисицкая // Радиотехника. – 2012. – Вып. 171 – С. 31–38.
22. Лисицкая И. В. Уточненная математическая модель случайной подстановки / И. В. Лисицкая, Е. В. Мельничук // Автоматизированные системы управления и приборы автоматики – 2013.– Вып. 162. – С. 22–34.
23. Juhani M. Cryptographic Analysis of All 16-Bit S-Boxes / MarkkuJuhani O. Saarinen // Volume 7118 of the series Lecture Notes in Computer Science. – 2008. – P. 118–133.
24. Токарева Н. Н. Квадратичные аппроксимации специального вида для четырехразрядных подстановок в S-блоках / Н. Н. Токарева // Прикладная дискретная математика. – 2008. – Т. 1, № 1. – С. 50–54.
25. Heys H. M. A Tutorial on Linear and Differential Cryptanalysis / H. M. Heys // CRYPTOLOGIA. – 2002. – 26, № 3. – P. 189–221.




DOI: https://doi.org/10.15588/1607-3274-2018-1-15



Copyright (c) 2018 K. E. Lisickiy

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
Zaporizhzhya National Technical University, 
Zhukovskiy street, 64, Zaporizhzhya, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.