In this paper, we present a general analytic toolbox for white-box implementations which extracts the secret information obfuscated in the implementation. For a general SLT cipher on $n$ bits with S-boxes on $m$ bits, one can remove the nonlinear encodings with complexity $O(\frac{n}{m_Q}2^{3m_Q})$ using our attack tool, if $m_Q$-bit nonlinear encodings are used to obfuscate input/output values in the implementation. Also, one can recover the affine encoding $A$ in time $O(\frac{n}{m}\cdot{m_A}^32^{3m})$ using our extended affine equivalence algorithm~(EAEA), if the inverse of the encoded round function $F$ on $n$ bits is given, where $m_A$ is the smallest integer $p$ such that $A$ or its similar matrix obtained by permuting rows and columns is a block diagonal matrix with a $p\times p$ matrix as a block.
To avoid our attack, we need to consider a special encoding of large $m_A$, up to $n$. This results in storage blowing up in general. We suggest one approach with special affine encodings of $m_A=n$ that saves storage. In that case, the EAEA has the complexity~$O\left(\min\left\{\tfrac{n}{m}\cdot {n}^{m+3}\cdot2^{2m}, {n}\cdot\log{n}\cdot {\sqrt{2}}^{n}\right\}\right)$, {which can be large up to $2^{74}$ and $2^{109}$ for $n=128$ and $256$, respectively, when $m=8$. This gives an approach to design secure white-box implementation with practical storage. We expect that our analytic toolbox initiates the research on white-box implementation design.}
Category / Keywords: implementation / white-box cryptography, white-box implementation, extended affine equivalence algorithm, AES, block cipher Date: received 2 Sep 2014 Contact author: love0116 at snu ac kr Available format(s): PDF | BibTeX Citation Version: 20140904:060921 (All versions of this report) Short URL: ia.cr/2014/688 Discussion forum: Show discussion | Start new discussion