Skip to main content

2015 | OriginalPaper | Buchkapitel

LS-Designs: Bitslice Encryption for Efficient Masked Software Implementations

verfasst von : Vincent Grosso, Gaëtan Leurent, François-Xavier Standaert, Kerem Varıcı

Erschienen in: Fast Software Encryption

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Side-channel analysis is an important issue for the security of embedded cryptographic devices, and masking is one of the most investigated solutions to mitigate such attacks. In this context, efficient masking has recently been considered as a possible criteria for new block cipher designs. Previous proposals in this direction were applicable to different types of masking schemes (e.g. Boolean and polynomial). In this paper, we study possible optimizations when specializing the designs to Boolean masking. For this purpose, we first observe that bitslice ciphers have interesting properties for improving both the efficiency and the regularity of masked software implementations. Next we specify a family of block ciphers (denoted as LS-designs) that can systematically take advantage of bitslicing in a principled manner. Eventually, we evaluate both the security and performance of such designs and two of their instances, confirming excellent properties for physically secure applications.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
Motivated by the recent results in [51], showing that non-bijective S-boxes lead to easily exploitable targets for generic (non-profiled) Differential Power Analysis.
 
2
Masking non-linear look-up tables has a cost that is quadratic in this number [11].
 
3
LED and PRESENT have the same number of non-linear gates, but encrypt only 64-bit. So we do not expect them to bring improvements in our masked setting.
 
4
This can be reduced to seven table look-ups for Robin, thanks to the L-box structure.
 
5
At the time of writing we haven’t had access to an AVX2-enabled CPU yet, and the 256-bit version of pshufb is not available in the first version of AVX.
 
