Abstract
Converting a Boolean mask to an arithmetic mask, and vice versa, is often required in implementing side-channel-resistant instances of cryptographic algorithms that mix Boolean and arithmetic operations. In this paper, we describe a method for converting a Boolean mask to an arithmetic mask that runs in constant time for a fixed order and has quadratic complexity as the security order increases, a significant improvement in previous work that has exponential complexity. We propose explicit algorithms for a second-order secure Boolean-to-arithmetic mask conversion that uses 31 instructions and for a third-order secure mask conversion that uses 74 instructions. We show that our second-order secure algorithm is at least an order of magnitude faster and our third-order secure algorithm is more than twice as fast as other algorithms in the literature.
Similar content being viewed by others
References
Agrawal, D., Archambeault, B., Rao, J.R., Rohatgi, P.: The EM side-channel(s). In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2003, Volume 2532 of LNCS, pp. 29–45. Springer, Heidelberg (2003)
Aumasson, J.-P., Henzen, L., Meier, W., C.-W. Phan, R.: SHA-3 Proposal BLAKE. https://131002.net/blake (2010) . Accessed May 2018
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, Volume 8968 of LNCS, pp. 64–81. Springer, Heidelberg (2014)
Barthe, G., Belaïd, S., Dupressoir, F., Fouque, P.-A., Grégoire, B., Strub, P.-Y., Zucchini, R.: Strong non-interference and type-directed higher-order masking. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM Conference on Computer and Communications Security 2016, pp. 116–129. Springer, Heidelberg (2016)
Bernstein, D. J.: Chacha, a variant of salsa20 (2008)
Coron, J.-S., Großschädl, J., Tibouchi, M., Vadnala, P.K.: Conversion from arithmetic to Boolean masking with logarithmic complexity. In: Leander, G. (ed.) FSE 2015, Volume 8731 of LNCS, pp. 130–149. Springer, Heidelberg (2015)
Coron, J.-S., Großschädl, J., Vadnala, P.K.: Secure Conversion between Boolean and Arithmetic Masking of Any Order. In: Batina, L., Robshaw, M. (eds.) CHES 2014, Volume 8731 of LNCS, pp. 188–205. Springer, Heidelberg (2014)
Coron, J.-S.: Higher-order conversion from Boolean to arithmetic masking. IACR Cryptol. ePrint Arch. 2017, 252 (2017)
Ferguson, N., Lucks, S., Schneier, B., Whiting, D., Bellare, M., Kohno, T., Callas, J., Walker, J.: The skein hash function family. http://www.skein-hash.info (2010). Accessed May 2018
Gandolfi, K., Mourtel, C., Olivier, F.: Electromagnetic analysis: concrete results. In: Koç, C.K., Naccache, D., Paar, C. (eds.) CHES 2001, Volume 2162 of LNCS, pp. 251–261. Springer, Heidelberg (2001)
Golić, J.D.: Techniques for random masking in hardware. IEEE Trans. Circuits Syst. 54(2), 291–300 (2007)
Goubin, L.: A sound method for switching between Boolean and arithmetic masking. In: Koç, C.K., Naccache, D., Paar, C. (eds.) CHES 2001, Volume 2162 of LNCS, pp. 3–15. Springer, Heidelberg (2001)
Hutter, M., Tunstall, M.: Constant time higher-order Boolean-to-arithmetic masking. Cryptol. ePrint Arch. Rep. 2016/1023/20161222:183711. https://eprint.iacr.org/2016/1023/20161222:183711 (2016). Accessed May 2018
Ishai, Y., Sahai, A., Wagner, D.: Private circuits: securing hardware against probing attacks. In: Boneh, D. (ed.) CRYPTO 2003, Volume 2729 of LNCS, pp. 463–481. Springer, Heidelberg (2003)
Karroumi, M., Richard, B., Joye, M.: Addition with blinded operands. In: Prouff, E. (ed.) COSADE 2014, Volume 8622 of LNCS, pp. 41–55. Springer, Heidelberg (2014)
Kocher, P., Jaffe, J., Jun, B.: Differential power analysis. In: Wiener, M.J. (ed.) CRYPTO ’99, Volume 1666 of LNCS, pp. 388–397. Springer, Heidelberg (1999)
Lai, X., Massey, J.L.: A proposal for a new block encryption standard. In: Damgård, I. (ed.) Workshop on the Theory and Application of Cryptographic Techniques, Volume 473 of LNCS, pp. 389–404. Springer, Heidelberg (1990)
Leiserson, A.J., Marson, M.E., Wachs, M.A.: Gate-level masking under a path-based leakage metric. In: Batina, L., Robshaw, M. (eds.) CHES 2014, Volume 8731 of LNCS, pp. 580–597. Springer, Heidelberg (2014)
Mangard, S., Oswald, E., Popp, T.: Power Analysis Attacks—Revealing the Secrets of Smart Cards. Springer, New York (2007)
Mangard, S., Popp, T., Gammel, B.M.: Side-channel leakage of masked CMOS gates. In: Menezes, A. (ed.) CT-RSA 2005, Volume 3376 of LNCS, pp. 351–365. Springer, Heidelberg (2005)
Marsaglia, G.: Xorshift RNGs. J. Stat. Softw. 8(14), 1–6 (2003)
National Institute of Standards and Technology (NIST). FIPS-180-4: Secure Hash Standard. http://csrc.nist.gov/publications/fips/fips180-4 (2015). Accessed May 2018
Nikova, S., Rechberger, C., Rijmen, V.: Threshold implementations against side-channel attacks and glitches. In: Ning, P., Qing, S., Li, N. (eds.) ICICS 2006, Volume 4307 of LNCS, pp. 529–545. Springer, Heidelberg (2006)
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)
Quisquater, J.-J., Samyde, D.: Electromagnetic analysis (EMA): measures and counter-measures for smart cards. In: Attali, I., Jensen, T.P. (eds.) E-smart 2001, Volume 2140 of LNCS, pp. 200–210. Springer, Heidelberg (2001)
Rivain, M., Dottax, E., Prouff, E.: Block ciphers implementations provably secure against second order side channel analysis. In: Nyberg, K. (ed.) FSE 2008, Volume 5086 of LNCS, pp. 127–143. Springer, Heidelberg (2008)
Rivest, R.L., Robshaw, M.J.B., Sidney, R., Yin, Y.L.: The RC6 Block Cipher. http://people.csail.mit.edu/rivest/pubs/RRSY98.pdf (1998). Accessed May 2018
Schneider, T., Moradi, A., Güneysu, T.: Arithmetic addition over Boolean masking-towards first- and second-order resistance in hardware. In: Malkin, T., Kolesnikov, V., Lewko, A.B., Polychronakis, M. (eds.) ACNS 2015, Volume 9092 of LNCS, pp. 559–578. Springer, Heidelberg (2015)
Trichina, E.: Combinational logic design for AES subbyte transformation on masked data. IACR Cryptol. ePrint Arch. 2003, 236 (2003)
Vadnala, P.K., Großschädl, J.: Algorithms for switching between boolean and arithmetic masking of second order. In: Gierlichs, B., Guilley, S., Mukhopadhyay, D. (eds.) SPACE 2013, Volume 8204 of LNCS, pp. 95–110. Springer, Heidelberg (2013)
Vadnala, P.K., Großschädl, J.: Faster mask conversion with lookup tables. In: Mangard, S., Poschmann, A.Y. (eds.) COSADE 2015, Volume 9064 of LNCS, pp. 207–221. Springer, Heidelberg (2015)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hutter, M., Tunstall, M. Constant-time higher-order Boolean-to-arithmetic masking. J Cryptogr Eng 9, 173–184 (2019). https://doi.org/10.1007/s13389-018-0191-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13389-018-0191-z