In any side-channel attack, it is desirable to exploit all the available leakage data to compute the distinguisher’s values. The profiling phase is essential to obtain an accurate leakage model, yet it may not be exhaustive. As a result, information theoretic distinguishers may come up on previously unseen data, a phenomenon yielding empty bins. A strict application of the maximum likelihood method yields a distinguisher that is not even sound. Ignoring empty bins reestablishes soundness, but seriously limits its performance in terms of success rate. The purpose of this paper is to remedy this situation. In this research, we propose six different techniques to improve the performance of information theoretic distinguishers. We study t hem thoroughly by applying them to timing attacks, both with synthetic and real leakages. Namely, we compare them in terms of success rate, and show that their performance depends on the amount of profiling, and can be explained by a bias-variance analysis. The result of our work is that there exist use-cases, especially when measurements are noisy, where our novel information theoretic distinguishers (typically the soft-drop distinguisher) perform the best compared to known side-channel distinguishers, despite the empty bin situation.
Daemen, J. and Rijmen, V. (2002) The Design of Rijndael: AES—The Advanced Encryption Standard. Springer, Berlin. https://doi.org/10.1007/978-3-662-04722-4_1
Schindler, W. (2000) A Timing Attack against RSA with the Chinese Remainder Theorem. In: Koç, Ç.K. and Paar, C., Eds., Proceedings of the Second International Workshop on Cryptographic Hardware and Embedded Systems, Lecture Notes in Computer Science, Vol. 1965, Springer, Berlin, 109-124. https://doi.org/10.1007/3-540-44499-8_8
Schindler, W. (2002) Optimized Timing Attacks against Public Key Cryptosystems. Statistics & Risk Modeling, 20, 191-210. https://doi.org/10.1524/strm.2002.20.14.191
Brumley, D. and Boneh, D. (2003) Remote Timing Attacks Are Practical. Proceedings of the 12th USENIX Security Symposium, Washington DC, 4-8 August 2003, 1-13. https://www.usenix.org/conference/12th-usenix-security-symposium/remote-timing-attacks-are-practical
Brumley, B.B. and Tuveri, N. (2011) Remote Timing Attacks Are Still Practical. In: Atluri, V. and Díaz, C., Eds., European Symposium on Research in Computer Security, Lecture Notes in Computer Science, Vol. 6879, Springer, Berlin, 355-371. https://doi.org/10.1007/978-3-642-23822-2_20
Danger, J.-L., Debande, N., Guilley, S. and Souissi, Y. (2014) High-Order Timing Attacks. In: Proceedings of the First Workshop on Cryptography and Security in Computing Systems, ACM, New York, 7-12. https://doi.org/10.1145/2556315.2556316
Chari, S., Rao, J.R. and Rohatgi, P. (2002) Template Attacks. In: International Workshop on Cryptographic Hardware and Embedded Systems, LNCS, Vol. 2523, Springer, Berlin, 13-28. https://doi.org/10.1007/3-540-36400-5_3
Kocher, P.C. (1996) Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. Advances in Cryptology—CRYPTO’96, Santa Barbara, 18-22 August 1996, Vol. 1109, 104-113. https://doi.org/10.1007/3-540-68697-5_9
Bernstein, D.J. (2005) Cache-Timing Attacks on AES. 1-37. http://cr.yp.to/antiforgery/cachetiming-20050414.pdf
Rebeiro, C. and Mukhopadhyay, D. (2012) Boosting Profiled Cache Timing Attacks with a Priori Analysis. IEEE Transactions on Information Forensics and Security, 7, 1900-1905. https://doi.org/10.1109/TIFS.2012.2217333
Weiß, M., Heinz, B. and Stumpf, F. (2012) A Cache Timing Attack on AES in Virtualization Environments. 16th International Conference on Financial Cryptography and Data Security, Kralendijk, 27 February-2 March 2012, Vol. 7397, 314-328. https://doi.org/10.1007/978-3-642-32946-3_23
Bhattacharya, S., Rebeiro, C. and Mukhopadhyay, D. (2012) Hardware Prefetchers Leak: A Revisit of SVF for Cache-Timing Attacks. 45th Annual IEEE/ACM International Symposium on Microarchitecture, Vancouver, 1-5 December 2012, 17-23. https://doi.org/10.1109/MICROW.2012.13
Parzen, E. (1962) On Estimation of a Probability Density Function and Mode. Annals of Mathematical Statistics, 33, 1065-1076. https://doi.org/10.1214/aoms/1177704472
Standaert, F.-X., Malkin, T. and Yung, M. (2009) A Unified Framework for the Analysis of Side-Channel Key Recovery Attacks. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, LNCS, Vol. 5479, Springer, Berlin, 443-461. https://doi.org/10.1007/978-3-642-01001-9_26
Heuser, A., Rioul, O. and Guilley, S. (2014) Good Is Not Good Enough—Deriving Optimal Distinguishers from Communication Theory. 16th Workshop on Cryptographic Hardware and Embedded Systems, Busan, 23-26 September 2014, Vol. 8731, 55-74. https://doi.org/10.1007/978-3-662-44709-3_4
Frigyik, B.A., Kapila, A. and Gupta, M.R. (2010) Introduction to the Dirichlet Distribution and Related Processes. UWEE (University of Washington, Electrical Engineering) Technical Report Series, Tech. Rep. 206.
Moradi, A. and Standaert, F. (2014) Moments-Correlating DPA. IACR Cryptology ePrint Archive, Vol. 2014, 409. http://eprint.iacr.org/2014/409
Moradi, A. and Standaert, F. (2016) Moments-Correlating DPA. Proceedings of the ACM Workshop on Theory of Implementation Security, Vienna, October 2016, 5-15.
Veyrat-Charvillon, N. and Standaert, F.-X. (2009) Mutual Information Analysis: How, When and Why? In: International Workshop on Cryptographic Hardware and Embedded Systems, LNCS, Vol. 5747, Springer, Berlin, 429-443. https://doi.org/10.1007/978-3-642-04138-9_30
Gierlichs, B., Batina, L., Tuyls, P. and Preneel, B. (2008) Mutual Information Analysis. In: CHES, 10th International Workshop, Lecture Notes in Computer Science, Vol. 5154, Springer, Berlin, 426-442. https://doi.org/10.1007/978-3-540-85053-3_27
Microelectronics, S. STM32F4DISCOVERY Discovery Kit with STM32F407VG MCU. http://www.st.com/web/catalog/tools/FM116/SC959/SS1532/PF252419?sc=internet/evalboard/product/252419.jsp
NIST (2003) AES Proposal: Rijndael (Now FIPS PUB 197). http://csrc.nist.gov/archive/aes/rijndael/Rijndael-ammended.pdf
Guilley, S., Heuser, A. and Rioul, O. (2015) A Key to Success—Success Exponents for Side-Channel Distinguishers. Progress in Cryptology—INDOCRYPT 2015—16th International Conference on Cryptology in India, Bangalore, 6-9 December 2015, Vol. 9462, 270-290. https://doi.org/10.1007/978-3-319-26617-6_15
Aly, H. and ElGayyar, M. (2013) Attacking AES Using Bernstein’s Attack on Modern Processors. Progress in Cryptology—AFRICACRYPT 2013, 6th International Conference on Cryptology in Africa, Cairo, 22-24 June 2013, Vol. 7918, 127-139. https://doi.org/10.1007/978-3-642-38553-7_7
Bernstein, D.J. (2005) Cache-Timing Attacks on AES. http://cr.yp.to/antiforgery/cachetiming-20050414.pdf
Renauld, M., Kamel, D., Standaert, F.-X. and Flandre, D. (2011) Information Theoretic and Security Analysis of a 65-Nanometer DDSLL AES SBox. In: Preneel, B. and Takagi, T., Eds., International Workshop on Cryptographic Hardware and Embedded Systems, LNCS, Vol. 6917, Springer, Berlin, 223-239. https://doi.org/10.1007/978-3-642-23951-9_15
Heuser, A. and Zohner, M. (2012) Intelligent Machine Homicide: Breaking Cryptographic Devices Using Support Vector Machines. In: Schindler, W. and Huss, S.A., Eds., International Workshop on Constructive Side-Channel Analysis and Secure Design, LNCS, Vol. 7275, Springer, Berlin, 249-264. https://doi.org/10.1007/978-3-642-29912-4_18