Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Designs, Codes and Cryptography 1/2022

19-11-2021

SAND: an AND-RX Feistel lightweight block cipher supporting S-box-based security evaluations

Authors: Shiyao Chen, Yanhong Fan, Ling Sun, Yong Fu, Haibo Zhou, Yongqing Li, Meiqin Wang, Weijia Wang, Chun Guo

Published in: Designs, Codes and Cryptography | Issue 1/2022

Login to get access
share
SHARE

Abstract

We revisit designing AND-RX block ciphers, that is, the designs assembled with the most fundamental binary operations—AND, Rotation and XOR operations and do not rely on existing units. Likely, the most popular representative is the NSA cipher SIMON, which remains one of the most efficient designs, but suffers from difficulty in security evaluation. As our main contribution, we propose SAND, a new family of lightweight AND-RX block ciphers. To overcome the difficulty regarding security evaluation, SAND follows a novel design approach, the core idea of which is to restrain the AND-RX operations to be within nibbles. By this, SAND admits an equivalent representation based on a \(4\times 8\) synthetic S-box (SSb). This enables the use of classical S-box-based security evaluation approaches. Consequently, for all versions of SAND, (a) we evaluated security bounds with respect to differential and linear attacks, and in both single-key and related-key scenarios; (b) we also evaluated security against impossible differential and zero-correlation linear attacks. This better understanding of the security enables the use of a relatively simple key schedule, which makes the ASIC round-based hardware implementation of SAND to be one of the state-of-art Feistel lightweight ciphers. As to software performance, due to the natural bitslice structure, SAND reaches the same level of performance as SIMON and is among the most software-efficient block ciphers.
Appendix
Available only for authorised users
Footnotes
1
For more details, we refer to the main page https://​www.​cryptolux.​org/​index.​php/​Lightweight_​Cryptography, maintained by the CryptoLUX research group.
 
2
The diffusion test codes are available at https://​github.​com/​sand-bar/​SAND-Diffusion-Test.
 
3
The valid means that the entry of corresponding differential propagation pair is non-zero in DDT. Similarly, for the linear introduced later, it means that the entry of corresponding linear propagation mask pair is non-zero in LAT.
 
4
We provide our source codes in https://​github.​com/​sand-bar/​SAND-Trail-Search to serve more details of these searching models, which is based on [2, 38, 66].
 
5
Informally speaking, a secure shared gate satisfied the properties of correctness, non-completeness and uniformity [56, 57].
 
