Lightweight Cryptography: Key-Reduced Variants and Beyond-Birthday-Bound Security

Lightweight cryptography has emerged as a hot research topic in the past two decades, with over 60 ciphers proposed. This includes examples like PRESENT, GIFT, SIMON/SPECK, and more. Authenticated encryption through CAESAR and NIST LWC plays a vital role, with ASCON and ACORN leading the lightweight applications. The focus on Lightweight MAC and the significance of MAC with lightweight block ciphers are explored, along with the quest for security beyond the birthday barrier in MAC designs. Notable schemes like DbHtS MACs, SUM-ECBC, PMAC_Plus, and 3kf9 are discussed, highlighting the balance between efficiency and security in lightweight cryptography.

• Cryptography
• Lightweight
• Security
• Encryption
• Authentication

ccook Follow

Uploaded on Sep 30, 2024 | 1 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Key-reduced Variants of 3kf9 with Beyond-birthday-bound Security Yaobin Shen and Ferdinand Sibleyras Dec 7, Asiacrypt 2022 1

2. Lightweight Cryptography A hot research topic in the past two decades More than 60 ciphers have been proposed Examples for lightweight block ciphers PRESENT (64-bit block, 80/128-bit key), ISO/IEC 29192-2:2019 GIFT (64/128-bit block, 128-bit key) SIMON/SPECK (32~128-bit block, 64~256-bit key), NSA 2

3. Authenticated Encryption: CAESAR & NIST LWC Authenticated Encryption = Authentication + Encryption CAESAR competition (57 submissions) Final portfolio for Lightweight applications : ASCON (1st), ACORN (2nd) NIST LWC (10 finalists out of 57 submissions) ASCON, ELEPHANT, GIFT-COFB, Grain-128AEAD, ISAP PHOTON-Beetle, Romulus, SPARKLE, TinyJambu, Xoodyak 3

4. Lightweight MAC? AE MAC MAC has its own interest and is widely used many applications require only authentication The research on Lightweight MAC is somewhat lack Algo Str. C. Block C. Total 32 58 Hash F. Auth C. MAC rare 10 14 3 The number of lightweight algorithms [BP17] 4

5. MAC + lightweight block ciphers Small block size is common for lightweight block ciphers to reduce implementation cost Security margin becomes small for conventional MACs, e.g. CBC-MAC, PMAC ? [BL16b] ? 2= 232is vulnerable when ? = 64 [BL16a] birthday bound 2 MAC desires security beyond the birthday barrier 5

6. Beyond-birthday-bound (BBB) MACs Double-block Hash-then-SUM (DbHtS) [DDNP19] ? ?? ,1 E?1 ? ? ? ?? ,2 E ?2 A class of MACs that aim for BBB security SUM-ECBC [Yas10] PMAC_Plus [Yas11] 3kf9 [ZWSW12] LightMAC_Plus [Nai17] 6

7. DbHtS MACs SUM-ECBC PMAC_Plus LightMAC_Plus 3kf9 7

8. DbHtS MACs: Lightweight? SUM-ECBC: two passes, rate Reduce #keys for efficiency but keep BBB security PMAC_Plus -> 1k-PMAC_Plus [DDN+17] LightMAC_Plus -> 1k-LightMAC_Plus [Nai18] at least ? field multiplications for a ?-block message 8

9. 3kf9: Lightweight? 3kf9, a sequential mode without field multiplications [ZWSW12] an enhanced version of standard f9 algorithm (3GPP-MAC) CBC-like MAC with 3 keys key-reduced variants of 3kf9? 9

10. Previous key-reduced variants of 3kf9: 1kf9 1kf9 [DDN+15]: Birthday-bound attack by exploiting fix functions [LNS18]: find ?||0?and ?||? such that ????0? ? ????0? ? = ? where ? is the inverse of 2 11

11. Previous key-reduced variants of 3kf9: 2kf9 2kf9 [DDN19]: One-query attack: ?,0?is a valid forgery for any ? = ? [SWGW21] Adding fix functions -> the similar attack as 1kf9 [SWGW21] 12

12. A plausible construction A constant block at the beginning to avoid one-query attack Two queries ?||? and ?||?: ?= ? ?= ? -> ?= ? ? ? ?= ? -> ? ?= ?-> birthday-bound dist. 13

13. Summary of attacks 1kf9: Fix functions will absorb some differences and maintain equalities. ?= ?and ?= ? d leads to a tag collision. 2kf9: the analysis of ?= ?is flawed ?1? ? ? 1 The plausible construction: The symmetry is such that ?= ?implies ?= ?, a birthday bound event. The analysis of this event is missing in the previous proof. = 0 always holds for a message ??with ?= 1 ? 14

14. Lesson learned Two fix functions may not help We should break the relation between and 15

15. Our method for BBB A simple doubling near the end: n2kf9 one-bit shift and one conditional XOR with some constant Doubling has no fixed point except for 0: avoid the singe-query attack 16

16. Our method for BBB A simple doubling near the end: n2kf9 rank 2 for two queries ?||? and ?||?: avoid the birthday- bound dist. ?= ? ?= ? -> ?= ? 2 ? ? 2 ?= ?-> ? 2 ?= ? 2 ? ?= ?-> rank 2 17

