Paper 2021/290

Dummy Shuffling against Algebraic Attacks in White-box Implementations

Alex Biryukov and Aleksei Udovenko

Abstract

At CHES 2016, Bos, Hubain, Michiels and Teuwen showed that most of existing white-box implementations are easily broken by standard side-channel attacks. A natural idea to apply the well-developed side-channel countermeasure - linear masking schemes - leaves implementations vulnerable to linear algebraic attacks which exploit absence of noise in the white-box setting and are applicable for any order of linear masking. At ASIACRYPT 2018, Biryukov and Udovenko proposed a security model (BU-model for short) for protection against linear algebraic attacks and a new quadratic masking scheme which is provably secure in this model. However, countermeasures against higher-degree attacks were left as an open problem. In this work, we study the effectiveness of another well-known side-channel countermeasure - shuffling - against linear and higher-degree algebraic attacks in the white-box setting. First, we extend the classic shuffling to include dummy computation slots and show that this is a crucial component for protecting against the algebraic attacks. We quantify and prove the security of dummy shuffling against the linear algebraic attack in the BU-model. We introduce a refreshing technique for dummy shuffling and show that it allows to achieve close to optimal protection in the model for arbitrary degrees of the attack, thus solving the open problem of protection against the algebraic attack in the BU-model. Furthermore, we describe an interesting proof-of-concept construction that makes the slot function public (while keeping the shuffling indexes private). A variant of this construction was used, among other countermeasures, in the challenge \#100, one of the three white-box AES challenges from the CHES 2019 CTF / WhibOx 2019 contest that proved to be challenging for the attackers.

Note: Typos and minor edits

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
A minor revision of an IACR publication in Eurocrypt 2021
DOI
10.1007/978-3-030-77886-6_8
Keywords
White-boxObfuscationProvable SecurityShufflingAlgebraic Attack
Contact author(s)
aleksei @ affine group
History
2021-10-08: last of 2 revisions
2021-03-07: received
See all versions
Short URL
https://ia.cr/2021/290
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/290,
      author = {Alex Biryukov and Aleksei Udovenko},
      title = {Dummy Shuffling against Algebraic Attacks in White-box Implementations},
      howpublished = {Cryptology ePrint Archive, Paper 2021/290},
      year = {2021},
      doi = {10.1007/978-3-030-77886-6_8},
      note = {\url{https://eprint.iacr.org/2021/290}},
      url = {https://eprint.iacr.org/2021/290}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.