Practical Challenges and Innovations in Hash-based Signature Schemes
Explore the latest advancements in hash-based signature schemes, focusing on practical challenges, security requirements, and innovative approaches such as Merkle trees and XMSS. Industry experts invite valuable insights for handling state efficiently. Stay informed about post-quantum security and reduced security requirements in digital signatures.
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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Towards A Standard for Practical Hash-based Signatures D. Butin, S.-L. Gazdag, A. H lsing
Hash-based Signature Schemes [Mer89] Post quantum Only secure hash function Security well understood Fast 19-4-2025 PAGE 1
Security Intractability assumption Collision resistant hash function Digital signature scheme 19-4-2025 PAGE 2
Post-Quantum Security n-bit hash function Grover 96: ? ?) Preimage finding ?(??) ?(? Brassard et al. 1998: ? ?) ? ?) ?(? Collision finding ?(? Aaronson & Shi 04: ? ?is lower bound Quantum collision finding ? 19-4-2025 PAGE 3
Merkles Hash-based Signatures Digital Signature PK SIG = (i=2, , , , , ) Encryption H H H Cryptography H OTS H H H Legality H H H H H H H H Hash Function OTS OTS OTS OTS OTS OTS OTS OTS MAC SK 19-4-2025 PAGE 4
Practical Challenge: Handle State Can be avoided in theory, paid with efficiency Different API Handle Integration Prevent copies No key back-up Multi-threading safety Industry input appreciated 19-4-2025 PAGE 5
McGrew & Curcio2014 19-4-2025 PAGE 6
McGrew & Curcio2014 Merkle Tree + Winternitz OTS Parameter Sets = Cipher Suites Security = collision resistance 19-4-2025 PAGE 7
XMSS eXtended Merkle Signature Scheme 19-4-2025 PAGE 8
Reduced Security Requirements Change WOTS -> WOTS+ Change Tree H H bi Security from second-preimage resistance Collision-resilient scheme No birthday-attacks 19-4-2025 PAGE 9
Size reduction Hash function h:{0,1}* {0,1}m Assume: - only generic attacks, - security level n Collision resistance required: generic attack = birthday attack m = 2n Halfes Signature Size! Second-preimage resistance required: generic attack = exhaustive search m = n 19-4-2025 PAGE 10
Early warning system MD5 MD5 Collisions (practical!) Collisions (theo.) SHA-1 Collisions (theo.) MD5 & SHA-1 No (Second-) Preimage Attacks! 2004 2005 2008 2014 19-4-2025 PAGE 11
Tree Chaining Requires computation of 2*2h/2 nodes in Merkle trees 19-4-2025 PAGE 12
Tree Chaining Can be extended to d layers Reduces signature and key generation time Necessary for smartcards & h >> 20 19-4-2025 PAGE 13
Tree Chaining Sign (ms) Verify (ms) Keygen (ms) Signature (byte) Public Key (byte) Secret Key (byte) Bit Sec. Comment XMSS 800 2,448 92 H = 16, w = 4 23 2,388 134 925,400 XMSS+ 544 3,760 94 H = 16, w = 4 25 3,476 106 5,600 RSA 2048 256 512 512 87 190 7 11,000 Infineon SLE78 16Bit-CPU@33MHz, 8KB RAM, TRNG, sym. & asym. co-processor NVM: Card 16.5 million write cycles/ sector, XMSS+< 5 million write cycles (h=20) [HBB12] 19-4-2025 PAGE 14
Forward Security 19-4-2025 PAGE 15
Forward Security pk classical sk pk forward sec sk sk1 sk2 skT ski time tT ti t1 t2 Key gen. = : ( , ), Goal Sig j j i 19-4-2025 PAGE 16
Requires special KeyGen F F F F F F F F F F PRG FSPRG FSPRG FSPRG FSPRG FSPRG 19-4-2025 PAGE 17
PoC Implementation C Implementation, using OpenSSL [BDH2011] Sign (ms) Verify (ms) Signature (bit) Public Key (bit) Secret Key (byte) Bit Security Comment XMSS-SHA-2 13,600 3,364 157 h = 20, w = 64, 35.60 1.98 16,672 XMSS-AES-NI 19,616 7,328 1,684 84 h = 20, w = 4 0.52 0.07 XMSS-AES 19,616 7,328 1,684 84 h = 20, w = 4 1.06 0.11 RSA 2048 2,048 4,096 512 87 3.08 0.09 Intel(R) Core(TM) i5-2520M CPU @ 2.50GHz with Intel AES-NI 19-4-2025 PAGE 18
Conclusion Current draft: Great first step ... BUT ... XMSS: Additional important features More efficient Stronger Security Guarantees Forward-security Add-on to draft required. 19-4-2025 PAGE 19
Thank you! Questions? 19-4-2025 PAGE 20
