Implementação Paralela do Algoritmo de Geração de Chaves do Esquema de Assinatura Digital XMSS (eXtended Merkle Signature Scheme)
Resumo
Algoritmos de assinatura baseados em hash estão ganhando atenção devido a sua apregoada resistência a algoritmos quânticos. Apesar dos tempos de confecção e verificação de assinatura serem compatíveis com os tempos dos algoritmos atualmente em uso, o tempo de geração das chaves é ordens de grandeza superior. Este artigo apresenta e analisa o desempenho de duas implementações de paralelismo MIMD (Multiple Instruction Multiple Data) para acelerar o tempo de execução do algoritmo de geração de chaves do esquema de assinatura digital baseado em hash XMSS (eXtended Merkle Signature Scheme).Referências
Bellare, M. (2002). A note on negligible functions. J. Cryptology, 15(4):271–284.
Bellare, M. and Rogaway, P. (1997). Collision-resistant hashing: Towards making uowhfs practical. In Advances in Cryptology - CRYPTO '97, 17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 1997, Proceedings, pages 470–484.
Bernstein, D. J., Hopwood, D., Hülsing, A., Lange, T., Niederhagen, R., Papachristodoulou, L., Schneider, M., Schwabe, P., and Wilcox-O'Hearn, Z. (2015). SPHINCS: practical stateless hash-based signatures. In Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Soa, Bulgaria, April 26-30, 2015, Proceedings, Part I, pages 368–397.
Brassard, G., Høyer, P., and Tapp, A. (1998). Quantum cryptanalysis of hash and clawfree functions. In LATIN '98: Theoretical Informatics, Third Latin American Symposium, Campinas, Brazil, April, 20-24, 1998, Proceedings, pages 163–169.
Buchmann, J. A., Dahmen, E., and Hülsing, A. (2011). XMSS - A practical forward IACR Cryptology
secure signature scheme based on minimal security assumptions. ePrint Archive, 2011:484.
Butin, D. (2017). Hash-based signatures: State of play. IEEE Security & Privacy, 15(4):37–43.
Butin, D., Walde, J., and Buchmann, J. A. (2017). Post-quantum authentication in openssl with hash-based signatures. In Tenth International Conference on Mobile Computing and Ubiquitous Network, ICMU 2017, Toyama, Japan, October 3-5, 2017, pages 1–6.
Daniel, H. W. and Steele, Jr., G. L. (1986). Data parallel algorithms. Commun. ACM, 29(12):1170–1183.
de Oliveira, A. K. D. S. and López, J. (2015). An efcient software implementation of the hash-based signature scheme MSS and its variants. In Progress in Cryptology - LATINCRYPT 2015 - 4th International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015, Proceedings, pages 366–383.
de Oliveira, A. K. D. S., Lopez, J., and Cabral, R. (2017). High performance of hash- based signature schemes. International Journal of Advanced Computer Science and Applications, 8:421–432.
Dods, C., Smart, N. P., and Stam, M. (2005). Hash based digital signature schemes. In Cryptography and Coding, 10th IMA International Conference, Cirencester, UK, December 19-21, 2005, Proceedings, pages 96–115.
Gorbenko, Y. I., Melnik, T. V., and Gorbenko, I. D. (2018). Analysis of potential postquantum schemes of hash-based digital signatures. Telecommunications and Radio Engineering, 77:603–626.
Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 212–219.
Hevia, A. and Micciancio, D. (2002). The provable security of graph-based one-time signatures and extensions to algebraic signature schemes. In Advances in Cryptology - ASIACRYPT 2002, 8th International Conference on the Theory and Application of Cryptology and Information Security, Queenstown, New Zealand, December 1-5, 2002, Proceedings, pages 379–396.
Hülsing, A. (2017). WOTS+ - shorter signatures for hash-based signature schemes. IACR Cryptology ePrint Archive, 2017:965.
Hülsing, A., Butin, D., Gazdag, S., Rijneveld, J., and Mohaisen, A. (2018). XMSS: extended merkle signature scheme. RFC, 8391:1–74.
Hülsing, A., Gazdag, S.-L., Butin, D., and Buchmann, J. (2015a). Hash-based signatures: In Workshop on Cybersecurity in a Post-Quantum An outline for a new standard. World, NIST.
Hülsing, A., Rausch, L., and Buchmann, J. A. (2017). Optimal parameters for XMSSM T . IACR Cryptology ePrint Archive, 2017:966.
Hülsing, A., Rijneveld, J., and Schwabe, P. (2015b). Armed SPHINCS - computing a 41kb signature in 16kb of RAM. IACR Cryptology ePrint Archive, 2015:1042.
Lamport, L. (1979). Constructing digital signatures from a one-way function. Technical report, SRI International Computer Science Laboratory.
Merkle, R. (1979). Secrecy, authentication and public key systems / A certied digital signature. PhD thesis, Dept. of Electrical Engineering, Stanford University.
Naor, M. and Yung, M. (1989). Universal one-way hash functions and their cryptographic applications. In Proceedings of the Twenty-rst Annual ACM Symposium on Theory of Computing, STOC '89, pages 33–43, New York, NY, USA. ACM.
NIST (2016). Submission requirements and evaluation criteria for the post-quantum cryptography standardization process. Announcement.
Pereira, G. C. C. F. (2015). Assinaturas Digitais Pós Quanticas Multivariadas e Baseadas em Hash. PhD thesis, Departamento de Engenharia de Computação e Sistemas Digitais, Escola Politécnica da Universidade de São Paulo.
Pereira, G. C. C. F., Puodzius, C., and Barreto, P. S. L. M. (2016). Shorter hash-based signatures. Journal of Systems and Software, 116:95–100.
Rompel, J. (1990). One-way functions are necessary and sufcient for secure signatures. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 387–394.
Stallings, W. (2014). Criptograa e Segurança de Redes - Princípios e Práticas (6. ed. Pearson Education.
Stevens, M., Bursztein, E., Karpman, P., Albertini, A., and Markov, Y. (2017). The rst collision for full SHA-1. In Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part I, pages 570–596.
Wang, W., Jungk, B., Wí'alde, J., Deng, S., Gupta, N., Szefer, J., and Niederhagen, R. (2018). XMSS and embedded systems - XMSS hardware accelerators for RISC-V. IACR Cryptology ePrint Archive, 2018:1225.
Wang, X., Feng, D., Lai, X., and Yu, H. (2004). Collisions for hash functions md4, md5, HAVAL-128 and RIPEMD. IACR Cryptology ePrint Archive, 2004:199.
Yuval, G. (1979). How to swindle rabin. Cryptologia, 3(3):187–191.
Zheng, A. Y. C. L., Ferraz, L. T. D., and Jr., M. A. S. (2018). A clipping technique for shorter hash-based signatures. In Anais do XVIII Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais, pages 167–180.
Bellare, M. and Rogaway, P. (1997). Collision-resistant hashing: Towards making uowhfs practical. In Advances in Cryptology - CRYPTO '97, 17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 1997, Proceedings, pages 470–484.
Bernstein, D. J., Hopwood, D., Hülsing, A., Lange, T., Niederhagen, R., Papachristodoulou, L., Schneider, M., Schwabe, P., and Wilcox-O'Hearn, Z. (2015). SPHINCS: practical stateless hash-based signatures. In Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Soa, Bulgaria, April 26-30, 2015, Proceedings, Part I, pages 368–397.
Brassard, G., Høyer, P., and Tapp, A. (1998). Quantum cryptanalysis of hash and clawfree functions. In LATIN '98: Theoretical Informatics, Third Latin American Symposium, Campinas, Brazil, April, 20-24, 1998, Proceedings, pages 163–169.
Buchmann, J. A., Dahmen, E., and Hülsing, A. (2011). XMSS - A practical forward IACR Cryptology
secure signature scheme based on minimal security assumptions. ePrint Archive, 2011:484.
Butin, D. (2017). Hash-based signatures: State of play. IEEE Security & Privacy, 15(4):37–43.
Butin, D., Walde, J., and Buchmann, J. A. (2017). Post-quantum authentication in openssl with hash-based signatures. In Tenth International Conference on Mobile Computing and Ubiquitous Network, ICMU 2017, Toyama, Japan, October 3-5, 2017, pages 1–6.
Daniel, H. W. and Steele, Jr., G. L. (1986). Data parallel algorithms. Commun. ACM, 29(12):1170–1183.
de Oliveira, A. K. D. S. and López, J. (2015). An efcient software implementation of the hash-based signature scheme MSS and its variants. In Progress in Cryptology - LATINCRYPT 2015 - 4th International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015, Proceedings, pages 366–383.
de Oliveira, A. K. D. S., Lopez, J., and Cabral, R. (2017). High performance of hash- based signature schemes. International Journal of Advanced Computer Science and Applications, 8:421–432.
Dods, C., Smart, N. P., and Stam, M. (2005). Hash based digital signature schemes. In Cryptography and Coding, 10th IMA International Conference, Cirencester, UK, December 19-21, 2005, Proceedings, pages 96–115.
Gorbenko, Y. I., Melnik, T. V., and Gorbenko, I. D. (2018). Analysis of potential postquantum schemes of hash-based digital signatures. Telecommunications and Radio Engineering, 77:603–626.
Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 212–219.
Hevia, A. and Micciancio, D. (2002). The provable security of graph-based one-time signatures and extensions to algebraic signature schemes. In Advances in Cryptology - ASIACRYPT 2002, 8th International Conference on the Theory and Application of Cryptology and Information Security, Queenstown, New Zealand, December 1-5, 2002, Proceedings, pages 379–396.
Hülsing, A. (2017). WOTS+ - shorter signatures for hash-based signature schemes. IACR Cryptology ePrint Archive, 2017:965.
Hülsing, A., Butin, D., Gazdag, S., Rijneveld, J., and Mohaisen, A. (2018). XMSS: extended merkle signature scheme. RFC, 8391:1–74.
Hülsing, A., Gazdag, S.-L., Butin, D., and Buchmann, J. (2015a). Hash-based signatures: In Workshop on Cybersecurity in a Post-Quantum An outline for a new standard. World, NIST.
Hülsing, A., Rausch, L., and Buchmann, J. A. (2017). Optimal parameters for XMSSM T . IACR Cryptology ePrint Archive, 2017:966.
Hülsing, A., Rijneveld, J., and Schwabe, P. (2015b). Armed SPHINCS - computing a 41kb signature in 16kb of RAM. IACR Cryptology ePrint Archive, 2015:1042.
Lamport, L. (1979). Constructing digital signatures from a one-way function. Technical report, SRI International Computer Science Laboratory.
Merkle, R. (1979). Secrecy, authentication and public key systems / A certied digital signature. PhD thesis, Dept. of Electrical Engineering, Stanford University.
Naor, M. and Yung, M. (1989). Universal one-way hash functions and their cryptographic applications. In Proceedings of the Twenty-rst Annual ACM Symposium on Theory of Computing, STOC '89, pages 33–43, New York, NY, USA. ACM.
NIST (2016). Submission requirements and evaluation criteria for the post-quantum cryptography standardization process. Announcement.
Pereira, G. C. C. F. (2015). Assinaturas Digitais Pós Quanticas Multivariadas e Baseadas em Hash. PhD thesis, Departamento de Engenharia de Computação e Sistemas Digitais, Escola Politécnica da Universidade de São Paulo.
Pereira, G. C. C. F., Puodzius, C., and Barreto, P. S. L. M. (2016). Shorter hash-based signatures. Journal of Systems and Software, 116:95–100.
Rompel, J. (1990). One-way functions are necessary and sufcient for secure signatures. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 387–394.
Stallings, W. (2014). Criptograa e Segurança de Redes - Princípios e Práticas (6. ed. Pearson Education.
Stevens, M., Bursztein, E., Karpman, P., Albertini, A., and Markov, Y. (2017). The rst collision for full SHA-1. In Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part I, pages 570–596.
Wang, W., Jungk, B., Wí'alde, J., Deng, S., Gupta, N., Szefer, J., and Niederhagen, R. (2018). XMSS and embedded systems - XMSS hardware accelerators for RISC-V. IACR Cryptology ePrint Archive, 2018:1225.
Wang, X., Feng, D., Lai, X., and Yu, H. (2004). Collisions for hash functions md4, md5, HAVAL-128 and RIPEMD. IACR Cryptology ePrint Archive, 2004:199.
Yuval, G. (1979). How to swindle rabin. Cryptologia, 3(3):187–191.
Zheng, A. Y. C. L., Ferraz, L. T. D., and Jr., M. A. S. (2018). A clipping technique for shorter hash-based signatures. In Anais do XVIII Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais, pages 167–180.
Publicado
02/09/2019
Como Citar
ARAÚJO, Thales; PANETTA, Jairo.
Implementação Paralela do Algoritmo de Geração de Chaves do Esquema de Assinatura Digital XMSS (eXtended Merkle Signature Scheme). In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 19. , 2019, São Paulo.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 15-28.
DOI: https://doi.org/10.5753/sbseg.2019.13959.
