IACR News item: 04 September 2014
Chung Hun Baek, Jung Hee Cheon, Hyunsook Hong
ePrint ReportThis concept was presented in 2002 by Chow et al., and since then there have been many proposals to give solutions for the white-box cryptography.
However, the progress does not seem to be substantial in spite of its practical importance.
In fact, it is repeated that as a proposal on white-box implementation is announced, an attack of this implementation with lower complexity followed soon.
It is mainly because most cryptanalytic methods were just targeted to some specific implementations and there is no general attack tool for the white-box cryptography.
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.}
Additional news items may be found on the IACR news page.