Improving the performance of Luffa Hash Algorithm
Resumo
Luffa is a new hash algorithm that has been accepted for round two of the NIST hash function competition SHA-3. Computational efficiency is the second most important evaluation criteria used to compare candidate algorithms. In this paper, we describe a fast software implementation of the Luffa hash algorithm for the Intel Core 2 Duo platform. We explore the use of the perfect shuffle operation to improve the performance of 64-bit implementation and 128-bit implementation with the Intel Supplemental SSSE3 instructions. In addition, we introduce a new way of implementing Luffa based on a Parallel Table Lookup instruction. The timings of our 64-bit implementation (C code) resulted in a 16 to 32% speed improvement over the previous fastest implementation.
Referências
Bernstein, D. J. and Lange, T. eBACS: ECRYPT benchmarking of cryptographic systems. http://bench.cr.yp.to. Accessed 15 July 2010.
Bertoni, G., Daemen, J., Peeters, M., and Assche, G. V. (2010). Keccak sponge function family main document version 2.1. http://keccak.noekeon.org/Keccak-main-2.1.pdf.
Bertoni, G., Daemen, J., Peeters, M., Assche, G. V., Bertoni, G., Daemen, J., Peeters, M., and Assche, G. V. (2007). Sponge functions. Ecrypt Hash Workshop 2007. Also available as public comment to NIST from [link].
Biham, E., Chen, R., Joux, A., Carribault, P., Lemuet, C., and Jalby,W. (2005). Collisions of SHA-0 and reduced SHA-1. In EUROCRYPT ’05, volume 3494 of LNCS, pages 36–57. Springer-Verlag.
Canniere, C. D., Sato, H., and Watanabe, D. (2009a). Hash function Luffa: Specification 2.0.1. Submission to NIST (Round 2). [link].
Canniere, C. D., Sato, H., and Watanabe, D. (2009b). Hash function Luffa: Supporting document. Submission to NIST (Round 2). [link].
Intel (2002). Intel architecture software developer’s manual volume 2: Instruction set reference. http://www.intel.com.
Intel (2010). Intel Advanced Vector Extensions programming reference. http://www.intel.com.
Jia, K. (2009). Practical pseudo-cryptanalysis of Luffa. Cryptology ePrint Archive, Report 2009/224. http://eprint.iacr.org/.
Khovratovich, D., Naya-Plasencia, M., Rechberger, C., Röck, A., and Schläffer, M. (2010). Cryptanalysis of Luffa v2 components. In Selected Areas in Cryptography - SAC 2010, Lecture Notes in Computer Science. Springer.
Knezevic, M. and Verbauwhede, I. (2009). Hardware evaluation of the Luffa hash family. In WESS ’09: Proceedings of the 4th Workshop on Embedded Systems Security, pages 1–6, New York, NY, USA. ACM.
Kobayashi, K., Ikegami, J., Matsuo, S., Sakiyama, K., and Ohta, K. (2010). Evaluation of hardware performance for the SHA-3 candidates using SASEBO-GII. Cryptology ePrint Archive, Report 2010/010. http://eprint.iacr.org/.
Namin, A. H. and Hasan, M. A. (2009). Hardware implementation of the compression function for selected SHA-3 candidates. Technical Report from CACR 2009-28. http://www.cacr.math.uwaterloo.ca/techreports/2009/cacr2009-28.pdf.
NIST (2002). Secure Hash Standard, Federal Information Processing Standards publication, FIPS pub 180-2. Technical report, Department of Commerce. http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Nov07.pdf.
Oikawa, K., Wang, J., Kodama, E., and Takata, T. (2010). Implementation and evaluation of cryptographic algorithm on OpenCL. SCIS 2010, 3C4-2 (in Japanese).
Pornin, T. Software library Sphlib 2.1. http://www.saphir2.com/sphlib/. Accessed 26 July 2010.
Pornin, T. (2010). Comparative performance review of most of the SHA-3 second-round candidates. http://tahoe-lafs.org/~zooko/report-speed-sha3.pdf.
Tillich, S., Feldhofer, M., Kirschbaum, M., Plos, T., Schmidt, J.-M., and Szekely, A. (2009). High-speed hardware implementations of BLAKE, Blue Midnight Wish, CubeHash, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Luffa, Shabal, SHAvite-3, SIMD, and Skein. Cryptology ePrint Archive, Report 2009/510. http://eprint.iacr.org/.
Wang, X., Yin, Y. L., and Yu, H. (2005). Finding collisions in the full SHA-1. In CRYPTO ’05, volume 3621 of LNCS, pages 17–36. Springer-Verlag.
Warren, H. S. (2002). Hacker’s Delight. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.
Bertoni, G., Daemen, J., Peeters, M., and Assche, G. V. (2010). Keccak sponge function family main document version 2.1. http://keccak.noekeon.org/Keccak-main-2.1.pdf.
Bertoni, G., Daemen, J., Peeters, M., Assche, G. V., Bertoni, G., Daemen, J., Peeters, M., and Assche, G. V. (2007). Sponge functions. Ecrypt Hash Workshop 2007. Also available as public comment to NIST from [link].
Biham, E., Chen, R., Joux, A., Carribault, P., Lemuet, C., and Jalby,W. (2005). Collisions of SHA-0 and reduced SHA-1. In EUROCRYPT ’05, volume 3494 of LNCS, pages 36–57. Springer-Verlag.
Canniere, C. D., Sato, H., and Watanabe, D. (2009a). Hash function Luffa: Specification 2.0.1. Submission to NIST (Round 2). [link].
Canniere, C. D., Sato, H., and Watanabe, D. (2009b). Hash function Luffa: Supporting document. Submission to NIST (Round 2). [link].
Intel (2002). Intel architecture software developer’s manual volume 2: Instruction set reference. http://www.intel.com.
Intel (2010). Intel Advanced Vector Extensions programming reference. http://www.intel.com.
Jia, K. (2009). Practical pseudo-cryptanalysis of Luffa. Cryptology ePrint Archive, Report 2009/224. http://eprint.iacr.org/.
Khovratovich, D., Naya-Plasencia, M., Rechberger, C., Röck, A., and Schläffer, M. (2010). Cryptanalysis of Luffa v2 components. In Selected Areas in Cryptography - SAC 2010, Lecture Notes in Computer Science. Springer.
Knezevic, M. and Verbauwhede, I. (2009). Hardware evaluation of the Luffa hash family. In WESS ’09: Proceedings of the 4th Workshop on Embedded Systems Security, pages 1–6, New York, NY, USA. ACM.
Kobayashi, K., Ikegami, J., Matsuo, S., Sakiyama, K., and Ohta, K. (2010). Evaluation of hardware performance for the SHA-3 candidates using SASEBO-GII. Cryptology ePrint Archive, Report 2010/010. http://eprint.iacr.org/.
Namin, A. H. and Hasan, M. A. (2009). Hardware implementation of the compression function for selected SHA-3 candidates. Technical Report from CACR 2009-28. http://www.cacr.math.uwaterloo.ca/techreports/2009/cacr2009-28.pdf.
NIST (2002). Secure Hash Standard, Federal Information Processing Standards publication, FIPS pub 180-2. Technical report, Department of Commerce. http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Nov07.pdf.
Oikawa, K., Wang, J., Kodama, E., and Takata, T. (2010). Implementation and evaluation of cryptographic algorithm on OpenCL. SCIS 2010, 3C4-2 (in Japanese).
Pornin, T. Software library Sphlib 2.1. http://www.saphir2.com/sphlib/. Accessed 26 July 2010.
Pornin, T. (2010). Comparative performance review of most of the SHA-3 second-round candidates. http://tahoe-lafs.org/~zooko/report-speed-sha3.pdf.
Tillich, S., Feldhofer, M., Kirschbaum, M., Plos, T., Schmidt, J.-M., and Szekely, A. (2009). High-speed hardware implementations of BLAKE, Blue Midnight Wish, CubeHash, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Luffa, Shabal, SHAvite-3, SIMD, and Skein. Cryptology ePrint Archive, Report 2009/510. http://eprint.iacr.org/.
Wang, X., Yin, Y. L., and Yu, H. (2005). Finding collisions in the full SHA-1. In CRYPTO ’05, volume 3621 of LNCS, pages 17–36. Springer-Verlag.
Warren, H. S. (2002). Hacker’s Delight. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.
Publicado
11/10/2010
Como Citar
OLIVEIRA, Thomaz; LÓPEZ, Julio.
Improving the performance of Luffa Hash Algorithm. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 10. , 2010, Fortaleza.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2010
.
p. 405-418.
DOI: https://doi.org/10.5753/sbseg.2010.20603.
