American Institute of Mathematical Sciences

Advanced
February  2019, 13(1): 185-193. doi: 10.3934/amc.2019012

On the security of the WOTS-PRF signature scheme

Philip Lafrance 1, and  Alfred Menezes 2,

1. 

ISARA Corporation, Waterloo, Canada
2. 

Department of Combinatorics & Optimization, University of Waterloo, Canada

Received  July 2018 Published  December 2018

We identify a flaw in the security proof and a flaw in the concrete security analysis of the WOTS-PRF variant of the Winternitz one-time signature scheme, and discuss the implications to its concrete security.

Keywords: One-time signature schemes, pseudorandom functions, security proofs.
Mathematics Subject Classification: Primary: 94A60.
Citation: Philip Lafrance, Alfred Menezes. On the security of the WOTS-PRF signature scheme. Advances in Mathematics of Communications, 2019, 13 (1) : 185-193. doi: 10.3934/amc.2019012
References:
[1]

M. Bellare, New proofs for NMAC and HMAC: Security without collision resistance, in: Advances in Cryptology - CRYPTO 2006, LNCS, 4117 (2006), 602-619. doi: 10.1007/11818175_36.  Google Scholar

[2]

D. Bernstein and T. Lange, Non-uniform cracks in the concrete: The power of free computation, in: Advances in Cryptology - ASIACRYPT 2013, LNCS, 8270 (2013), 321-340. doi: 10.1007/978-3-642-42045-0_17.  Google Scholar

[3]

J. Buchmann, E. Dahmen, S. Ereth, A. Hülsing and M. Rückert, On the security of the Winternitz one-time signature scheme, in: Progress in Cryptology - AFRICACRYPT 2011, LNCS, 6737 (2011), 363-378. doi: 10.1007/978-3-642-21969-6_23.  Google Scholar

[4]

J. Buchmann, E. Dahmen, S. Ereth, A. Hülsing and M. Rückert, On the security of the Winternitz one-time signature scheme, International Journal of Applied Cryptography, 3 (2013), 84-96.  doi: 10.1504/IJACT.2013.053435.  Google Scholar

[5]

J. Buchmann, E. Dahmen and A. H¨ulsing, XMSS - a practical forward secure signature scheme based on minimal security assumptions, in: Post-Quantum Cryptography - PQCrypto 2011, LNCS, 7071 (2011), 117-129. doi: 10.1007/978-3-642-25405-5_8.  Google Scholar

[6]

C. Dods, N. Smart and M. Stam, Hash based digital signature schemes, in: Cryptography and Coding, LNCS, 3796 (2005), 96-115. doi: 10.1007/11586821_8.  Google Scholar

[7]

E. Eaton, Leighton-Micali hash-based signatures in the quantum random-oracle model, in: Selected Areas in Cryptography - SAC 2017, LNCS 10719 (2018), 263-280.  Google Scholar

[8]

S. Even, O. Goldreich and S. Micali, On-line/off-line digital signatures, Journal of Cryptology, 9 (1996), 35-67.  doi: 10.1007/BF02254791.  Google Scholar

[9]

O. Goldreich, S. Goldwasser and S. Micali, How to construct random functions, Journal of the ACM, 33 (1986), 792-807.  doi: 10.1145/6490.6503.  Google Scholar

[10]

J. Håstad, R. Impagliazzo, L. Levin and M. Luby, A pseudorandom generator from any oneway function, SIAM Journal on Computing, 28 (1999), 1364-1396.  doi: 10.1137/S0097539793244708.  Google Scholar

[11]

A. Hülsing, Practical Forward Secure Signatures Using Minimal Security Assumptions, Ph. D. thesis, Technical University of Darmstadt, 2013. Google Scholar

[12]

A. Hülsing, W-OTS+ - Shorter signatures for hash-based signature schemes, in: Progress in Cryptology - AFRICACRYPT 2013, LNCS 7918 (2013), 173-188. Google Scholar

