Implementação em Software da Cifra LowMC

• Roberto Cabral UFC
• Julio López UNICAMP

DOI: https://doi.org/10.5753/sbseg.2022.224092

Resumo

Nos últimos anos surgiram várias propostas de primitivas simétricas construídas visando a minimização das operações não lineares, dentre elas, a família de cifras de bloco LowMC. Embora o LowMC seja uma primitiva muito atraente para aplicações que se beneficiam da sua baixa complexidade multiplicativa, o fato dele operar diretamente sobre bits torna-o muito custoso em software. Visto que algumas aplicações executam múltiplas mensagens por vez; tirando proveito do conjuntos de instruções vetoriais AVX, adaptou-se o algoritmo de modo a processar múltiplas mensagens por vez, facilitando sua implementação em software e melhorando o desempenho por encriptação. Conseguindo uma aceleração de 2,3x quando encriptadas oito mensagens por vez e de 3,3x quando encriptadas 16 mensagens para a instância do LowMC que processa todos os bits do estado por caixas de substituição e segurança de 129 bits. Adicionalmente, pensando em arquiteturas convencionais que não possuem instruções vetoriais, foi desenvolvida uma implementação nativa do LowMC cerca de 25% mais eficiente que o estado da arte.

Palavras-chave: Criptografia, cifra de Bloco, Implementação em Software

Referências

Alagic, G., Alperin-Sheriff, J., Apon, D., Cooper, D., Dang, Q., Kelsey, J., Liu, Y.-K., Miller, C., Moody, D., Peralta, R., et al. (2020). Status report on the second round of the nist post-quantum cryptography standardization process. US Department of Commerce, NIST.

Albrecht, M., Grassi, L., Rechberger, C., Roy, A., and Tiessen, T. (2016). Mimc: Efficient encryption and cryptographic hashing with minimal multiplicative complexity. In International Conference on the Theory and Application of Cryptology and Information Security, pages 191–219. Springer.

Albrecht, M. R., Rechberger, C., Schneider, T., Tiessen, T., and Zohner, M. (2015). Ciphers for mpc and fhe. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 430–454. Springer.

Aly, A., Ashur, T., Ben-Sasson, E., Dhooghe, S., and Szepieniec, A. (2020). Design of symmetric-key primitives for advanced cryptographic protocols. IACR Transactions on Symmetric Cryptology, pages 1–45.

Biham, E. (1997). A fast new des implementation in software. In International Workshop on Fast Software Encryption, pages 260–272. Springer.

Cabral, R. and López, J. (2018). Implementation of the sha-3 family using avx512 instructions. In Anais do XVIII Simpósio Brasileiro de Segurança da Informação e de Sistemas Computacionais, pages 25–32. SBC.

Chase, M., Derler, D., Goldfeder, S., Orlandi, C., Ramacher, S., Rechberger, C., Slamanig, D., and Zaverucha, G. (2017). Post-quantum zero-knowledge and signatures from symmetric-key primitives. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS ’17, page 1825–1842, New York, NY, USA. Association for Computing Machinery.

Corporation, I. (2011). Intel® Advanced Vector Extensions Programming Reference. Disponível em [link].

Dobraunig, C., Kales, D., Rechberger, C., Schofnegger, M., and Zaverucha, G. (2021). Shorter signatures based on tailor-made minimalist symmetric-key crypto. Cryptology ePrint Archive.

Faz-Hernández, A., Cabral, R., Aranha, D. F., and López, J. (2015). Implementação Eficiente e Segura de Algoritmos Criptográficos. In Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais - Minicursos, volume XV, pages 93–140. Sociedade Brasileira de Computação.

Flynn, M. (1972). Some Computer Organizations and Their Effectiveness. Computers, IEEE Transactions on, C-21(9):948–960.

Greg, Z. et al. (2020). The picnic signature algorithm specification version 3.0.

Guide, P. (2011). Intel® 64 and ia-32 architectures software developer’s manual. Volume 3B: System programming Guide, Part, 2(11).

Kales, D., Perrin, L., Promitzer, A., Ramacher, S., and Rechberger, C. (2017). Improvements to the linear operations of lowmc: A faster picnic. Cryptology ePrint Archive.

Kales, D. and Zaverucha, G. (2020). Improving the performance of the picnic signature scheme. IACR Transactions on Cryptographic Hardware and Embedded Systems, pages 154–188.

Käsper, E. and Schwabe, P. (2009). Faster and timing-attack resistant aes-gcm. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 1–17. Springer.

Matsui, M. and Nakajima, J. (2007). On the power of bitslice implementation on intel core2 processor. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 121–134. Springer.

Orisaka, G., Aranha, D. F., and López, J. (2018). Finite field arithmetic using avx-512 for isogeny-based cryptography. In Anais do XVIII Simpósio Brasileiro de Segurança da Informação e de Sistemas Computacionais, pages 49–56. SBC.

Ramacher, S., Zaverucha, G., and Kales, D. (2022). Optimized implementation of the picnic signature scheme. Repositório: https://github.com/IAIK/Picnic. (Jul,2022).

Rebeiro, C., Selvakumar, D., and Devi, A. (2006). Bitslice implementation of aes. In International Conference on Cryptology and Network Security, pages 203–212. Springer.

Shannon, C. E. (1945). A mathematical theory of cryptography. Mathematical Theory of Cryptography.