Article: Bitslice Masking and Improved Shuffling: How and When to Mix Them in Software?

Article: Bitslice Masking and Improved Shuffling: How and When to Mix Them in Software?


The Laboratoire Hubert Curien’s SESAM team has released an article in TCHES, a journal/conference hybrid publication model highlighting new results in the design and analysis of cryptographic hardware and software implementations. The journal is published by the Ruhr-University of Bochum.


Several countermeasures do exist to protect cryptographic implementations against side-channel attacks. Whilst the safety contribution of the various protections taken individually has been studied for several years, the impact of their combination is more complex.

In this article we put forward a framework to combine different protections, and we do a theoretical analysis of their security. In particular, we can estimate a better compromise depending on the additional penalty cost that we are ready to pay. We validate this theoretical analysis by tests on micro-controllers.


We revisit the popular adage that side-channel countermeasures must be combined to be efficient, and study its application to bitslice masking and shuffling. Our contributions are threefold. First, we improve this combination: by shuffling the shares of a masked implementation rather than its tuples, we can amplify the impact of the shuffling exponentially in the number of shares, while this impact was independent of the masking security order in previous works. Second, we evaluate the masking and shuffling combination's performance vs. security tradeoff under sufficient noise conditions: we show that the best approach is to mask first (i.e., fill the registers with as many shares as possible) and shuffle the independent operations that remain. Third, we discuss the challenges for implementing masking and shuffling under low noise conditions: we recall that such algorithmic countermeasures cannot be implemented securely without a minimum level of physical noise. We conclude that with moderate but sufficient noise, the bitslice masking + shuffling combination is relevant, and its interest increases when randomness is expensive and many independent operations are available for shuffling. When these conditions are not met, masking only is the best option. As a side result, we improve the best known attack against shuffling from Asiacrypt 2012, which we use in our concrete evaluations. 


The figure above illustrates different shuffling and masking combination options:

On the left, the shuffling is applied to the shares;

In the centre, the shuffling is applied between the shares;

On the right, the shuffling is applied to each element.



Read the full article here.

Published on July 13, 2022