STATISTICAL APPROXIMATION THEORYFOR DISCRETE FUNCTIONS WITH APPLICATION IN CRYPTANALY-SIS OF ITERATIVE BLOCK CIPHERS | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2010. № 3(9).

FOR DISCRETE FUNCTIONS WITH APPLICATION IN CRYPTANALY-SIS OF ITERATIVE BLOCK CIPHERS. A statistical approximation of a discrete function is defined as a Boolean equation being satisfied with a probability and accompanied by a Boolean function being statisticaly independent on a subset of variables. Properties of this notion are studied. A constructive test for the statistical independence is formulated. Methods for designing linear ststistical approximations for functions used in iterative block symmetric ciphers are considered. Cryptanalysis algorithms based on solving systems of statistical approximations being linear or nonlinear ones are proposed for symmetric ciphers. The algorithms are based on the maximum likelihood method. Definitions, methods and algorithms are demonstrated by examples taken from DES. Paticularly, it is shown that one of the cryptanalysis algorithms proposed in the paper allows to find 34 key bits for full 16-round DES being based on two known nonlinear approximate equations providing 26 key bits only by Matsui's algorithm.
Download file
Counter downloads: 69
  • Title STATISTICAL APPROXIMATION THEORYFOR DISCRETE FUNCTIONS WITH APPLICATION IN CRYPTANALY-SIS OF ITERATIVE BLOCK CIPHERS
  • Headline STATISTICAL APPROXIMATION THEORYFOR DISCRETE FUNCTIONS WITH APPLICATION IN CRYPTANALY-SIS OF ITERATIVE BLOCK CIPHERS
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 3(9)
  • Date:
  • DOI
Keywords
DES, nonlinear cryptanalysis, linear cryptanalysis, statistical approximations, iterative block ciphers, DES, нелинейный криптоанализ, линейный криптоанализ, криптоанализ, итеративные блочные шифры, статистические аналоги функций, статистическая независимость
Authors
References
Буряков М. Л., Логачев О. А. Об уровне аффинности булевых функций // Дискретная математика. 2005. Т. 17. Вып. 4. С. 98-107.
Балакин Г. В. Введение в теорию случайных систем уравнений // Труды по дискретной математике. Т. 1. М.: ТВП, 1997. С. 1-18.
Агибалов Г. П. Логические уравнения в криптоанализе генераторов ключевого потока // Вестник Томского госуниверситета. Приложение. 2003. № 6. С. 31-41.
Агибалов Г. П. Элементы теории дифференциального криптоанализа итеративных блочных шифров с аддитивным раундовым ключом // Прикладная дискретная математика. 2008. №1. С. 34-43.
Логачев О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптографии. М.: МЦНМО, 2004.
Matsui M. Linear Cryptanalysis Method for DES Cipher // LNCS. 1993. V. 765. P. 386-397.
Matsui M. The First Experimental Cryptanalysis of the Data Encryption Standard // LNCS. 1994. V. 839. P. 1-11.
Агибалов Г. П. Методы решения систем уравнений над конечным полем // Вестник Томского госуниверситета. Приложение. 2006. №17. С. 4-9.
 STATISTICAL APPROXIMATION THEORYFOR DISCRETE FUNCTIONS WITH APPLICATION IN CRYPTANALY-SIS OF ITERATIVE BLOCK CIPHERS | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2010. № 3(9).
STATISTICAL APPROXIMATION THEORYFOR DISCRETE FUNCTIONS WITH APPLICATION IN CRYPTANALY-SIS OF ITERATIVE BLOCK CIPHERS | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2010. № 3(9).