Upper-bound estimation of the average probabilities of integer-valued differentials in the composition of key adder, sub
- PDF / 118,887 Bytes
- 9 Pages / 595.276 x 793.701 pts Page_size
- 20 Downloads / 149 Views
UPPER-BOUND ESTIMATION OF THE AVERAGE PROBABILITIES OF INTEGER-VALUED DIFFERENTIALS IN THE COMPOSITION OF KEY ADDER, SUBSTITUTION BLOCK, AND SHIFT OPERATOR UDC 621.391:519.2:519.7
L. V. Kovalchuk
Abstract. The upper bounds for average probabilities of integer-valued round differentials are obtained for the composition of key adder, substitution block, and shift operator. Statistical distributions are obtained for parameters on which the probabilities depend. Keywords: non-Markov block ciphers, integer-valued differential cryptanalysis. INTRODUCTION Structurally, the majority of modern block ciphers (AES [1], GOST 28147 [2], “Kalina” [3], “Mukhomor” [4]) contain a composition of key adder, substitution block, and permutation operator linear over a field F2 or some its extension. Therefore, the assessment of the strength of ciphers against linear, bilinear, and various modifications of differential cryptanalysis [5–11] either reduces to the problem of upper-bound estimation of average probabilities of such compositions or contains it as a subproblem. The latter is completely solved in the following cases: — if bit-by-bit addition is implemented in the key adder and input and output differences in the round differential are considered with respect to the same operation (see the bibliography in [5, 7]); — if modulo 2ï addition is implemented in the key adder and input and output differences in the round differential are considered with respect to bit-by-bit addition [5–10]; — if modulo 2ï addition is implemented in the key adder, input and output differences are considered with respect to the same operation (such differential is called integer-valued [12, 13]), and either there is no permutation operator [6] or there is no substitution block and the permutation operator is a cyclic shift operator [14]. If the substitution block and permutation operator are nontrivial, obtaining the upper bounds of average probabilities of integer-valued differentials remains in abeyance. Note that the analytic complexities because of carry bit in modulo addition amplify since the permutation operator is not linear with respect to this operation. The present paper solves this problem for the case where either bit-by-bit addition or modulo 2ï addition is implemented in the key adder, the substitution block is arbitrary, and the permutation operator is a cyclic shift operator. Similarly to our study, to construct high-probability characteristic of hash function MD5, the papers [12, 14] propose to use integer-valued differentials, i.e., those where the difference operation is modulo 2ï addition because the hash function ÌD5 contains many transformations that are linear with respect to this operation. Berson [14] found a large number of high-probability differentials (whose probability is no less than 1/ 4 ) for mappings that are a composition of the modulo 2ï adder and shift operator. Integer-valued differentials were used both for cryptanalysis and to construct collisions of hash functions and in many other studies (for a rather complet
Data Loading...