[13]

A. Hülsing, C. Busold and J. Buchmann, Forward secure signatures on smart cards, in: Selected Areas in Cryptography - SAC 2012, LNCS 7707 (2013), 66-80. Google Scholar

[14]

A. Hülsing, D. Butin, S. Gazdag, J. Rijneveld and A. Mohaisen, XMSS: eXtended Merkle Signature Scheme, RFC 8391, May 31, 2018; available at https://datatracker.ietf.org/doc/rfc8391/. Google Scholar

[15]

A. Hülsing, L. Rausch and J. Buchmann, Optimal parameters for XMSSMT, in: Availability, Reliability, and Security in Information Systems and HCI - CD-ARES 2013, LNCS 8128 (2013), 194-208. Google Scholar

[16]

A. Hülsing, J. Rijneveld and F. Song, Mitigating multi-target attacks in hash-based signatures, in: Public-Key Cryptography - PKC 2016, LNCS 9614 (2016), 387-416. doi: 10.1007/978-3-662-49384-7_15.  Google Scholar

[17]

J. Katz, Analysis of a proposed hash-based signature scheme, in: Security Standardisation Research - SSR 2016, LNCS 10074 (2016), 261-273. Google Scholar

[18]

N. Koblitz and A. Menezes, Another look at HMAC, Journal of Mathematical Cryptology, 7 (2013), 225-251.  doi: 10.1515/jmc-2013-5004.  Google Scholar

[19]

N. Koblitz and A. Menezes, Another look at non-uniformity, Groups Complexity Cryptology, 5 (2013), 117-139.  doi: 10.1515/gcc-2013-0008.  Google Scholar

[20]

L. Lamport, Constructing digital signatures from a one way function, Technical Report CSL-98, SRI International, 1979. Google Scholar

[21]

D. McGrew, M. Curcio and S. Fluhrer, Hash-based signatures, Internet Draft, April 5, 2018; available at https://datatracker.ietf.org/doc/draft-mcgrew-hash-sigs/. Google Scholar

[22]

R. Merkle, A digital signature based on a conventional encryption function, in: Advances in Cryptology - CRYPTO '87, LNCS 293 (1988), 369-378. Google Scholar

[23]

M. Raab and A. Steger, "Balls into bins" - = - a simple and tight analysis, in: Randomization and Approximation Techniques in Computer Science - RANDOM 1998, LNCS 1518 (1998), 159-170. doi: 10.1007/3-540-49543-6_13.  Google Scholar

show all references

References:
[1]

M. Bellare, New proofs for NMAC and HMAC: Security without collision resistance, in: Advances in Cryptology - CRYPTO 2006, LNCS, 4117 (2006), 602-619. doi: 10.1007/11818175_36.  Google Scholar

[2]

D. Bernstein and T. Lange, Non-uniform cracks in the concrete: The power of free computation, in: Advances in Cryptology - ASIACRYPT 2013, LNCS, 8270 (2013), 321-340. doi: 10.1007/978-3-642-42045-0_17.  Google Scholar

[3]

J. Buchmann, E. Dahmen, S. Ereth, A. Hülsing and M. Rückert, On the security of the Winternitz one-time signature scheme, in: Progress in Cryptology - AFRICACRYPT 2011, LNCS, 6737 (2011), 363-378. doi: 10.1007/978-3-642-21969-6_23.  Google Scholar

[4]

J. Buchmann, E. Dahmen, S. Ereth, A. Hülsing and M. Rückert, On the security of the Winternitz one-time signature scheme, International Journal of Applied Cryptography, 3 (2013), 84-96.  doi: 10.1504/IJACT.2013.053435.  Google Scholar

[5]

