SAT-Based Differential Analysis of the Feistel Block Cipher GRANULE

Laifeng Lu

¹School of Mathematics and Statistics, Shaanxi Normal University, Xi’an, 710119, China

²School of Innovation and Entrepreneurship, North University of China, Taiyuan, 030051, China

*Corresponding author

Given the critical role lightweight block ciphers play in resource restricted scenarios, it is essential to rigorously evaluate their security against classical cryptanalytic methods such as differential analysis. Accordingly, this paper employs automated search techniques to conduct a comprehensive investigation of the differential behavior of the lightweight Feistel-structured cipher GRANULE. In the context of differential cryptanalysis, the core of evaluating a cipher’s security lies in identifying high-probability differential characteristics. We formulate the search for such characteristics as a boolean satisfiability problem (SAT), express the propagation of differences through the cipher in conjunctive normal form (CNF), invoke the SAT solver CaDiCaL to determine satisfiability, and recover the corresponding differential characteristics from the obtained solutions. Using this approach, we search for high-probability differential characteristics of GRANULE, and successfully obtain both the minimum number of active S-boxes over all rounds and a 15-round differential characteristic with probability 2−60. Based on this characteristic, we further mount a 19-round key-recovery attack and provide a detailed complexity analysis. Among them, the data complexity is 2144, the time complexity is 2144 19-round encryptions, and the memory complexity is 285. Our results significantly improve the previously known differential cryptanalysis of GRANULE. And the proposed method is also applicable to other Feistel ciphers with similar structures.

Lightweight Block Cipher, Feistel Structure, GRANULE, Differential Analysis, Automated Search, SAT

Ruichen Feng, Yueyuan Xi, Hongmin Liu, and Laifeng Lu (2025). SAT-Based Differential Analysis of the Feistel Block Cipher GRANULE. Journal of Networking and Network Applications, Volume 5, Issue 3, pp. 130–136. https://doi.org/10.33969/J-NaNA.2025.050303.

[1] G. Li, J. Xu, Q. Wang et al., Survey of IoT Forensics, Journal of Computer Engineering & Applications, vol. 58, no. 8, 2022.

[2] E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryp-tosystems, Journal of Cryptology, vol. 4, no. 1, pp. 3–72, 1991.

[3] L. R. Knudsen, Truncated and higher order differentials, in Fast Soft-ware Encryption: Second International Workshop, Springer, pp. 196–211, 1994.

[4] D. Wagner, The Boomerang Attack, in Fast Software Encryption: 6th International Workshop, Springer, pp. 156–170, 1999.

[5] E. Biham, A. Biryukov and A. Shamir, Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials, in Advances in Cryptology—EUROCRYPT’99, Springer, pp. 12–23, 1999.

[6] Y. Xi, R. Feng, Y. Zhou, H. Liu and L. Lu, Analysis methods for block ciphers under noise interference: a case study of XOR operations, in Proceedings of the 2025 International Conference on Satellite Internet (SAT-NET 2025), Hangzhou, China, 2025, accepted.

[7] M. Tian, J. Zhou, Z. Qin, B. Liu, L. Lu and H. Liu, Design of a fusion scheme for linear analysis methods under differences in grouped cipher structures, in Proceedings of the 2025 International Conference on Networking and Network Applications (NaNA 2025), Tashkent City: NaNA, 2025, doi:10.1109/NaNA66698.2025.00038.

[8] J. Zhou, M. Tian, Z. Wu, L. Lu and Y. Zhou, Recent ad-vances in differential cryptanalysis of block ciphers, in Pro-ceedings of the 2025 International Conference on Networking and Network Applications (NaNA 2025), Tashkent City: NaNA, 2025, doi:10.1109/NaNA66698.2025.00069.

[9] A. Biere, T. Faller, K. Fazekas et al., CaDiCaL 2.0, in International Conference on Computer Aided Verification, Springer, pp. 3–17, 2024.

[10] N. Mouha and B. Preneel, Towards Finding Optimal Differential Char-acteristics for ARX: Application to Salsa20, IACR Cryptology ePrint Archive, vol. 2013, p. 328, 2013.

[11] S. K¨olbl, G. Leander and T. Tiessen, Observations on the SIMON Block Cipher Family, in Advances in Cryptology–CRYPTO 2015, Springer, pp. 161–185, 2015.

[12] L. Sun, W. Wang and M. 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.

[13] G. Bansod, A. Patil and N. Pisharoty, GRANULE: An Ultra lightweight cipher design for embedded security, IACR Cryptology ePrint Archive, vol. 2018, p. 600, 2018.

[14] S. Shi and J. He, Impossible Differential Analysis of GRANULE Algo-rithm, Computer Engineering, vol. 45, no. 10, p. 5, 2019.

[15] X. Wu, Y. Li, Y. Wei et al., Impossible Differential Distinguisher Analysis of GRANULE and MANTRA Algorithms, Journal of Com-munications, 2020.

[16] X. Wu, J. Kuang, R. Zhang et al., Impossible Differential Analysis of GRANULE Algorithm Based on SAT, Journal of Computer Applica-tions, vol. 44, no. 3, pp. 797–804, 2024.

[17] X. Liu and Y. Zhang, Meet-in-the-Middle Analysis of Reduced-Round GRANULE Algorithm, Modeling and Simulation, vol. 14, 2025.

[18] X. Liu and Y. Liu, Truncated Impossible Differential Analysis of GRANULE Algorithm, Journal of Shanxi Normal University (Natural Science Edition), vol. 37, no. 1, pp. 41–51, 2023.

[19] Z. Yan, L. Li and Y. Wei, Perfect Linear Approximations of Ultra-Lightweight Block Ciphers LiCi, LiCi-2 and GRANULE, Acta Elec-tronica Sinica, pp. 1–7, 2025.