Differential cryptanalysis of WARP

Differential cryptanalysis; GFN; Rectangle attack; Related-key; WARP; Block ciphers; Distinguishers; Energy efficient; Key recovery attacks; Lightweight block ciphers; Related keys; Software; Safety, Risk, Reliability and Quality; Computer Networks and Communications

Abstract :

[en] WARP is an energy-efficient lightweight block cipher that is currently the smallest 128-bit block cipher in terms of hardware. It was proposed by Banik et al. in SAC 2020 as a lightweight replacement for AES-128 without changing the mode of operation. This paper proposes key-recovery attacks on WARP based on differential cryptanalysis in single and related-key settings. We searched for differential trails for up to 20 rounds of WARP, with the first 19 having optimal differential probabilities. We also found that the cipher has a strong differential effect, whereby 16 to 20-round differentials have substantially higher probabilities than their corresponding individual trails. A 23-round key-recovery attack was then realized using an 18-round differential distinguisher. Next, we formulated an automatic boomerang search using SMT that relies on the Feistel Boomerang Connectivity Table to identify valid switches. We designed the search as an add-on to the CryptoSMT tool, making it applicable to other Feistel-like ciphers such as TWINE and LBlock-s. For WARP, we found a 21-round boomerang distinguisher which was used in a 24-round rectangle attack. In the related-key setting, we describe a family of 2-round iterative differential trails, which we used in a practical related-key attack on the full 41-round WARP.

Research center :

Interdisciplinary Centre for Security, Reliability and Trust (SnT) > CryptoLUX – Cryptography

Disciplines :

Computer science

Author, co-author :

TEH, Je Sen ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust > Cryptolux > Team Alexei BIRYUKOV ; School of Computer Sciences, Universiti Sains Malaysia, Gelugor, Malaysia

BIRYUKOV, Alexei ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)

External co-authors :

yes

Language :

English

Title :

Differential cryptanalysis of WARP

Publication date :

November 2022

Journal title :

Journal of Information Security and Applications

ISSN :

2214-2126

eISSN :

2214-2134

Publisher :

Elsevier Ltd

Volume :

Pages :

103316

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://api.elsevier.com/content/article/PII:S2214212622001648?httpAccept=text/xml

FnR Project :

APLICA

Name of the research project :

R-AGR-3748 - C19/IS/13641232/APLICA (01/09/2020 - 30/08/2022) - BIRYUKOV Alexei

Funders :

Fonds National de la Recherche Luxembourg
Deutsche Forschungsgemeinschaft

Funding text :

Je Sen Teh was supported by the Luxembourgish Fonds National de la Recherche (FNR) and the German Research Foundation (DFG) project APLICA ( C19/IS/13641232 ).

Available on ORBilu :

since 27 November 2023

Statistics

Number of views

110 (4 by Unilu)

Number of downloads

