Improved MILP Modeling for Automatic Security Evaluation and Application to FOX

Kexin QIAO; Lei HU; Siwei SUN; Xiaoshuang MA; Haibin KAN

doi:10.1587/transfun.E98.A.72

IEICE TRANSACTIONS on Fundamentals

Improved MILP Modeling for Automatic Security Evaluation and Application to FOX

Kexin QIAO, Lei HU, Siwei SUN, Xiaoshuang MA, Haibin KAN

Full Text Views

0

Cite this

Summary :

Counting the number of differentially active S-boxes is of great importance in evaluating the security of a block cipher against differential attack. Mouha et al. proposed a technique based on Mixed-Integer Linear Programming (MILP) to automatically calculate a lower bound of the number of differentially active S-boxes for word-oriented block ciphers, and applied it to symmetric ciphers AES and Enocoro-128v2. Later Sun et al. extended the method by introducing bit-level representations for S-boxes and new constraints in the MILP problem, and applied the extended method to PRESENT-80 and LBlock. This kind of methods greatly depends on the constraints in the MILP problem describing the differential propagation of the block cipher. A more accurate description of the differential propagation leads to a tighter bound on the number of differentially active S-boxes. In this paper, we refine the constraints in the MILP problem describing XOR operations, and apply the refined MILP modeling to determine a lower bound of the number of active S-boxes for the Lai-Massey type block cipher FOX in the model of single-key differential attack, and obtain a tighter bound in FOX64 than existing results. Experimental results show that 6, instead of currently known 8, rounds of FOX64 is strong enough to resist against basic single-key differential attack since the differential characteristic probability is upper bounded by 2^-64, and thus the maximum differential characteristic probability of 12-round FOX64 is upper bounded by 2^-128, where 128 is the key-length of FOX64. We also get the lower bound of the number of differentially active S-boxes for 5-round FOX128, and proved the security of the full-round FOX128 with respect to single-key differential attack.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E98-A No.1 pp.72-80

Publication Date: 2015/01/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E98.A.72

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category: Symmetric Key Based Cryptography

Authors

Kexin QIAO
  Institute of Information Engineering, Chinese Academy of Sciences,Chinese Academy of Sciences,University of Chinese Academy of Sciences
Lei HU
  Institute of Information Engineering, Chinese Academy of Sciences,Chinese Academy of Sciences
Siwei SUN
  Institute of Information Engineering, Chinese Academy of Sciences,Chinese Academy of Sciences
Xiaoshuang MA
  Institute of Information Engineering, Chinese Academy of Sciences,Chinese Academy of Sciences,University of Chinese Academy of Sciences
Haibin KAN
  School of Computer Science, Fudan University

Keyword

FOX block cipher, differential attack, active S-box, mixed-integer linear programming

Cite this

Copy

Kexin QIAO, Lei HU, Siwei SUN, Xiaoshuang MA, Haibin KAN, "Improved MILP Modeling for Automatic Security Evaluation and Application to FOX" in IEICE TRANSACTIONS on Fundamentals, vol. E98-A, no. 1, pp. 72-80, January 2015, doi: 10.1587/transfun.E98.A.72.
Abstract: Counting the number of differentially active S-boxes is of great importance in evaluating the security of a block cipher against differential attack. Mouha et al. proposed a technique based on Mixed-Integer Linear Programming (MILP) to automatically calculate a lower bound of the number of differentially active S-boxes for word-oriented block ciphers, and applied it to symmetric ciphers AES and Enocoro-128v2. Later Sun et al. extended the method by introducing bit-level representations for S-boxes and new constraints in the MILP problem, and applied the extended method to PRESENT-80 and LBlock. This kind of methods greatly depends on the constraints in the MILP problem describing the differential propagation of the block cipher. A more accurate description of the differential propagation leads to a tighter bound on the number of differentially active S-boxes. In this paper, we refine the constraints in the MILP problem describing XOR operations, and apply the refined MILP modeling to determine a lower bound of the number of active S-boxes for the Lai-Massey type block cipher FOX in the model of single-key differential attack, and obtain a tighter bound in FOX64 than existing results. Experimental results show that 6, instead of currently known 8, rounds of FOX64 is strong enough to resist against basic single-key differential attack since the differential characteristic probability is upper bounded by 2^-64, and thus the maximum differential characteristic probability of 12-round FOX64 is upper bounded by 2^-128, where 128 is the key-length of FOX64. We also get the lower bound of the number of differentially active S-boxes for 5-round FOX128, and proved the security of the full-round FOX128 with respect to single-key differential attack.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E98.A.72/_p

