When Does Second-Preimage Resistance Imply Preimage Resistance?

decisional second preimage resistance when does n.w
1 / 25
Embed
Share

This work delves into the relationship between hash function properties, shedding light on when Second-Preimage Resistance (SPR) implies Preimage Resistance (PRE). Through a comprehensive analysis, the study provides valuable insights for enhancing the security proofs of hash-based signatures like XMSS-T and SPHINCS+.

  • Hash functions
  • Security proofs
  • Second-Preimage Resistance
  • Preimage Resistance
  • Cryptography
rayaanacharya
seri_arm Follow

Uploaded on | 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. 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.

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

E N D

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 (XMSS-T & SPHINCS+) 11.12.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. 11.12.2019 https://sphincs.org 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] 11.12.2019 https://sphincs.org 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 ? ? ?,? : ?? = ?? ? ? ] 11.12.2019 https://sphincs.org 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 ? ?? ,? ? ?,? : ?? = ?] 11.12.2019 https://sphincs.org 6

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

  8. CR implies SPR? ????(?): Reduction ??? 1. ? ? 0,1? ? 2. ? ????(?,?) 3. Return (?,? ) ????= ????? ??????? Succ Succ 11.12.2019 https://sphincs.org 8

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

  10. Positive result Rogaway-Shrimpton (FSE 2004) show that for ?(?) sufficiently greater then ? we are fine 11.12.2019 https://sphincs.org 10

  11. Negative result The identity function demonstrates that SPR cannot unconditionally imply PRE. 11.12.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.12.2019 https://sphincs.org 12

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

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

  15. Decisional second-preimage resistance (DSPR) 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 Pr SPprob ?? < 0.6 2 2239 ?for the overwhelming 11.12.2019 https://sphincs.org 15

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

  17. Some intuition about DSPR ????? 0 SPprob fk 1 Adv? If fkis strongly compressing, it is information-theoretically DSPR. Using ???? to break DSPR we need Succ? ??????? > 2 SPprob fk 1 for non-zero advantage! ????? = Adv? Pr[? ? 0,1?,? ? 0,1?,? ? ?,? :??? = ?] SPprob(fk) max{0, } 11.12.2019 https://sphincs.org 17

  18. DSPR + SPR PRE ????(?,?): Reduction ???? 1. ? = ?(?) 2. ? ????(?,?) 3. Return ? We show ??????? ????????? ??????? Succ? Adv? 3 Succ? ????+ ???? ????(?,?): Reduction ????? 1. ? = ?(?) 2. ? ????(?,?) 3. Return 0 if ? = ? 4. Return 1 11.12.2019 https://sphincs.org 18

  19. Application to hash-based signatures Interactive Game T-OpenPRE: , ?? ? 0,1? 1. Generate T pairs ??,?? = ??,????? 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.12.2019 https://sphincs.org 19

  20. 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.12.2019 https://sphincs.org 20

  21. T-DSPR (multi-target, multi-function) 11.12.2019 https://sphincs.org 21

  22. T-DSPR + T-SPR T-OpenPRE, tightly! ????, and ????? ???? Use T-target versions of ???? Can replace all pairs by challenges We do know a preimage for each challenge -> can open! ?? ??????? will have If ?? ??????? always returns known image, ?? ???? advantage in breaking T-DSPR ?? ??????? succeeds with high probability Else, ?? ??? 11.12.2019 https://sphincs.org 22

  23. More in paper DSPR is quantum-hard for random functions Detailed analysis of Spprob Details on T-*** notions Full proofs See The SPHINCS+Signature Framework (CCS 19) for application to SPHINCS+and other hash-based signatures. 11.12.2019 https://sphincs.org 23

  24. Open problem Generic hardness of T-DSPR: 1 ?Adv? ? ???? ???? Can prove Adv? Conjecture: Adv? ? ????= Adv? ???? (as for SPR) 11.12.2019 https://sphincs.org 24

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

Related


No related presentations.

More Related Content