Paper 2018/867

Poly-Logarithmic Side Channel Rank Estimation via Exponential Sampling

Liron David and Avishai Wool

Abstract

Rank estimation is an important tool for a side-channel evaluations laboratories. It allows estimating the remaining security after an attack has been performed, quantified as the time complexity and the memory consumption required to brute force the key given the leakages as probability distributions over $d$ subkeys (usually key bytes). These estimations are particularly useful where the key is not reachable with exhaustive search. We propose ESrank, the first rank estimation algorithm that enjoys provable poly-logarithmic time- and space-complexity, which also achieves excellent practical performance. Our main idea is to use exponential sampling to drastically reduce the algorithm's complexity. Importantly, ESrank is simple to build from scratch, and requires no algorithmic tools beyond a sorting function. After rigorously bounding the accuracy, time and space complexities, we evaluated the performance of ESrank on a real SCA data corpus, and compared it to the currently-best histogram-based algorithm. We show that ESrank gives excellent rank estimation (with roughly a 1-bit margin between lower and upper bounds), with a performance that is on-par with the Histogram algorithm: a run-time of under 1 second on a standard laptop using 6.5 MB RAM.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision. RSA Conference Cryptographers' Track 2019 (CT-RSA 19)
Keywords
Side ChannelRank EstimationKey Enumeration
Contact author(s)
lirondavid @ gmail com
History
2018-12-09: revised
2018-09-22: received
See all versions
Short URL
https://ia.cr/2018/867
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/867,
      author = {Liron David and Avishai Wool},
      title = {Poly-Logarithmic Side Channel Rank Estimation via Exponential Sampling},
      howpublished = {Cryptology ePrint Archive, Paper 2018/867},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/867}},
      url = {https://eprint.iacr.org/2018/867}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.