Darius Mercadier
Gilles Muller
ABSTRACT
Bitslicing is a programming technique commonly used in cryptography that consists in implementing a combinational circuit in software. It results in a massively parallel program immune to cache-timing attacks by design.
However, writing a program in bitsliced form requires extreme minutia. This paper introduces Usuba, a synchronous dataflow language producing bitsliced C code. Usuba is both a domain-specific language -- providing syntactic support for the implementation of cryptographic algorithms -- as well as a domain-specific compiler -- taking advantage of well-defined semantics invariants to perform various optimizations before handing the generated code to an (optimizing) C compiler.
On the Data Encryption Standard (DES) algorithm, we show that Usuba outperforms a reference, hand-tuned implementation by 15% (using Intel's 64 bits general-purpose registers and depending on the underlying C compiler) whilst our implementation also transparently supports modern SIMD extensions (SSE, AVX, AVX-512), other architectures (ARM Neon, IBM Altivec) as well as multicore processors through an OpenMP backend.
- Specification for the advanced encryption standard (aes). Federal Information Processin Standards Publication 197, 2001.Google Scholar
- R. Anderson, E. Biham, and L. Knudsen. Serpent: A proposal for the advanced encryption standard. In AES, 1998.Google Scholar
- K. Aoki, T. Ichikawa, M. Kanda, M. Matsui, S. Moriai, J. Nakajima, and T. Tokita. Camellia: A 128-bit block cipher suitable for multiple platforms - design and analysis. In SAC, 2000. Google ScholarDigital Library
- Z. Bao, P. Luo, and D. Lin. Bitsliced implementations of the PRINCE, LED and RECTANGLE block ciphers on AVR 8-bit microcontrollers. In ICICS, 2015.Google Scholar
- D. J. Bernstein. Cache-timing attacks on AES. Technical report, 2005. URL https://cr.yp.to/antiforgery/cachetiming-20050414.pdf.Google Scholar
- D. Biernacki, J.-L. Colaço, G. Hamon, and M. Pouzet. Clock-directed modular code generation for synchronous data-flow languages. LCTES, 2008. Google ScholarDigital Library
- E. Biham. A fast new DES implementation in software. In FSE, 1997. Google ScholarDigital Library
- A. Cassagne, B. L. Gal, C. Leroux, O. Aumage, and D. Barthou. An efficient, portable and generic library for successive cancellation decoding of polar codes. In LCPC, 2015. Google ScholarDigital Library
- L. Dagum and R. Menon. OpenMP: An Industry-Standard API for Shared-Memory Programming. IEEE Comput. Sci. Eng., 1998. Google ScholarDigital Library
- W. Dai. Crypto++ library 5.6. 0, 2009.Google Scholar
- P. Estérie, J. Falcou, M. Gaunard, and J. Lapresté. Boost.simd: generic programming for portable simdization. In WPMVP, 2014.Google ScholarDigital Library
- G. Gaubatz and B. Sunar. Leveraging the multiprocessing capabilities of modern network processors for cryptographic acceleration. In NCA, 2005. Google ScholarDigital Library
- N. Halbwachs, P. Caspi, P. Raymond, and D. Pilaud. The synchronous dataflow programming language Lustre. Proceedings of the IEEE, 1991.Google ScholarCross Ref
- P. Karpinski and J. McDonald. A high-performance portable abstract interface for explicit SIMD vectorization. In PMAM@PPoPP, 2017. Google ScholarDigital Library
- E. Käsper and P. Schwabe. Faster and timing-attack resistant AESGCM. CHES, 2009.Google ScholarDigital Library
- M. Kretz. Extending C++ for explicit data-parallel programming via SIMD vector types. PhD thesis, Goethe University Frankfurt am Main, 2015.Google Scholar
- M. Kwan. Bitslice DES, 1998. URL http://www.darkside.com.au/bitslice/.Google Scholar
- R. Leißa, I. Haffner, and S. Hack. Sierra: a SIMD extension for C++. In WPMVP, 2014.Google ScholarDigital Library
- A. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. ISBN 0-8493-8523-7. Google ScholarDigital Library
- A. Peslyak and R. Rusakov. John the Ripper 1.7.8: DES speedup, 2011. URL http://www.openwall.com/lists/john-users/2011/06/22/1.Google Scholar
- A. Pnueli, M. Siegel, and E. Singerman. Translation validation. In TACAS, 1998. Google ScholarDigital Library
- T. Pornin. Implantation et optimisation des primitives cryptographiques. PhD thesis, Laboratoire d'Informatique de l'École Normale Supérieure, 2001.Google Scholar
- Usuba: Optimizing & Trustworthy Bitslicing Compiler
Recommendations
Usuba: high-throughput and constant-time ciphers, by construction
PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and ImplementationCryptographic primitives are subject to diverging imperatives. Functional correctness and auditability pushes for the use of a high-level programming language. Performance and the threat of timing attacks push for using no more abstract than an ...
Layout-sensitive language extensibility with SugarHaskell
Haskell '12: Proceedings of the 2012 Haskell SymposiumProgrammers need convenient syntax to write elegant and concise programs. Consequently, the Haskell standard provides syntactic sugar for some scenarios (e.g., do notation for monadic code), authors of Haskell compilers provide syntactic sugar for more ...
Layout-sensitive language extensibility with SugarHaskell
Haskell '12Programmers need convenient syntax to write elegant and concise programs. Consequently, the Haskell standard provides syntactic sugar for some scenarios (e.g., do notation for monadic code), authors of Haskell compilers provide syntactic sugar for more ...
Comments