Lightweight Permutation-Based Cryptography for the Ultra-Low-Power Internet of Things

in Bella, Giampaolo; Doinea, Mihai; Janicke, Helge (Eds.) Innovative Security Solutions for Information Technology and Communications, 15th International Conference, SECITC 2022, Virtual Event, December 8-9, 2022, Revised Selected Papers (2022, December)

The U.S. National Institute of Standards and Technology is currently undertaking a process to evaluate and eventually standardize one or more "lightweight" algorithms for authenticated encryption and ... [more ▼]

The U.S. National Institute of Standards and Technology is currently undertaking a process to evaluate and eventually standardize one or more "lightweight" algorithms for authenticated encryption and hashing that are suitable for resource-restricted devices. In addition to security, this process takes into account the efficiency of the candidate algorithms in various hardware environments (e.g. FPGAs, ASICs) and software platforms (e.g. 8, 16, 32-bit microcontrollers). However, while there exist numerous detailed benchmarking results for 8-bit AVR and 32-bit ARM/RISC-V/ESP32 microcontrollers, relatively little is known about the candidates' efficiency on 16-bit platforms. In order to fill this gap, we present a performance evaluation of the final-round candidates Ascon, Schwaemm, TinyJambu, and Xoodyak on the MSP430 series of ultra-low-power 16-bit microcontrollers from Texas Instruments. All four algorithms were explicitly designed to achieve high performance in software and have further in common that the underlying primitive is a permutation. We discuss how these permutations can be implemented efficiently in Assembly language and analyze how basic design decisions impact their execution time on the MSP430 architecture. Our results show that, overall, Schwaemm is the fastest algorithm across various lengths of data and associated data, respectively. Xoodyak has benefits when a large amount of associated data is to be authenticated, whereas TinyJambu is very efficient for the authentication of short messages. [less ▲]

Highly Vectorized SIKE for AVX-512

in IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES) (2022, February), 2022(2), 41-68

It is generally accepted that a large-scale quantum computer would be capable to break any public-key cryptosystem used today, thereby posing a serious threat to the security of the Internet’s public-key ... [more ▼]

It is generally accepted that a large-scale quantum computer would be capable to break any public-key cryptosystem used today, thereby posing a serious threat to the security of the Internet’s public-key infrastructure. The US National Institute of Standards and Technology (NIST) addresses this threat with an open process for the standardization of quantum-safe key establishment and signature schemes, which is now in the final phase of the evaluation of candidates. SIKE (an abbreviation of Supersingular Isogeny Key Encapsulation) is one of the alternate candidates under evaluation and distinguishes itself from other candidates due to relatively short key lengths and relatively high computing costs. In this paper, we analyze how the latest generation of Intel’s Advanced Vector Extensions (AVX), in particular AVX-512IFMA, can be used to minimize the latency (resp. maximize the throughput) of the SIKE key encapsulation mechanism when executed on Ice LakeCPUs based on the Sunny Cove microarchitecture. We present various techniques to parallelize and speed up the base/extension field arithmetic, point arithmetic, and isogeny computations performed by SIKE. All these parallel processing techniques are combined in AVXSIKE, a highly optimized implementation of SIKE using Intel AVX-512IFMA instructions. Our experiments indicate that AVXSIKE instantiated with the SIKEp503 parameter set is approximately 1.5 times faster than the to-date best AVX-512IFMA-based SIKE software from the literature. When executed on an Intel Core i3-1005G1 CPU, AVXSIKE outperforms the x64 assembly implementation of SIKE contained in Microsoft’s SIDHv3.4 library by a factor of about 2.5 for key generation and decapsulation, while the encapsulation is even 3.2 times faster. [less ▲]

Optimized Implementation of SHA-512 for 16-bit MSP430 Microcontrollers

in Ryan, Peter Y A; Toma, Cristian (Eds.) Innovative Security Solutions for Information Technology and Communications 14th International Conference, SECITC 2021, Virtual Event, November 25-26, 2021, Revised Selected Papers (2021, November)

The enormous growth of the Internet of Things (IoT) in the recent past has fueled a strong demand for lightweight implementations of cryptosystems, i.e. implementations that are efficient enough to run on ... [more ▼]

