Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

04.08.2021 | Regular Paper

Rank estimation with bounded error via exponential sampling

Zeitschrift:
Journal of Cryptographic Engineering
Autoren:
Liron David, Avishai Wool
Wichtige Hinweise
A preliminary version of this paper appeared in the proceeding of the CT-RSA 2019 conference.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

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.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Premium Partner