J. Buchmann, E. Dahmen and A. H¨ulsing, XMSS - a practical forward secure signature scheme based on minimal security assumptions, in: Post-Quantum Cryptography - PQCrypto 2011, LNCS, 7071 (2011), 117-129. doi: 10.1007/978-3-642-25405-5_8.  Google Scholar

[6]

C. Dods, N. Smart and M. Stam, Hash based digital signature schemes, in: Cryptography and Coding, LNCS, 3796 (2005), 96-115. doi: 10.1007/11586821_8.  Google Scholar

[7]

E. Eaton, Leighton-Micali hash-based signatures in the quantum random-oracle model, in: Selected Areas in Cryptography - SAC 2017, LNCS 10719 (2018), 263-280.  Google Scholar

[8]

S. Even, O. Goldreich and S. Micali, On-line/off-line digital signatures, Journal of Cryptology, 9 (1996), 35-67.  doi: 10.1007/BF02254791.  Google Scholar

[9]

O. Goldreich, S. Goldwasser and S. Micali, How to construct random functions, Journal of the ACM, 33 (1986), 792-807.  doi: 10.1145/6490.6503.  Google Scholar

[10]

J. Håstad, R. Impagliazzo, L. Levin and M. Luby, A pseudorandom generator from any oneway function, SIAM Journal on Computing, 28 (1999), 1364-1396.  doi: 10.1137/S0097539793244708.  Google Scholar

[11]

A. Hülsing, Practical Forward Secure Signatures Using Minimal Security Assumptions, Ph. D. thesis, Technical University of Darmstadt, 2013. Google Scholar

[12]

A. Hülsing, W-OTS+ - Shorter signatures for hash-based signature schemes, in: Progress in Cryptology - AFRICACRYPT 2013, LNCS 7918 (2013), 173-188. Google Scholar

[13]

A. Hülsing, C. Busold and J. Buchmann, Forward secure signatures on smart cards, in: Selected Areas in Cryptography - SAC 2012, LNCS 7707 (2013), 66-80. Google Scholar

[14]

A. Hülsing, D. Butin, S. Gazdag, J. Rijneveld and A. Mohaisen, XMSS: eXtended Merkle Signature Scheme, RFC 8391, May 31, 2018; available at https://datatracker.ietf.org/doc/rfc8391/. Google Scholar

[15]

A. Hülsing, L. Rausch and J. Buchmann, Optimal parameters for XMSSMT, in: Availability, Reliability, and Security in Information Systems and HCI - CD-ARES 2013, LNCS 8128 (2013), 194-208. Google Scholar

[16]

A. Hülsing, J. Rijneveld and F. Song, Mitigating multi-target attacks in hash-based signatures, in: Public-Key Cryptography - PKC 2016, LNCS 9614 (2016), 387-416. doi: 10.1007/978-3-662-49384-7_15.  Google Scholar

[17]

J. Katz, Analysis of a proposed hash-based signature scheme, in: Security Standardisation Research - SSR 2016, LNCS 10074 (2016), 261-273. Google Scholar

[18]

N. Koblitz and A. Menezes, Another look at HMAC, Journal of Mathematical Cryptology, 7 (2013), 225-251.  doi: 10.1515/jmc-2013-5004.  Google Scholar

[19]

N. Koblitz and A. Menezes, Another look at non-uniformity, Groups Complexity Cryptology, 5 (2013), 117-139.  doi: 10.1515/gcc-2013-0008.  Google Scholar

[20]

L. Lamport, Constructing digital signatures from a one way function, Technical Report CSL-98, SRI International, 1979. Google Scholar

[21]

D. McGrew, M. Curcio and S. Fluhrer, Hash-based signatures, Internet Draft, April 5, 2018; available at https://datatracker.ietf.org/doc/draft-mcgrew-hash-sigs/. Google Scholar

[22]

R. Merkle, A digital signature based on a conventional encryption function, in: Advances in Cryptology - CRYPTO '87, LNCS 293 (1988), 369-378. Google Scholar

[23]