189 (0 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

WoS citations^™

Bibliography

Bogdanov, A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M.J.B., Seurin, Y., Vikkelsoe, C., PRESENT: An ultra-lightweight block cipher. Paillier, P., Verbauwhede, I., (eds.) CHES 2007 LNCS, vol. 4727, 2007, Springer, Heidelberg, 450–466, 10.1007/978-3-540-74735-2_31.
De Cannière, C., Dunkelman, O., Knežević, M., KATAN and KTANTAN - a family of small and efficient hardware-oriented block ciphers. Clavier, C., Gaj, K., (eds.) CHES 2009 LNCS, vol. 5747, 2009, Springer, Heidelberg, 272–288, 10.1007/978-3-642-04138-9_20.
Guo, J., Peyrin, T., Poschmann, A., Robshaw, M.J.B., The LED block cipher. Preneel, B., Takagi, T., (eds.) CHES 2011 LNCS, vol. 6917, 2011, Springer, Heidelberg, 326–341, 10.1007/978-3-642-23951-9_22.
Borghoff, J., Canteaut, A., Güneysu, T., Kavun, E.B., Knežević, M., Knudsen, L.R., Leander, G., Nikov, V., Paar, C., Rechberger, C., Rombouts, P., Thomsen, S.S., Yalçin, T., PRINCE - a low-latency block cipher for pervasive computing applications - extended abstract. Wang, X., Sako, K., (eds.) ASIACRYPT 2012 LNCS, vol. 7658, 2012, Springer, Heidelberg, 208–225, 10.1007/978-3-642-34961-4_14.
Banik, S., Bogdanov, A., Isobe, T., Shibutani, K., Hiwatari, H., Akishita, T., Regazzoni, F., Midori: A block cipher for low energy. Iwata, T., Cheon, J.H., (eds.) ASIACRYPT 2015, part II LNCS, vol. 9453, 2015, Springer, Heidelberg, 411–436, 10.1007/978-3-662-48800-3_17.
Banik, S., Pandey, S.K., Peyrin, T., Sasaki, Y., Sim, S.M., Todo, Y., GIFT: A small present - towards reaching the limit of lightweight encryption. Fischer, W., Homma, N., (eds.) CHES 2017 LNCS, vol. 10529, 2017, Springer, Heidelberg, 321–345, 10.1007/978-3-319-66787-4_16.
Zheng, Y., Matsumoto, T., Imai, H., On the construction of block ciphers provably secure and not relying on any unproved hypotheses. Brassard, G., (eds.) CRYPTO’89 LNCS, vol. 435, 1990, Springer, Heidelberg, 461–480, 10.1007/0-387-34805-0_42.
Banik, S., Bao, Z., Isobe, T., Kubo, H., Liu, F., Minematsu, K., Sakamoto, K., Shibata, N., Shigeri, M., WARP: Revisiting GFN for lightweight 128-bit block cipher. Dunkelman, O., Jacobson, M.J. Jr., O'Flynn, C., (eds.) Selected areas in cryptography - SAC 2020 - 27th international conference, Halifax, NS, Canada, October 21-23, 2020 Lecture notes in computer science, vol. 12804, 2020, Springer, 535–564, 10.1007/978-3-030-81652-0_21.
Suzaki, T., Minematsu, K., Morioka, S., Kobayashi, E., TWINE: A lightweight block cipher for multiple platforms. Knudsen, L.R., Wu, H., (eds.) SAC 2012 LNCS, vol. 7707, 2013, Springer, Heidelberg, 339–354, 10.1007/978-3-642-35999-6_22.
Kumar M, Yadav T. MILP based differential attack on round reduced WARP. Cryptology ePrint Archive, Report 2020/1598, Version 20210802:090929, 2020, https://ia.cr/2020/1598.
Biham, E., Shamir, A., Differential cryptanalysis of DES-like cryptosystems. J Cryptol 4:1 (1991), 3–72, 10.1007/BF00630563.
Boukerrou, H., Huynh, P., Lallemand, V., Mandal, B., Minier, M., On the feistel counterpart of the boomerang connectivity table introduction and analysis of the FBCT. IACR Trans Symmetric Cryptol 2020:1 (2020), 331–362, 10.13154/tosc.v2020.i1.331-362.
Kölbl S. CryptoSMT: An easy to use tool for cryptanalysis of symmetric primitives. https://github.com/kste/cryptosmt.
Zhang L, Wu W, Wang Y, Wu S, Zhang J. LAC. Tech. rep., 2014, Available at.
Lai, X., Massey, J.L., Murphy, S., Markov ciphers and differential cryptanalysis. Davies, D.W., (eds.) EUROCRYPT’91 LNCS, vol. 547, 1991, Springer, Heidelberg, 17–38, 10.1007/3-540-46416-6_2.
Matsui, M., On correlation between the order of S-boxes and the strength of DES. Santis, A.D., (eds.) EUROCRYPT’94 LNCS, vol. 950, 1995, Springer, Heidelberg, 366–375, 10.1007/BFb0053451.
Biryukov, A., Velichkov, V., Automatic search for differential trails in ARX ciphers. Benaloh, J., (eds.) CT-RSA 2014 LNCS, vol. 8366, 2014, Springer, Heidelberg, 227–250, 10.1007/978-3-319-04852-9_12.
Chen, J., Teh, J., Liu, Z., Su, C., Samsudin, A., Xiang, Y., Towards accurate statistical analysis of security margins: New searching strategies for differential attacks. IEEE Trans Comput 66:10 (2017), 1763–1777, 10.1109/TC.2017.2699190.
Mouha, N., Wang, Q., Gu, D., Preneel, B., Differential and linear cryptanalysis using mixed-integer linear programming. Wu, C., Yung, M., Lin, D., (eds.) Information security and cryptology - 7th international conference, inscrypt 2011, Beijing, China, november 30 - december 3, 2011. Lecture notes in computer science, vol. 7537, 2011, Springer, 57–76, 10.1007/978-3-642-34704-7_5.
Sun, S., Hu, L., Wang, P., Qiao, K., Ma, X., Song, L., Automatic security evaluation and (related-key) differential characteristic search: Application to SIMON, PRESENT, lblock, DES(l) and other bit-oriented block ciphers. Sarkar, P., Iwata, T., (eds.) ASIACRYPT 2014, part I LNCS, vol. 8873, 2014, Springer, Heidelberg, 158–178, 10.1007/978-3-662-45611-8_9.
Zhu, B., Dong, X., Yu, H., MILP-based differential attack on round-reduced GIFT. Matsui, M., (eds.) CT-RSA 2019 LNCS, vol. 11405, 2019, Springer, Heidelberg, 372–390, 10.1007/978-3-030-12612-4_19.
Mouha N, Preneel B. Towards Finding Optimal Differential Characteristics for ARX: Application to Salsa20. Cryptology ePrint Archive, Report 2013/328, 2013,.
Sun, L., Wang, W., Wang, M., Accelerating the search of differential and linear characteristics with the SAT method. IACR Trans Symmetric Cryptol 2021:1 (2021), 269–315, 10.46586/tosc.v2021.i1.269-315.
Ankele, R., Kölbl, S., Mind the gap - A closer look at the security of block ciphers against differential cryptanalysis. Cid, C., Jacobson Jr:, M.J., (eds.) SAC 2018 LNCS, vol. 11349, 2019, Springer, Heidelberg, 163–190, 10.1007/978-3-030-10970-7_8.
Hall-Andersen, M., Vejre, P.S., Generating graphs packed with paths. IACR Trans Symmetric Cryptol 2018:3 (2018), 265–289, 10.13154/tosc.v2018.i3.265-289.
Biham, E., Dunkelman, O., Keller, N., A related-key rectangle attack on the full KASUMI. Roy, B.K., (eds.) ASIACRYPT 2005 LNCS, vol. 3788, 2005, Springer, Heidelberg, 443–461, 10.1007/11593447_24.
Jeong, K., Lee, C., Sung, J., Hong, S., Lim, J., Related-key amplified boomerang attacks on the full-round Eagle-64 and eagle-128. Pieprzyk, J., Ghodosi, H., Dawson, E., (eds.) ACISP 07 LNCS, vol. 4586, 2007, Springer, Heidelberg, 143–157.
Biryukov, A., Khovratovich, D., Related-key cryptanalysis of the full AES-192 and AES-256. Matsui, M., (eds.) ASIACRYPT 2009 LNCS, vol. 5912, 2009, Springer, Heidelberg, 1–18, 10.1007/978-3-642-10366-7_1.
Dunkelman, O., Keller, N., Shamir, A., A practical-time related-key attack on the KASUMI cryptosystem used in GSM and 3G telephony. Rabin, T., (eds.) CRYPTO 2010 LNCS, vol. 6223, 2010, Springer, Heidelberg, 393–410, 10.1007/978-3-642-14623-7_21.
Ashur, T., Dunkelman, O., A practical related-key boomerang attack for the full MMB block cipher. Abdalla, M., Nita-Rotaru, C., Dahab, R., (eds.) CANS 13 LNCS, vol. 8257, 2013, Springer, Heidelberg, 271–290, 10.1007/978-3-319-02937-5_15.
Lu, J., Yap, W.-S., Wei, Y., Weak keys of the full MISTY1 block cipher for related-key differential cryptanalysis. Dawson, E., (eds.) CT-RSA 2013 LNCS, vol. 7779, 2013, Springer, Heidelberg, 389–404, 10.1007/978-3-642-36095-4_25.
Sasaki, Y., Related-key boomerang attacks on full ANU lightweight block cipher. Preneel, B., Vercauteren, F., (eds.) ACNS 18 LNCS, vol. 10892, 2018, Springer, Heidelberg, 421–439, 10.1007/978-3-319-93387-0_22.
Tsudik, G., Van Herreweghen, E., On simple and secure key distribution. Denning, D.E., Pyle, R., Ganesan, R., Sandhu, R.S., Ashby, V., (eds.) ACM CCS 93, 1993, ACM Press, 49–57, 10.1145/168588.168594.
Kelsey, J., Schneier, B., Wagner, D., Related-key cryptanalysis of 3-WAY, biham-DES, CAST, DES-X, NewDES, RC2, and TEA. Han, Y., Okamoto, T., Qing, S., (eds.) ICICS 97 LNCS, vol. 1334, 1997, Springer, Heidelberg, 233–246.
Biham, E., Dunkelman, O., Keller, N., A unified approach to related-key attacks. Nyberg, K., (eds.) FSE 2008 LNCS, vol. 5086, 2008, Springer, Heidelberg, 73–96, 10.1007/978-3-540-71039-4_5.
Wagner, D., The boomerang attack. Knudsen, L.R., (eds.) FSE’99 LNCS, vol. 1636, 1999, Springer, Heidelberg, 156–170, 10.1007/3-540-48519-8_12.
Kelsey, J., Kohno, T., Schneier, B., Amplified boomerang attacks against reduced-round MARS and serpent. Schneier, B., (eds.) FSE 2000 LNCS, vol. 1978, 2001, Springer, Heidelberg, 75–93, 10.1007/3-540-44706-7_6.
Biham, E., Dunkelman, O., Keller, N., New results on boomerang and rectangle attacks. Daemen, J., Rijmen, V., (eds.) FSE 2002 LNCS, vol. 2365, 2002, Springer, Heidelberg, 1–16, 10.1007/3-540-45661-9_1.
Murphy, S., The return of the cryptographic boomerang. IEEE Trans. Inf. Theory 57:4 (2011), 2517–2521, 10.1109/TIT.2011.2111091.
Cid, C., Huang, T., Peyrin, T., Sasaki, Y., Song, L., Boomerang connectivity table: A new cryptanalysis tool. Nielsen, J.B., Rijmen, V., (eds.) EUROCRYPT 2018, part II LNCS, vol. 10821, 2018, Springer, Heidelberg, 683–714, 10.1007/978-3-319-78375-8_22.
Song, L., Qin, X., Hu, L., Boomerang connectivity table revisited. IACR Trans Symmetric Cryptol 2019:1 (2019), 118–141, 10.13154/tosc.v2019.i1.118-141.
Biryukov, A., Nikolic, I., Complementing feistel ciphers. Moriai, S., (eds.) FSE 2013 LNCS, vol. 8424, 2014, Springer, Heidelberg, 3–18, 10.1007/978-3-662-43933-3_1.
Shibutani, K., Isobe, T., Hiwatari, H., Mitsuda, A., Akishita, T., Shirai, T., Piccolo: An ultra-lightweight blockcipher. Preneel, B., Takagi, T., (eds.) CHES 2011 LNCS, vol. 6917, 2011, Springer, Heidelberg, 342–357, 10.1007/978-3-642-23951-9_23.
Zhao, B., Dong, X., Meier, W., Jia, K., Wang, G., Generalized related-key rectangle attacks on block ciphers with linear key schedule: applications to SKINNY and GIFT. Des Codes Cryptogr 88:6 (2020), 1103–1126, 10.1007/s10623-020-00730-1.
Zong, R., Dong, X., Chen, H., Luo, Y., Wang, S., Li, Z., Towards key-recovery-attack friendly distinguishers: Application to GIFT-128. IACR Trans Symmetric Cryptol 2021:1 (2021), 156–184, 10.46586/tosc.v2021.i1.156-184.
Selçuk, A.A., On probability of success in linear and differential cryptanalysis. J Cryptol 21:1 (2008), 131–147, 10.1007/s00145-007-9013-7.