Copy

@ARTICLE{e98-a_1_72,
author={Kexin QIAO, Lei HU, Siwei SUN, Xiaoshuang MA, Haibin KAN, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Improved MILP Modeling for Automatic Security Evaluation and Application to FOX},
year={2015},
volume={E98-A},
number={1},
pages={72-80},
abstract={Counting the number of differentially active S-boxes is of great importance in evaluating the security of a block cipher against differential attack. Mouha et al. proposed a technique based on Mixed-Integer Linear Programming (MILP) to automatically calculate a lower bound of the number of differentially active S-boxes for word-oriented block ciphers, and applied it to symmetric ciphers AES and Enocoro-128v2. Later Sun et al. extended the method by introducing bit-level representations for S-boxes and new constraints in the MILP problem, and applied the extended method to PRESENT-80 and LBlock. This kind of methods greatly depends on the constraints in the MILP problem describing the differential propagation of the block cipher. A more accurate description of the differential propagation leads to a tighter bound on the number of differentially active S-boxes. In this paper, we refine the constraints in the MILP problem describing XOR operations, and apply the refined MILP modeling to determine a lower bound of the number of active S-boxes for the Lai-Massey type block cipher FOX in the model of single-key differential attack, and obtain a tighter bound in FOX64 than existing results. Experimental results show that 6, instead of currently known 8, rounds of FOX64 is strong enough to resist against basic single-key differential attack since the differential characteristic probability is upper bounded by 2^-64, and thus the maximum differential characteristic probability of 12-round FOX64 is upper bounded by 2^-128, where 128 is the key-length of FOX64. We also get the lower bound of the number of differentially active S-boxes for 5-round FOX128, and proved the security of the full-round FOX128 with respect to single-key differential attack.},
keywords={},
doi={10.1587/transfun.E98.A.72},
ISSN={1745-1337},
month={January},}

Copy

TY - JOUR
TI - Improved MILP Modeling for Automatic Security Evaluation and Application to FOX
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 72
EP - 80
AU - Kexin QIAO
AU - Lei HU
AU - Siwei SUN
AU - Xiaoshuang MA
AU - Haibin KAN
PY - 2015
DO - 10.1587/transfun.E98.A.72
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E98-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2015
AB - Counting the number of differentially active S-boxes is of great importance in evaluating the security of a block cipher against differential attack. Mouha et al. proposed a technique based on Mixed-Integer Linear Programming (MILP) to automatically calculate a lower bound of the number of differentially active S-boxes for word-oriented block ciphers, and applied it to symmetric ciphers AES and Enocoro-128v2. Later Sun et al. extended the method by introducing bit-level representations for S-boxes and new constraints in the MILP problem, and applied the extended method to PRESENT-80 and LBlock. This kind of methods greatly depends on the constraints in the MILP problem describing the differential propagation of the block cipher. A more accurate description of the differential propagation leads to a tighter bound on the number of differentially active S-boxes. In this paper, we refine the constraints in the MILP problem describing XOR operations, and apply the refined MILP modeling to determine a lower bound of the number of active S-boxes for the Lai-Massey type block cipher FOX in the model of single-key differential attack, and obtain a tighter bound in FOX64 than existing results. Experimental results show that 6, instead of currently known 8, rounds of FOX64 is strong enough to resist against basic single-key differential attack since the differential characteristic probability is upper bounded by 2^-64, and thus the maximum differential characteristic probability of 12-round FOX64 is upper bounded by 2^-128, where 128 is the key-length of FOX64. We also get the lower bound of the number of differentially active S-boxes for 5-round FOX128, and proved the security of the full-round FOX128 with respect to single-key differential attack.
ER -

IEICE TRANSACTIONS on Fundamentals