Leakage-Resilient Authentication and Encryption from Symmetric Cryptographic Primitives

ABSTRACT

Leakage-resilient cryptosystems aim to maintain security in situations where their implementation leaks physical information about their internal secrets. Because of their efficiency and usability on a wide range of platforms, solutions based on symmetric primitives (such as block ciphers) are particularly attractive in this context. So far, the literature has mostly focused on the design of leakage-resilient pseudorandom objects (e.g. PRGs, PRFs, PRPs). In this paper, we consider the complementary and practically important problem of designing secure authentication and encryption schemes. For this purpose, we follow a pragmatic approach based on the advantages and limitations of existing leakage-resilient pseudorandom objects, and rely on the (arguably necessary, yet minimal) use of a leak-free component. The latter can typically be instantiated with a block cipher implementation protected by traditional countermeasures, and we investigate how to combine it with the more intensive use of a much more efficient (less protected) block cipher implementation. Based on these premises, we propose and analyse new constructions of leakage-resilient MAC and encryption schemes, which allow fixing security and efficiency drawbacks of previous proposals in this direction. For encryption, we additionally provide a detailed discussion of why previously proposed (indistinguishability based) security definitions cannot capture actual side-channel attacks, and suggest a relaxed and more realistic way to quantify leakage-resilience in this case, by reducing the security of many iterations of the primitive to the security of a single iteration, independent of the security notion guaranteed by this single iteration (that remains hard to define).

References

