×

Parallel implementations of masking schemes and the bounded moment leakage model. (English) Zbl 1411.94050

Coron, Jean-Sébastien (ed.) et al., Advances in cryptology – EUROCRYPT 2017. 36th annual international conference on the theory and applications of cryptographic techniques, Paris, France, April 30 – May 4, 2017. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 10210, 535-566 (2017).
Summary: In this paper, we provide a necessary clarification of the good security properties that can be obtained from parallel implementations of masking schemes. For this purpose, we first argue that (i) the probing model is not straightforward to interpret, since it more naturally captures the intuitions of serial implementations, and (ii) the noisy leakage model is not always convenient, e.g. when combined with formal methods for the verification of cryptographic implementations. Therefore we introduce a new model, the bounded moment model, that formalizes a weaker notion of security order frequently used in the side-channel literature. Interestingly, we prove that probing security for a serial implementation implies bounded moment security for its parallel counterpart. This result therefore enables an accurate understanding of the links between formal security analyses of masking schemes and experimental security evaluations based on the estimation of statistical moments. Besides its consolidating nature, our work also brings useful technical contributions. First, we describe and analyze refreshing and multiplication algorithms that are well suited for parallel implementations and improve security against multivariate side-channel attacks. Second, we show that simple refreshing algorithms (with linear complexity) that are not secure in the continuous probing model are secure in the continuous bounded moment model. Eventually, we discuss the independent leakage assumption required for masking to deliver its security promises, and its specificities related to the serial or parallel nature of an implementation.
For the entire collection see [Zbl 1360.94005].

MSC:

