Criptografia bazată pe hash

Criptografia bazată pe hash este termenul generic pentru construcțiile de primitive criptografice bazate pe securitatea funcțiilor hash. Este interesantă ca tip de criptografie post-cuantică.

Până în prezent, criptografia bazată pe hash este utilizată pentru a construi scheme de semnătură digitală, cum ar fi schema de semnătură Merkle, dovezi de cunoștințe zero și de integritate computațională, cum ar fi sistemul de demonstrații zk-STARK[1] și dovezi de interval pe baza acreditărilor emise prin protocolul HashWires[2]. Schemele de semnătură bazate pe hash combină o schemă de semnătură unică, cum ar fi o semnătură Lamport, cu o structură arborescentă Merkle. Deoarece o cheie a schemei de semnătură unică poate semna în siguranță doar un singur mesaj, este practic să se combine mai multe astfel de chei într-o singură structură mai mare. În acest scop se utilizează o structură arborescentă Merkle. În această structură ierarhică de date, o funcție hash și concatenarea sunt utilizate în mod repetat pentru a calcula nodurile arborelui.

O considerație cu schemele de semnătură bazate pe hash este că acestea pot semna în siguranță doar un număr limitat de mesaje, datorită utilizării schemelor de semnătură unică. Institutul Național de Standarde și Tehnologie din SUA (NIST) a specificat că algoritmii din competiția sa de criptografie post-cuantică acceptă în siguranță minimum 264 de semnături.[3]

NIST a standardizat criptografia bazată pe hash cu stări, bazată pe schema de semnături Merkle extinsă (XMSS) și semnăturile Leighton-Micali (LMS),[4] care sunt aplicabile în diferite circumstanțe, în 2020, dar a remarcat că cerința de a menține starea atunci când se utilizează le face mai dificil de implementat într-un mod care să evite utilizarea necorespunzătoare.[5][6][7]

În 2022, NIST a anunțat SPHINCS+ ca unul dintre cei trei algoritmi care urmează să fie standardizați pentru semnăturile digitale.[8] iar în 2024 NIST a anunțat standardul de semnătură digitală bazat pe hash fără stare (SLH-DSA)[9] bazat pe SPHINCS+.

Istoric

Leslie Lamport a inventat semnăturile bazate pe hash în 1979. Schemele de semnătură bazate pe hash XMSS (eXtended Merkle Signature Scheme)[10] și SPHINCS[11][12] au fost introduse în 2010 și, respectiv, 2015. XMSS a fost dezvoltat de o echipă de cercetători sub conducerea lui Johannes Buchmann și se bazează atât pe schema fundamentală a lui Merkle, cât și pe schema generalizată de semnătură Merkle (GMSS) din 2007.[13] O variantă multi-arborescentă a XMSS, XMSSMT, a fost descrisă în 2013.[14]

Scheme de semnătură unică

Schemele de semnătură bazate pe hash utilizează scheme de semnătură unică ca element constitutiv. O cheie de semnătură unică dată poate fi utilizată doar pentru a semna un singur mesaj în siguranță. Într-adevăr, semnăturile dezvăluie o parte din cheia de semnătură. Securitatea schemelor de semnătură unică (bazate pe hash) se bazează exclusiv pe securitatea unei funcții hash subiacente.

Schemele de semnătură unică utilizate în mod obișnuit includ schema Lamport-Diffie, schema Winternitz[15] și îmbunătățirile acesteia, cum ar fi schema W-OTS+.[16] Spre deosebire de schema fundamentală Lamport-Diffie, schema Winternitz și variantele sale pot semna mai mulți biți simultan. Numărul de biți care trebuie semnați simultan este determinat de o valoare: parametrul Winternitz. Existența acestui parametru oferă un compromis între dimensiune și viteză. Valorile mari ale parametrului Winternitz produc semnături și chei scurte, cu prețul unei semnări și verificări mai lente. În practică, o valoare tipică pentru acest parametru este 16.

În cazul semnăturilor bazate pe hash fără stare, se utilizează scheme de semnătură de puține ori. Astfel de scheme permit scăderea treptată a securității în cazul în care o cheie de timp mic este utilizată de mai multe ori. HORST este un exemplu de schemă de semnătură de timp mic.

Referințe

1. Ben-Sasson, Eli and Bentov, Iddo and Horesh, Yinon and Riabzev, Michael, 2018. Scalable, transparent, and post-quantum secure computational integrity.
2. Chalkias, Konstantinos; Cohen, Shir; Lewi, Kevin; Moezinia, Fredric; Romailler, Yolan (2021). „HashWires: Hyperefficient Credential-Based Range Proofs”. Privacy Enhancing Technologies Symposium (PETS) 2021.
3. „Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process” (PDF). NIST CSRC.
4. McGrew, David; Curcio, Michael; Fluhrer, Scott (April 2019). „RFC 8554 – Leighton–Micali Hash-Based Signatures”. tools.ietf.org. IETF.
5. Computer Security Division, Information Technology Laboratory (2019-02-01). „Request for Public Comments on Stateful HBS | CSRC”. CSRC | NIST. Retrieved 2019-02-04.
6. Alagic, Gorjan; Apon, Daniel; Cooper, David; Dang, Quynh; Dang, Thinh; Kelsey, John; Lichtinger, Jacob; Miller, Carl; Moody, Dustin; Peralta, Rene; Perlner, Ray (2022-07-05). „Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process”. NIST Ir 8413. doi:10.6028/NIST.IR.8413-upd1.
7. Cooper, David; Apon, Daniel; Dang, Quynh; Davidson, Michael; Dworkin, Morris; Miller, Carl (2020-10-29). „Recommendation for Stateful Hash-Based Signature Schemes”. NIST Special Publication 800-208. doi:10.6028/NIST.SP.800-208.
8. „NIST announces four quantum-resistant algorithms”. VentureBeat. 2022-07-05. Retrieved 2022-07-10.
9. „Stateless Hash-Based Digital Signature Standard” (PDF). NIST.gov. August 2024. doi:10.6028/NIST.FIPS.205.
10. Buchmann, Johannes; Dahmen, Erik; Hülsing, Andreas (2011). „XMSS – A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions”. Post-Quantum Cryptography. Lecture Notes in Computer Science. Vol. 7071. pp. 117–129. CiteSeerX 10.1.1.400.6086. doi:10.1007/978-3-642-25405-5_8. ISBN 978-3-642-25404-8. ISSN 0302-9743.
11. Bernstein, Daniel J.; Hopwood, Daira; Hülsing, Andreas; Lange, Tanja; Niederhagen, Ruben; Papachristodoulou, Louiza; Schneider, Michael; Schwabe, Peter; Wilcox-O’Hearn, Zooko (2015). „SPHINCS: Practical Stateless Hash-Based Signatures”. In Oswald, Elisabeth; Fischlin, Marc (eds.). Advances in Cryptology – EUROCRYPT 2015. Lecture Notes in Computer Science. Vol. 9056. Springer Berlin Heidelberg. pp. 368–397. CiteSeerX 10.1.1.690.6403. doi:10.1007/978-3-662-46800-5_15. ISBN 9783662467992.
12. „SPHINCS:Introduction”.
13. Buchmann, Johannes; Dahmen, Erik; Klintsevich, Elena; Okeya, Katsuyuki; Vuillaume, Camille (2007). „Merkle Signatures with Virtually Unlimited Signature Capacity”. Applied Cryptography and Network Security. Lecture Notes in Computer Science. Vol. 4521. pp. 31–45. doi:10.1007/978-3-540-72738-5_3. ISBN 978-3-540-72737-8.
14. Hülsing, Andreas; Rausch, Lea; Buchmann, Johannes (2013). „Optimal Parameters for XMSS MT”. Security Engineering and Intelligence Informatics. Lecture Notes in Computer Science. Vol. 8128. pp. 194–208. doi:10.1007/978-3-642-40588-4_14. ISBN 978-3-642-40587-7.
15. Dods, C.; Smart, N. P.; Stam, M. (2005). „Hash Based Digital Signature Schemes”. Cryptography and Coding. Lecture Notes in Computer Science. Vol. 3796. pp. 96–115. doi:10.1007/11586821_8. ISBN 978-3-540-30276-6.
16. Hülsing, Andreas (2013). „W-OTS+ – Shorter Signatures for Hash-Based Signature Schemes”. Progress in Cryptology – AFRICACRYPT 2013. Lecture Notes in Computer Science. Vol. 7918. pp. 173–188. doi:10.1007/978-3-642-38553-7_10. ISBN 978-3-642-38552-0.

(Include texte traduse și adaptate din Wikipedia de Nicolae Sfetcu)