Analysis of Impossible Differential on LowMC Block Cipher

Document Type : Original Article

Authors

beheshti university

Abstract

Impossible differential attack is one of the strongest methods of cryptanalysis on block ciphers. In block ciphers based on SPN (substitution permutation network), the only layer that resists the difference is the nonlinear layer. Obviously, paying attention to the features of nonlinear layer is important for the sake of preventing statistical attacks, such as the differential attack. Therefore, this layers’ features regarding attack tolerance should be carefully investigated. The existence of such a nonlinear layer with the required features and applying it in the entire length of the block can lead to more resistance against differential attacks. Over the past few years, a new set of block ciphers based on SPN has been introduced, in which the nonlinear layer is applied only to a particular part of the state. In this paper, a general framework for finding the   characteristics of the impossible difference in this type of new block cipher is presented. Contrary to the previous miss-in-the-middle methods, which are used to find the impossible differences, the method       presented in this article is independent of the feature of linear layer of the algorithm and allows the attacker to systematically find the effective impossible differential even in cryptographic algorithms with highly complex linear layer. In order to demonstrate the efficiency of the proposed method, the family of LowMC ciphers that use bitwise linear layer are examined in this paper and based on this framework some           impossible differential characteristics are proposed for some versions of reduced LowMCs. This proposed impossible differential characteristics can be easily applied in key-recovery attacks based on the framework presented in this paper. As an example, we show that based on the impossible difference characteristic    obtained for 63 rounds of the LowMC (128,128,2,128), a key-recovery attack is applied to the 64-round of this algorithm. In proposed attack, the complexity of memory is 289, the complexity of the time is 2123.7, and the complexity of the data is equal to 2123.1 of the chosen plain text.
 

Keywords

References

[1]
M. R. Albrecht, C. Rechberger, T. Schneider, T. Tiessen, and M. Zohner, “Ciphers for MPC and FHE,” in EUROCRYPT 2015, 2015.##
[2]
A. Canteaut, S. Carpov, C. Fontaine, T. Lepoint, M. N. Plasencia, P. Paillier, and R. Sirdey, “Stream ciphers: A Practical Solution for Efficient Homomorphic-Ciphertext Compression,” in FSE 2016, 2016.##
[3]
P. Meaux, A. Journault, F. X. Standaert, and C. Carlet, “Towards Stream Ciphers for Efficient FHE with Low-Noise Ciphertexts,” in EUROCRYPT 2016, 2016.##
[4]
M. R. Albrecht, L. Grassi, C. Rechberger, A. Roy, and T. Tiessen, “MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity,” in ASIACRYPT 2016, 2016.##
[5]
C. Dobraunig, M. Eichlseder, L. Grassi, V. Lallemand, G. Leander, E. List, F. Mendel, and C. Rechberger, “Rasta: A cipher with low ANDdepth and few ANDs per bit,” in CRYPTO 2018, 2018.##
[6]
B. Gerard, V. Grosso, M. N. Plasencia, and F. X. Standaert, “Block Ciphers That Are Easier to Mask: How Far Can We Go?,” in CHES 2013, 2013.##
[7]
H. Soleimany, “Probabilistic Slide Cryptanalysis and Its Applications to LED-64 and Zorro,” in FSE 2014, 2014.##
[8]
S. Rasoolzadeh, Z. Ahmadian , M. Salmasizadeh, and M. R. Aref, “Total break of Zorro using linear and differential attacks,” Isecure, 2014.##
[9]
Y. Wang, W. Wu , Z. Guo, and X. Yu, “Differential cryptanalysis and linear distinguisher of full-round Zorro,” in ACNS 2014, 2013.##
[10]
G. Leander, B. Minaud, and S. Ronjom, “A Generic Approach to Invariant Subspace Attacks: Cryptanalysis of Robin, iSCREAM and Zorro,” in EUROCRYPT 2015, 2015.##
[11]
I. Dinur, Y. Liu, W. Meier, and Q. Wang, “Optimized Interpolation Attacks on LowMC,” in ASIACRYPT 2015, 2015.##
[12]
C. Dobraunig, M. Eichlseder, and F. Mendel, “Higher-Order Cryptanalysis of LowMC,” in ICISC 2015, 2015.##
[13]
M. R. Albrecht, C. Rechberger, T. Schneider, T. Tiessen, and M. Zohner, “Ciphers for MPC and FHE,” IACR Cryptology ePrint Archive, 2016.##
[14]
D. Derler, C. Orlandi, S. Ramacher, C. Rechberger, and D. Slamanig, “Digital Signatures from Symmetric-Key Primitives,” IACR Cryptology ePrint Archive, 2016.##
[15]
D. Derler, S. Ramacher, and D. Slamanig, “Post-Quantum Zero-Knowledge Proofs for Accumulators with Applications to Ring Signatures from Symmetric-Key Primitives,” in PQCrypto 2018, 2018.##
[16]
M. Chase , D. Derler, S. Goldfeder, C. Orlandi, S. Ramacher, C. Rechberger, D. Slamanig, and G. Zaverucha, “Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives,” in CCS 2017, 2017.##
[17]
A. BarOn, I. Dinur, O. Dunkelman, V. Lallemand, N. Keller, and B. Tsaban, “Cryptanalysis of SP Networks with Partial Non-Linear Layers,” in EUROCRYPT 2015, 2015.##
[18]
L. Knudsen, “DEAL - A 128-bit Block Cipher,” Technical report no. 151. University of Bergen, Norway, 1998.##
[19]
E. Biham, A. Biryukov, and A. Shamir, “Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials,” in EUROCRYPT 1999, 1999.##
[20]
M. R. Dastajani, M. Javad, and P. Ali, “Impossible Differential Cryptanalysis of Piccolo-80,” Defence Sci. & Tech., vol. 5, no. 1, pp. 1-12, 2013. (In persian)##
[21]
A. Bogdanov, L. R. Knudsen, G. Leander, C. Paar, A. Poschmann, M. J. Robshaw, Y. Seurin,  and C. Vikkelsoe, “PRESENT: An ultra-lightweight block cipher,” In International Workshop on Cryptographic Hardware and Embedded Systems 2007 Sep 10 (pp. 450-466). Springer, Berlin, Heidelberg, 2007.##
[22]
J. Daemen and V. Rijmen, “AES proposal: Rijndael,” 1999.##

Files

History

  • Receive Date: 27 May 2018
  • Accept Date: 13 October 2018
  • Publish Date: 22 June 2019

Share

How to cite

Statistics