Geodesic
Statistical approximation theory for discrete functions with application in cryptanalysis of iterative block ciphers
Prikladnaâ diskretnaâ matematika, no. 3 (2010), pp. 51-68.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: iterative block ciphers, statistical approximations, linear cryptanalysis, nonlinear cryptanalysis
Mots-clés : DES. 
@article{PDM_2010_3_a4,
     author = {G. P. Agibalov and I. A. Pankratova},
     title = {Statistical approximation theory for discrete functions with application in cryptanalysis of iterative block ciphers},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {51--68},
     publisher = {mathdoc},
     number = {3},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2010_3_a4/}
}
TY  - JOUR
AU  - G. P. Agibalov
AU  - I. A. Pankratova
TI  - Statistical approximation theory for discrete functions with application in cryptanalysis of iterative block ciphers
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2010
SP  - 51
EP  - 68
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2010_3_a4/
LA  - ru
ID  - PDM_2010_3_a4
ER  - 
%0 Journal Article
%A G. P. Agibalov
%A I. A. Pankratova
%T Statistical approximation theory for discrete functions with application in cryptanalysis of iterative block ciphers
%J Prikladnaâ diskretnaâ matematika
%D 2010
%P 51-68
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2010_3_a4/
%G ru
%F PDM_2010_3_a4
G. P. Agibalov; I. A. Pankratova. Statistical approximation theory for discrete functions with application in cryptanalysis of iterative block ciphers. Prikladnaâ diskretnaâ matematika, no. 3 (2010), pp. 51-68. http://geodesic.mathdoc.fr/item/PDM_2010_3_a4/

[1] Agibalov G. P., “Metody resheniya sistem uravnenii nad konechnym polem”, Vestnik Tomskogo gosuniversiteta, 2006, Prilozhenie No 17, 4–9

[2] Matsui M., “Linear Cryptanalysis Method for DES Cipher”, LNCS, 765, 1993, 386–397

[3] Matsui M., “The First Experimental Cryptanalysis of the Data Encryption Standard”, LNCS, 839, 1994, 1–11 | Zbl

[4] Logachev O. A., Salnikov A. A., Yaschenko V. V., Bulevy funktsii v teorii kodirovaniya i kriptografii, MTsNMO, M., 2004

[5] Agibalov G. P., “Elementy teorii differentsialnogo kriptoanaliza iterativnykh blochnykh shifrov s additivnym raundovym klyuchom”, Prikladnaya diskretnaya matematika, 2008, no. 1, 34–42

[6] Balakin G. V., “Vvedenie v teoriyu sluchainykh sistem uravnenii”, Trudy po diskretnoi matematike, 1, TVP, M., 1997, 1–18 | MR | Zbl

[7] Agibalov G. P., “Logicheskie uravneniya v kriptoanalize generatorov klyuchevogo potoka”, Vestnik Tomskogo gosuniversiteta, 2003, Prilozhenie No 6, 31–41

[8] Buryakov M. L., Logachev O. A., “Ob urovne affinnosti bulevykh funktsii”, Diskretnaya matematika, 17:4 (2005), 98–107 | MR | Zbl