research-article

Usuba: Optimizing & Trustworthy Bitslicing Compiler

Authors:

Darius Mercadier,

Pierre-Évariste Dagand,

Lionel Lacassagne,

Gilles MullerAuthors Info & Claims

WPMVP'18: Proceedings of the 2018 4th Workshop on Programming Models for SIMD/Vector Processing

Article No.: 4, Pages 1 - 8

https://doi.org/10.1145/3178433.3178437

Published: 24 February 2018 Publication History

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.

References

[1]

Specification for the advanced encryption standard (aes). Federal Information Processin Standards Publication 197, 2001.

[2]

R. Anderson, E. Biham, and L. Knudsen. Serpent: A proposal for the advanced encryption standard. In AES, 1998.

[3]

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.

Digital Library

[4]

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.

[5]

D. J. Bernstein. Cache-timing attacks on AES. Technical report, 2005. URL https://cr.yp.to/antiforgery/cachetiming-20050414.pdf.

[6]

D. Biernacki, J.-L. Colaço, G. Hamon, and M. Pouzet. Clock-directed modular code generation for synchronous data-flow languages. LCTES, 2008.

Digital Library

[7]

E. Biham. A fast new DES implementation in software. In FSE, 1997.

Digital Library

[8]

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.

Digital Library

[9]

L. Dagum and R. Menon. OpenMP: An Industry-Standard API for Shared-Memory Programming. IEEE Comput. Sci. Eng., 1998.

Digital Library

[10]

W. Dai. Crypto++ library 5.6. 0, 2009.

[11]

P. Estérie, J. Falcou, M. Gaunard, and J. Lapresté. Boost.simd: generic programming for portable simdization. In WPMVP, 2014.

Digital Library

[12]

G. Gaubatz and B. Sunar. Leveraging the multiprocessing capabilities of modern network processors for cryptographic acceleration. In NCA, 2005.

Digital Library

[13]

N. Halbwachs, P. Caspi, P. Raymond, and D. Pilaud. The synchronous dataflow programming language Lustre. Proceedings of the IEEE, 1991.

[14]

P. Karpinski and J. McDonald. A high-performance portable abstract interface for explicit SIMD vectorization. In PMAM@PPoPP, 2017.

Digital Library

[15]

E. Käsper and P. Schwabe. Faster and timing-attack resistant AESGCM. CHES, 2009.

Digital Library

[16]

M. Kretz. Extending C++ for explicit data-parallel programming via SIMD vector types. PhD thesis, Goethe University Frankfurt am Main, 2015.

[17]

M. Kwan. Bitslice DES, 1998. URL http://www.darkside.com.au/bitslice/.

[18]

R. Leißa, I. Haffner, and S. Hack. Sierra: a SIMD extension for C++. In WPMVP, 2014.

Digital Library

[19]

A. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. ISBN 0-8493-8523-7.

Digital Library

[20]

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.

[21]

A. Pnueli, M. Siegel, and E. Singerman. Translation validation. In TACAS, 1998.

Digital Library

[22]

T. Pornin. Implantation et optimisation des primitives cryptographiques. PhD thesis, Laboratoire d'Informatique de l'École Normale Supérieure, 2001.

Cited By

Buschkowski FSasdrich PGüneysu T(2023)EasiMask-Towards Efficient, Automated, and Secure Implementation of Masking in Hardware2023 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE56975.2023.10137330(1-6)Online publication date: Apr-2023
https://doi.org/10.23919/DATE56975.2023.10137330
Peng XWang YYang M(2023)CHOPPER: A Compiler Infrastructure for Programmable Bit-serial SIMD Processing Using Memory in DRAM2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA56546.2023.10071070(1275-1288)Online publication date: Feb-2023
https://doi.org/10.1109/HPCA56546.2023.10071070
Monfared SHajihassani OKiarostami MZanjani SRahmati DGorgin S(2020)BSRNG: A High Throughput Parallel BitSliced Approach for Random Number GeneratorsWorkshop Proceedings of the 49th International Conference on Parallel Processing10.1145/3409390.3409402(1-10)Online publication date: 17-Aug-2020
https://dl.acm.org/doi/10.1145/3409390.3409402
Show More Cited By

Usuba: Optimizing & Trustworthy Bitslicing Compiler
1. Software and its engineering
  1. Software notations and tools

Recommendations

Usuba: high-throughput and constant-time ciphers, by construction
PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation

Cryptographic 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 Symposium

Programmers 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 '12

Programmers 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WPMVP'18: Proceedings of the 2018 4th Workshop on Programming Models for SIMD/Vector Processing

February 2018

68 pages

ISBN:9781450356466

DOI:10.1145/3178433

Editors:
Jan Eitzinger
University of Erlangen-Nuremberg, Germany
,
James Brodman
Intel, USA

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 February 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Conference

PPoPP '18

Sponsor:

PPoPP '18: 23nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

February 24 - 28, 2018

Vienna, Austria

Acceptance Rates

WPMVP'18 Paper Acceptance Rate 8 of 12 submissions, 67%;

Overall Acceptance Rate 20 of 30 submissions, 67%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
130
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Buschkowski FSasdrich PGüneysu T(2023)EasiMask-Towards Efficient, Automated, and Secure Implementation of Masking in Hardware2023 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE56975.2023.10137330(1-6)Online publication date: Apr-2023
https://doi.org/10.23919/DATE56975.2023.10137330
Peng XWang YYang M(2023)CHOPPER: A Compiler Infrastructure for Programmable Bit-serial SIMD Processing Using Memory in DRAM2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA56546.2023.10071070(1275-1288)Online publication date: Feb-2023
https://doi.org/10.1109/HPCA56546.2023.10071070
Monfared SHajihassani OKiarostami MZanjani SRahmati DGorgin S(2020)BSRNG: A High Throughput Parallel BitSliced Approach for Random Number GeneratorsWorkshop Proceedings of the 49th International Conference on Parallel Processing10.1145/3409390.3409402(1-10)Online publication date: 17-Aug-2020
https://dl.acm.org/doi/10.1145/3409390.3409402
Belaïd SDagand PMercadier DRivain MWintersdorff R(2020)Tornado: Automatic Generation of Probing-Secure Masked Bitsliced ImplementationsAdvances in Cryptology – EUROCRYPT 202010.1007/978-3-030-45727-3_11(311-341)Online publication date: 1-May-2020
https://doi.org/10.1007/978-3-030-45727-3_11
Mercadier DDagand PMcKinley KFisher K(2019)Usuba: high-throughput and constant-time ciphers, by constructionProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314636(157-173)Online publication date: 8-Jun-2019
https://dl.acm.org/doi/10.1145/3314221.3314636

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents