Paper 2019/076

Analysis and Improvement of Differential Computation Attacks against Internally-Encoded White-Box Implementations

Matthieu Rivain and Junwei Wang

Abstract

White-box cryptography is the last security barrier for a cryptographic software implementation deployed in an untrusted environment. The principle of internal encodings is a commonly used white-box technique to protect block cipher implementations. It consists in representing an implementation as a network of look-up tables which are then encoded using randomly generated bijections (the internal encodings). When this approach is implemented based on nibble (i.e. 4-bit wide) encodings, the protected implementation has been shown to be vulnerable to differential computation analysis (DCA). The latter is essentially an adaptation of differential power analysis techniques to computation traces consisting of runtime information, e.g., memory accesses, of the target software. In order to thwart DCA, it has then been suggested to use wider encodings, and in particular byte encodings, at least to protect the outer rounds of the block cipher which are the prime targets of DCA. In this work, we provide an in-depth analysis of when and why DCA works. We pinpoint the properties of the target variables and the encodings that make the attack (in)feasible. In particular, we show that DCA can break encodings wider than 4-bit, such as byte encodings. Additionally, we propose new DCA-like attacks inspired from side-channel analysis techniques. Specifically, we describe a collision attack particularly effective against the internal encoding countermeasure. We also investigate mutual information analysis (MIA) which naturally applies in this context. Compared to the original DCA, these attacks are also passive and they require very limited knowledge of the attacked implementation, but they achieve significant improvements in terms of trace complexity. All the analyses of our work are experimentally backed up with various attack simulation results. We also verified the practicability of our analyses and attack techniques against a publicly available white-box AES implementation protected with byte encodings --which DCA has failed to break before-- and against a ``masked'' white-box AES implementation --which intends to resist DCA.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published by the IACR in TCHES 2019
Keywords
white-box cryptographyinternal encodingdifferential computation analysiscollision attackmutual information analysis
Contact author(s)
matthieu rivain @ cryptoexperts com
junwei wang @ cryptoexperts com
History
2019-01-28: received
Short URL
https://ia.cr/2019/076
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/076,
      author = {Matthieu Rivain and Junwei Wang},
      title = {Analysis and Improvement of Differential Computation Attacks against Internally-Encoded White-Box Implementations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/076},
      year = {2019},
      url = {https://eprint.iacr.org/2019/076}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.