Literatur
1.
Zurück zum Zitat Barreto, P., Rijmen, V.: The KHAZAD legacy-level block cipher. Primitive submitted to NESSIE, 4 (2000) Barreto, P., Rijmen, V.: The KHAZAD legacy-level block cipher. Primitive submitted to NESSIE, 4 (2000)
2.
3.
Zurück zum Zitat Biham, E.: FSE1997. LNCS, vol. 1267. Springer, Heidelberg (1997) Biham, E.: FSE1997. LNCS, vol. 1267. Springer, Heidelberg (1997)
4.
Zurück zum Zitat Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 2–21. Springer, Heidelberg (1991) Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 2–21. Springer, Heidelberg (1991)
5.
Zurück zum Zitat Bilgin, B., Bogdanov, A., Knezevic, M., Mendel, F., Wang, Q.: Fides: lightweight authenticated cipher with side-channel resistance for constrained hardware. [2], pp. 142–158 Bilgin, B., Bogdanov, A., Knezevic, M., Mendel, F., Wang, Q.: Fides: lightweight authenticated cipher with side-channel resistance for constrained hardware. [2], pp. 142–158
6.
Zurück zum Zitat Biryukov, A., Wagner, D.: Slide Attacks. [32], pp. 245–259 Biryukov, A., Wagner, D.: Slide Attacks. [32], pp. 245–259
7.
Zurück zum Zitat Bogdanov, A.A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M., Seurin, Y., Vikkelsoe, C.: PRESENT: an ultra-lightweight block cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450–466. Springer, Heidelberg (2007) CrossRef Bogdanov, A.A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M., Seurin, Y., Vikkelsoe, C.: PRESENT: an ultra-lightweight block cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450–466. Springer, Heidelberg (2007) CrossRef
8.
Zurück zum Zitat Boura, C., Canteaut, A., De Cannière, C.: Higher-order differential properties of Keccak and Luffa. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 252–269. Springer, Heidelberg (2011) CrossRef Boura, C., Canteaut, A., De Cannière, C.: Higher-order differential properties of Keccak and Luffa. In: Joux, A. (ed.) FSE 2011. LNCS, vol. 6733, pp. 252–269. Springer, Heidelberg (2011) CrossRef
9.
Zurück zum Zitat Boyar, J., Peralta, R.: A new combinational logic minimization technique with applications to cryptology. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 178–189. Springer, Heidelberg (2010) CrossRef Boyar, J., Peralta, R.: A new combinational logic minimization technique with applications to cryptology. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 178–189. Springer, Heidelberg (2010) CrossRef
10.
Zurück zum Zitat Cid, C., Murphy, S., Robshaw, M.: Small scale variants of the AES. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 145–162. Springer, Heidelberg (2005) CrossRef Cid, C., Murphy, S., Robshaw, M.: Small scale variants of the AES. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 145–162. Springer, Heidelberg (2005) CrossRef
12.
Zurück zum Zitat Daemen, J.: Limitations of the Even-Mansour construction. [25], pp. 495–498 Daemen, J.: Limitations of the Even-Mansour construction. [25], pp. 495–498
13.
Zurück zum Zitat Daemen, J., Knudsen, L.R., Rijmen, V.: The block cipher SQUARE. [3], pp. 149–165 Daemen, J., Knudsen, L.R., Rijmen, V.: The block cipher SQUARE. [3], pp. 149–165
14.
Zurück zum Zitat Daemen, J., Peeters, M., Van Assche, G.: Bitslice ciphers and power analysis attacks. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, p. 134. Springer, Heidelberg (2001) CrossRef Daemen, J., Peeters, M., Van Assche, G.: Bitslice ciphers and power analysis attacks. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, p. 134. Springer, Heidelberg (2001) CrossRef
16.
Zurück zum Zitat Daemen, J., Rijmen, V.: The wide trail design strategy. In: Honary, B. (ed.) Cryptography and Coding 2001. LNCS, vol. 2260, p. 222. Springer, Heidelberg (2001) CrossRef Daemen, J., Rijmen, V.: The wide trail design strategy. In: Honary, B. (ed.) Cryptography and Coding 2001. LNCS, vol. 2260, p. 222. Springer, Heidelberg (2001) CrossRef
17.
Zurück zum Zitat Dinur, I., Dunkelman, O., Keller, N., Shamir, A.: Key recovery attacks on 3-round Even-Mansour, 8-step LED-128, and full \(\text{ AES }^{2}\). Cryptology ePrint Archive, Report 2013/391 (2013). http://eprint.iacr.org/2013/391 Dinur, I., Dunkelman, O., Keller, N., Shamir, A.: Key recovery attacks on 3-round Even-Mansour, 8-step LED-128, and full \(\text{ AES }^{2}\). Cryptology ePrint Archive, Report 2013/391 (2013). http://​eprint.​iacr.​org/​2013/​391
18.
Zurück zum Zitat Dunkelman, O., Keller, N., Shamir, A.: Minimalism in cryptography: the Even-Mansour scheme revisited. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 336–354. Springer, Heidelberg (2012) CrossRef Dunkelman, O., Keller, N., Shamir, A.: Minimalism in cryptography: the Even-Mansour scheme revisited. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 336–354. Springer, Heidelberg (2012) CrossRef
19.
Zurück zum Zitat Even, S., Mansour, Y.: A construction of a cipher from a single pseudorandom permutation. [25], pp. 210–224 Even, S., Mansour, Y.: A construction of a cipher from a single pseudorandom permutation. [25], pp. 210–224
20.
Zurück zum Zitat Gérard, B., Grosso, V., Naya-Plasencia, M., Standaert, F.X.: Block ciphers that are easier to mask: how far can we go? [2], pp. 383–399 Gérard, B., Grosso, V., Naya-Plasencia, M., Standaert, F.X.: Block ciphers that are easier to mask: how far can we go? [2], pp. 383–399
22.
Zurück zum Zitat Grosso, V., Standaert, F.X., Faust, S.: Masking vs. multiparty computation: how large is the gap for AES? [2], pp. 400–416 Grosso, V., Standaert, F.X., Faust, S.: Masking vs. multiparty computation: how large is the gap for AES? [2], pp. 400–416
24.
Zurück zum Zitat Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)CrossRef Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100–107 (1968)CrossRef
25.
Zurück zum Zitat Imai, H., Rivest, R.L., Matsumoto, T.: ASIACRYPT 1991. LNCS, vol. 739. Springer, Heidelberg (1993) MATH Imai, H., Rivest, R.L., Matsumoto, T.: ASIACRYPT 1991. LNCS, vol. 739. Springer, Heidelberg (1993) MATH
26.
Zurück zum Zitat 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) CrossRef 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) CrossRef
27.
Zurück zum Zitat Isobe, T., Shibutani, K.: Security analysis of the lightweight block ciphers XTEA, LED and Piccolo. In: Susilo, W., Mu, Y., Seberry, J. (eds.) ACISP 2012. LNCS, vol. 7372, pp. 71–86. Springer, Heidelberg (2012) CrossRef Isobe, T., Shibutani, K.: Security analysis of the lightweight block ciphers XTEA, LED and Piccolo. In: Susilo, W., Mu, Y., Seberry, J. (eds.) ACISP 2012. LNCS, vol. 7372, pp. 71–86. Springer, Heidelberg (2012) CrossRef
28.
Zurück zum Zitat Käsper, E., Schwabe, P.: Faster and timing-attack resistant AES-GCM. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 1–17. Springer, Heidelberg (2009) CrossRef Käsper, E., Schwabe, P.: Faster and timing-attack resistant AES-GCM. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 1–17. Springer, Heidelberg (2009) CrossRef
29.
Zurück zum Zitat Kerckhof, S., Durvaux, F., Hocquet, C., Bol, D., Standaert, F.-X.: Towards green cryptography: a comparison of lightweight ciphers from the energy viewpoint. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol. 7428, pp. 390–407. Springer, Heidelberg (2012) CrossRef Kerckhof, S., Durvaux, F., Hocquet, C., Bol, D., Standaert, F.-X.: Towards green cryptography: a comparison of lightweight ciphers from the energy viewpoint. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol. 7428, pp. 390–407. Springer, Heidelberg (2012) CrossRef
30.
Zurück zum Zitat Khovratovich, D., Nikolić, I.: Rotational cryptanalysis of ARX. In: Hong, S., Iwata, T. (eds.) FSE 2010. LNCS, vol. 6147, pp. 333–346. Springer, Heidelberg (2010) CrossRef Khovratovich, D., Nikolić, I.: Rotational cryptanalysis of ARX. In: Hong, S., Iwata, T. (eds.) FSE 2010. LNCS, vol. 6147, pp. 333–346. Springer, Heidelberg (2010) CrossRef
31.
Zurück zum Zitat Kim, H., Hong, S., Lim, J.: A fast and provably secure higher-order masking of AES S-Box. [42], pp. 95–107 Kim, H., Hong, S., Lim, J.: A fast and provably secure higher-order masking of AES S-Box. [42], pp. 95–107
32.
Zurück zum Zitat Knudsen, L.: FSE 1999. LNCS, vol. 1636. Springer, Heidelberg (1999) Knudsen, L.: FSE 1999. LNCS, vol. 1636. Springer, Heidelberg (1999)
33.
Zurück zum Zitat Kwon, D., et al.: Information security and cryptology - ICISC 2003. In: Lim, J.-I., Lee, D.-H. (eds.) ARIA. LNCS, vol. 2971, pp. 432–445. Springer, Heidelberg (2004) Kwon, D., et al.: Information security and cryptology - ICISC 2003. In: Lim, J.-I., Lee, D.-H. (eds.) ARIA. LNCS, vol. 2971, pp. 432–445. Springer, Heidelberg (2004)
34.
Zurück zum Zitat Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994) CrossRef Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994) CrossRef
35.
Zurück zum Zitat Matsui, M.: On correlation between the order of S-boxes and the strength of DES. [46], pp. 366–375 Matsui, M.: On correlation between the order of S-boxes and the strength of DES. [46], pp. 366–375
36.
Zurück zum Zitat Matsui, M.: New block encryption algorithm MISTY. [3], pp. 54–68 Matsui, M.: New block encryption algorithm MISTY. [3], pp. 54–68
37.
Zurück zum Zitat Mendel, F., Rijmen, V., Toz, D., Varıcı, K.: Differential analysis of the LED block cipher. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 190–207. Springer, Heidelberg (2012) CrossRef Mendel, F., Rijmen, V., Toz, D., Varıcı, K.: Differential analysis of the LED block cipher. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 190–207. Springer, Heidelberg (2012) CrossRef
38.
Zurück zum Zitat Nikolić, I., Wang, L., Wu, S.: Cryptanalysis of round-reduced LED. In: Moriai, S. (ed.) FSE 2013. LNCS, vol. 8424, pp. 112–130. Springer, Heidelberg (2014) CrossRef Nikolić, I., Wang, L., Wu, S.: Cryptanalysis of round-reduced LED. In: Moriai, S. (ed.) FSE 2013. LNCS, vol. 8424, pp. 112–130. Springer, Heidelberg (2014) CrossRef
39.
Zurück zum Zitat 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)CrossRefMATH 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)CrossRefMATH
40.
Zurück zum Zitat Nyberg, K.: Linear approximation of block ciphers. [46], pp. 439–444 Nyberg, K.: Linear approximation of block ciphers. [46], pp. 439–444
41.
Zurück zum Zitat Piret, G., Roche, T., Carlet, C.: PICARO – a block cipher allowing efficient higher-order side-channel resistance. In: Bao, F., Samarati, P., Zhou, J. (eds.) ACNS 2012. LNCS, vol. 7341, pp. 311–328. Springer, Heidelberg (2012) CrossRef Piret, G., Roche, T., Carlet, C.: PICARO – a block cipher allowing efficient higher-order side-channel resistance. In: Bao, F., Samarati, P., Zhou, J. (eds.) ACNS 2012. LNCS, vol. 7341, pp. 311–328. Springer, Heidelberg (2012) CrossRef
42.
43.
Zurück zum Zitat Prouff, E., Roche, T.: Higher-order glitches free implementation of the AES using secure multi-party computation protocols. [42], pp. 63–78 Prouff, E., Roche, T.: Higher-order glitches free implementation of the AES using secure multi-party computation protocols. [42], pp. 63–78
45.
Zurück zum Zitat 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) CrossRef 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) CrossRef
46.
Zurück zum Zitat De Santis, A.: EUROCRYPT 1994. LNCS, vol. 950. Springer, Heidelberg (1995) MATH De Santis, A.: EUROCRYPT 1994. LNCS, vol. 950. Springer, Heidelberg (1995) MATH
47.
Zurück zum Zitat Toffoli, T.: Reversible computing. In: de Bakker, J., van Leeuwen, J. (eds.) Automata, Languages and Programming. LNCS, vol. 85, pp. 632–644. Springer, Heidelberg (1980) CrossRef Toffoli, T.: Reversible computing. In: de Bakker, J., van Leeuwen, J. (eds.) Automata, Languages and Programming. LNCS, vol. 85, pp. 632–644. Springer, Heidelberg (1980) CrossRef
48.
Zurück zum Zitat Ullrich, M., Cannière, C.D., Indesteege, S., Küçük, Ö., Mouha, N., Preneel, B.: Finding optimal bitsliced implementations of \(4\times 4\)-bit S-boxes. Symmetric Key Encryption Workshop, p. 20. Copenhagen, DK (2011) Ullrich, M., Cannière, C.D., Indesteege, S., Küçük, Ö., Mouha, N., Preneel, B.: Finding optimal bitsliced implementations of \(4\times 4\)-bit S-boxes. Symmetric Key Encryption Workshop, p. 20. Copenhagen, DK (2011)
49.
Zurück zum Zitat Veyrat-Charvillon, N., Gérard, B., Standaert, F.-X.: Security evaluations beyond computing power. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 126–141. Springer, Heidelberg (2013) CrossRef Veyrat-Charvillon, N., Gérard, B., Standaert, F.-X.: Security evaluations beyond computing power. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 126–141. Springer, Heidelberg (2013) CrossRef
50.
Zurück zum Zitat Wagner, D.: The boomerang attack. [42], pp. 156–170 Wagner, D.: The boomerang attack. [42], pp. 156–170
51.
Zurück zum Zitat Whitnall, C., Oswald, E., Standaert, F.-X.: The myth of generic DPA..and the magic of learning. In: Benaloh, J. (ed.) CT-RSA 2014. LNCS, vol. 8366, pp. 183–205. Springer, Heidelberg (2014) CrossRef Whitnall, C., Oswald, E., Standaert, F.-X.: The myth of generic DPA..and the magic of learning. In: Benaloh, J. (ed.) CT-RSA 2014. LNCS, vol. 8366, pp. 183–205. Springer, Heidelberg (2014) CrossRef
Metadaten
Titel
LS-Designs: Bitslice Encryption for Efficient Masked Software Implementations
verfasst von
Vincent Grosso
Gaëtan Leurent
François-Xavier Standaert
Kerem Varıcı
Copyright-Jahr
2015
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-662-46706-0_2