|
Prikladnaya Diskretnaya Matematika. Supplement, 2014, Issue 7, Pages 49–51
(Mi pdma169)
|
|
|
|
Mathematical Methods of Cryptography
Influence of difference Hamming weight on it's propagation through arithmetic operations
A. I. Pestunovab a Institute of Computing Technologies, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b Novosibirsk State University for Economics and Management, Novosibirsk
Abstract:
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.
Keywords:
differential cryptanalysis, block cipher, Hamming weight.
Citation:
A. I. Pestunov, “Influence of difference Hamming weight on it's propagation through arithmetic operations”, Prikl. Diskr. Mat. Suppl., 2014, no. 7, 49–51
Linking options:
https://www.mathnet.ru/eng/pdma169 https://www.mathnet.ru/eng/pdma/y2014/i7/p49
|
|