The enormous growth of the Internet of Things (IoT) in the recent past has fueled a strong demand for lightweight implementations of cryptosystems, i.e. implementations that are efficient enough to run on resource-limited devices like sensor nodes. However, most of today's widely-used cryptographic algorithms, including the AES or the SHA2 family of hash functions, were already designed some 20 years ago and did not take efficiency in restricted environments into account. In this paper, we introduce implementation options and software optimization techniques to reduce the execution time of SHA-512 on 16-bit MSP430 microcontrollers. These optimizations include a novel register allocation strategy for the 512-bit hash state, a fast "on-the-fly" message schedule with low RAM footprint, special pointer arithmetic to avoid the need to copy state words, as well as instruction sequences for multi-bit rotation of 64-bit operands. Thanks to the combination of all these optimization techniques, our hand-written MSP430 Assembler code for the SHA-512 compression function reaches an execution time of roughly 40.6k cycles on an MSP430F1611 microcontroller. Hashing a message of 1000 bytes takes slightly below 338k clock cycles, which corresponds to a hash rate of about 338 cycles/byte. This execution time sets a new speed record for hashing with 256 bits of security on a 16-bit platform and improves the time needed by the fastest C implementations by a factor of 2.3. In addition, our implementation is extremely small in terms of code size (roughly 2.1k bytes) and has a RAM footprint of only 390 bytes. [less ▲]

Batching CSIDH Group Actions using AVX-512

in IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES) (2021, August), 2021(4), 618-649

Commutative Supersingular Isogeny Diffie-Hellman (or CSIDH for short) is a recently-proposed post-quantum key establishment scheme that belongs to the family of isogeny-based cryptosystems. The CSIDH ... [more ▼]

Commutative Supersingular Isogeny Diffie-Hellman (or CSIDH for short) is a recently-proposed post-quantum key establishment scheme that belongs to the family of isogeny-based cryptosystems. The CSIDH protocol is based on the action of an ideal class group on a set of supersingular elliptic curves and comes with some very attractive features, e.g. the ability to serve as a “drop-in” replacement for the standard elliptic curve Diffie-Hellman protocol. Unfortunately, the execution time of CSIDH is prohibitively high for many real-world applications, mainly due to the enormous computational cost of the underlying group action. Consequently, there is a strong demand for optimizations that increase the efficiency of the class group action evaluation, which is not only important for CSIDH, but also for related cryptosystems like the signature schemes CSI-FiSh and SeaSign. In this paper, we explore how the AVX-512 vector extensions (incl. AVX-512F and AVX-512IFMA) can be utilized to optimize constant-time evaluation of the CSIDH-512 class group action with the goal of, respectively, maximizing throughput and minimizing latency. We introduce different approaches for batching group actions and computing them in SIMD fashion on modern Intel processors. In particular, we present a hybrid batching technique that, when combined with optimized (8 × 1)-way prime-field arithmetic, increases the throughput by a factor of 3.64 compared to a state-of-the-art (non-vectorized) x64 implementation. On the other hand, vectorization in a 2-way fashion aimed to reduce latency makes our AVX-512 implementation of the group action evaluation about 1.54 times faster than the state-of-the-art. To the best of our knowledge, this paper is the first to demonstrate the high potential of using vector instructions to increase the throughput (resp. decrease the latency) of constant-time CSIDH. [less ▲]

Lightweight Post-quantum Key Encapsulation for 8-bit AVR Microcontrollers

in Liardet, Pierre-Yvan; Mentens, Nele (Eds.) Smart Card Research and Advanced Applications, 19th International Conference, CARDIS 2020, Virtual Event, November 18–19, 2020, Revised Selected Papers (2020, November)

Recent progress in quantum computing has increased interest in the question of how well the existing proposals for post-quantum cryptosystems are suited to replace RSA and ECC. While some aspects of this ... [more ▼]

Recent progress in quantum computing has increased interest in the question of how well the existing proposals for post-quantum cryptosystems are suited to replace RSA and ECC. While some aspects of this question have already been researched in detail (e.g. the relative computational cost of pre- and post-quantum algorithms), very little is known about the RAM footprint of the proposals and what execution time they can reach when low memory consumption rather than speed is the main optimization goal. This question is particularly important in the context of the Internet of Things (IoT) since many IoT devices are extremely constrained and possess only a few kB of RAM. We aim to contribute to answering this question by exploring the software design space of the lattice-based key-encapsulation scheme ThreeBears on an 8-bit AVR microcontroller. More concretely, we provide new techniques for the optimization of the ring arithmetic of ThreeBears (which is, in essence, a 3120-bit modular multiplication) to achieve either high speed or low RAM footprint, and we analyze in detail the trade-offs between these two metrics. A low-memory implementation of BabyBear that is secure against Chosen Plaintext Attacks (CPA) needs just about 1.7 kB RAM, which is significantly below the RAM footprint of other lattice-based cryptosystems reported in the literature. Yet, the encapsulation time of this RAM-optimized BabyBear version is below 12.5 million cycles, which is less than the execution time of scalar multiplication on Curve25519. The decapsulation is more than four times faster and takes roughly 3.4 million cycles on an ATmega1284 microcontroller. [less ▲]

