Cryptology ePrint Archive: Report 2021/941

Spectral Approach to Process the (Multivariate) High-Order Template Attack against Any Masking Scheme

Maamar Ouladj and Sylvain Guilley and Philippe Guillot and Farid Mokrane

Abstract: Cryptographic software is particularly vulnerable to side-channel attacks when programmed in embedded devices. Indeed, the leakage is particularly intense compared to the noise level, making it mandatory for the developer to implement side-channel attack protections. Random masking is a customary option, but in this case, the countermeasure must be high-order, meaning that each sensitive variable is splitted into multiple (at least two) shares. Attacks therefore become computationally challenging.

In this paper, we show that high-order template attacks can be expressed under the form of a convolution. This formulation allows for a considerable speed-up in their computation thanks to fast Fourier transforms. To further speed-up the attack, we also provide an interesting multi-threading implementation of this approach. This strategy naturally applies to template attacks where the leakage of each share is multivariate. We show that this strategy can be adapted to several masking schemes, inherently to the way the splitting is realized. This technique allows us to validate multiple very high-order attacks (order of some tens). In particular, it revealed a non-trivial flaw (hard to detect otherwise) in a multivariate extension of the DSM masking (and subsequently to fix it, and validate its rationale).

Category / Keywords: implementation / Template attacks, Masking schemes, High-order attacks, Convolution, Fourier transform, Walsh-Hadamard transform

Original Publication (with minor differences): Journal of Cryptographic Engineering

Date: received 11 Jul 2021

Contact author: sylvain guilley at secure-ic com

Available format(s): PDF | BibTeX Citation

Note: Same version as accepted at JCEN, with a few minor typos fixed.

Version: 20210713:162619 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]