Key Rank Estimation Methods: Comparisons and Practical Considerations

Rebecca Hay; Elisabeth Oswald

doi:10.62056/aytxl86bm

Key Rank Estimation Methods: Comparisons and Practical Considerations

Authors

Rebecca Hay, Elisabeth Oswald

Rebecca Hay

University of Bristol, Bristol, United Kingdom
rebecca dot hay at bristol dot ac dot uk

Elisabeth Oswald

University of Klagenfurt, Klagenfurt, Austria
University of Birmingham, Birmingham, United Kingdom
m dot e dot oswald at bham dot ac dot uk

Keywords: Key Rank Estimation Large Keys Key Security Assessments

Abstract

New proposals for scalable key rank estimation methods have appeared recently, in particular the sampling based approach MCRank. The idea is that one can consistently estimate the key rank by sampling only a small portion of the key space as a “proxy”, leading to both an accurate and scalable approach, at least in comparison with another approach based on histograms. We show that the (earlier) GEEA algorithm is in fact a sampling based algorithm, and provide an in-depth comparison between GEEA (when adapted to produce rank estimates rather than guessing entropy estimates), GM bounds, MCRank and the currently most performant counting based rank estimation as implemented in the Labynkyr library. We find that although MCRank does live up to the promised accuracy and scalability for probability-based distinguishers, it fails to handle cases with unusual distinguisher distributions.

Furthermore, we put forward a novel proposal for a highly scalable key rank estimation method by introducing the notion of an “attacker budget”. Our proposal is based on the idea that, in particular for very long keys, the exact key rank is less important than the knowledge whether a key is within a certain bound. Thus our “budget approach” is based on efficiently checking if the result of an attack is such that the attacker's budget suffices for successful enumeration. Our budget approach scales linearly with the key size and thus enables security estimations even for post-quantum key lengths.

References

[BLvV15]

Daniel J. Bernstein, Tanja Lange, and Christine van Vredendaal. Tighter, faster, simpler side-channel security evaluations beyond computing power. IACR Cryptology ePrint Archive, 2015:221, 2015.

Google Scholar ePrint

[Bur14]

John Burkardt. The truncated normal distribution. 2014.

Google Scholar ePrint

[CDS23]

Giovanni Camurati, Matteo Dell'Amico, and François-Xavier Standaert. MCRank: Monte Carlo Key Rank Estimation for Side-Channel Security Evaluations. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2023(1):277–300, 2023. DOI: 10.46586/TCHES.V2023.I1.277-300

Google Scholar ePrint

[CP17]

Marios O. Choudary and Pantelimon George Popescu. Back to Massey: Impressively Fast, Scalable and Tight Security Evaluation Tools. In Wieland Fischer and Naofumi Homma, editors, Cryptographic Hardware and Embedded Systems - CHES 2017 - 19th International Conference, Taipei, Taiwan, September 25-28, 2017, Proceedings, volume 10529 of Lecture Notes in Computer Science, pages 367–386. 2017. Springer. DOI: 10.1007/978-3-319-66787-4_18

Google Scholar ePrint

[CPS16]

Marios O. Choudary, Romain Poussier, and François-Xavier Standaert. Score-Based vs. Probability-Based Enumeration - A Cautionary Note. In Orr Dunkelman and Somitra Kumar Sanadhya, editors, Progress in Cryptology - INDOCRYPT 2016 - 17th International Conference on Cryptology in India, Kolkata, India, December 11-14, 2016, Proceedings, volume 10095 of Lecture Notes in Computer Science, pages 137–152. 2016. DOI: 10.1007/978-3-319-49890-4_8

Google Scholar ePrint

[DW19a]

Liron David and Avishai Wool. Fast Analytical Rank Estimation. In Ilia Polian and Marc Stöttinger, editors, Constructive Side-Channel Analysis and Secure Design - 10th International Workshop, COSADE 2019, Darmstadt, Germany, April 3-5, 2019, Proceedings, volume 11421 of Lecture Notes in Computer Science, pages 168–190. 2019. Springer. DOI: 10.1007/978-3-030-16350-1_10

Google Scholar ePrint

[DW19b]

Liron David and Avishai Wool. Poly-Logarithmic Side Channel Rank Estimation via Exponential Sampling. In Mitsuru Matsui, editor, Topics in Cryptology - CT-RSA 2019 - The Cryptographers' Track at the RSA Conference 2019, San Francisco, CA, USA, March 4-8, 2019, Proceedings, volume 11405 of Lecture Notes in Computer Science, pages 330–349. 2019. Springer. DOI: 10.1007/978-3-030-12612-4_17

Google Scholar ePrint

[DW22]

Liron David and Avishai Wool. Rank estimation with bounded error via exponential sampling. J. Cryptogr. Eng., 12(2):151–168, 2022. DOI: 10.1007/s13389-021-00269-4

