Citation: | Yiyi HAN, Caibing WANG, Zhongfeng NIU, et al., “SAT-Based Automatic Searching for Differential and Linear Trails: Applying to CRAX,” Chinese Journal of Electronics, vol. 33, no. 1, pp. 72–79, 2024 doi: 10.23919/cje.2022.00.313 |
[1] |
D. Hong, J. Sung, S. Hong, et al., “HIGHT: A new block cipher suitable for low-resource device,” in Proceedings of the 8th International Workshop on Cryptographic Hardware and Embedded Systems - CHES, Yokohama, Japan, pp. 46–59, 2006.
|
[2] |
D. Dinu, L. Perrin, A. Udovenko, et al., “Design strategies for ARX with provable bounds: SPARX and LAX,” in Proceedings of the 22nd International Conference on Advances in Cryptology, Hanoi, Vietnam, pp. 484–513, 2016.
|
[3] |
D. J. Wheeler and R. M. Needham, “TEA, a tiny encryption algorithm,” in Proceedings of the 2nd International Workshop on Fast Software Encryption, Leuven, Belgium, pp. 363–366, 1995.
|
[4] |
D. Wheeler and R. Needham, TEA Extensions. Cambridge: University of Cambridge, 1997.
|
[5] |
B. Koo, D. Roh, H. Kim, et al., “CHAM: A family of lightweight block ciphers for resource-constrained devices,” in Proceedings of the 20th International Conference on Information Security and Cryptology -ICISC 2017, Seoul, South Korea, pp. 3–25, 2018.
|
[6] |
R. Beaulieu, D. Shors, J. Smith, et al., “The SIMON and SPECK lightweight block ciphers,” in Proceedings of the 52nd Annual Design Automation Conference, San Francisco, CA, USA, article no.175, 2015.
|
[7] |
D. J. Bernstein, “The Salsa20 family of stream ciphers,” in New Stream Cipher Designs, M. Robshaw, O. Billet, Eds. Springer, Berlin, Germany, pp. 84–97, 2008.
|
[8] |
D. J. Bernstein, “ChaCha, a variant of Salsa20,” Workshop Record of SASC. Available at: https://www.mendeley.com/catalogue/27343fad-085e-3a7f-a002-7541bba412d6/, 2008.
|
[9] |
N. Ferguson, S. Lucks, B. Schneier, et al., The Skein Hash Function Family. NIST, 2010
|
[10] |
J. P. Aumasson, L. Henzen, W. Meier, et al., SHA-3 Proposal BLAKE. ETH Zürich, 2008
|
[11] |
C. Beierle, A. Biryukov, L. C. Dos Santos, et al., “Alzette: A 64-Bit ARX-box,” in Proceedings of the 40th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, CA, USA, pp. 419–448, 2020.
|
[12] |
E. Biham and A. Shamir, “Differential cryptanalysis of DES-like cryptosystems,” Journal of Cryptology, vol. 4, no. 1, pp. 3–72, 1991. doi: 10.1007/BF00630563
|
[13] |
M. Matsui, “Linear cryptanalysis method for DES cipher,” in Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques, Lofthus, Norway, pp. 386–397, 1994.
|
[14] |
A. Bogdanov and V. Rijmen, “Linear hulls with correlation zero and linear cryptanalysis of block ciphers,” Designs, Codes and Cryptography, vol. 70, no. 3, pp. 369–383, 2014. doi: 10.1007/s10623-012-9697-z
|
[15] |
L. R. Knudsen, “Truncated and higher order differentials,” in Proceedings of the Second International Workshop on Fast Software Encryption, Leuven, Belgium, pp. 196–211, 1995.
|
[16] |
E. Biham, A. Biryukov, and A. Shamir, “Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials,” in Proceedings of the 17th International Conference on Theory and Application of Cryptographic Techniques, Prague, Czech Republic, pp. 12–23, 1999.
|
[17] |
S. K. Langford and M. E. Hellman, “Differential-linear cryptanalysis,” in Proceedings of the 14th Annual International Cryptology Conference, Santa Barbara, CA, USA, pp. 17–25, 1994.
|
[18] |
M. Matsui, “On correlation between the order of s-boxes and the strength of DES,” in Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques, Perugia, Italy, pp. 366–375, 1995.
|
[19] |
N. Mouha, Q. J. Wang, D. W. Gu, et al., “Differential and linear cryptanalysis using mixed-integer linear programming,” in Proceedings of the 7th International Conference on Information Security and Cryptology, Beijing, China, pp. 57–76, 2011.
|
[20] |
S. B. Wu and M. S. Wang, Security Evaluation Against Differential Cryptanalysis for Block Cipher Structures, in Press, 2011.
|
[21] |
S. W. Sun, L. Hu, M. Q. Wang, et al., Towards Finding the Best Characteristics of Some Bit-Oriented Block Ciphers and Automatic Enumeration of (Related-Key) Differential and Linear Characteristics with Predefined Properties, in Press, 2014.
|
[22] |
S. W. Sun, L. Hu, P. Wang, 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 the 20th International Conference on Advances in Cryptology, Kaoshiung, China, pp. 158–178, 2014.
|
[23] |
Y. X. Cui, H. Xu, W. F. Qi, “MILP-based linear attacks on round-reduced GIFT,” Chinese Journal of Electronics, vol. 31, no. 1, pp. 89–98, 2022. doi: 10.1049/cje.2020.00.113
|
[24] |
M. Soos, K. Nohl, and C. Castelluccia, “Extending SAT solvers to cryptographic problems,” in Proceedings of the 12th International Conference on Theory and Applications of Satisfiability Testing, Swansea, UK, pp. 244–257, 2009.
|
[25] |
S. Kölbl, G. Leander, and T. Tiessen, “Observations on the SIMON block cipher family,” in Proceedings of the 35th Annual Cryptology Conference on Advances in Cryptology, Santa Barbara, CA, USA, pp. 161–185, 2015.
|
[26] |
Y. W. Liu, Q. J. Wang, and V. Rijmen, “Automatic search of linear trails in ARX with applications to SPECK and Chaskey,” in Proceedings of the 14th International Conference on Applied Cryptography and Network Security, Guildford, UK, pp. 485–499, 2016.
|
[27] |
L. Sun, W. Wang, and M. Q. Wang, “Automatic search of bit-based division property for ARX ciphers and word-based division property,” in Proceedings of the 23rd International Conference on Advances in Cryptology, Hong Kong, China, pp. 128–157, 2017.
|
[28] |
A. Biryukov, V. Velichkov, and Y. Le Corre, “Automatic search for the best trails in ARX: Application to block cipher SPECK,” in Proceedings of the 23rd International Conference on Fast Software Encryption, Bochum, Germany, pp. 289–310, 2016.
|
[29] |
K. Fu, M. Q. Wang, Y. H. Guo, et al., “MILP-based automatic search algorithms for differential and linear trails for speck,” in Proceedings of the 23rd International Conference on Fast Software Encryption, Bochum, Germany, pp. 268–288, 2016.
|
[30] |
Y. W. Liu, S. W. Sun, and C. Li, “Rotational cryptanalysis from a differential-linear perspective,” in Proceedings of the 40th Annual International Conference on Advances in Cryptology, Zagreb, Croatia, pp. 741–770, 2021.
|
[31] |
Z. F. Niu, S. W. Sun, Y. W. Liu, et al., “Rotational differential-linear distinguishers of ARX Ciphers with arbitrary output linear masks,” in Proceedings of the 42nd Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, CA, USA, pp. 3–32, 2022.
|
[32] |
Z. Xu, Y. Q. Li, and M. S. Wang, “Security analysis of Alzette,” Journal of Cryptologic Research, vol. 9, no. 4, pp. 698–708, 2022. (in Chinese) doi: 10.13868/j.cnki.jcr.000543
|
[33] |
L. Sun, W. Wang, and M. Q. Wang, “Accelerating the search of differential and linear characteristics with the sat method,” IACR Transactions on Symmetric Cryptology, vol. 2021, no. 1, pp. 269–315, 2021. doi: 10.46586/TOSC.V2021.I1.269-315
|
[34] |
B. Sun, Z. Q. Liu, V. Rijmen, et al., “Links among impossible differential, integral and zero correlation linear cryptanalysis,” in Proceedings of the 35th Annual Cryptology Conference on Advances in Cryptology, Santa Barbara, CA, USA, pp. 95–115, 2015.
|
[35] |
H. Lipmaa and S. Moriai, “Efficient algorithms for computing differential properties of addition,” in Proceedings of the 8th International Workshop on Fast Software Encryption, Yokohama, Japan, pp. 336–350, 2002.
|
[36] |
K. Nyberg and J. Wallén, “Improved linear distinguishers for SNOW 2.0,” in Proceedings of the 13th International Workshop on Fast Software Encryption, Graz, Austria, pp. 144–162, 2006.
|
[37] |
J. Wallén, “Linear approximations of addition modulo 2n,” in Proceedings of the 10th International Workshop on Fast Software Encryption, Lund, Sweden, pp. 261–273, 2003.
|
[38] |
E. Schulte-Geers, “On CCZ-equivalence of addition mod 2n,” Designs, Codes and Cryptography, vol. 66, no. 1-3, pp. 111–127, 2013. doi: 10.1007/s10623-012-9668-4
|
[39] |
N. Mouha and B. Preneel, Towards Finding Optimal Differential Characteristics for ARX: Application to Salsa20. 2013
|
[40] |
A. Biere, “CaDiCaL at the SAT Race 2019,” in Proceedings of the SAT Race 2019 – Solver and Benchmark Descriptions, M. Heule, M. Järvisalo, and M. Suda, Ed. University of Helsinki, Helsinki, pp. 8–9, 2019.
|
[41] |
J. P. Marques Silva and K. A. Sakallah, “GRASP - A new search algorithm for satisfiability,” in Proceedings of the International Conference on Computer Aided Design, San Jose, CA, USA, pp. 220–227, 1996.
|
[42] |
R. J. Bayardo and R. C. Schrag, “Using CSP look-back techniques to solve real-world SAT instances,” in Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Conference on Innovative Applications of Artificial Intelligence, Providence, RL, USA, pp. 203–208, 1997.
|