Top

Designs, Codes and Cryptography

Published in:

09-03-2016

Improving the security and efficiency of block ciphers based on LS-designs

Authors: Anthony Journault, François-Xavier Standaert, Kerem Varici

Published in: Designs, Codes and Cryptography | Issue 1-2/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

LS-designs are a family of bitslice ciphers aiming at efficient masked implementations against side-channel analysis. This paper discusses their security against invariant subspace attacks, and describes an alternative family of eXtended LS-designs (XLS-designs), that enables additional options to prevent such attacks. LS- and XLS-designs provide a large family of ciphers from which efficient implementations can be obtained, possibly enhanced with countermeasures against physical attacks. We argue that they are interesting primitives in order to discuss the general question of “how simple can block ciphers be?”.

previous article A code-based group signature scheme

Available only for authorised users

As just mentioned, this attack can be applied by finding an invariant subspace for the linear layer as well, in which case the S-box layer will not change the subspace.

More precisely, three ANDs and one OR, which can be masked at the same cost.

Any S-box has (small dimensional) subspaces that gets mapped to subspaces.

For more constrained space, they could be computed as suggested in Sect. 3.1.

Albrecht M.R., Driessen B., Kavun, E.B., Leander G., Paar C., Yalçin T.: Proceedings on Block ciphers—focus on the linear layer (feat. PRIDE) Part I. In: Garay J.A., Gennaro R. (eds.) Advances in Cryptology—CRYPTO 2014—34th Annual Cryptology Conference, Santa Barbara, 17–21 Aug, 2014. Lecture Notes in Computer Science, vol. 8616, pp. 57–76. Springer, Berlin (2014).

Albrecht M.R., Rechberger C., Schneider T., Tiessen T., Zohner M. Ciphers for MPC and FHE. In: Oswald, E., Fischlin M (eds.): Proceedings on Advances in Cryptology—EUROCRYPT 2015—34th Annual International Conference on the Theory and Applications of Cryptographic Techniques Part I, Sofia, 26–30 Apr 2015, pp. 430–454. Lecture Notes in Computer Science, vol. 9056. Springer, Berlin (2015)

Augot D., Finiasz M.: Direct construction of recursive MDS diffusion layers using shortened BCH codes. In: Cid C., Rechberger C. (eds.): Fast Software Encryption-21st International Workshop, FSE 2014, 3–5 London, 2014, Revised Selected Papers, pp. 3–17. Lecture Notes in Computer Science, vol. 8540, Springer, Berlin (2015).

Biryukov A., De Cannière C.: Block ciphers and systems of quadratic equations. In: Johansson T. (ed.) Fast Software Encryption, 10th International Workshop, FSE 2003, Lund, 24–26 Feb, 2003, Revised Papers. Lecture Notes in Computer Science, vol. 2887, pp. 274–289. Springer, Berlin (2003).

Bogdanov A., Knudsen L.R., Leander G., Standaert F.-X., Steinberger, J.P., Tischhauser E.: Key-alternating ciphers in a provable setting: encryption using a small number of public permutations—(extended abstract). In: Pointcheval D., Johansson T. (eds.) Proceedings on Advances in Cryptology—EUROCRYPT 2012—31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, 15–19 Apr 2012. Lecture Notes in Computer Science, vol. 7237, pp. 45–62. Springer, Berlin (2012).

Boura C., Canteaut A.: Zero-sum distinguishers for iterated permutations and application to Keccak-f and Hamsi-256. In: Biryukov A., Gong G., Stinson D.R. (eds.) Selected Areas in Cryptography—17th International Workshop, SAC 2010, Waterloo, 12–13 Aug 2010, Revised Selected Papers. Lecture Notes in Computer Science, vol. 6544, pp. 1–17. Springer, Berlin (2010).

Boura C., Canteaut A. De Cannière C.: Higher-order differential properties of Keccak and Luffa. In: Joux A. (ed.) FSE. Lecture Notes in Computer Science, vol. 6733, pp. 252–269. Springer, Berlin (2011).

Chari S., Jutla C.S., Rao J.R., Rohatgi P.: Towards sound approaches to counteract power-analysis attacks. In: Wiener M.J. (ed.) Proceedings on Advances in Cryptology—CRYPTO ’99, 19th Annual International Cryptology Conference, Santa Barbara, 15–19 Aug 1999. Lecture Notes in Computer Science, vol. 1666, pp. 398–412. Springer, Berlin (1999).