Google Scholar ePrint

[GGP⁺15]

Cezary Glowacz, Vincent Grosso, Romain Poussier, Joachim Schüth, and François-Xavier Standaert. Simpler and More Efficient Rank Estimation for Side-Channel Security Assessment. In Gregor Leander, editor, Fast Software Encryption - 22nd International Workshop, FSE 2015, Istanbul, Turkey, March 8-11, 2015, Revised Selected Papers, volume 9054 of Lecture Notes in Computer Science, pages 117–129. 2015. Springer. DOI: 10.1007/978-3-662-48116-5_6

Google Scholar ePrint

[Gro18]

Vincent Grosso. Scalable Key Rank Estimation (and Key Enumeration) Algorithm for Large Keys. In Begül Bilgin and Jean-Bernard Fischer, editors, Smart Card Research and Advanced Applications, 17th International Conference, CARDIS 2018, Montpellier, France, November 12-14, 2018, Revised Selected Papers, volume 11389 of Lecture Notes in Computer Science, pages 80–94. 2018. Springer. DOI: 10.1007/978-3-030-15462-2_6

Google Scholar ePrint

[HMC05]

R.V. Hogg, J.W. McKean, and A.T. Craig. Introduction to Mathematical Statistics. Pearson education international. Pearson Education 2005.

Google Scholar ePrint

[HS16]

Christian Heumann and Micheal Schomaker Shalabh. Introduction to statistics and data analysis. Springer 2016. DOI: 10.1007/978-3-031-11833-3

Google Scholar ePrint

[KK51]

J.F. Kenney and E.S. Keeping. Mathematics of Statistics: Part two. D. Van Nostrand Company, Incorporated 1951.

Google Scholar ePrint

[LMM⁺16]

Jake Longo, Daniel P. Martin, Luke Mather, Elisabeth Oswald, Benjamin Sach, and Martijn Stam. How low can you go? Using side-channel data to enhance brute-force key recovery. IACR Cryptol. ePrint Arch., 2016.

Google Scholar ePrint

[Mas94]

James L Massey. Guessing and entropy. In Proceedings of 1994 IEEE International Symposium on Information Theory, pages 204. 1994. IEEE. DOI: 10.1109/ISIT.1994.394764

Google Scholar ePrint

[mdt23]

The mpmath development team. mpmath: a Python library for arbitrary-precision floating-point arithmetic (version 1.3.0). , 2023.

Google Scholar ePrint

[MM18]

Daniel P. Martin and Marco Martinoli. A Note on Key Rank. https://eprint.iacr.org/2018/614. Cryptology ePrint Archive, Paper 2018/614. 2018.

Google Scholar ePrint

[MMO18]

Daniel P. Martin, Luke Mather, and Elisabeth Oswald. Two Sides of the Same Coin: Counting and Enumerating Keys Post Side-Channel Attacks Revisited. In Nigel P. Smart, editor, Topics in Cryptology - CT-RSA 2018 - The Cryptographers' Track at the RSA Conference 2018, San Francisco, CA, USA, April 16-20, 2018, Proceedings, volume 10808 of Lecture Notes in Computer Science, pages 394–412. 2018. Springer. DOI: 10.1007/978-3-319-76953-0_21

Google Scholar ePrint

[MMOS16a]

Daniel P. Martin, Luke Mather, Elisabeth Oswald, and Martijn Stam. Characterisation and Estimation of the Key Rank Distribution in the Context of Side Channel Evaluations. In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I, volume 10031 of Lecture Notes in Computer Science, pages 548–572. 2016. DOI: 10.1007/978-3-662-53887-6_20

Google Scholar ePrint

[MMOS16b]

Daniel P. Martin, Luke Mather, Elisabeth Oswald, and Martijn Stam. Labynkyr. https://github.com/sca-research/labynkyr. 2016.

Google Scholar ePrint

[MOOS15]

Daniel P. Martin, Jonathan F. O'Connell, Elisabeth Oswald, and Martijn Stam. Counting Keys in Parallel After a Side Channel Attack. In Tetsu Iwata and Jung Hee Cheon, editors, Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings, Part II, volume 9453 of Lecture Notes in Computer Science, pages 313–337. 2015. Springer. DOI: 10.1007/978-3-662-48800-3_13

Google Scholar ePrint

[Pol19]

Ricardo Villanueva Polanco. Cold boot attacks on post-quantum schemes. PhD thesis, Royal Holloway, University of London, 2019.

Google Scholar ePrint

[PSG16]

Romain Poussier, François-Xavier Standaert, and Vincent Grosso. Simple Key Enumeration (and Rank Estimation) Using Histograms: An Integrated Approach. In Benedikt Gierlichs and Axel Y. Poschmann, editors, Cryptographic Hardware and Embedded Systems - CHES 2016 - 18th International Conference, Santa Barbara, CA, USA, August 17-19, 2016, Proceedings, volume 9813 of Lecture Notes in Computer Science, pages 61–81. 2016. Springer. DOI: 10.1007/978-3-662-53140-2_4

