MILP/MIQCP-Based Differential-Linear Cryptanalysis on CHAM-64/128
摘要
Differential-linear (DL) cryptanalysis decomposes a cipher E into three parts, that is the differential part \(E_1\) , the middle part \(E_m\) , and the linear part \(E_2\) . The exact correlation of a DL distinguisher is the sum of the correlations of all DL trails, which needs to exhaust the output difference of \(E_1\) and the input mask of \(E_2\) . However, the DL distinguishers that searched by existing automated models only consist of a single high-correlation DL trail. In addition, these models are challenging to search for certain DL distinguishers that involve a large number of rounds, due to limitations in computing resources. In this paper, we propose an automated tool based on a divide-and-conquer strategy to consider both the number of rounds and the accuracy of the correlation. Specifically, we first prepare a large number of \(r_d\) -round differential characteristics and \(r_l\) -round linear trails, whose probabilities and correlations fall within specific ranges. Then, by considering all combinations of the aforementioned differential characteristics and linear trails, and connecting them through an \(r_m\) -round middle part, we derive \((r_d + r_m + r_l)\) -round DL trails and preserve the input difference and output mask pairs \((\varDelta , \varGamma )\) of the trails with competitive correlations. Finally, the correlations of multiple DL trails are clustered to more accurately evaluate the correlation of the candidate distinguishers, and the distinguisher with the highest correlation is selected. We apply our automated tools to search for DL distinguishers of CHAM-64/128. As a result, we find DL distinguishers covering from 9 to 41 rounds. To the best of our knowledge, our 41-round distinguisher is the longest distinguisher for CHAM-64/128 in the single-key scenario. Furthermore, we present a 45-round DL attack on CHAM-64/128 based on eight 41-round distinguishers. The data and time complexities of our attack are \(2^{60.2}\) and \(2^{117.71}\) , respectively.