Courtois N., Pieprzyk J.: Cryptanalysis of block ciphers with overdefined systems of equations. In: Zheng Y. (ed.) Proceedings on Advances in Cryptology—ASIACRYPT 2002, 8th International Conference on the Theory and Application of Cryptology and Information Security, Queenstown, 1–5 Dec 2002. Lecture Notes in Computer Science, vol. 2501, pp. 267–287. Springer, Berlin (2002).

10.

Daemen J., Rijmen V.: The wide trail design strategy. In: Honary B. (ed.) Proceedings on Cryptography and Coding, 8th IMA International Conference, Cirencester, 17–19 Dec 2001. Lecture Notes in Computer Science, vol. 2260, pp. 222–238. Springer, Berlin (2001).

11.

Daemen J., Rijmen V.: Information Security and Cryptography. The Design of Rijndael: AES—The Advanced Encryption Standard. Springer, Berlin (2002)

12.

Daemen J., Knudsen L.R., Rijmen V.: The block cipher Square. In: Biham E. (ed.) Proceedings on Fast Software Encryption, 4th International Workshop, FSE ’97, Haifa, 2–22 Jan 1997. Lecture Notes in Computer Science, vol. 1267, pp. 149–165. Springer, Berlin (1997).

13.

Daemen J., Peeters M., Van Assche G., Rijmen V.: Nessie proposal: the block cipher Noekeon. Nessie submission (2000). http://gro.noekeon.org/.

14.

Dinur I., Shamir A.: Cube attacks on tweakable black box polynomials. In: Joux A. (ed.) Proceedings on Advances in Cryptology—EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, 26–30 Apr 2009. Lecture Notes in Computer Science, vol. 5479, pp. 278–299, Springer, Berlin (2009).

15.

Galice S., Minier M.: Improving integral attacks against Rijndael-256 up to 9 rounds. In: Vaudenay S. (ed.) Proceedings on Progress in Cryptology—AFRICACRYPT 2008, First International Conference on Cryptology in Africa, Casablanca, 11–14 Jun 2008. Lecture Notes in Computer Science, vol. 5023, pp. 1–15. Springer, Berlin (2008).

16.

Gérard B., Grosso V., Naya-Plasencia M., Standaert, F.-X.: Block ciphers that are easier to mask: How far can we go? In: Bertoni G., Coron J.-S. (ed.) Proceedings on Cryptographic Hardware and Embedded Systems—CHES 2013—15th International Workshop, Santa Barbara, 20–23 Aug 2013. Lecture Notes in Computer Science, vol. 8086, pp. 383–399. Springer, Berlin (2013).

17.

Gilbert H., Peyrin T.: Super-sbox cryptanalysis: improved attacks for AES-like permutations. In: Hong S., Iwata T. (eds.) Fast Software Encryption, 17th International Workshop, FSE 2010, Seoul, 7–10 Feb 2010, Revised Selected Papers. Lecture Notes in Computer Science, vol. 6147, pp. 365–383. Springer, Berlin (2010).

18.

Grosso V., Leurent G., Standaert F.-X., Varici K.: LS-designs: Bitslice encryption for efficient masked software implementations. In: Cid C., Rechberger C. (eds.): Fast Software Encryption—21st International Workshop, FSE 2014, 3–5 London, 2014, Revised Selected Papers, pp. 18–37. Lecture Notes in Computer Science, vol. 8540, Springer, Berlin (2015).

19.

Guo J., Peyrin T., Poschmann A. Robshaw M.: The LED block cipher. In: Preneel B., Takagi T. (eds.) Proceedings on Cryptographic Hardware and Embedded Systems—CHES 2011—13th International Workshop, Nara, Sep 28–1 Oct 2011. Lecture Notes in Computer Science, vol. 6917, pp. 326–341. Springer, Berlin (2011).

20.

Knudsen L.R.: Truncated and higher order differentials. In: Preneel, B. (ed.) Proceedings on Fast Software Encryption: Second International Workshop, Leuven, 14–16 Dec 1994. Lecture Notes in Computer Science, vol. 1008, pp. 196–211. Springer, Berlin (1994).

21.