94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Francillon, A., Rohatgi, P. (eds.): CARDIS 2013. LNCS, vol. 8419. Springer, Heidelberg (2014)
[2] Prouff, E., Schaumont, P. (eds.): CHES 2012. LNCS, vol. 7428. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-33027-8 · Zbl 1250.68047 · doi:10.1007/978-3-642-33027-8
[3] Güneysu, T., Handschuh, H. (eds.): CHES 2015. LNCS, vol. 9293. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-48324-4 · Zbl 1343.68011 · doi:10.1007/978-3-662-48324-4
[4] Gierlichs, B., Poschmann, A.Y. (eds.): CHES 2016. LNCS, vol. 9813. Springer, Heidelberg (2016). doi: 10.1007/978-3-662-53140-2 · Zbl 1343.68009 · doi:10.1007/978-3-662-53140-2
[5] Wiener, M. (ed.): CRYPTO 1999. LNCS, vol. 1666. Springer, Heidelberg (1999). doi: 10.1007/3-540-48405-1 · Zbl 0921.00042 · doi:10.1007/3-540-48405-1
[6] Oswald, E., Fischlin, M. (eds.): EUROCRYPT 2015. LNCS, vol. 9056. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-46800-5 · Zbl 1321.94010 · doi:10.1007/978-3-662-46800-5
[7] Fischlin, M., Coron, J.-S. (eds.): EUROCRYPT 2016. LNCS, vol. 9666. Springer, Heidelberg (2016) · Zbl 1339.94004
[8] Joye, M., Moradi, A. (eds.): CARDIS 2014. LNCS, vol. 8968. Springer, Heidelberg (2015). doi: 10.1007/978-3-319-16763-3 · Zbl 06473521 · doi:10.1007/978-3-319-16763-3
[9] Andrychowicz, M., Dziembowski, S., Faust, S.: Circuit compilers with O(1/ \[ \backslash \] n)) leakage rate. In: EUROCRYPT 2016, Part II [7], pp. 586–615 (2016) · Zbl 1371.94620
[10] Archambeau, C., Peeters, E., Standaert, F.-X., Quisquater, J.-J.: Template attacks in principal subspaces. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 1–14. Springer, Heidelberg (2006). doi: 10.1007/11894063_1 · Zbl 05317706 · doi:10.1007/11894063_1
[11] Balasch, J., Gierlichs, B., Grosso, V., Reparaz, O., Standaert, F.-X.: On the cost of lazy engineering for masked software implementations. In: Joye, M., Moradi, A. (eds.) CARDIS 2014. LNCS, vol. 8968, pp. 64–81. Springer, Heidelberg (2015). doi: 10.1007/978-3-319-16763-3_5 · doi:10.1007/978-3-319-16763-3_5
[12] Balasch, J., Gierlichs, B., Reparaz, O., Verbauwhede, I.: DPA, bitslicing and masking at 1 GHz. In: Güneysu, T., Handschuh, H. (eds.) CHES 2015. LNCS, vol. 9293, pp. 599–619. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-48324-4_30 · Zbl 06838246 · doi:10.1007/978-3-662-48324-4_30
[13] Barthe, G., Belaïd, S., Dupressoir, F., Fouque, P.-A., Grégoire, B., Strub, P.-Y.: Verified proofs of higher-order masking. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 457–485. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-46800-5_18 · Zbl 1370.94486 · doi:10.1007/978-3-662-46800-5_18
[14] Barthe, G., Belaid, S., Dupressoir, F., Fouque, P.-A., Gregoire, B., Strub, P.-Y., Zucchini, R.: Strong non-interference and type-directed higher-order masking. In: Proceedings of ACM CCS (2016, to appear) · doi:10.1145/2976749.2978427
[15] Barthe, G., Dupressoir, F., Faust, S., Grégoire, B., Standaert, F., Strub, P.: Parallel implementations of masking schemes and the bounded moment leakage model. IACR Cryptol. ePrint Arch. 2016, 912 (2016) · Zbl 1411.94050
[16] Batina, L., Gierlichs, B., Prouff, E., Rivain, M., Standaert, F., Veyrat-Charvillon, N.: Mutual information analysis: a comprehensive study. J. Cryptol. 24(2), 269–291 (2011) · Zbl 1239.94032 · doi:10.1007/s00145-010-9084-8
[17] Battistello, A., Coron, J.-S., Prouff, E., Zeitoun, R.: Horizontal side-channel attacks and countermeasures on the ISW masking scheme. In: Gierlichs, B., Poschmann, A.Y. (eds.) CHES 2016. LNCS, vol. 9813, pp. 23–39. Springer, Heidelberg (2016). doi: 10.1007/978-3-662-53140-2_2 · Zbl 1380.94071 · doi:10.1007/978-3-662-53140-2_2
[18] Bayrak, A.G., Regazzoni, F., Novo, D., Ienne, P.: Sleuth: automated verification of software power analysis countermeasures. In: Bertoni, G., Coron, J.-S. (eds.) CHES 2013. LNCS, vol. 8086, pp. 293–310. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-40349-1_17 · Zbl 06215105 · doi:10.1007/978-3-642-40349-1_17
[19] Belaïd, S., Benhamouda, F., Passelègue, A., Prouff, E., Thillard, A., Vergnaud, D.: Randomness complexity of private circuits for multiplication. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 616–648. Springer, Heidelberg (2016). doi: 10.1007/978-3-662-49896-5_22 · Zbl 1371.94624 · doi:10.1007/978-3-662-49896-5_22
[20] Bilgin, B., Daemen, J., Nikov, V., Nikova, S., Rijmen, V., Assche, G.: Efficient and first-order DPA resistant implementations of keccak. In: Francillon, A., Rohatgi, P. (eds.) CARDIS 2013. LNCS, vol. 8419, pp. 187–199. Springer, Heidelberg (2014). doi: 10.1007/978-3-319-08302-5_13 · doi:10.1007/978-3-319-08302-5_13
[21] Bilgin, B., Gierlichs, B., Nikova, S., Nikov, V., Rijmen, V.: Higher-order threshold implementations. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 326–343. Springer, Heidelberg (2014). doi: 10.1007/978-3-662-45608-8_18 · Zbl 1317.94086 · doi:10.1007/978-3-662-45608-8_18
[22] Bilgin, B., Gierlichs, B., Nikova, S., Nikov, V., Rijmen, V.: A more efficient AES threshold implementation. In: Pointcheval, D., Vergnaud, D. (eds.) AFRICACRYPT 2014. LNCS, vol. 8469, pp. 267–284. Springer, Heidelberg (2014). doi: 10.1007/978-3-319-06734-6_17 · Zbl 1288.94053 · doi:10.1007/978-3-319-06734-6_17
[23] Bilgin, B., Nikova, S., Nikov, V., Rijmen, V., Stütz, G.: Threshold implementations of all 3 \[ \times \] 3 and 4 \[ \times \] 4 S-boxes. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol. 7428, pp. 76–91. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-33027-8_5 · Zbl 1366.94478 · doi:10.1007/978-3-642-33027-8_5
[24] Blömer, J., Guajardo, J., Krummel, V.: Provably secure masking of AES. In: Handschuh, H., Hasan, M.A. (eds.) SAC 2004. LNCS, vol. 3357, pp. 69–83. Springer, Heidelberg (2004). doi: 10.1007/978-3-540-30564-4_5 · Zbl 1117.94312 · doi:10.1007/978-3-540-30564-4_5
[25] Carlet, C., Danger, J., Guilley, S., Maghrebi, H., Prouff, E.: Achieving side-channel high-order correlation immunity with leakage squeezing. J. Cryptogr. Eng. 4(2), 107–121 (2014) · doi:10.1007/s13389-013-0067-1
[26] Chari, S., Jutla, C.S., Rao, J.R., Rohatgi, P.: Towards sound approaches to counteract power-analysis attacks. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 398–412. Springer, Heidelberg (1999). doi: 10.1007/3-540-48405-1_26 · Zbl 0942.68045 · doi:10.1007/3-540-48405-1_26
[27] Chen, C., Eisenbarth, T., Shahverdi, A., Ye, X.: Balanced encoding to mitigate power analysis: a case study. In: Joye, M., Moradi, A. (eds.) CARDIS 2014. LNCS, vol. 8968, pp. 49–63. Springer, Heidelberg (2015). doi: 10.1007/978-3-319-16763-3_4 · doi:10.1007/978-3-319-16763-3_4
[28] De Cnudde, T., Reparaz, O., Bilgin, B., Nikova, S., Nikov, V., Rijmen, V.: Masking AES with \[ d+1 \] shares in hardware. In: Gierlichs, B., Poschmann, A.Y. (eds.) CHES 2016. LNCS, vol. 9813, pp. 194–212. Springer, Heidelberg (2016). doi: 10.1007/978-3-662-53140-2_10 · Zbl 1429.94056 · doi:10.1007/978-3-662-53140-2_10
[29] Coron, J.-S., Giraud, C., Prouff, E., Renner, S., Rivain, M., Vadnala, P.K.: Conversion of security proofs from one leakage model to another: a new issue. In: Schindler, W., Huss, S.A. (eds.) COSADE 2012. LNCS, vol. 7275, pp. 69–81. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-29912-4_6 · Zbl 1352.94032 · doi:10.1007/978-3-642-29912-4_6
[30] Coron, J.-S., Prouff, E., Rivain, M.: Side channel cryptanalysis of a higher order masking scheme. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 28–44. Springer, Heidelberg (2007). doi: 10.1007/978-3-540-74735-2_3 · Zbl 1300.94048 · doi:10.1007/978-3-540-74735-2_3
[31] Duc, A., Dziembowski, S., Faust, S.: Unifying leakage models: from probing attacks to noisy leakage. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 423–440. Springer, Heidelberg (2014). doi: 10.1007/978-3-642-55220-5_24 · Zbl 1326.94086 · doi:10.1007/978-3-642-55220-5_24
[32] Duc, A., Faust, S., Standaert, F.-X.: Making masking security proofs concrete. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 401–429. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-46800-5_16 · Zbl 1370.94508 · doi:10.1007/978-3-662-46800-5_16
[33] Durvaux, F., Standaert, F.-X.: From improved leakage detection to the detection of points of interests in leakage traces. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 240–262. Springer, Heidelberg (2016). doi: 10.1007/978-3-662-49890-3_10 · Zbl 1384.94058 · doi:10.1007/978-3-662-49890-3_10
[34] Durvaux, F., Standaert, F.-X., Pozo, S.M.: Towards easy leakage certification. In: Gierlichs, B., Poschmann, A.Y. (eds.) CHES 2016. LNCS, vol. 9813, pp. 40–60. Springer, Heidelberg (2016). doi: 10.1007/978-3-662-53140-2_3 · Zbl 1380.94086 · doi:10.1007/978-3-662-53140-2_3
[35] Dziembowski, S., Faust, S.: Leakage-resilient cryptography from the inner-product extractor. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 702–721. Springer, Heidelberg (2011). doi: 10.1007/978-3-642-25385-0_38 · Zbl 1227.94043 · doi:10.1007/978-3-642-25385-0_38
[36] Dziembowski, S., Faust, S., Herold, G., Journault, A., Masny, D., Standaert, F.-X.: Towards sound fresh re-keying with hard (physical) learning problems. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 272–301. Springer, Heidelberg (2016). doi: 10.1007/978-3-662-53008-5_10 · Zbl 1391.94746 · doi:10.1007/978-3-662-53008-5_10
[37] Eldib, H., Wang, C.: Synthesis of masking countermeasures against side channel attacks. In: Biere, A., Bloem, R. (eds.) CAV 2014. LNCS, vol. 8559, pp. 114–130. Springer, Heidelberg (2014). doi: 10.1007/978-3-319-08867-9_8 · Zbl 1445.68058 · doi:10.1007/978-3-319-08867-9_8
[38] Eldib, H., Wang, C., Schaumont, P.: Formal verification of software countermeasures against side-channel attacks. ACM Trans. Softw. Eng. Methodol. 24(2), 11:1–11:24 (2014) · doi:10.1145/2685616
[39] Eldib, H., Wang, C., Taha, M.M.I., Schaumont, P.: Quantitative masking strength: quantifying the power side-channel resistance of software code. IEEE Trans. CAD Integr. Circuits Syst. 34(10), 1558–1568 (2015) · doi:10.1109/TCAD.2015.2424951
[40] Grosso, V., Leurent, G., Standaert, F.-X., Varıcı, K.: LS-designs: bitslice encryption for efficient masked software implementations. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 18–37. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-46706-0_2 · Zbl 1382.94111 · doi:10.1007/978-3-662-46706-0_2
[41] Grosso, V., Standaert, F.-X., Prouff, E.: Low entropy masking schemes, revisited. In: Francillon, A., Rohatgi, P. (eds.) CARDIS 2013. LNCS, vol. 8419, pp. 33–43. Springer, Heidelberg (2014). doi: 10.1007/978-3-319-08302-5_3 · doi:10.1007/978-3-319-08302-5_3
[42] Ishai, Y., Sahai, A., Wagner, D.: Private circuits: securing hardware against probing attacks. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 463–481. Springer, Heidelberg (2003). doi: 10.1007/978-3-540-45146-4_27 · Zbl 1122.94378 · doi:10.1007/978-3-540-45146-4_27
[43] Kocher, P., Jaffe, J., Jun, B.: Differential power analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999). doi: 10.1007/3-540-48405-1_25 · Zbl 0942.94501 · doi:10.1007/3-540-48405-1_25
[44] Longo, J., Mulder, E., Page, D., Tunstall, M.: SoC it to EM: electromagnetic side-channel attacks on a complex system-on-chip. In: Güneysu, T., Handschuh, H. (eds.) CHES 2015. LNCS, vol. 9293, pp. 620–640. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-48324-4_31 · Zbl 06838247 · doi:10.1007/978-3-662-48324-4_31
[45] Mangard, S., Popp, T., Gammel, B.M.: Side-channel leakage of masked CMOS gates. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 351–365. Springer, Heidelberg (2005). doi: 10.1007/978-3-540-30574-3_24 · Zbl 1079.94561 · doi:10.1007/978-3-540-30574-3_24
[46] Mangard, S., Pramstaller, N., Oswald, E.: Successfully attacking masked AES hardware implementations. In: Rao, J.R., Sunar, B. (eds.) CHES 2005. LNCS, vol. 3659, pp. 157–171. Springer, Heidelberg (2005). doi: 10.1007/11545262_12 · Zbl 05317678 · doi:10.1007/11545262_12
[47] Moradi, A.: Statistical tools flavor side-channel collision attacks. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 428–445. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-29011-4_26 · Zbl 1297.94092 · doi:10.1007/978-3-642-29011-4_26
[48] Moradi, A., Poschmann, A., Ling, S., Paar, C., Wang, H.: Pushing the limits: a very compact and a threshold implementation of AES. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 69–88. Springer, Heidelberg (2011). doi: 10.1007/978-3-642-20465-4_6 · Zbl 1281.94044 · doi:10.1007/978-3-642-20465-4_6
[49] Moss, A., Oswald, E., Page, D., Tunstall, M.: Compiler assisted masking. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol. 7428, pp. 58–75. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-33027-8_4 · Zbl 06105580 · doi:10.1007/978-3-642-33027-8_4
[50] Nikova, S., Rijmen, V., Schläffer, M.: Secure hardware implementation of nonlinear functions in the presence of glitches. J. Cryptol. 24(2), 292–321 (2011) · Zbl 1239.94060 · doi:10.1007/s00145-010-9085-7
[51] Paul, C.R.: Introduction to Electromagnetic Compatibility. Wiley & Sons, Hoboken (2006)
[52] Poschmann, A., Moradi, A., Khoo, K., Lim, C., Wang, H., Ling, S.: Side-channel resistant crypto for less than 2,300 GE. J. Cryptol. 24(2), 322–345 (2011) · Zbl 1239.94063 · doi:10.1007/s00145-010-9086-6
[53] Prouff, E., Rivain, M.: Masking against side-channel attacks: a formal security proof. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 142–159. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-38348-9_9 · Zbl 1306.94087 · doi:10.1007/978-3-642-38348-9_9
[54] Prouff, E., Rivain, M., Bevan, R.: Statistical analysis of second order differential power analysis. IEEE Trans. Comput. 58(6), 799–811 (2009) · Zbl 1367.94339 · doi:10.1109/TC.2009.15
[55] Reparaz, O., Bilgin, B., Nikova, S., Gierlichs, B., Verbauwhede, I.: Consolidating masking schemes. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 764–783. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-47989-6_37 · Zbl 1375.94156 · doi:10.1007/978-3-662-47989-6_37
[56] Rivain, M., Prouff, E.: Provably secure higher-order masking of AES. In: Mangard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol. 6225, pp. 413–427. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-15031-9_28 · Zbl 1321.94087 · doi:10.1007/978-3-642-15031-9_28
[57] Schneider, T., Moradi, A.: Leakage assessment methodology. In: Güneysu, T., Handschuh, H. (eds.) CHES 2015. LNCS, vol. 9293, pp. 495–513. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-48324-4_25 · Zbl 1380.68171 · doi:10.1007/978-3-662-48324-4_25
[58] Standaert, F.-X., Archambeau, C.: Using subspace-based template attacks to compare and combine power and electromagnetic information leakages. In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 411–425. Springer, Heidelberg (2008). doi: 10.1007/978-3-540-85053-3_26 · Zbl 05488444 · doi:10.1007/978-3-540-85053-3_26
[59] Standaert, F.-X., Malkin, T.G., Yung, M.: A unified framework for the analysis of side-channel key recovery attacks. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 443–461. Springer, Heidelberg (2009). doi: 10.1007/978-3-642-01001-9_26 · Zbl 1239.94066 · doi:10.1007/978-3-642-01001-9_26
[60] Standaert, F.-X., Veyrat-Charvillon, N., Oswald, E., Gierlichs, B., Medwed, M., Kasper, M., Mangard, S.: The world is not enough: another look on second-order DPA. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 112–129. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-17373-8_7 · Zbl 1290.94132 · doi:10.1007/978-3-642-17373-8_7
[61] Tiri, K., Verbauwhede, I.: Securing encryption algorithms against DPA at the logic level: next generation smart card technology. In: Walter, C.D., Koç, Ç.K., Paar, C. (eds.) CHES 2003. LNCS, vol. 2779, pp. 125–136. Springer, Heidelberg (2003). doi: 10.1007/978-3-540-45238-6_11 · Zbl 05679226 · doi:10.1007/978-3-540-45238-6_11
[62] Ullrich, M., de Cannière, C., Indesteege, S., Küçük, Ö., Mouha, N., Preneel, B.: Finding optimal bitsliced implementations of 4 \[ \times \] 4-bit S-boxes. In: Symmetric Key Encryption Workshop 2011 (2011)
[63] Waddle, J., Wagner, D.: Towards efficient second-order power analysis. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 1–15. Springer, Heidelberg (2004). doi: 10.1007/978-3-540-28632-5_1 · Zbl 1104.68499 · doi:10.1007/978-3-540-28632-5_1
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.