Influence of difference Hamming weight on it's propagation through arithmetic operations

A. I. Pestunov

Prikladnaya Diskretnaya Matematika. Supplement, no. 7 (2014), pp. 49-51.

Résumé

Despite the fact that differential cryptanalysis is a widely used approach to cryptanalysis of iterative block ciphers, the authors of differential attacks rarely provide their strict mathematical reasoning. However, some steps in this direction have been already made. For instance, X. Lai and J. Massey (1991) suggested a model of so-called Markov iterative block cipher and formulated a hypothesis of stochastic equivalence. K. Nyberg and L. Knudsen (1994) showed that it is possible to create a cipher resistant to differential cryptanalysis, and, later, S. Vaudenay (2003) developed a model for creating such a cipher. G. P. Agibalov (2008) presented a general description of differential cryptanalysis for arbitrary iterative block ciphers with additive round keys. A. A. Selcuk analytically calculated probability of a differential attack success. A. I. Pestunov (2013) suggested a formalization of the basic differential cryptanalysis notions and used it for their systematization. One more important, though not thoroughly investigated problem, is finding out how does two-values difference propagate through operations used in block ciphers. The problem consists in estimating the probability that a pair of values with a fixed difference is transformed by an operation into another fixed difference. For some operations (e.g. bitwise rotation or XOR) this task is rather simple, while for some commonly used operations such as modulo addition, subtraction and multiplication, it is not a trivial one. When developing an attack on RC5, A. Biryukov and E. Kushilevitz (1998) claimed that a one-bit difference remains unchanged after modulo addition with the probability $1/2$ (or with the probability $1$ if the difference is located in the most significant bit). The claim has not been proved theoretically but the authors carried out some experiments verifying the attack. In works devoted to differential cryptanalysis of MARS and CAST-256, A. I. Pestunov (2009) used this fact referencing the paper of A. Biryukov and E. Kushilevitz and verifying developed attacks. Besides, in the second paper (about CAST-256) he used an experimentally found relation between the Hamming weight of a difference and the probability that this difference is preserved after modulo addition. In the current paper, the existence of this relation is proved theoretically. Exactly, it is proved that the difference of two values is preserved after their modulo addition or subtraction with a third randomly chosen value with the probability $2^{-h}$ or $2^{-(h-1)}$, if the most significant bit of the difference is equal to $0$ or to $1$ respectively. The obtained results extend the results obtained by A. I. Pestunov (2013) for one-bit differences.

Détail

Keywords: differential cryptanalysis, block cipher, Hamming weight.

Bibliographie

[1] Biham E., Shamir A., “Differential cryptanalysis of DES-like cryptosystems”, J. Cryptology, 4 (1991), 3–72 | DOI | MR | Zbl

[2] Lai X., Massey J., “Markov ciphers and differential cryptanalysis”, LNCS, 547, 1991, 17–38 | MR | Zbl

[3] Nyberg K., Knudsen L., “Provable security against a differential attack”, J. Cryptology, 8 (1995), 27–37 | MR | Zbl

[4] Vaudenay S., “Decorrelation: a theory for block cipher security”, J. Cryptology, 16 (2003), 249–286 | DOI | MR | Zbl

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

[6] Selcuk A. A., “On probability of success in linear and differential cryptanalysis”, J. Cryptology, 21 (2007), 131–147 | MR

[7] Pestunov A. I., “O svyazyakh mezhdu osnovnymi ponyatiyami raznostnogo analiza iterativnykh blochnykh shifrov”, Prikladnaya diskretnaya matematika. Prilozhenie, 2013, no. 6, 44–48

[8] Biryukov A., Kushilevitz E., “Improved cryptanalysis of RC5”, LNCS, 1403, 1998, 85–99 | Zbl

[9] Pestunov A. I., “Differentsialnyi kriptoanaliz blochnogo shifra MARS”, Prikladnaya diskretnaya matematika, 2009, no. 4, 56–63

[10] Pestunov A. I., “Differentsialnyi kriptoanaliz blochnogo shifra CAST-256”, Bezopasnost informatsionnykh tekhnologii, 2009, no. 4, 57–62

[11] Pestunov A. I., “O veroyatnosti protyazhki odnobitovoi raznosti cherez slozhenie i vychitanie po modulyu”, Prikladnaya diskretnaya matematika, 2012, no. 4, 53–60

[12] Pestunov A. I., “O vliyanii vesa Khemminga raznosti dvukh velichin na veroyatnost eë sokhraneniya posle slozheniya i vychitaniya”, Diskretnyi analiz i issledovanie operatsii, 20:5 (2013), 58–65 | MR