تحلیل تفاضل ناممکن الگوریتم رمزقالبی LowMC

نوع مقاله : مقاله پژوهشی

نویسندگان

1 استادیار، گروه امنیت شبکه و رمزنگاری، پژوهشکده‌ فضای مجازی، دانشگاه شهید بهشتی، تهران،

2 کارشناس ارشد مخابرات امن و رمزنگاری، پژوهشکده‌ فضای مجازی، دانشگاه شهید بهشتی، تهران

چکیده

تحلیل تفاضل ناممکن یک ابزار قوی برای ارزیابی امنیت رمزهای قالبی به­شمار می­آید. در رمزهای قالبی که بر مبنای ساختار شبکه  جانشینی­ـ جایگشتی بنا شده­اند، تنها لایه­ای که در برابر تفاضل از خود مقاومت نشان می­دهد، لایه غیرخطی است. بدیهی است توجه به خصوصیات لایه غیرخطی در جلوگیری اعمال حملات آماری نظیر حمله تفاضلی از اهمیت بالایی برخوردار است. بنابراین، ویژگی­های این لایه برای مقاومت در برابر این حمله باید به دقت مورد بررسی قرار بگیرد. وجود چنین لایه غیرخطی با توجه به ویژگی­های مورد نیاز و اعمال آن به تمام طول قالب می­تواند باعث مقاومت بیشتر الگوریتم در مقابل حمله تفاضلی شود. طی سالیان اخیر دسته­ جدیدی از رمزهای قالبی بر مبنای ساختار شبکه جانشینی ـ جایگشتی معرفی شده­اند که در آنها لایه غیرخطی تنها به بخشی از قالب اعمال می­شود. در این مقاله چارچوبی عمومی برای یافتن مشخصه­های تفاضل ناممکن در این دسته از رمزهای قالبی نوین ارائه می­شود. برخلاف روش­های فقدان در میانه پیشین که برای یافتن مشخصه­های تفاضل ناممکن استفاده شده است، روش ارائه­شده در این مقاله مستقل از مشخصات لایه خطی الگوریتم رمزنگاری است و به مهاجم اجازه می­دهد که برای الگوریتم­های رمزنگاری با لایه خطی بسیار پیچیده به­صورت سیستماتیک مشخصه­های تفاضل ناممکن موثری را پیدا کند. به منظور نشان دادن کارائی روش ارائه­شده، خانواده رمزهای قالبی LowMC که از لایه­های خطی بیت محور استفاده می­کنند را در این مقاله مورد بررسی قرار داده و براساس چارچوب ارائه­شده در مقاله، مشخصه­های تفاضل ناممکن متعددی برای نسخه­های کاهش یافته LowMC ارائه کرده­ایم. مشخصه­های تفاضل ناممکن به­دست­آمده می­تواند به راحتی در حملات بازیابی کلید    به­کار روند. به­عنوان نمونه نشان می­دهیم که براساس مشخصه تفاضل ناممکن به­دست­آمده برای 63 دور الگوریتم LowMC(128,128,2,128)، یک حمله بازیابی کلید به 64 دور الگوریتم قابل اعمال است. در حمله ارائه شده، پیچیدگی حافظه ، پیچیدگی زمانی برابر  و پیچیدگی داده برابر با  متن منتخب است.

کلیدواژه‌ها


[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.##