Literature
1.
go back to reference Andreeva E., Lallemand V., Purnal A., Reyhanitabar R., Roy A., Vizár D.: ForkAE v.1. In: Submission to Round 2 of the NIST Lightweight Cryptography Standardization process (2020) Andreeva E., Lallemand V., Purnal A., Reyhanitabar R., Roy A., Vizár D.: ForkAE v.1. In: Submission to Round 2 of the NIST Lightweight Cryptography Standardization process (2020)
2.
go back to reference Ankele R., Kölbl S.: Mind the gap—a closer look at the security of block ciphers against differential cryptanalysis. In: Selected Areas in Cryptography—SAC 2018—25th International Conference, Calgary, AB, Canada, 15–17 August 2018, Revised Selected Papers. pp. 163–190 (2018). https://​doi.​org/​10.​1007/​978-3-030-10970-7_​8. Ankele R., Kölbl S.: Mind the gap—a closer look at the security of block ciphers against differential cryptanalysis. In: Selected Areas in Cryptography—SAC 2018—25th International Conference, Calgary, AB, Canada, 15–17 August 2018, Revised Selected Papers. pp. 163–190 (2018). https://​doi.​org/​10.​1007/​978-3-030-10970-7_​8.
5.
go back to reference Banik S., Bogdanov A., Isobe T., Shibutani K., Hiwatari H., Akishita T., Regazzoni F.: Midori: A block cipher for low energy. In: Advances in Cryptology—ASIACRYPT 2015—21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, 29 November–December 3, 2015, Proceedings, Part II, pp. 411–436 (2015). https://​doi.​org/​10.​1007/​978-3-662-48800-3_​17. Banik S., Bogdanov A., Isobe T., Shibutani K., Hiwatari H., Akishita T., Regazzoni F.: Midori: A block cipher for low energy. In: Advances in Cryptology—ASIACRYPT 2015—21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, 29 November–December 3, 2015, Proceedings, Part II, pp. 411–436 (2015). https://​doi.​org/​10.​1007/​978-3-662-48800-3_​17.
6.
go back to reference Banik S., Pandey S.K., Peyrin T., Sasaki Y., Sim S.M., Todo Y.: GIFT: a small present—towards reaching the limit of lightweight encryption. In: Cryptographic Hardware and Embedded Systems—CHES 2017—19th International Conference, Taipei, Taiwan, 25–28 September 2017, Proceedings. pp. 321–345 (2017). https://​doi.​org/​10.​1007/​978-3-319-66787-4_​16. Banik S., Pandey S.K., Peyrin T., Sasaki Y., Sim S.M., Todo Y.: GIFT: a small present—towards reaching the limit of lightweight encryption. In: Cryptographic Hardware and Embedded Systems—CHES 2017—19th International Conference, Taipei, Taiwan, 25–28 September 2017, Proceedings. pp. 321–345 (2017). https://​doi.​org/​10.​1007/​978-3-319-66787-4_​16.
8.
go back to reference Banik S., Bogdanov A., Peyrin T., Sasaki Y., Sim S.M., Tischhauser E., Todo Y.: SUNDAE-GIFT v1.0. In: Submission to Round 2 of the NIST Lightweight Cryptography Standardization process (2020). Banik S., Bogdanov A., Peyrin T., Sasaki Y., Sim S.M., Tischhauser E., Todo Y.: SUNDAE-GIFT v1.0. In: Submission to Round 2 of the NIST Lightweight Cryptography Standardization process (2020).
9.
go back to reference Banik S., Chakraborti A., Iwata T., Minematsu K., Nandi M., Peyrin T., Sasaki Y., Sim S.M., Todo Y.: GIFT-COFB v1.0. In: Finalists of the NIST Lightweight Cryptography Standardization process (2021). Banik S., Chakraborti A., Iwata T., Minematsu K., Nandi M., Peyrin T., Sasaki Y., Sim S.M., Todo Y.: GIFT-COFB v1.0. In: Finalists of the NIST Lightweight Cryptography Standardization process (2021).
10.
go back to reference Bansod G., Patil A., Sutar S., Pisharoty N.: ANU: an ultra lightweight cipher design for security in IoT. Security Commun. Netw. 9(18), 5238–5251 (2016). CrossRef Bansod G., Patil A., Sutar S., Pisharoty N.: ANU: an ultra lightweight cipher design for security in IoT. Security Commun. Netw. 9(18), 5238–5251 (2016). CrossRef
11.
go back to reference Baysal A., Sahin S.: RoadRunneR: a small and fast bitslice block cipher for low cost 8-bit processors. In: Lightweight Cryptography for Security and Privacy—4th International Workshop, LightSec 2015, Bochum, Germany, 10–11 September 2015, Revised Selected Papers, pp. 58–76 (2015). https://​doi.​org/​10.​1007/​978-3-319-29078-2_​4. Baysal A., Sahin S.: RoadRunneR: a small and fast bitslice block cipher for low cost 8-bit processors. In: Lightweight Cryptography for Security and Privacy—4th International Workshop, LightSec 2015, Bochum, Germany, 10–11 September 2015, Revised Selected Papers, pp. 58–76 (2015). https://​doi.​org/​10.​1007/​978-3-319-29078-2_​4.
13.
go back to reference Beierle C., Jean J., Kölbl S., Leander G., Moradi A., Peyrin T., Sasaki Y., Sasdrich P., Sim S.M.: The SKINNY family of block ciphers and its low-latency variant MANTIS. In: Advances in Cryptology—CRYPTO 2016—36th Annual International Cryptology Conference, Santa Barbara, CA, USA, 14–18 August 2016, Proceedings, Part II, pp. 123–153 (2016). https://​doi.​org/​10.​1007/​978-3-662-53008-5_​5. Beierle C., Jean J., Kölbl S., Leander G., Moradi A., Peyrin T., Sasaki Y., Sasdrich P., Sim S.M.: The SKINNY family of block ciphers and its low-latency variant MANTIS. In: Advances in Cryptology—CRYPTO 2016—36th Annual International Cryptology Conference, Santa Barbara, CA, USA, 14–18 August 2016, Proceedings, Part II, pp. 123–153 (2016). https://​doi.​org/​10.​1007/​978-3-662-53008-5_​5.
15.
go back to reference Beierle C., JeanJ., Kölbl S., Leander G., Moradi A., Peyrin T., Sasaki Y., Sasdrich P., Sim S.M.: SKINNY-AEAD and SKINNY-Hash v1.1. In: Submission to Round 2 of the NIST Lightweight Cryptography Standardization process (2020). Beierle C., JeanJ., Kölbl S., Leander G., Moradi A., Peyrin T., Sasaki Y., Sasdrich P., Sim S.M.: SKINNY-AEAD and SKINNY-Hash v1.1. In: Submission to Round 2 of the NIST Lightweight Cryptography Standardization process (2020).
17.
go back to reference Berger T.P., Francq J., Minier M.: CUBE cipher: a family of quasi-involutive block ciphers easy to mask. In: Codes, Cryptology, and Information Security—First International Conference, C2SI 2015, Rabat, Morocco, 26–28 May 2015, Proceedings—In Honor of Thierry Berger, pp. 89–105 (2015). https://​doi.​org/​10.​1007/​978-3-319-18681-8_​8. Berger T.P., Francq J., Minier M.: CUBE cipher: a family of quasi-involutive block ciphers easy to mask. In: Codes, Cryptology, and Information Security—First International Conference, C2SI 2015, Rabat, Morocco, 26–28 May 2015, Proceedings—In Honor of Thierry Berger, pp. 89–105 (2015). https://​doi.​org/​10.​1007/​978-3-319-18681-8_​8.
18.
go back to reference Bertoni G., Daemen J., Peeters M., Van Assche G.: Keccak. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 313–314. Springer, New York (2013) Bertoni G., Daemen J., Peeters M., Van Assche G.: Keccak. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 313–314. Springer, New York (2013)
21.
go back to reference Biham E., Biryukov A., Shamir A.: Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials. In: Advances in Cryptology—EUROCRYPT ’99, International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, 2–6 May 1999, Proceeding, pp. 12–23 (1999). https://​doi.​org/​10.​1007/​3-540-48910-X_​2. Biham E., Biryukov A., Shamir A.: Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials. In: Advances in Cryptology—EUROCRYPT ’99, International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, 2–6 May 1999, Proceeding, pp. 12–23 (1999). https://​doi.​org/​10.​1007/​3-540-48910-X_​2.
23.
go back to reference Bogdanov A., Knudsen L.R., Leander G., Paar C., Poschmann A., Robshaw M.J.B., Seurin Y., Vikkelsoe C.: PRESENT: an ultra-lightweight block cipher. In: Cryptographic Hardware and Embedded Systems—CHES 2007, 9th International Workshop, Vienna, Austria, 10–13 September 2007, Proceedings, pp. 450–466 (2007). https://​doi.​org/​10.​1007/​978-3-540-74735-2_​31. Bogdanov A., Knudsen L.R., Leander G., Paar C., Poschmann A., Robshaw M.J.B., Seurin Y., Vikkelsoe C.: PRESENT: an ultra-lightweight block cipher. In: Cryptographic Hardware and Embedded Systems—CHES 2007, 9th International Workshop, Vienna, Austria, 10–13 September 2007, Proceedings, pp. 450–466 (2007). https://​doi.​org/​10.​1007/​978-3-540-74735-2_​31.
24.
go back to reference Borghoff J., Canteaut A., Güneysu T., Kavun E.B., Knezevic M., Knudsen L.R., Leander G., Nikov V., Paar C., Rechberger C., Rombouts P., Thomsen S.S., Yalçin T.: PRINCE—A low-latency block cipher for pervasive computing applications - extended abstract. In: Advances in Cryptology—ASIACRYPT 2012—18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, 2–6 December 2012, Proceedings. pp. 208–225 (2012). https://​doi.​org/​10.​1007/​978-3-642-34961-4_​14. Borghoff J., Canteaut A., Güneysu T., Kavun E.B., Knezevic M., Knudsen L.R., Leander G., Nikov V., Paar C., Rechberger C., Rombouts P., Thomsen S.S., Yalçin T.: PRINCE—A low-latency block cipher for pervasive computing applications - extended abstract. In: Advances in Cryptology—ASIACRYPT 2012—18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, 2–6 December 2012, Proceedings. pp. 208–225 (2012). https://​doi.​org/​10.​1007/​978-3-642-34961-4_​14.
25.
go back to reference Chakraborti A., Datta N., Jha A., Lopez C.M., Nandi M., Sasaki Y.: LOTUS-AEAD/LOCUS-AEAD. In: Submission to Round 2 of the NIST Lightweight Cryptography Standardization Process (2020). Chakraborti A., Datta N., Jha A., Lopez C.M., Nandi M., Sasaki Y.: LOTUS-AEAD/LOCUS-AEAD. In: Submission to Round 2 of the NIST Lightweight Cryptography Standardization Process (2020).
26.
go back to reference Chakraborti A., Datta N., Jha A., Nandi M.: HYENA. In: Submission to Round 2 of the NIST Lightweight Cryptography Standardization Process (2020). Chakraborti A., Datta N., Jha A., Nandi M.: HYENA. In: Submission to Round 2 of the NIST Lightweight Cryptography Standardization Process (2020).
28.
go back to reference Chen S., Fan Y., Fu Y., Huang L., Wang M.: On the design of ANT family block ciphers. J. Cryptol. Res. 6(6), 748–759 (2019). Chen S., Fan Y., Fu Y., Huang L., Wang M.: On the design of ANT family block ciphers. J. Cryptol. Res. 6(6), 748–759 (2019).
31.
go back to reference Daemen J., Peeters M., Van Assche G., Rijmen V.: Nessie proposal: NOEKEON. In: First Open NESSIE Workshop, pp. 213–230 (2000). Daemen J., Peeters M., Van Assche G., Rijmen V.: Nessie proposal: NOEKEON. In: First Open NESSIE Workshop, pp. 213–230 (2000).
33.
go back to reference Dinu D., Perrin L., Udovenko A., Velichkov V., Großschädl J., Biryukov A.: Design strategies for ARX with provable bounds: Sparx and LAX. In: Advances in Cryptology—ASIACRYPT 2016—22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 4–8 December 2016, Proceedings, Part I, pp. 484–513 (2016). https://​doi.​org/​10.​1007/​978-3-662-53887-6_​18. Dinu D., Perrin L., Udovenko A., Velichkov V., Großschädl J., Biryukov A.: Design strategies for ARX with provable bounds: Sparx and LAX. In: Advances in Cryptology—ASIACRYPT 2016—22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 4–8 December 2016, Proceedings, Part I, pp. 484–513 (2016). https://​doi.​org/​10.​1007/​978-3-662-53887-6_​18.
34.
go back to reference Dobraunig C., Eichlseder M., Mendel F., Schläffer M.: Ascon. Submission to the Caesar Competition. Institute for Applied Information Processing and Communications, Graz University of Technology, Graz (2014). Dobraunig C., Eichlseder M., Mendel F., Schläffer M.: Ascon. Submission to the Caesar Competition. Institute for Applied Information Processing and Communications, Graz University of Technology, Graz (2014).
39.
go back to reference Iwata T., Khairallah M., Minematsu K., Peyrin T.: Remus v1.0. In: Submission to Round 1 of the NIST Lightweight Cryptography Standardization Process (2019). Iwata T., Khairallah M., Minematsu K., Peyrin T.: Remus v1.0. In: Submission to Round 1 of the NIST Lightweight Cryptography Standardization Process (2019).
40.
go back to reference Iwata T., Khairallah M., Minematsu K., Peyrin T., Sasaki Y., Sim S.M., Sun L.: Thank Goodness Its Friday (TGIF). In: Submission to Round 1 of the NIST Lightweight Cryptography Standardization Process (2019). Iwata T., Khairallah M., Minematsu K., Peyrin T., Sasaki Y., Sim S.M., Sun L.: Thank Goodness Its Friday (TGIF). In: Submission to Round 1 of the NIST Lightweight Cryptography Standardization Process (2019).
41.
go back to reference Iwata T., Khairallah M., Minematsu K., Peyrin T.: Romulus v1.2. In: Finalists of the NIST Lightweight Cryptography Standardization Process (2021). Iwata T., Khairallah M., Minematsu K., Peyrin T.: Romulus v1.2. In: Finalists of the NIST Lightweight Cryptography Standardization Process (2021).
45.
go back to reference Knudsen L.R.: Deal—a 128-bit block cipher. In: NIST AES Proposal (1998). Knudsen L.R.: Deal—a 128-bit block cipher. In: NIST AES Proposal (1998).
55.
go back to reference Mouha N., Wang Q., Gu D., Preneel B.: Differential and linear cryptanalysis using mixed-integer linear programming. In: Information Security and Cryptology—7th International Conference, Inscrypt 2011, Beijing, China, 30 November–3 December 2011. Revised Selected Papers, pp. 57–76 (2011). https://​doi.​org/​10.​1007/​978-3-642-34704-7_​5. Mouha N., Wang Q., Gu D., Preneel B.: Differential and linear cryptanalysis using mixed-integer linear programming. In: Information Security and Cryptology—7th International Conference, Inscrypt 2011, Beijing, China, 30 November–3 December 2011. Revised Selected Papers, pp. 57–76 (2011). https://​doi.​org/​10.​1007/​978-3-642-34704-7_​5.
56.
go back to reference Nikova S., Rechberger C., Rijmen V.: Threshold implementations against side-channel attacks and glitches. In: Ning, P., Qing, S., Li, N. (eds.) Information and Communications Security, 8th International Conference, ICICS 2006, Raleigh, NC, USA, 4–7 December 2006, Proceedings. Lecture Notes in Computer Science, vol. 4307, pp. 529–545. Springer, Berlin (2006). https://​doi.​org/​10.​1007/​11935308_​38. Nikova S., Rechberger C., Rijmen V.: Threshold implementations against side-channel attacks and glitches. In: Ning, P., Qing, S., Li, N. (eds.) Information and Communications Security, 8th International Conference, ICICS 2006, Raleigh, NC, USA, 4–7 December 2006, Proceedings. Lecture Notes in Computer Science, vol. 4307, pp. 529–545. Springer, Berlin (2006). https://​doi.​org/​10.​1007/​11935308_​38.
59.
go back to reference Sakamoto K., Minematsu K., Shibata N., Shigeri M., Kubo H., Funabiki Y., Bogdanov A., Morioka S., Isobe T.: Tweakable TWINE: building a tweakable block cipher on generalized feistel structure. In: Advances in Information and Computer Security - 14th International Workshop on Security, IWSEC 2019, Tokyo, Japan, 28–30 August 2019, Proceedings, pp. 129–145 (2019). https://​doi.​org/​10.​1007/​978-3-030-26834-3_​8. Sakamoto K., Minematsu K., Shibata N., Shigeri M., Kubo H., Funabiki Y., Bogdanov A., Morioka S., Isobe T.: Tweakable TWINE: building a tweakable block cipher on generalized feistel structure. In: Advances in Information and Computer Security - 14th International Workshop on Security, IWSEC 2019, Tokyo, Japan, 28–30 August 2019, Proceedings, pp. 129–145 (2019). https://​doi.​org/​10.​1007/​978-3-030-26834-3_​8.
60.
go back to reference Sasaki Y.: Related-key boomerang attacks on full ANU lightweight block cipher. In: International Conference on Applied Cryptography and Network Security, pp. 421–439. Springer, Cham (2018). Sasaki Y.: Related-key boomerang attacks on full ANU lightweight block cipher. In: International Conference on Applied Cryptography and Network Security, pp. 421–439. Springer, Cham (2018).
61.
go back to reference Sasaki Y., Todo Y.: New impossible differential search tool from design and cryptanalysis aspects - revealing structural properties of several ciphers. In: Advances in Cryptology—EUROCRYPT 2017—36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, 30 April–4 May 2017, Proceedings, Part III, pp. 185–215 (2017). https://​doi.​org/​10.​1007/​978-3-319-56617-7_​7. Sasaki Y., Todo Y.: New impossible differential search tool from design and cryptanalysis aspects - revealing structural properties of several ciphers. In: Advances in Cryptology—EUROCRYPT 2017—36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, 30 April–4 May 2017, Proceedings, Part III, pp. 185–215 (2017). https://​doi.​org/​10.​1007/​978-3-319-56617-7_​7.
63.
67.
go back to reference Sun S., Hu L., Wang P., Qiao K., Ma X., Song L.: Automatic security evaluation and (related-key) differential characteristic search: application to simon, present, lblock, DES(L) and other bit-oriented block ciphers. In: Advances in Cryptology—ASIACRYPT 2014—20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., 7–11 December 2014, Proceedings, Part I, pp. 158–178 (2014). https://​doi.​org/​10.​1007/​978-3-662-45611-8_​9. Sun S., Hu L., Wang P., Qiao K., Ma X., Song L.: Automatic security evaluation and (related-key) differential characteristic search: application to simon, present, lblock, DES(L) and other bit-oriented block ciphers. In: Advances in Cryptology—ASIACRYPT 2014—20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., 7–11 December 2014, Proceedings, Part I, pp. 158–178 (2014). https://​doi.​org/​10.​1007/​978-3-662-45611-8_​9.
69.
73.
go back to reference Xiang Z., Zhang W., Bao Z., Lin D.: Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers. In: Advances in Cryptology—ASIACRYPT 2016—22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 4–8 December 2016, Proceedings, Part I, pp. 648–678 (2016). https://​doi.​org/​10.​1007/​978-3-662-53887-6_​24. Xiang Z., Zhang W., Bao Z., Lin D.: Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers. In: Advances in Cryptology—ASIACRYPT 2016—22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 4–8 December 2016, Proceedings, Part I, pp. 648–678 (2016). https://​doi.​org/​10.​1007/​978-3-662-53887-6_​24.
Metadata
Title
SAND: an AND-RX Feistel lightweight block cipher supporting S-box-based security evaluations
Authors
Shiyao Chen
Yanhong Fan
Ling Sun
Yong Fu
Haibo Zhou
Yongqing Li
Meiqin Wang
Weijia Wang
Chun Guo
Publication date
19-11-2021
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 1/2022
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-021-00970-9

Other articles of this Issue 1/2022

Designs, Codes and Cryptography 1/2022 Go to the issue

Premium Partner