High-Throughput Elliptic Curve Cryptography Using AVX2 Vector Instructions

in Dunkelman, Orr; Jacobson Jr., Michael J.; O'Flynn, Colin (Eds.) Selected Areas in Cryptography, 27th International Conference, Halifax, NS, Canada (Virtual Event), October 21-23, 2020, Revised Selected Papers (2020, October)

Single Instruction Multiple Data (SIMD) execution engines like Intel’s Advanced Vector Extensions 2 (AVX2) offer a great potential to accelerate elliptic curve cryptography compared to implementations ... [more ▼]

Single Instruction Multiple Data (SIMD) execution engines like Intel’s Advanced Vector Extensions 2 (AVX2) offer a great potential to accelerate elliptic curve cryptography compared to implementations using only basic x64 instructions. All existing AVX2 implementations of scalar multiplication on e.g. Curve25519 (and alternative curves) are optimized for low latency. We argue in this paper that many real-world applications, such as server-side SSL/TLS handshake processing, would benefit more from throughput-optimized implementations than latency-optimized ones. To support this argument, we introduce a throughput-optimized AVX2 implementation of variable-base scalar multiplication on Curve25519 and fixed-base scalar multiplication on Ed25519. Both implementations perform four scalar multiplications in parallel, where each uses a 64-bit element of a 256-bit vector. The field arithmetic is based on a radix-2^29 representation of the field elements, which makes it possible to carry out four parallel multiplications modulo a multiple of p=2^255−19 in just 88 cycles on a Skylake CPU. Four variable-base scalar multiplications on Curve25519 require less than 250,000 Skylake cycles, which translates to a throughput of 32,318 scalar multiplications per second at a clock frequency of 2 GHz. For comparison, the to-date best latency-optimized AVX2 implementation has a throughput of some 21,000 scalar multiplications per second on the same Skylake CPU. [less ▲]

Alzette: A 64-Bit ARX-box (Feat. CRAX and TRAX)

in Micciancio, Daniele; Ristenpart, Thomas (Eds.) Advances in Cryptology -- CRYPTO 2020, 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17-21, 2020, Proceedings, Part III (2020, August)

S-boxes are the only source of non-linearity in many symmetric primitives. While they are often defined as being functions operating on a small space, some recent designs propose the use of much larger ... [more ▼]

S-boxes are the only source of non-linearity in many symmetric primitives. While they are often defined as being functions operating on a small space, some recent designs propose the use of much larger ones (e.g., 32 bits). In this context, an S-box is then defined as a subfunction whose cryptographic properties can be estimated precisely. We present a 64-bit ARX-based S-box called Alzette, which can be evaluated in constant time using only 12 instructions on modern CPUs. Its parallel application can also leverage vector (SIMD) instructions. One iteration of Alzette has differential and linear properties comparable to those of the AES S-box, and two are at least as secure as the AES super S-box. As the state size is much larger than the typical 4 or 8 bits, the study of the relevant cryptographic properties of Alzette is not trivial. We further discuss how such wide S-boxes could be used to construct round functions of 64-, 128- and 256-bit (tweakable) block ciphers with good cryptographic properties that are guaranteed even in the related-tweak setting. We use these structures to design a very lightweight 64-bit block cipher (Crax) which outperforms SPECK-64/128 for short messages on micro-controllers, and a 256-bit tweakable block cipher (Trax) which can be used to obtain strong security guarantees against powerful adversaries (nonce misuse, quantum attacks). [less ▲]

A Lightweight Implementation of NTRU Prime for the Post-Quantum Internet of Things

in Laurent, Maryline; Giannetsos, Thanassis (Eds.) Information Security Theory and Practice, 13th IFIP WG 11.2 International Conference, WISTP 2019, Paris, France, December 11–12, 2019, Proceedings (2019, December)

The dawning era of quantum computing has initiated various initiatives for the standardization of post-quantum cryptosystems with the goal of (eventually) replacing RSA and ECC. NTRU Prime is a variant of ... [more ▼]

