Automated Generation of EfficientBitslice Implementations forArbitrary Sboxes

Abstract: Whitebox cryptography aims at protecting standard cryptographic algorithmsthat execute in attacker-controlled environments. In these, the attacker is ableto read a secret key directly from memory. Common implementations mask alldata at runtime and operate on masked data by using many small precomputedtables. Practical whiteboxes involve trade-offs between security and executionspeed, to limit their footprints and enable applications such as real-time videostreaming.To improve this compromise, we study the use of bitslicing (or bitparallelism)to implement whiteboxes. Bitslicing is commonly used to writefast constant-time implementations of cryptographic algorithms and relies onthe synthesis of boolean circuits implementing the corresponding algorithms.The synthesis of optimal circuits for lookup tables is resource intensive andgenerally only performed once. In a whitebox context however, many randomlookup tables are generated at compile-time. We therefore require the booleancircuit generation to be time efficient.In this master thesis, we review the existing circuit-synthesis algorithms,and analyse their usability in the whitebox context. In particular, we studythe technique of Binary Decision Diagrams to generate efficient circuits ina cheap and adaptable manner. We implemented a flexible version of thisalgorithm as a C++ library. Eventually, we go through different techniques toevaluate the generated circuits and analyse the performances of our algorithm,and recommand the best parameters for the whitebox context.