Quantum-Resistance Meets White-Box Cryptography: How to Implement Hash-Based Signatures against White-Box Attackers?

Kemal Bicakci; Kemal Ulker; Yusuf Uzunay; Halis Taha Şahin; Muhammed Said Gündoğan

doi:10.62056/an59qgxq

Quantum-Resistance Meets White-Box Cryptography: How to Implement Hash-Based Signatures against White-Box Attackers?

Authors

Kemal Bicakci, Kemal Ulker, Yusuf Uzunay, Halis Taha Şahin, Muhammed Said Gündoğan

Kemal Bicakci

Informatics Institute, Istanbul Technical University, Istanbul, Türkiye
Securify Information Tech. and Security Training Consulting Ltd., Ankara, Türkiye
kemalbicakci at itu dot edu dot tr

Kemal Ulker

TOBB University of Economics and Technology, Ankara, Türkiye
Securify Information Tech. and Security Training Consulting Ltd., Ankara, Türkiye
kemal dot lkr at gmail dot com

Yusuf Uzunay

Securify Information Tech. and Security Training Consulting Ltd., Ankara, Türkiye
yusuf dot uzunay at securify dot com dot tr

Halis Taha Şahin

Informatics Institute, Istanbul Technical University, Istanbul, Türkiye
TÜBİTAK, Kocaeli, Türkiye
halis dot sahin at tubitak dot gov dot tr

Muhammed Said Gündoğan

TÜBİTAK, Kocaeli, Türkiye
said dot gundogan at tubitak dot gov dot tr

Keywords: white-box cryptography digital signature white-box signature quantum-safe signature hash chain one-time password hash tree SPHINCS+

Abstract

The adversary model of white-box cryptography includes an extreme case where the adversary, sitting at the endpoint, has full access to a cryptographic scheme. Motivating by the fact that most existing white-box implementations focus on symmetric encryption, we present implementations for hash-based signatures so that the security against white-box attackers (who have read-only access to data with a size bounded by a space-hardness parameter M) depends on the availability of a white-box secure cipher (in addition to a general one-way function). We also introduce parameters and key-generation complexity results for white-box secure instantiation of stateless hash-based signature scheme SPHINCS+, one of the NIST selections for quantum-resistant digital signature algorithms, and its older version SPHINCS. We also present a hash tree-based solution for one-time passwords secure in a white-box attacker context. We implement the proposed solutions and share our performance results.

References

[ACD⁺22]

Gorjan Alagic, David Cooper, Quynh Dang, Thinh Dang, John M. Kelsey, Jacob Lichtinger, Yi-Kai Liu, Carl A. Miller, Dustin Moody, Rene Peralta, Ray Perlner, Angela Robinson, Daniel Smith-Tone, and Daniel Apon. Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process. 2022-07-05 04:07:00 2022.

Google Scholar ePrint

[BHH⁺15]

Daniel J. Bernstein, Daira Hopwood, Andreas Hülsing, Tanja Lange, Ruben Niederhagen, Louiza Papachristodoulou, Michael Schneider, Peter Schwabe, and Zooko Wilcox-O'Hearn. SPHINCS: Practical Stateless Hash-Based Signatures. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology – EUROCRYPT 2015, Part I, volume 9056 of Lecture Notes in Computer Science, pages 368–397, Sofia, Bulgaria. 2015. Springer, Heidelberg, Germany. DOI: 10.1007/978-3-662-46800-5_15

Google Scholar ePrint

[BHK⁺19]

Daniel J. Bernstein, Andreas Hülsing, Stefan Kölbl, Ruben Niederhagen, Joost Rijneveld, and Peter Schwabe. The SPHINCS$^+$ Signature Framework. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019: 26th Conference on Computer and Communications Security, pages 2129–2146, London, UK. 2019. ACM Press. DOI: 10.1145/3319535.3363229

Google Scholar ePrint

[BI15]

Andrey Bogdanov and Takanori Isobe. White-Box Cryptography Revisited: Space-Hard Ciphers. In Indrajit Ray, Ninghui Li, and Christopher Kruegel, editors, ACM CCS 2015: 22nd Conference on Computer and Communications Security, pages 1058–1069, Denver, CO, USA. 2015. ACM Press. DOI: 10.1145/2810103.2813699

Google Scholar ePrint

[BIT16]

Andrey Bogdanov, Takanori Isobe, and Elmar Tischhauser. Towards Practical Whitebox Cryptography: Optimizing Efficiency and Space Hardness. In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in Cryptology – ASIACRYPT 2016, Part I, volume 10031 of Lecture Notes in Computer Science, pages 126–158, Hanoi, Vietnam. 2016. Springer, Heidelberg, Germany. DOI: 10.1007/978-3-662-53887-6_5

Google Scholar ePrint

[BTT03]

Kemal Bicakci, Gene Tsudik, and Brian Tung. How to construct optimal one-time signatures. Comput. Netw., 43(3):339–349, 2003. DOI: 10.1016/S1389-1286(03)00285-8

Google Scholar ePrint

[CAD⁺20]

D. A. Cooper, D. C. Apon, Q. H. Dang, M. S. Davidson, M. J. Dworkin, and C. A. Miller. Recommendation for stateful hash-based signature schemes. NIST Special Publication, 800:208, 2020. DOI: 10.6028/NIST.SP.800-208

Google Scholar ePrint

[CEJv03]

Stanley Chow, Philip A. Eisen, Harold Johnson, and Paul C. van Oorschot. White-Box Cryptography and an AES Implementation. In Kaisa Nyberg and Howard M. Heys, editors, SAC 2002: 9th Annual International Workshop on Selected Areas in Cryptography, volume 2595 of Lecture Notes in Computer Science, pages 250–270, St. John's, Newfoundland, Canada. 2003. Springer, Heidelberg, Germany. DOI: 10.1007/3-540-36492-7_17

Google Scholar ePrint

[DGH21]

Emmanuelle Dottax, Christophe Giraud, and Agathe Houzelot. White-Box ECDSA: Challenges and Existing Solutions. In Shivam Bhasin and Fabrizio De Santis, editors, COSADE 2021: 12th International Workshop on Constructive Side-Channel Analysis and Secure Design, volume 12910 of Lecture Notes in Computer Science, pages 184–201, Lugano, Switzerland. 2021. Springer, Heidelberg, Germany. DOI: 10.1007/978-3-030-89915-8_9

Google Scholar ePrint

[ERC]

ERC-4337. ERC-4337. Accessed 07-06-2024. https://www.erc4337.io.

Google Scholar ePrint

[FHW⁺20]

Qi Feng, Debiao He, Huaqun Wang, Neeraj Kumar, and Kim-Kwang Raymond Choo. White-Box Implementation of Shamir’s Identity-Based Signature Scheme. IEEE Systems Journal, 14(2):1820-1829, 2020. DOI: 10.1109/JSYST.2019.2910934

Google Scholar ePrint

[GG22]

Pierre Galissant and Louis Goubin. Resisting Key-Extraction and Code-Compression: a Secure Implementation of the HFE Signature Scheme in the White-Box Model. https://eprint.iacr.org/2022/138. Cryptology ePrint Archive, Report 2022/138. 2022.

Google Scholar ePrint

[Hal95]

N. Haller. The S/KEY One-Time Password System. RFC 1760, 1995.

Google Scholar ePrint

[Jak02]

M. Jakobsson. Fractal hash sequence representation and traversal. In Proceedings IEEE International Symposium on Information Theory, pages 437. June 2002. IEEE. DOI: 10.1109/ISIT.2002.1023709

Google Scholar ePrint

[Joy08]

Marc Joye. On white-box cryptography. Security of Information and Networks, 1:7–12, 2008.

Google Scholar ePrint

[KMB17]

Dmitry Kogan, Nathan Manohar, and Dan Boneh. T/Key: Second-Factor Authentication From Secure Hash Chains. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017: 24th Conference on Computer and Communications Security, pages 983–999, Dallas, TX, USA. 2017. ACM Press. DOI: 10.1145/3133956.3133989

Google Scholar ePrint

[Lam79]

Leslie Lamport. Constructing Digital Signatures from a One-way Function. Technical report number SRI-CSL-98, SRI International Computer Science Laboratory. October 1979.

Google Scholar ePrint

[Lam81]

L. Lamport. Password authentication with insecure communication. Communications of the ACM, 24(11):770–772, 1981. DOI: 10.1145/358790.358797

Google Scholar ePrint

[LLW22]

Lingyun Li, Xianhui Lu, and Kunpeng Wang. Hash-based signature revisited. Cybersecurity, 5(1):1–26, 2022. DOI: 10.1186/s42400-022-00117-w

Google Scholar ePrint

[LRH⁺22]

Jun Liu, Vincent Rijmen, Yupu Hu, Jie Chen, and Baocang Wang. WARX: efficient white-box block cipher based on ARX primitives and random MDS matrix. Sci. China Inf. Sci., 65(132302), 2022. DOI: 10.1007/s11432-020-3105-1

Google Scholar ePrint

[Ma20]

Tianchen Ma. White-box Schnorr Signature for Internet of Things Security. In 2020 5th International Conference on Mechanical, Control and Computer Engineering (ICMCCE). 2020. IEEE. DOI: 10.1109/ICMCCE51767.2020.00425

Google Scholar ePrint

[Mer88]

Ralph C. Merkle. A Digital Signature Based on a Conventional Encryption Function. In Carl Pomerance, editor, Advances in Cryptology – CRYPTO'87, volume 293 of Lecture Notes in Computer Science, pages 369–378, Santa Barbara, CA, USA. 1988. Springer, Heidelberg, Germany. DOI: 10.1007/3-540-48184-2_32

Google Scholar ePrint

[Mer90]

Ralph C. Merkle. A Certified Digital Signature. In Gilles Brassard, editor, Advances in Cryptology – CRYPTO'89, volume 435 of Lecture Notes in Computer Science, pages 218–238, Santa Barbara, CA, USA. 1990. Springer, Heidelberg, Germany. DOI: 10.1007/0-387-34805-0_21

Google Scholar ePrint

[MMPR11]

D. M'Raihi, S. Machani, M. Pei, and J. Rydell. TOTP: Time-Based One-Time Password Algorithm. Technical report number 6238, Internet Engineering Task Force (IETF). May 2011.

Google Scholar ePrint

[qrc20]

QR Codes. Last accessed on 2/28/2022. https://github.com/ricmoo/QRCode/blob/master/README.md. 2020.

Google Scholar ePrint

[RR02]

Leonid Reyzin and Natan Reyzin. Better than BiBa: Short One-Time Signatures with Fast Signing and Verifying. In Lynn Margaret Batten and Jennifer Seberry, editors, ACISP 02: 7th Australasian Conference on Information Security and Privacy, volume 2384 of Lecture Notes in Computer Science, pages 144–153, Melbourne, Victoria, Australia. 2002. Springer, Heidelberg, Germany. DOI: 10.1007/3-540-45450-0_11

Google Scholar ePrint

[sph]

SPHINCS+ Parameter Exploration. https://sphincs.org/data/spx_parameter_exploration.sage.

Google Scholar ePrint

[ZHH⁺20]

Yudi Zhang, Debiao He, Xinyi Huang, Ding Wang, Kim-Kwang Raymond Choo, and Jing WANG. White-box implementation of the identity-based signature scheme in the IEEE P1363 standard for public key cryptography. IEICE TRANSACTIONS on Information and Systems, 103(2):188–195, 2020. DOI: 10.1587/transinf.2019INP0004

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/an59qgxq

History

Submitted: 2024-03-04
Accepted: 2024-06-03
Published: 2024-07-08

How to cite

Kemal Bicakci, Kemal Ulker, Yusuf Uzunay, Halis Taha Şahin, and Muhammed Said Gündoğan, "Quantum-Resistance Meets White-Box Cryptography: How to Implement Hash-Based Signatures against White-Box Attackers?," IACR Communications in Cryptology, vol. 1, no. 2, Jul 08, 2024, doi: 10.62056/an59qgxq.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-2-5,
    author = "Bicakci, Kemal and Ulker, Kemal and Uzunay, Yusuf and Şahin, Halis Taha and Gündoğan, Muhammed Said",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Quantum-Resistance Meets White-Box Cryptography: How to Implement Hash-Based Signatures against White-Box Attackers?",
    volume = "1",
    number = "2",
    date = "2024-07-08",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/an59qgxq"
}

TY - JOUR
AU - Bicakci, Kemal
AU - Ulker, Kemal
AU - Uzunay, Yusuf
AU - Şahin, Halis
AU - Gündoğan, Muhammed
PY  - 2024
TI  - Quantum-Resistance Meets White-Box Cryptography: How to Implement Hash-Based Signatures against White-Box Attackers?
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 2
DO  - 10.62056/an59qgxq
UR  - https://doi.org/10.62056/an59qgxq
AB  - <p>The adversary model of white-box cryptography includes an extreme case where the adversary, sitting at the endpoint, has full access to a cryptographic scheme. Motivating by the fact that most existing white-box implementations focus on symmetric encryption, we present implementations for hash-based signatures so that the security against white-box attackers (who have read-only access to data with a size bounded by a space-hardness parameter M) depends on the availability of a white-box secure cipher (in addition to a general one-way function). We also introduce parameters and key-generation complexity results for white-box secure instantiation of stateless hash-based signature scheme SPHINCS+, one of the NIST selections for quantum-resistant digital signature algorithms, and its older version SPHINCS. We also present a hash tree-based solution for one-time passwords secure in a white-box attacker context. We implement the proposed solutions and share our performance results. </p>
ER  -

Kemal Bicakci, Kemal Ulker, Yusuf Uzunay, Halis Taha Şahin, and Muhammed Said Gündoğan, "Quantum-Resistance Meets White-Box Cryptography: How to Implement Hash-Based Signatures against White-Box Attackers?," IACR Communications in Cryptology, vol. 1, no. 2, Jul 08, 2024, doi: 10.62056/an59qgxq.