logo

Journals Books
Advanced Search
Sign in Register

中文

SCIENCE CHINA Information Sciences
Download PDF
SCIENCE CHINA Information Sciences, Volume 64 , Issue 2 : 129103(2021) https://doi.org/10.1007/s11432-018-1506-4

New automatic tool for finding impossible differentials and zero-correlation linear approximations

Tingting CUI 1, Shiyao CHEN 2, Kai FU 4, Meiqin WANG 2, Keting JIA 3,*
More info
  • ReceivedNov 7, 2018
  • AcceptedAug 2, 2019
  • PublishedOct 27, 2020
Previous Table of Contents Next
Share
Rating

Abstract

There is no abstract available for this article.


Acknowledgment

This work was supported by National Key Research and Development Program of China (Grant No. 2017YFA0303903), National Cryptography Development Fund (Grant Nos. MMJJ20170121, MMJJ20170102), Zhejiang Province Key RD Project (Grant No. 2017C01062), National Natural Science Foundation of China (Grant Nos. 61572293, 61502276, 61692276), Major Scientific and Technological Innovation Projects of Shandong Province (Grant No. 2017CXGC0704), and National Natural Science Foundation of Shandong Province (Grant No. ZR2016FM22).


Supplement

Appendixes A and B.


References

[1] Sun S W, Hu L, Wang P, et al. Automatic security evaluation and (related-key) differential characteristic search: application to SIMON, PRESENT, LBlock, DES (L) and other bit-oriented block ciphers. In: Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Taiwan, 2014. 8873: 158--178. Google Scholar

[2] Fu K, Wang M Q, Guo Y H, et al. MILP-based automatic search algorithms for differential and linear trails for speck. In: Proceedings of International Workshop on Fast Software Encryption, Bochum, 2016. 9783: 268--288. Google Scholar

[3] Lu J Q. Cryptanalysis of reduced versions of the HIGHT block cipher from CHES 2006. In: Proceedings of International Conference on Information Security and Cryptology, Seoul, 2007. 4817: 11--26. Google Scholar

[4] Zhang K, Guan J, Hu B. Automatic search of impossible differentials and zero-correlation linear hulls for ARX ciphers. China Communications, 2018, 15: 54--66. Google Scholar

[5] Wen L, Wang M, Bogdanov A. Multidimensional zero-correlation attacks on lightweight block cipher HIGHT: Improved cryptanalysis of an ISO standard. Inf Processing Lett, 2014, 114: 322-330 CrossRef Google Scholar

[6] Wen L, Wang M Q. Integral zero-correlation distinguisher for ARX block cipher, with application to SHACAL-2. In: Proceedings of Australasian Conference on Information Security and Privacy, Wollongong, 2014. 8544: 454--461. Google Scholar

[7] Hong S, Kim J, Kim G, et al. Impossible differential attack on 30-round SHACAL-2. In: Proceedings of International Conference on Cryptology in India, New Delhi, 2003. 2904: 97--106. Google Scholar

[8] Hong D, Lee J -K, Kim D -C, et al. LEA: a 128-bit block cipher for fast encryption on common processors. In: Proceedings of International Workshop on Information Security Applications, Jeju Island, 2013. 8267: 3--27. Google Scholar

[9] Wen L, Wang M Q, Zhao J Y. Related-Key Impossible Differential Attack on Reduced-Round LBlock. J Comput Sci Technol, 2014, 29(1): 165-176 doi: 10.1007/s11390-013-1419-0. Google Scholar

  •   

    Algorithm 1 General impossible differential search process

    // Step 1: Construct the MILP model.

    Represent the input and output differences for each operation as binary variables.

    Link the binary variables by adding linear inequalities for each target cipher operation.

    // Step 2: Find all the impossible differentials within a given set of input and output differences.

    Determine the sets of input differences $\Delta$ and output differences $\Gamma$.

    for input difference $\Delta~x_i~\in~\Delta$

    for output difference $\Delta~y_j\in~\Gamma$

    Add all constraints related to the current input and output differences to the MILP model.

    Attempt to solve the model.

    if solver found a solution then

    // The current input and output differences represent a possible differential.

    Break;

    else

    // The current input and output differences yield an impossible differential.

    Store the current input and output differences.

    end if

    end for

    end for

  • Table 1  

    Table 1Summary of results for the HIGHT, SHACAL-2, LEA, and LBlock ciphers

    Cipher Type Round Reference
    HIGHT Impossible differential 16 [2]
    Impossible differential 17 [3]
    Impossible differential 17 Ours
    Zero-correlation linear approximation 16 [4]
    Zero-correlation linear approximation 17 [3]
    Zero-correlation linear approximation 17 Ours
    SHACAL-2 Zero-correlation linear approximation 12 [5]
    Impossible differential 14 [6]
    Impossible differential 15 Ours
    LEA Zero-correlation linear approximation 7 [7]
    Zero-correlation linear approximation 9 [3]
    Zero-correlation linear approximation 10 Ours
    LBlock Related-key impossible differential$^{\rm~a)}$ 16 [8]
    Related-key impossible differential 16 Ours