Post-Quantum Security and Cryptographic Hash Functions
Explore the transition to post-quantum security with a focus on cryptographic hash functions like SPHINCS+, covering collision resistance, second-preimage resistance, preimage resistance, and more. Understand the concepts behind classical and post-quantum security, including adversary capabilities in local and remote quantum computations. Engage with the discussion on security properties and quantum security worlds.
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
From hash-function security in a post-quantum world to SPHINCS+ Andreas H lsing
Cryptographic hash functions Efficient function h: 0,1? 0,1?(?) 0,1? We write h k,x = ?(?) Key ? in this case is public information. Think of function description. 11.12.2019 https://sphincs.org 2
Collision resistance Success probability of an adversary ? against collision resistance (CR) of h is defined as ??(?) = Pr[? ? 0,1?, ?1,?2 ? ? : Succ ??1 = ??2 ?1 ?2] 11.12.2019 https://sphincs.org 3
Second-preimage resistance (SPR) Success probability of an adversary ? against second-preimage resistance (SPR) of h is defined as ???? = Pr[? ? 0,1?,? ? 0,1? ?, Succ ? ? ?,? : ?? = ?? ? ? ] 11.12.2019 https://sphincs.org 4
Security properties: Preimage resistance / One-wayness Success probability of an adversary ? against preimage resistance (PRE) of h is defined as ???? = Pr[? ? 0,1?,? ? 0,1? ?, Succ ? ?? ,? ? ?,? : ?? = ?] 11.12.2019 https://sphincs.org 5
Quantum security worlds [Gagliardoni 17]
QS0: Classical security 01010101110110 11010101 01110110 11010101 01110110 11000101 00010110 01/07/2019 https://huelsing.net 7
QS1: Post-quantum security 01010101110110 11010101 01110110 11010101 01110110 0 1 0 1 0 1 0 0 1 1 1 1 1 0 01/07/2019 https://huelsing.net 8
QS1: Post-quantum security Adversary can run local quantum computations Adversary cannot communicate with honest parties using quantum states! Local functions & oracles that do not contain secret information: Quantum access Remote functions & secretly keyed oracles: Classical access 01/07/2019 https://huelsing.net 9
QS2: Quantum security 0 0 0 0 1 1 0 1 0 1 1 1 1 1 0 1 0 1 0 1 0 0 1 1 1 1 1 0 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 1 1 1 0 01/07/2019 https://huelsing.net 10
QS2: Quantum security Adversary can run local quantum computations Adversary can communicate with honest parties using quantum states! Local functions & oracles that do not contain secret information: Quantum access Remote functions & secretly keyed oracles: Quantum access This assumes a world where users have quantum computers 01/07/2019 https://huelsing.net 11
We care about QS1 for practical applications in the foreseeable future. 01/07/2019 https://huelsing.net 12
What does this mean for hash function security? 14.11.2019 https://sphincs.org/ 13
Re-assess generic hardness joint work with Rijneveld & Song, PKC 16 What is the complexity of generic quantum attacks? Consider ? bit hash function, adversary that makes ? queries ?2 2? ???? =?+1 ??? = ???? = Succ Classically: Succ 2?, Succ PRE SPR CR [Zha15] ?3 2? Quantum: ?2 2? ?2 2? Quantum 14.11.2019 https://sphincs.org/ 14
What about actual hash functions? 15
Hash function design Create fixed input size building block Use building block to build compression function Use mode for length extension Engineering Generic transforms Permutation / Block cipher Compression function Hash function Cryptanalysis / best practices Reductionist proofs 16
M-D (SHA2): Most classical results carry over (CR / OW) compression function (CR / OW) Hash 17
Sponges (SHA3): Classical result fails in quantum setting Guido Bertoni, Joan Daemen, Micha l Peeters and Gilles Van Assche. Cryptographic Sponge Functions. 2007 18
SHA3: Classical result fails in quantum setting Theorem([BDPV07] Informally): If f is a random permutation or transformation, the expected complexity for differentiating a sponge ?f from a random oracle is ?(2 Proof inherently query based. Proof requires knowledge of queries to ?f. ? 2). 19
Post-quantum security of Sponges joint work with Jan Czajkowski, Leon Groot Bruinderink, Christian Schaffner, and Dominique Unruh, PQCrypto 2018 / QCRYPT 2017, Crypto 19 PQCrypto 18 Sponges are collapsing, CR, SPR, PRE if block function is random function or random one-way permutation (does not cover SHA3!) Quantum attack that meets lower bounds Crypto 19 Sponges are quantum-secure PRFs / MACs if keyed via block function ( = indistinguishability of random sponges) TBD Indifferentiability of random sponges 20
New applications for hash-functions Hash-based signatures 14.11.2019 https://sphincs.org/ 21
(Stateful) Hash-based signatures 14.11.2019 https://sphincs.org/ 22
OTS 1-bit Lamport: PK Sig (M=0) Sig (M=1) SK X0 Y0 = H(X0) X0 X1 Y1 = H(X1) X1 N-bit Lamport: Use N pairs of secret values. 14.11.2019 https://sphincs.org/ 23
Merkle Signatures (from OTS to MTS) PK SIG = (i=2, , , , , ) H H H OTS H H H H H H H H H H H H OTS OTS OTS OTS OTS OTS OTS OTS SK 19-3-2025 PAGE 24
Hypertree: A tree of trees Single tree: Root & authpath computation costs (2 ) time (w/o state) Hypertree = Certification tree (think of a PKI): Root & authpath computation costs (2 ) (2 /?) (w/o state) 14.11.2019 https://sphincs.org/ 26
Minimizing security assumptions MSS MSS-SPR XMSS+ XMSS-T PRF, CR, PRE Non-tight PRF, SPR, PRE Inefficient Non-tight PRF, SPR, PRE Non-tight PRF, SPR Tight but bad assumption 14.11.2019 https://sphincs.org/ 27
New security requirements for hash functions Decisional second preimage resistance (DSPR) Joint work with Daniel J. Bernstein 14.11.2019 https://sphincs.org/ 28
OTS 1-bit Lamport: PK Sig (M=0) Sig (M=1) SK X0 Y0 = H(X0) X0 X1 Y1 = H(X1) X1 N-bit Lamport: Use N pairs of secret values. 14.11.2019 https://sphincs.org/ 29
Tightness loss Security reduction has to implant PRE challenge in PK. For this position reduction cannot produce signature value Reduction loss: Similar guessing step appears about 268 times for a modern hash- based signature scheme. Not only theoretic loss: Matching multi-target attacks exist! [HRS16]: Can be overcome reducing from SPR 14.11.2019 https://sphincs.org/ 30
Relations Stronger assumption / easier to break Collision-Resistance Assumption / 2nd-Preimage- Resistance Attacks Our work weaker assumption/ harder to break One-way 11.12.2019 https://sphincs.org 31
Decisional Second-Preimage Resistance joint work with Daniel J. Bernstein, Asiacrypt 2019 DSPR it is hard to reliably determine if an input has a collision DSPR + SPR PRE (tightly) DSPR is hard for quantum adversaries 14.11.2019 https://sphincs.org/ 32
Stateless hash-based signatures SPHINCS Joint work with Daniel J. Bernstein, Daira Hopwood, Tanja Lange, Ruben Niederhagen, Louiza Papachristodoulou, Michael Schneider, Peter Schwabe, and Zooko Wilcox-O Hearn 14.11.2019 https://sphincs.org/ 33
Stateless hash-based signatures [NY89,Gol87,Gol04] OTS Goldreich s approach [Gol04]: Security parameter ? = 128 Use binary tree as in Merkle, but... for statelessness pick index i at random; requires huge tree to avoid index collisions (e.g., height h = 2? = 256). for efficiency: use binary certification tree of OTS key pairs (= Hypertree with ? = ), all OTS secret keys are generated pseudorandomly. OTS OTS OTS OTS OTS OTS OTS OTS 14.11.2019 https://sphincs.org/ 34
SPHINCS [BHH+15] Select index pseudorandomly Use a few-time signature key-pair on leaves to sign messages Few index collisions allowed Allows to reduce tree height Use hypertree: Use d < h. (SPHINCS-256: h=60, d=12) FTS 14.11.2019 https://sphincs.org/ 35
The SPHINCS+Signature Framework Joint work with Daniel J. Bernstein, Stefan K lbl, Ruben Niederhagen, Joost Rijneveld, Peter Schwabe
The SPHINCS+team Jean-Philippe Aumasson, Daniel J. Bernstein, Christoph Dobraunig, Maria Eichlseder, Scott Fluhrer, Stefan-Lukas Gazdag, Andreas H lsing, Panos Kampanakis, Stefan K lbl, Tanja Lange, Martin M. Lauridsen, Florian Mendel, Ruben Niederhagen, Christian Rechberger, Joost Rijneveld, Peter Schwabe 14.11.2019 https://sphincs.org/ 37
From SPHINCS to SPHINCS+ Allow for 264instead of 250signatures per key pair Add multi-target attack mitigation (Tweakable hash functions) New few-time signature scheme FORS Verifiable index selection Optional non-deterministic signatures (better SCA protection) 14.11.2019 https://sphincs.org/ 38
FTS (HORST FORS) Basic idea of FTS: ? ??= ?0,?1, ,?? Signature consists of ???0,???1, ,???? Generic attack: Find ? such that all ???selected by ??have been part of previous signatures. HORST: Draw all ???from same pool of secret values Issue: Possible to have ?0= ?1= = ??= ? so signature only requires knowledge of single value ??? FORS: Use ? independent pools of secret values Generic attacks get harder can choose smaller parameters smaller signatures 14.11.2019 https://sphincs.org/ 39
Tweakable hash functions A tool for modular proofs for hash-based signatures 14.11.2019 https://sphincs.org/ 40
Hashing for hash-based signatures (Change driven by goal to minimize security assumptions) LMS MSS XMSS XMSS-T (I q i j X) X X X B B H K H H H Y Y Y Y Gravity- SPHINCS SPHINCS+ robust SPHINCS+ simple SPHINCS 14.11.2019 https://sphincs.org/ 41
Tweakable hash function ?? ?,?,? ? P: Public parameters (one per key pair) T: Tweak (one per hash call) X: Message Y: Message Digest All of the previous modes are instantiations! 14.11.2019 https://sphincs.org/ 42
Required security properties (see paper for formal definitions) (PQ-)SM-TCR for distinct tweaks: - Single-function (= random but fixed P), - Multi-target (= adversary A can adaptively define targets (?,?), using oracle inititalized with P) - Target-Collision Resistance (= when targets defined, A receives P, has to find collision ?,? for one of the targets) - For distinct tweaks (= only one target per tweak) (PQ-)SM-DSPR for distinct tweaks: - ... - Decisional Second-Preimage Resistance (= decide for one target if it has a second preimage) - ... 14.11.2019 https://sphincs.org/ 43
In paper Tweakable hash constructions that achieve PQ-SM-TCR & PQ-SM- DSPR Construction 1: Standard model proof but massive public parameters Construction 2: Construction 1 with compressed public parameters (compression needs QROM, approx. XMSS-T construction) Construction 3: All QROM proof (simplified LMS construction) 14.11.2019 https://sphincs.org/ 44
Security using tweakable hash 14.11.2019 https://sphincs.org/ 45
Comparison 14.11.2019 https://sphincs.org/ 46
14.11.2019 https://sphincs.org/ 47
Conclusion We got several results establishing security of cryptographic hash functions in a post-quantum world. Strongest security notions are still open. New applications for hash functions lead to new security requirements that have to be studied. Skipped: Security proofs in the random oracle model change entirely. Often old security properties do not suffice (collapsing) Although Grovers algorithm is optimal, there are still many open questions for hash functions in a post-quantum world. 14.11.2019 https://sphincs.org/ 48
If youre signing something for the long-term future, and 40KB sigs is not a problem, use (stateless) hash-based sigs e.g. SPHINCS 30 30 Vadim Lyubashevsky, 2017 14.11.2019 https://sphincs.org/ 49