17. Our method for BBB A simple doubling near the end: n2kf9 Removal of fix functions fix_0 and fix_1: avoid attack in 1kf9 18

18. Our method for BBB A simple doubling near the end: n2kf9 Security analysis: the collision relation between and is negligible 19

19. One-key version for BBB The doubling also works: n1kf9 to be prefix- free The message space should be prefix-free as CBC-MAC no query is a prefix of another required in the proof but no attacks currently 20

20. n2kf9 vs EMAC Higher security guarantee with a 2n-bit state, one additional block cipher call and one doubling ?3 22?for n2kf9 vs ? ?2 2?for EMAC this bound is tight ? EMAC this bound may be improved further n2kf9 21

21. n1kf9 vs CBC-MAC Higher security guarantee with a 2n-bit state, one additional block cipher call and one doubling ?3 22?for n1kf9 vs ? ?2 2?for CBC-MAC this bound is tight ? CBC-MAC (the last block is 0?) this bound may be improved further n1kf9 22

22. Proof ideas essential part of the proof that previous attempts failed High-level idea first show ( ?, ?) is cover-free (at least one of two is fresh) then apply the result of sum of two identical permutations base on the structure graph of CBC-MAC n2kf9 23

23. Proof ideas show ( ?, ?) is cover-free for any message ?? ?= ?for itself ? { ?, ?} and ? { ?, ?} for another message ?? ? { ?, ?} and ? { ?, ?} for another two messages ??and ?? easy to handle these two equations has rank 2 these two equations has rank 2, and rank 3 plus equations from collisions n2kf9 24

24. Conclusion Two new key-reduced variants of 3kf9 with beyond-birthday security n2kf9 ( EMAC + n-bit state, 1 block cipher call and 1 doubling) n1kf9 ( CBC-MAC + n-bit state, 1 block cipher call and 1 doubling) Possible candidates for Lightweight MAC Lightweight block cipher + beyond-birthday MAC 25

25. Thanks yaobin.shen@uclouvain.be [BP17] Alex Biryukov, L o Perrin: State of the Art in Lightweight Symmetric Cryptography. IACR Cryptol. ePrint Arch. 2017: 511 (2017) [BL16a] Karthikeyan Bhargavan, Ga tan Leurent: On the Practical (In-)Security of 64-bit Block Ciphers: Collision Attacks on HTTP over TLS and OpenVPN. CCS 2016: 456-467 [BL16b] Karthikeyan Bhargavan, Ga tan Leurent: https://sweet32.info/ [DDNP19] Nilanjan Datta, Avijit Dutta, Mridul Nandi, Goutam Paul: Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF. IACR Trans. Symmetric Cryptol. 2018(3): 36-92 (2018) [Yas10] Kan Yasuda:The Sum of CBC MACs Is a Secure PRF. CT-RSA 2010: 366-381 [Yas11] Kan Yasuda: A New Variant of PMAC: Beyond the Birthday Bound. CRYPTO 2011: 596-609 [ZWSW12] Liting Zhang, Wenling Wu, Han Sui, Peng Wang: 3kf9: Enhancing 3GPP-MAC beyond the Birthday Bound. ASIACRYPT 2012: 296-312 [Nai17] Yusuke Naito: Blockcipher-Based MACs: Beyond the Birthday Bound Without Message Length. ASIACRYPT (3) 2017: 446-470 [DDN+17] Nilanjan Datta, Avijit Dutta, Mridul Nandi, Goutam Paul, Liting Zhang: Single Key Variant of PMAC_Plus. IACR Trans. Symmetric Cryptol. 2017(4): 268-305 (2017) [Nai18] Yusuke Naito: Improved Security Bound of LightMAC_Plus and Its Single-Key Variant. CT-RSA 2018: 300-318 [ZWSW12] Liting Zhang, Wenling Wu, Han Sui, Peng Wang: 3kf9: Enhancing 3GPP-MAC beyond the Birthday Bound. ASIACRYPT 2012: 296-312 [GT] G. T. . v 3.1.1. Specification of the 3gpp confidentiality and integrity algorithms, document 1: f8 and f9 specification. https://www.3gpp.org/DynaReport/35- series.htm. [DDN+15]] N. Datta, A. Dutta, M. Nandi, G. Paul, and L. Zhang. Building single-key beyond birthday bound message authentication code. Cryptology ePrint Archive, Report 2015/958, 2015. https://eprint.iacr.org/2015/958. (withdrawn) [LNS18] G. Leurent, M. Nandi, and F. Sibleyras. Generic attacks against beyond-birthday-bound MACs. In H. Shacham and A. Boldyreva, editors, CRYPTO 2018, Part I, volume 10991 of LNCS, pages 306 336. Springer, Heidelberg, Aug. 2018. [DDNP19] Nilanjan Datta, Avijit Dutta, Mridul Nandi, Goutam Paul: Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF. IACR Trans. Symmetric Cryptol. 2018(3) (FSE 2019): 36-92 (2018) [SWGW21] Y. Shen, L. Wang, D. Gu, and J. Weng. Revisiting the security of DbHtS MACs: Beyond-birthday-bound in the multi-user setting. In T. Malkin and C. Peikert, editors, CRYPTO 2021, Part III, volume 12827 of LNCS, pages 309 336, Virtual Event, Aug. 2021. Springer, Heidelberg. 26