International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: A Fast and Accurate Guessing Entropy Estimation Algorithm for Full-key Recovery

Authors:
Ziyue Zhang , Department of Math., Northeastern University, Boston, MA, USA
A. Adam Ding , Department of Math., Northeastern University, Boston, MA, USA
Yunsi Fei , Department of Math., Northeastern University, Boston, MA, USA
Download:
DOI: 10.13154/tches.v2020.i2.26-48
URL: https://tches.iacr.org/index.php/TCHES/article/view/8543
Search ePrint
Search Google
Abstract: Guessing entropy (GE) is a widely adopted metric that measures the average computational cost needed for a successful side-channel analysis (SCA). However, with current estimation methods where the evaluator has to average the correct key rank over many independent side-channel leakage measurement sets, full-key GE estimation is impractical due to its prohibitive computing requirement. A recent estimation method based on posterior probabilities, although scalable, is not accurate.We propose a new guessing entropy estimation algorithm (GEEA) based on theoretical distributions of the ranking score vectors. By discovering the relationship of GE with pairwise success rates and utilizing it, GEEA uses a sum of many univariate Gaussian probabilities instead of multi-variate Gaussian probabilities, significantly improving the computation efficiency.We show that GEEA is more accurate and efficient than all current GE estimations. To the best of our knowledge, it is the only practical full-key GE evaluation on given experimental data sets which the evaluator has access to. Moreover, it can accurately predict the GE for larger sizes than the experimental data sets, providing comprehensive security evaluation.
Video from TCHES 2020
BibTeX
@article{tches-2020-30153,
  title={A Fast and Accurate Guessing Entropy Estimation Algorithm for Full-key Recovery},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universit├Ąt Bochum},
  volume={2020, Issue 2},
  pages={26-48},
  url={https://tches.iacr.org/index.php/TCHES/article/view/8543},
  doi={10.13154/tches.v2020.i2.26-48},
  author={Ziyue Zhang and A. Adam Ding and Yunsi Fei},
  year=2020
}