1. CHES 2013, volume 8086 of Lecture Notes in Computer Science. Springer, 2013.
2. M. Abdalla, S. Belaıd, and P. Fouque. Leakage-resilient symmetric encryption via re-keying. In CHES 2013citeDBLP:conf/ches/2013, pages 471--488.
3. S. Belaıd, V. Grosso, and F. Standaert. Masking and leakage-resilient primitives: One, the other(s) or both? Cryptography and Communications, 7(1):163--184, 2015.
4. M. Bellare, J. Kilian, and P. Rogaway. The security of the cipher block chaining message authentication code. J. Comput. Syst. Sci., 61(3):362--399, 2000.
5. S. Chari, C. S. Jutla, J. R. Rao, and P. Rohatgi. Towards sound approaches to counteract power-analysis attacks. In CRYPTO '99, volume 1666 of Lecture Notes in Computer Science, pages 398--412. Springer, 1999.
6. Y. Dodis and K. Pietrzak. Leakage-resilient pseudorandom functions and side-channel attacks on feistel networks. In CRYPTO 2010, volume 6223 of Lecture Notes in Computer Science, pages 21--40. Springer, 2010.
7. S. Dziembowski and K. Pietrzak. Leakage-resilient cryptography. In FOCS 2008, pages 293--302. IEEE Computer Society, 2008.
8. T. Eisenbarth, Z. Gong, T. Güneysu, S. Heyse, S. Indesteege, S. Kerckhof, F. Koeune, T. Nad, T. Plos, F. Regazzoni, F. Standaert, and L. van Oldeneel tot Oldenzeel. Compact implementation and performance evaluation of block ciphers in attiny devices. In A. Mitrokotsa and S. Vaudenay, editors, AFRICACRYPT 2012, volume 7374 of Lecture Notes in Computer Science, pages 172--187. Springer, 2012.
9. S. Faust, K. Pietrzak, and J. Schipper. Practical leakage-resilient symmetric cryptography. In CHES 2012, volume 7428 of Lecture Notes in Computer Science, pages 213--232. Springer, 2012.
10. B. Fuller and A. Hamlin. Unifying leakage classes: Simulatable leakage and pseudoentropy. In ICITS 2015, volume 9063 of Lecture Notes in Computer Science, pages 69--86. Springer, 2015.
11. J. L. Galea, D. P. Martin, E. Oswald, D. Page, M. Stam, and M. Tunstall. Simulatable leakage: Analysis, pitfalls, and new constructions. In ASIACRYPT 2014, volume 8873 of Lecture Notes in Computer Science, pages 223--242. Springer, 2014.
12. D. Galindo and S. Vivek. A leakage-resilient pairing-based variant of the Schnorr signature scheme. In IMA International Conference, IMACC 2013, volume 8308 of Lecture Notes in Computer Science, pages 173--192. Springer, 2013.
13. V. Grosso, F. Standaert, and S. Faust. Masking vs. multiparty computation: How large is the gap for aes? In CHES 2013citeDBLP:conf/ches/2013, pages 400--416.
14. V. Grosso, F. Standaert, and S. Faust. Masking vs. multiparty computation: how large is the gap for AES? J. Cryptographic Engineering, 4(1):47--57, 2014.
15. C. Hazay, A. López-Alt, H. Wee, and D. Wichs. Leakage-resilient cryptography from minimal assumptions. In EUROCRYPT 2013, volume 7881 of Lecture Notes in Computer Science, pages 160--176. Springer, 2013.
16. Y. Ishai, A. Sahai, and D. Wagner. Private circuits: Securing hardware against probing attacks. In CRYPTO 2003, volume 2729 of Lecture Notes in Computer Science, pages 463--481. Springer, 2003.
17. M. Joye and M. Tunstall, editors. Fault Analysis in Cryptography. Information Security and Cryptography. Springer, 2012.
18. E. Kiltz and K. Pietrzak. Leakage resilient ElGamal encryption. In ASIACRYPT 2010, volume 6477 of Lecture Notes in Computer Science, pages 595--612. Springer, 2010.
19. L. R. Knudsen and M. Robshaw. The Block Cipher Companion. Information Security and Cryptography. Springer, 2011.
20. M. Liskov, R. L. Rivest, and D. Wagner. Tweakable block ciphers. In CRYPTO 2002, volume 2442 of Lecture Notes in Computer Science, pages 31--46. Springer, 2002.
21. S. Mangard, E. Oswald, and T. Popp. Power analysis attacks - revealing the secrets of smart cards. Springer, 2007.
22. S. Mangard, T. Popp, and B. M. Gammel. Side-channel leakage of masked CMOS gates. In CT-RSA 2005, volume 3376 of Lecture Notes in Computer Science, pages 351--365. Springer, 2005.
23. D. P. Martin, E. Oswald, and M. Stam. A leakage resilient MAC. IACR Cryptology ePrint Archive, 2013:292, 2013.
24. M. Medwed, F. Standaert, J. Großschadl, and F. Regazzoni. Fresh re-keying: Security against side-channel and fault attacks for low-cost devices. In AFRICACRYPT 2010, volume 6055 of Lecture Notes in Computer Science, pages 279--296. Springer, 2010.
25. S. Micali and L. Reyzin. Physically observable cryptography (extended abstract). In TCC 2004, volume 2951 of Lecture Notes in Computer Science, pages 278--296. Springer, 2004.
26. A. Moradi, A. Poschmann, S. Ling, C. Paar, and H. Wang. Pushing the limits: A very compact and a threshold implementation of AES. In K. G. Paterson, editor, EUROCRYPT, volume 6632 of Lecture Notes in Computer Science, pages 69--88. Springer, 2011.
27. M. Naor and G. Segev. Public-key cryptosystems resilient to key leakage. In CRYPTO 2009, volume 5677 of Lecture Notes in Computer Science, pages 18--35. Springer, 2009.
28. S. Nikova, V. Rijmen, and M. Schl\"affer. Secure hardware implementation of nonlinear functions in the presence of glitches. J. Cryptology, 24(2):292--321, 2011.
29. P. Pessl, F. Standaert, S. Mangard, and F. Durvaux. Towards leakage simulators that withstand the correlation distinguisher. ASIACRYPT 2014 rump session talk, 2014.
30. C. Petit, F. Standaert, O. Pereira, T. Malkin, and M. Yung. A block cipher based pseudo random number generator secure against side-channel key recovery. In ASIACCS 2008, pages 56--65. ACM, 2008.
31. K. Pietrzak. A leakage-resilient mode of operation. In EUROCRYPT 2009, volume 5479 of Lecture Notes in Computer Science, pages 462--482. Springer, 2009.
32. E. Prouff and T. Roche. Higher-order glitches free implementation of the AES using secure multi-party computation protocols. In B. Preneel and T. Takagi, editors, CHES 2011, volume 6917 of Lecture Notes in Computer Science, pages 63--78. Springer, 2011.
33. F. Regazzoni, W. Yi, and F.-X. Standaert. FPGA implementations of the AES masked against power analysis attacks. IntextitCOSADE 2011, pp 56--66, Darmstadt, Germany, February 2011.
34. M. Rivain and E. Prouff. Provably secure higher-order masking of AES. In S. Mangard and F. Standaert, editors, CHES 2010, volume 6225 of Lecture Notes in Computer Science, pages 413--427. Springer, 2010.
35. J. Schipper. Leakage-resilient authentication. Msc thesis, Centrum Wiskunde and Informatica, The Netherlands, 2010.
36. F. Standaert, O. Pereira, and Y. Yu. Leakage-resilient symmetric cryptography under empirically verifiable assumptions. In CRYPTO 2013, volume 8042 of Lecture Notes in Computer Science, pages 335--352. Springer, 2013.
37. F. Standaert, O. Pereira, Y. Yu, J. Quisquater, M. Yung, and E. Oswald. Leakage resilient cryptography in practice. In Towards Hardware-Intrinsic Security - Foundations and Practice, Information Security and Cryptography, pages 99--134. Springer, 2010.
38. Y. Yu and F. Standaert. Practical leakage-resilient pseudorandom objects with minimum public randomness. In CT-RSA 2013, volume 7779 of Lecture Notes in Computer Science, pages 223--238. Springer, 2013.
39. Y. Yu, F. Standaert, O. Pereira, and M. Yung. Practical leakage-resilient pseudorandom generators. In CCS 2010, pages 141--151. ACM, 2010.

Index Terms

• Information systems

  • Information systems applications