Sparkle

News

• 2020-06-23: Sparkle paper appeared in IACR Transactions on Symmetric Cryptology (ToSC) Special Issue on Designs for the NIST Lightweight Standardisation Process [1]
• 2020-06-22: The paper on Alzette (i.e., the ARX-box of Sparkle) is accepted at CRYPTO [2] ePrint
• 2019-10-11: New faster implementations of SPARKLE256 and SPARKLE384 for ARMv7M: Sparkle-ARMv7M.zip
• 2019-08-30: Version v1.1 is announced as a Round 2 Candidate of the NIST lightweight cryptography standardization process!
• 2019-07-24: New ARMv7M assembler implementation of the Sparkle permutations with roughly three times better performance than the previous version: Sparkle-ARMv7M.zip
• 2019-04-23: Supporting analysis code is now available
• 2019-04-20: There is a typo on page 73 of the v1.0 specification: Table 5.2 compares the performance of Esch256 to other hash functions, not Esch384.
• 2019-04-18: Version v1.0 is announced as a Round 1 Candidate of the NIST lightweight cryptography standardization process

Overview

What Is Sparkle?

It is a family of cryptographic permutations based on an ARX design. It is designed by Christof Beierle, Alex Biryukov, Luan Cardoso dos Santos, Johann Großschädl, Léo Perrin, Aleksei Udovenko, Vesselin Velichkov, and Qingju Wang. Its name comes from the block cipher Sparx, which Sparkle is closely related to. Sparkle can basically be understood as a Sparx instance with a wider block size and a fixed key, hence its name: SPARx, but Key LEss.

We provide three versions corresponding to three block sizes, namely Sparkle256, Sparkle384, and Sparkle512. Unlike most ARX constructions, we provide security guarantees with regard to differential and linear cryptanalysis thanks to the long trail strategy (LTS). The particular structure it imposes is also convenient to investigate other attacks (integral, impossible differential, etc.) and thus to argue about the security of our algorithms against them. The LTS is a strategy which was first used to design the lightweight block cipher Sparx, presented at ASIACRYPT 2016. Several independent research teams have already analyzed this algorithm and their results have bolstered our confidence in this design approach.

What Are Esch and Schwaemm?

Both are cryptographic algorithms that were designed to be lightweight in software (i.e., to have small code size and low RAM footprint) and still reach high performance on a wide range of 8, 16, and 32-bit microcontrollers. Esch and Schwaemm can also be well optimized to achieve small silicon area and low power consumption when implemented in hardware. Our schemes are built from well-understood principles, i.e., the sponge (resp. duplex-sponge) construction based on the Sparkle permutation family.

More precisely, Esch is a family of cryptographic hash functions. The name stands for Efficient, Sponge-based, and Cheap Hashing. It is also the part of the name of a small town in southern Luxembourg, which is close to the campus of the University of Luxembourg. Esch employs the Sparkle permutation family in a sponge.

Schwaemm is a family of ciphers for authenticated encrytption with associated data. The name stands for Sponge-based Cipher for Hardened but Weightless Authenticated Encryption on Many Microcontrollers. It is also the Luxembourgish word for "sponges". Schwaemm employs the Sparkle permutation family in the Beetle mode of operation (which is based on a duplexed sponge).

What is Their Efficiency Based On?

• Small State Size.

Both Esch and Schwaemm are characterized by a relatively small state size, which is only 256 bits for the most lightweight instance of Schwaemm (achieving a security level of 120 bits) and 384 bits for the lightest variant of Esch. Having a small state is an important asset for lightweight cryptosystems for several reasons. First and foremost, the size of the state determines to a large extent the RAM consumption (in the case of software implementation) and the silicon area (when implemented in hardware) of a symmetric algorithm. Furthermore, software implementations for 8 and 16-bit microcontrollers with small register space (e.g., Atmel AVR or TI MSP430) can profit significantly from a small state size since it allows a large fraction of the state to reside in registers, which reduces the number of load and store operations. On 32-bit microcontrollers (e.g., ARM Cortex-M series) it is even possible to keep a full 256-bit state in registers, thereby eliminating almost all loads and stores. The ability to hold the whole state in registers does not only benefit execution time, but also provides some intrinsic protection against side-channel attacks.

• Extremely Lightweight Permutation.