The dawning era of quantum computing has initiated various initiatives for the standardization of post-quantum cryptosystems with the goal of (eventually) replacing RSA and ECC. NTRU Prime is a variant of the classical NTRU cryptosystem that comes with a couple of tweaks to minimize the attack surface; most notably, it avoids rings with "worrisome" structure. This paper presents, to our knowledge, the first assembler-optimized implementation of Streamlined NTRU Prime for an 8-bit AVR microcontroller and shows that high-security lattice-based cryptography is feasible for small IoT devices. An encapsulation operation using parameters for 128-bit post-quantum security requires 8.2 million clock cycles when executed on an 8-bit ATmega1284 microcontroller. The decapsulation is approximately twice as costly and has an execution time of 15.6 million cycles. We achieved this performance through (i) new low-level software optimization techniques to accelerate Karatsuba-based polynomial multiplication on the 8-bit AVR platform and (ii) an efficient implementation of the coefficient modular reduction written in assembly language. The execution time of encapsulation and decapsulation is independent of secret data, which makes our software resistant against timing attacks. Finally, we assess the performance one could theoretically gain by using a so-called product-form polynomial as part of the secret key and discuss potential security implications. [less ▲]

Fast ECDH Key Exchange Using Twisted Edwards Curves with an Efficiently Computable Endomorphism

in Proceedings of the 8th International Workshop on Secure Internet of Things 2019 (SIoT 2019) (2019, September)

It is widely accepted that public-key cryptosystems play a major role in the security arena of the Internet of Things (IoT), but they need to be implemented efficiently to not deplete the scarce resources ... [more ▼]

It is widely accepted that public-key cryptosystems play a major role in the security arena of the Internet of Things (IoT), but they need to be implemented efficiently to not deplete the scarce resources of battery-operated devices such as wireless sensor nodes. This paper describes a highly-optimized software implementation of scalar multiplication for Elliptic Curve Diffie-Hellman (ECDH) key exchange on resource-limited IoT devices that achieves fast execution times along with reasonably small code size and RAM consumption. Our software uses a special class of elliptic curves, namely twisted Edwards curves with an efficiently computable endomorphism similar to that of the so- called Gallant-Lambert-Vanstone (GLV) curves. This allows us to combine the main advantage of the GLV model, which is an efficiently-computable endomorphism to speed up variable-base scalar multiplication, with the fast and complete addition rules of the (twisted) Edwards model. We implemented variable-base scalar multiplication for static ECDH on two such curves, one over a 159-bit and the second over a 207-bit pseudo-Mersenne prime field, respectively, and evaluated their execution time on a 16-bit MSP430F1611 processor. The arithmetic operations in the prime field do not contain operand-dependent conditional statements (in particular no "if-then-else" clauses) and also the scalar multiplication follows a fixed execution path for a given (static) scalar. A variable-base scalar multiplication on curves over the 159 and 207-bit field takes about 2.63 and 4.84 million clock cycles, respectively, on an MSP430F1611 processor. These results compare favorably with the Montgomery ladder on the equivalent Montgomery curves, which is almost 50% slower. [less ▲]

A Lightweight Implementation of NTRUEncrypt for 8-bit AVR Microcontrollers

E-print/Working paper (2019)

Introduced in 1996, NTRUEncrypt is not only one of the earliest but also one of the most scrutinized lattice-based cryptosystems and a serious contender in NIST’s ongoing Post-Quantum Cryptography (PQC ... [more ▼]

Introduced in 1996, NTRUEncrypt is not only one of the earliest but also one of the most scrutinized lattice-based cryptosystems and a serious contender in NIST’s ongoing Post-Quantum Cryptography (PQC) standardization project. An important criterion for the assessment of candidates is their computational cost in various hardware and software environments. This paper contributes to the evaluation of NTRUEncrypt on the ATmega class of AVR microcontrollers, which belongs to the most popular 8-bit platforms in the embedded domain. More concretely, we present AvrNtru, a carefully-optimized implementation of NTRUEncrypt that we developed from scratch with the goal of achieving high performance and resistance to timing attacks. AvrNtru complies with version 3.3 of the EESS#1 specification and supports recent product-form parameter sets like ees443ep1, ees587ep1, and ees743ep1. A full encryption operation (including mask generation and blinding- polynomial generation) using the ees443ep1 parameters takes 834,272 clock cycles on an ATmega1281 microcontroller; the decryption is slightly more costly and has an execution time of 1,061,683 cycles. When choosing the ees743ep1 parameters to achieve a 256-bit security level, 1,539,829 clock cycles are cost for encryption and 2,103,228 clock cycles for decryption. We achieved these results thanks to a novel hybrid technique for multiplication in truncated polynomial rings where one of the operands is a sparse ternary polynomial in product form. Our hybrid technique is inspired by Gura et al’s hybrid method for multiple-precision integer multiplication (CHES 2004) and takes advantage of the large register file of the AVR architecture to minimize the number of load instructions. A constant-time multiplication in the ring specified by the ees443ep1 parameters requires only 210,827 cycles, which sets a new speed record for the arithmetic component of a lattice-based cryptosystem on an 8-bit microcontroller. [less ▲]