Google Scholar ePrint

[Tuk77]

John Wilder Tukey. Exploratory data analysis. Reading/Addison-Wesley, 1977.

Google Scholar ePrint

[VGRS12]

Nicolas Veyrat-Charvillon, Benoît Gérard, Mathieu Renauld, and François-Xavier Standaert. An Optimal Key Enumeration Algorithm and Its Application to Side-Channel Attacks. In Lars R. Knudsen and Huapeng Wu, editors, Selected Areas in Cryptography, 19th International Conference, SAC 2012, Windsor, ON, Canada, August 15-16, 2012, Revised Selected Papers, volume 7707 of Lecture Notes in Computer Science, pages 390–406. 2012. Springer. DOI: 10.1007/978-3-642-35999-6_25

Google Scholar ePrint

[VGS13]

Nicolas Veyrat-Charvillon, Benoît Gérard, and François-Xavier Standaert. Security Evaluations beyond Computing Power. In Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings, volume 7881 of Lecture Notes in Computer Science, pages 126–141. 2013. Springer. DOI: 10.1007/978-3-642-38348-9_8

Google Scholar ePrint

[YEM14]

Xin Ye, Thomas Eisenbarth, and William Martin. Bounded, yet Sufficient? How to Determine Whether Limited Side Channel Information Enables Key Recovery. In Marc Joye and Amir Moradi, editors, Smart Card Research and Advanced Applications - 13th International Conference, CARDIS 2014, Paris, France, November 5-7, 2014. Revised Selected Papers, volume 8968 of Lecture Notes in Computer Science, pages 215–232. 2014. Springer. DOI: 10.1007/978-3-319-16763-3_13

Google Scholar ePrint

[YMO22]

Rebecca Young, Luke Mather, and Elisabeth Oswald. Comparing Key Rank Estimation Methods. In Ileana Buhan and Tobias Schneider, editors, Smart Card Research and Advanced Applications - 21st International Conference, CARDIS 2022, Birmingham, UK, November 7-9, 2022, Revised Selected Papers, volume 13820 of Lecture Notes in Computer Science, pages 188–204. 2022. Springer. DOI: 10.1007/978-3-031-25319-5_10

Google Scholar ePrint

[ZDF20]

Ziyue Zhang, A. Adam Ding, and Yunsi Fei. A Fast and Accurate Guessing Entropy Estimation Algorithm for Full-key Recovery. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2020(2):26–48, 2020. DOI: 10.13154/TCHES.V2020.I2.26-48

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/aytxl86bm

History

Submitted: 2024-07-08
Accepted: 2024-09-02
Published: 2024-10-07

How to cite

Rebecca Hay and Elisabeth Oswald, Key Rank Estimation Methods: Comparisons and Practical Considerations. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/aytxl86bm.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-3-34,
    author = "Hay, Rebecca and Oswald, Elisabeth",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Key Rank Estimation Methods: Comparisons and Practical Considerations",
    volume = "1",
    number = "3",
    date = "2024-10-07",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/aytxl86bm"
}

TY - JOUR
AU - Hay, Rebecca
AU - Oswald, Elisabeth
PY  - 2024
TI  - Key Rank Estimation Methods: Comparisons and Practical Considerations
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 3
DO  - 10.62056/aytxl86bm
UR  - https://doi.org/10.62056/aytxl86bm
AB  - <p>New proposals for scalable key rank estimation methods have appeared recently, in particular the sampling based approach MCRank. The idea is that one can consistently estimate the key rank by sampling only a small portion of the key space as a “proxy”, leading to both an accurate and scalable approach, at least in comparison with another approach based on histograms. We show that the (earlier) GEEA algorithm is in fact a sampling based algorithm, and provide an in-depth comparison between GEEA (when adapted to produce rank estimates rather than guessing entropy estimates), GM bounds, MCRank and the currently most performant counting based rank estimation as implemented in the Labynkyr library. We find that although MCRank does live up to the promised accuracy and scalability for probability-based distinguishers, it fails to handle cases with unusual distinguisher distributions.</p><p>Furthermore, we put forward a novel proposal for a highly scalable key rank estimation method by introducing the notion of an “attacker budget”. Our proposal is based on the idea that, in particular for very long keys, the exact key rank is less important than the knowledge whether a key is within a certain bound. Thus our “budget approach” is based on efficiently checking if the result of an attack is such that the attacker's budget suffices for successful enumeration. Our budget approach scales linearly with the key size and thus enables security estimations even for post-quantum key lengths. </p>
ER  -

Rebecca Hay and Elisabeth Oswald, Key Rank Estimation Methods: Comparisons and Practical Considerations. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/aytxl86bm.