Welcome to the resource topic for 2021/313
Title:
Rank Estimation with Bounded Error via Exponential Sampling
Authors: Liron David, Avishai Wool
Abstract:Efficient rank estimation algorithms are of prime interest in security evaluation against side-channel attacks (SCA) and recently also for password strength estimators. In a side channel setting 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). In password strength estimators the rank estimation allows estimating how many attempts a password cracker would need until it finds a given password. We propose ESrank, the first rank estimation algorithm with a bounded error ratio: its error ratio is bounded by \gamma^{2d-2}, for any probability distribution, where d is the number of subkey dimensions and \gamma>1 can be chosen according to the desired accuracy. ESrank is also the first rank estimation algorithm that enjoys provable poly-logarithmic time- and space-complexity. Our main idea is to use exponential sampling to drastically reduce the algorithm’s complexity. We evaluated the performance of ESrank on real SCA and password strength corpora. We show ESrank gives excellent rank estimation with roughly a 1-bit margin between lower and upper bounds in less than 1 second on the SCA corpus and 4 seconds preprocessing time and 7$\mu$sec lookup time on the password strength corpus.
ePrint: https://eprint.iacr.org/2021/313
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .