Prikladnaya Diskretnaya Matematika. Supplement
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat. Suppl.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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
References:
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.
Document Type: Article
UDC: 519.7
Language: Russian
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
Citation in format AMSBIB
\Bibitem{Pes14}
\by A.~I.~Pestunov
\paper Influence of difference Hamming weight on it's propagation through arithmetic operations
\jour Prikl. Diskr. Mat. Suppl.
\yr 2014
\issue 7
\pages 49--51
\mathnet{http://mi.mathnet.ru/pdma169}
Linking options:
  • https://www.mathnet.ru/eng/pdma169
  • https://www.mathnet.ru/eng/pdma/y2014/i7/p49
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Prikladnaya Diskretnaya Matematika. Supplement
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024