M. Raab and A. Steger, "Balls into bins" - = - a simple and tight analysis, in: Randomization and Approximation Techniques in Computer Science - RANDOM 1998, LNCS 1518 (1998), 159-170. doi: 10.1007/3-540-49543-6_13.  Google Scholar

Figure 1.  The incomplete $\alpha$'th Winternitz hash chain in ${\mathcal{A}}_{{\rm KOW}}$'s experiment
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  The tree of $w$-keychains to $pk_{\alpha}$
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Shan Liu, Hui Zhao, Ximin Rong. Time-consistent investment-reinsurance strategy with a defaultable security under ambiguous environment. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021015
[2]

Dong-Ho Tsai, Chia-Hsing Nien. On space-time periodic solutions of the one-dimensional heat equation. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3997-4017. doi: 10.3934/dcds.2020037
[3]

Pablo D. Carrasco, Túlio Vales. A symmetric Random Walk defined by the time-one map of a geodesic flow. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020390
[4]

Peter Giesl, Zachary Langhorne, Carlos Argáez, Sigurdur Hafstein. Computing complete Lyapunov functions for discrete-time dynamical systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 299-336. doi: 10.3934/dcdsb.2020331
[5]

Palash Sarkar, Subhadip Singha. Verifying solutions to LWE with implications for concrete security. Advances in Mathematics of Communications, 2021, 15 (2) : 257-266. doi: 10.3934/amc.2020057
[6]

Jie Shen, Nan Zheng. Efficient and accurate sav schemes for the generalized Zakharov systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 645-666. doi: 10.3934/dcdsb.2020262
[7]

Fabio Camilli, Giulia Cavagnari, Raul De Maio, Benedetto Piccoli. Superposition principle and schemes for measure differential equations. Kinetic & Related Models, 2021, 14 (1) : 89-113. doi: 10.3934/krm.2020050
[8]

Julian Koellermeier, Giovanni Samaey. Projective integration schemes for hyperbolic moment equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2021008
[9]

Jintai Ding, Zheng Zhang, Joshua Deaton. The singularity attack to the multivariate signature scheme HIMQ-3. Advances in Mathematics of Communications, 2021, 15 (1) : 65-72. doi: 10.3934/amc.2020043
[10]

Bimal Mandal, Aditi Kar Gangopadhyay. A note on generalization of bent boolean functions. Advances in Mathematics of Communications, 2021, 15 (2) : 329-346. doi: 10.3934/amc.2020069
[11]

Andreas Koutsogiannis. Multiple ergodic averages for tempered functions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1177-1205. doi: 10.3934/dcds.2020314
[12]

Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044
[13]

Zhouchao Wei, Wei Zhang, Irene Moroz, Nikolay V. Kuznetsov. Codimension one and two bifurcations in Cattaneo-Christov heat flux model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020344
[14]

Anton A. Kutsenko. Isomorphism between one-dimensional and multidimensional finite difference operators. Communications on Pure & Applied Analysis, 2021, 20 (1) : 359-368. doi: 10.3934/cpaa.2020270
[15]

Mikhail I. Belishev, Sergey A. Simonov. A canonical model of the one-dimensional dynamical Dirac system with boundary control. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021003
[16]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169
[17]

Xinpeng Wang, Bingo Wing-Kuen Ling, Wei-Chao Kuang, Zhijing Yang. Orthogonal intrinsic mode functions via optimization approach. Journal of Industrial & Management Optimization, 2021, 17 (1) : 51-66. doi: 10.3934/jimo.2019098
[18]

Lars Grüne. Computing Lyapunov functions using deep neural networks. Journal of Computational Dynamics, 2020  doi: 10.3934/jcd.2021006
[19]

Peter Giesl, Sigurdur Hafstein. System specific triangulations for the construction of CPA Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020378
[20]

Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $ (n, m) $-functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020117

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (173)
  • HTML views (324)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences