Paper 2014/688
WhiteBox AES Implementation Revisited
Chung Hun Baek, Jung Hee Cheon, and Hyunsook Hong
Abstract
Whitebox cryptography is an obfuscation technique for protecting secret keys in software implementations even if an adversary has full access to the implementation of the encryption algorithm and full control over its execution platforms. This concept was presented by Chow et al. with whitebox implementations of DES and AES in 2002. The strategy used in the implementations has become a design principle for subsequent whitebox implementations. However, despite its practical importance, progress has not been substantial. In fact, it is repeated that as a proposal for a whitebox implementation is reported, an attack of lower complexity is soon announced. This is mainly because most cryptanalytic methods target specific implementations, and there is no general attack tool for whitebox cryptography. In this paper, we present an analytic toolbox on whitebox implementations in this design framework and show how to reveal the secret information obfuscated in the implementation using this. For a substitutionlinear transformation cipher on $n$ bits with Sboxes on $m$ bits, if $m_Q$bit nonlinear encodings are used to obfuscate output values in the implementation, our attack tool can remove the nonlinear encodings with complexity $O(\frac{n}{m_Q}2^{3m_Q})$. We should increase $m_Q$ to obtain higher security, but it yields exponential storage blowing up and so there are limits to increase the security using the nonlinear encoding. If the inverse of the encoded round function $F$ on $n$ bits is given, the affine encoding $A$ can be recovered in $O(\frac{n}{m}\cdot{m_A}^32^{3m})$ time using our specialized affine equivalence algorithm, where $m_A$ is the smallest integer $p$ such that $A$ (or its similar matrix obtained by permuting rows and columns) is a blockdiagonal matrix with $p\times p$ matrix blocks. According to our toolbox, a whitebox implementation in the Chow et al.'s framework has complexity at most $O\left(\min\left\{ \tfrac{2^{2m}}{m}\cdot n^{m+4}, n\log n \cdot 2^{n/2}\right\}\right)$ within reasonable storage, which is much less than $2^n$. To overcome this, we introduce an idea that obfuscates two AES128 ciphers at once with input/output encoding on 256 bits. To reduce storage, we use a sparse unsplit input encoding. As a result, our whitebox AES implementation has up to 110bit security against our toolbox, close to that of the original cipher. More generally, we may consider a whitebox implementation on the concatenation of $t$ ciphertexts to increase security.
Note: This paper will be to appear in the Journal of Communications and Networks.
Metadata
 Available format(s)
 Publication info
 Preprint. MAJOR revision.
 Keywords
 whitebox cryptographywhitebox implementationspecialized affine equivalence algorithmAESblock cipher
 Contact author(s)
 hongsuk07 @ snu ac kr
 History
 20160520: revised
 20140904: received
 See all versions
 Short URL
 https://ia.cr/2014/688
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/688, author = {Chung Hun Baek and Jung Hee Cheon and Hyunsook Hong}, title = {WhiteBox {AES} Implementation Revisited}, howpublished = {Cryptology ePrint Archive, Paper 2014/688}, year = {2014}, note = {\url{https://eprint.iacr.org/2014/688}}, url = {https://eprint.iacr.org/2014/688} }