The Sparkle permutation family is a classical ARX design and performs additions, rotations, and XOR operations on 32-bit words. Using a word-size of 32 bits enables high efficiency in software on 8, 16, and 32-bit platforms; smaller word-sizes (e.g., 16 bits) would compromise performance on 32-bit platforms, whereas 64-bit words are problematic for 8-bit microcontrollers. The rotation amounts have been carefully chosen to minimize the execution time and code size on microcontrollers that support only rotations by one bit at a time. An implementation of Sparkle for ARM microcontrollers can exploit their ability to combine an addition or XOR with a rotation into a single instruction with a latency of one clock cycle. On the other hand, a small-area hardware implementation can take advantage of the fact that only six arithmetic/logical operations need to be supported: 32-bit XOR, addition modulo 2^32, and rotations by 16, 17, 24, and 31 bits. A minimalist 32-bit Arithmetic/Logic Unit (ALU) for these six operations can be well optimized to achieve small silicon area and low power consumption.

• Consistency Across Security Levels.

Schwaemm and Esch were designed to be consistent across security levels, which facilitates a parameterized software implementation of the algorithms and the underlying permutation. All instances of Schwaemm and Esch can use a single implementation of Sparkle that is parameterized with respect to the block (i.e., state) size and the number of steps. Such a parameterized implementation reduces the software development effort significantly since only a single function for Sparkle needs to be implemented and tested.

• Even Higher Speed Through Parallelism.

The performance of Schwaemm and Esch on processor platforms with vector engines (e.g., ARM NEON, Intel SSE/AVX) can be significantly increased by taking advantage of the SIMD-level parallelism they provide, which is possible since all 32-bit words of the state perform the same operations in the same order. Hardware implementations can trade performance for silicon area by instantiating several 32-bit ALUs that work in parallel.

What is Their Security Based On?

• The Security of Sponges.

The security of our schemes is based on the security of the underlying cryptographic permutations and the security of sponge-based modes, more precisely the sponge-based hashing mode and the Beetle mode for authenticated encryption. The sponge-based approach has received a lot of attention as it the one used by the latest NIST-standardized hash function, SHA-3. We re-use this approach to leverage both its low memory footprint and the confidence cryptographers have gained for such components.

• The Literature on Block Cipher Design.

The design of the Sparkle family of permutations is based on the decades old SPN structure which allows us to decompose its analysis into two stages: first the study of its substitution layer, and, second, the study of its linear layer. The latter combines the Feistel structure, which has been used since the publication of the DES, and a linear permutation with a high branching number, like a vast number of SPNs such as the AES. To combine these two types of subcomponents, we rely on the design strategy that was used for the block cipher Sparx: the long trail strategy. Our substitution layer operates on 64-bit branches using ARX-based S-boxes, where ARX stands (modular) Addition, Rotation and XOR. The study of the differential and linear properties of modular addition in the context of block cipher can be traced back to the late 90's. The fact that the block size of the ARX component is limited to 64 bits means that it is possible to investigate it thoroughly using computer assisted methods. The simplicity and particular shape of the linear layer then allows us to deduce the properties of the full permutation from those of the 64-bit ARX-box.

• Components Tailored for their Use Cases.

When using a permutation in a mode of operation, two approaches are possible. We can use a hermetic approach, meaning that no distinguishers are known to exist against the permutation. This security then carries over directly to the whole function (e.g. to the whole hash function or AEAD scheme). The downside in this case is that this hermetic strategy requires an expensive permutation which, in the context of lightweight cryptography, may be too much.

At the opposite, we can use a permutation which, on its own, cannot provide the properties needed. The security is then provided by the coupling of the permutation and the mode of operation in which it is used. For example, the recently announced winner of the CAESAR competition ASCON and the third-round CAESAR candidate Ketje, both authenticated ciphers, use such an approach. The advantage in this case is a much higher efficiency as we need fewer rounds of the permutation. However, the security guarantees are a priori weaker in this case as it is harder to estimate the strength needed by the permutation.

For Sparkle (and thus for both Esch and Schwaemm) we use the latter approach: the permutation used has a number of rounds that may allow the existence of some distinguishers. However, using a novel application of the established long trail strategy, we are able to prove that our sponge-based algorithms are safe with regard to the most important attack vectors differential attacks and linear attacks with a comfortable security margin. We thus get the best of both worlds: we do not have the performance penalty of a hermetic approach but still obtain security guarantees similar to those of a hermetic design.

See also

Supporting analysis code is available at https://github.com/cryptolu/sparkle