Knudsen L.R., Leander G., Poschmann A., Robshaw M.J.B.: Printcipher: a block cipher for ic-printing. In: Mangard S., Standaert F.-X. (eds.): Proceedings on Cryptographic Hardware and Embedded Systems, CHES 2010, 12th International Workshop, Santa Barbara, 17–20 Aug 2010, pp. 16–32. Lecture Notes in Computer Science, vol. 6225, Springer, Berin (2010).

22.

Knudsen L.R., Wagner D.: Integral cryptanalysis. In: Daemen J., Rijmen V. (eds.) Fast Software Encryption, 9th International Workshop, FSE 2002, Leuven, 4–6 Feb 2002, Revised Papers. Lecture Notes in Computer Science, vol. 2365, pp. 112–127. Springer, Berlin (2002).

23.

Leander G., Abdelraheem M.A., AlKhzaimi H., Zenner E.: A cryptanalysis of PRINTcipher: the invariant subspace attack. In: Rogaway P. (ed.) Proceedings on Advances in Cryptology—CRYPTO 2011—31st Annual Cryptology Conference, Santa Barbara, 14–18 Aug 2011. Lecture Notes in Computer Science, vol. 6841, pp. 206–221. Springer, Berlin (2011).

24.

Leander G., Minaud B, Rønjom S.: A generic approach to invariant subspace attacks cryptanalysis of Robin, iSCREAM and Zorro. To Appear in the Proceedings of EUROCRYPT 2015 (2015).

25.

Leander G., Minaud B., Rønjom S.: A generic approach to invariant subspace attacks: cryptanalysis of Robin, iSCREAM and zorro. In: swald, E., Fischlin M (eds.): Proceedings on Advances in Cryptology—EUROCRYPT 2015—34th Annual International Conference on the Theory and Applications of Cryptographic Techniques Part I, Sofia, 26–30 Apr 2015, pp. 254–283. Lecture Notes in Computer Science, vol. 9056, Springer, Berlin (2015).

26.

Minier M., Phan R.C.-W., Pousse B.: On integral distinguishers of Rijndael family of ciphers. Cryptologia 36(2), 104–118 (2012).

27.

Piret G., Roche T., Carlet C.: PICARO—a block cipher allowing efficient higher-order side-channel resistance—extended version-IACR Cryptology ePrint Archive 2012, 358 (2012)

28.

Rivain M., Prouff E.: Provably secure higher-order masking of AES. In: Mangard S., Standaert F.-X. (eds.): Proceedings on Cryptographic Hardware and Embedded Systems, CHES 2010, 12th International Workshop, Santa Barbara, 17–20 Aug 2010, pp. 413–427. Lecture Notes in Computer Science, vol. 6225, Springer, Berin (2010).

29.

Todo Y.: Structural evaluation by generalized integral property. In: Oswald, E., Fischlin M (eds.): Proceedings on Advances in Cryptology—EUROCRYPT 2015—34th Annual International Conference on the Theory and Applications of Cryptographic Techniques Part I, Sofia, 26–30 Apr 2015, pp. 287–314. Lecture Notes in Computer Science, vol. 9056, Springer, Berlin (2015).

30.

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: SKEW 2011 Symmetric Key Encryption Workshop, Copenhagen, pp. 16–17 (2011)

31.

Wagner D.: The boomerang attack. In: Lars R.K. (ed.) Proceedings on Fast Software Encryption, 6th International Workshop, FSE ’99, Rome, 24–26 Mar 1999. Lecture Notes in Computer Science, vol. 1636, pp. 156–170. Springer, Berlin (1999).

Title: Improving the security and efficiency of block ciphers based on LS-designs
Authors: Anthony Journault
François-Xavier Standaert
Kerem Varici
Publication date: 09-03-2016
Publisher: Springer US
Published in: Designs, Codes and Cryptography / Issue 1-2/2017
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-016-0193-8

Springer Professional

Improving the security and efficiency of block ciphers based on LS-designs

Abstract

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Other articles of this Issue 1-2/2017

Observing biases in the state: case studies with Trivium and Trivia-SC

Signature codes for noisy multiple access adder channel

Row reduction applied to decoding of rank-metric and subspace codes

Antiderivative functions over

Security proof of the canonical form of self-synchronizing stream ciphers

Cover-free codes and separating system codes

Premium Partner