Understanding the Relationship between Decisional Second-Preimage Resistance and Preimage Resistance in Cryptographic Hash Functions

This work delves into the subtle question of when Decisional Second-Preimage Resistance (SPR) implies Preimage Resistance (PRE) in hash functions. It presents a tool for enabling tight security proofs for hash-based signatures by exploring the success probability of adversaries against collision resistance, second-preimage resistance, and one-wayness. The study also discusses the implications of stronger assumptions such as Collision Resistance in relation to easier attack scenarios compared to Second-Preimage Resistance. Additionally, it addresses reductions and challenges in proving that Collision Resistance implies Second-Preimage Resistance and Second-Preimage Resistance implies Preimage Resistance.

• Cryptographic Hash Functions
• Security Properties
• SPR
• PRE
• Hash-Based Signatures

jessabe Follow

Uploaded on Oct 02, 2024 | 0 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. Decisional second- preimage resistance When does SPR imply PRE? Daniel J. Bernstein, Andreas H lsing

2. Motivation This work answers a long standing subtle question about the relation of hash function properties provides a tool that enables tight security proofs for hash-based signatures 11/29/2019 https://sphincs.org 2

3. 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. 3

4. 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] 4

5. 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 ? ? ?,? : ?? = ?? ? ? ] 5

6. 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 ? ?? ,? ? ?,? : ?? = ?] 6

7. Relations Stronger assumption / easier to break Collision-Resistance Assumption / 2nd-Preimage- Resistance Attacks weaker assumption/ harder to break One-way 11/29/2019 https://sphincs.org 7

8. CR implies SPR? ????(?): Reduction ??? 1. ? ? 0,1? ? 2. ? ????(?,?) 3. Return (?,? ) ????= ????? ??????? Succ Succ 8

9. SPR implies PRE? ????(?,?): Reduction ???? 1. ? = ?(?) 2. ? ????(?,?) 3. Return ? ???? ? ??????? ??????? Succ 0.5 Succ Where is the problem? 9

10. Positive result Rogaway-Shrimpton show that for ?(?) much bigger then ? we are fine 11/29/2019 https://sphincs.org 10

11. Negative result The identity function demonstrates that SPR cannot generally imply PRE. 11/29/2019 https://sphincs.org 11

12. The gap Functions with ?(?) ? (especially length preserving) Exactly the ones we use in hash-based OTS Are we doomed? 11/29/2019 https://sphincs.org 12

13. The general case SHA-X identity function SHA-X random function 11/29/2019 https://sphincs.org 13

14. Fooling the reduction Reductions have to work for all ?! ?(?,?): 1. Compute ? = ?? 2. If ? > 1, abort 3. Else ? = {?}, return ? 1(?) For ??: 0,1? 0,1? 0,1?random, ???? =1 Succ ? ????= 0 ??????? Succ 11/29/2019 https://sphincs.org 14

15. Decisional second-preimage resistance to the rescue! 1(??(?)) = 1 1, otherwise ??? = 0, if ?? ????if Can salvage reduction ???? 1. SPprob(fk) = Pr ??? = 1 ? ? 0,1? is non- negligible , and 2. it is hard to reliably determine ??? We show that SPprob fk 1 1 majority of all functions. E.g., for a random 256bit hash fk ?for the overwhelming 11/29/2019 https://sphincs.org 15

16. DSPR = It is hard to reliably determine ??? ????? = max{0, Adv? Pr[? ? 0,1?,? ? 0,1?,? ? ?,? :??? = ?] SPprob(fk) } 11/29/2019 https://sphincs.org 16

17. Some intuition about DSPR ????? 0 SPprob fk 1 Adv? If fkis strongly compressing, it is information-theoretically DSPR. ????? = max{0, Adv? Pr[? ? 0,1?,? ? 0,1?,? ? ?,? :??? = ?] SPprob(fk) } 11/29/2019 https://sphincs.org 17

18. Some intuition about DSPR Given SPR adversary ???? define: ????? 1. If ????(?,?) succeeds, return 1 2. Return 0. Requires Succ? non-zero advantage! ?????,? : ??????? > 2 SPprob fk 1 for ????? = max{0, Adv? Pr[? ? 0,1?,? ? 0,1?,? ? ?,? :??? = ?] SPprob(fk) } 11/29/2019 https://sphincs.org 18

19. DSPR at work ????(?,?): Reduction ???? 1. ? = ?(?) 2. ? ????(?,?) 3. Return ? We show ??????? ????????? ??????? Succ? Adv? 3 Succ? ????+ ???? ????(?,?): Reduction ????? 1. ? = ?(?) 2. ? ????(?,?) 3. Return 1 if ? ? 4. Return 0 11/29/2019 https://sphincs.org 19

20. Application to hash-based signatures Interactive Game T-OpenPRE: 1. Generate T pairs ??,?? = ??,???? ?? ? 0,1? 2. Give pairs to ? and allow ? to ask for up to ? 1 of the ?? 3. Output 1 if (?,?) ?( ) is a preimage (???? = ??)for unopened image ?? , Variants of this naturally arise in security proof of WOTS, and L-OTS 11/29/2019 https://sphincs.org 20

21. Pre T-OpenPRE is non-tight! Given ?? ??????? build ? ?,? : 1. Play T-OpenPRE game but replace random pair (??,??) by challenge ?,? 2. If ? asks to open position ?, abort 3. If ? returns (?,?), output ? Reduction loss of 1/T! 11/29/2019 https://sphincs.org 21

22. Multi-target DSPR 11/29/2019 https://sphincs.org 22

23. T-DSPR + T-SPR T-OpenPRE, tightly! ????, and ????? ???? Use T-target versions of ???? Can replace all pairs by challenges We do know a preimage If ?? ??????? always returns known image, ?? ???? DSPR ?? ??????? succeeds with high probability ?? ??????? will have advantage in breaking T- Else, ?? ??? 11/29/2019 https://sphincs.org 23

24. More in paper DSPR is quantum-hard for random functions Detailed analysis of SPprob Full proofs See The SPHINCS+ Signature Framework (CCS 19) for application to SPHINCS+ and other hash-based signatures. 11/29/2019 https://sphincs.org 24

25. Questions? Paper(s) available at https://sphincs.org/resources.html 11/29/2019 https://sphincs.org 25