Chaskey is a very efficient MAC algorithm for microcontrollers (paper, slides, source code). It is intended for applications that require 128-bit security, yet cannot implement standard MAC algorithms (such as HMAC, CMAC or UMAC) because of stringent requirements on speed, energy consumption or code size. Chaskey is the result of a research collaboration between COSIC and Hitachi YRL.

Updates

January 14, 2017: Damian Gryski has ported his Go implementation of Chaskey to AMD64 assembly.

January 13, 2017: Chrysanthi Mavromati will defend her Ph.D. thesis on January 24 at the Pierre and Marie Curie University in Paris. In her thesis, she made significant contributions to the cryptanalysis Even-Mansour-style ciphers, and to Chaskey in particular.

January 10, 2017: Ozhan has written a size-optimized implementation of Chaskey in C and x86 assembly.

October 17, 2016: At the NIST Lightweight Cryptography Workshop 2016, Diego F. Aranha presented improved Chaskey benchmarking results on ARM Cortex-M3.

August 15, 2016: At CRYPTO 2016, Bart Mennink presented XPX, which is a tweakable block cipher based on a single permutation. This work not only generalizes the security analysis of Chaskey, but also shows how a slight adjustment to Chaskey can achieve XOR-related-key security.

July 16, 2016: Pavel Werl has obtained improved benchmarks for optimized C# implementations of SipHash and Chaskey.

June 22, 2016: At ACNS 2016, Liu et al. explained how to search for linear trails in Chaskey using automated techniques (paper).

May 10, 2016: At EUROCRYPT 2016, Leurent presented the currently best-known cryptanalysis attack on Chaskey (ePrint 2015/968).

December 13, 2015: Chaskey-12 is proposed in ePrint 2015/1182 as the twelve-round variant of Chaskey. It addresses the concerns of ISO/IEC JTC 1/SC 27/WG 2 by significantly increasing the security margin, while only reducing the speed by about 15% on ARM Cortex-M0/M3/M4. We are nevertheless confident that the original 8-round Chaskey will remain secure. A Chaskey-12 reference implementation with test vectors is available.

October 31, 2015: Regarding the standardization of Chaskey: ISO/IEC JTC 1/SC 27/WG 2 has decided to terminate the study period on lightweight MAC algorithms, and to circulate a first working draft.

October 8, 2015: The research paper of currently best-known cryptanalysis attack on Chaskey by Gaëtan Leurent is now available as ePrint 2015/968. More below…

September 14, 2015: The FELICS benchmark results of the Chaskey block cipher have been improved significantly, in particular for 8-bit and 16-bit microcontrollers. We thank Jason Smith of the NSA for his time and effort in improving the implementations.

August 1, 2015: Chrysanthi Mavromati presented several new key-recovery attacks on Chaskey at SAC 2015. The attacks consider both the single-user and multi-user settings. As the attacks assume that Chaskey uses an ideal permutation, they do not violate the security proof of Chaskey (which can be extended to the multi-user setting using the techniques of ePrint 2015/101).

July 20, 2015: Chaskey was presented at the NIST Lightweight Cryptography Workshop 2015 in Gaithersburg, Maryland, USA.

July 16, 2015: An optimized implementation by Björn Haase reaches 9.77 cycles/byte on an ARM Cortex-M0. Source code below…

May 21, 2015: Guo et al. announced two new observations on Chaskey in ePrint 2015/484. The results do not have any practical impact, as they are only small speed-ups of exhaustive search. However, interesting is that their complexity goes down when the number of rounds of Chaskey is increased. In other work, Mennink showed in ePrint 2015/476 how Chaskey can easily be made related-key-secure.

April 21, 2015: The underlying block cipher of Chaskey was benchmarked by the FELICS project of the University of Luxembourg on a variety of microcontrollers. As the implementation results show, the Chaskey block cipher performs very well on 8-bit, 16-bit and 32-bit microcontrollers. It is nearly always the fastest block cipher, even when compared to other ciphers with significantly smaller block and key sizes.

January 19, 2015: First external cryptanalysis of Chaskey by Gaëtan Leurent (Inria, France). More below…

November 6, 2014: ISO/IEC JTC 1/SC 27/WG 2 is currently conducting a preliminary study on the standardization of Chaskey, and ITU-T SG17 has added new work items related to IoT and ITS security, for which Chaskey seems to be well-suited.

August 15, 2014: Chaskey was introduced at the SAC 2014 conference in Montreal, Canada.

Features

Chaskey is fast. On an ARM Cortex-M4, Chaskey runs at 7.0 cycles/byte, compared to 89.4 cycles/byte for AES-128-CMAC. As there is roughly a linear relation between the number of cycles and energy consumption, Chaskey is an order of magnitude more energy-efficient as well.

Chaskey is provably secure. Chaskey is proven to be secure in the standard model, based on the security of an underlying Even-Mansour block cipher. The best generic attacks on Chaskey require about D=264 message blocks for an internal collision, about T=2128/D permutation evaluations for a key recovery attack, or about 2t guesses for a tag guessing attack, where t is the tag length in bits.

Chaskey resists cryptanalysis. Chaskey uses a reduced-word-size variant of the SipHash round function. SipHash-2-4 is very widely used: in FreeBSD, Perl, Python,… We analyzed Chaskey against a wide variety of cryptanalytical attacks, including differential cryptanalysis, truncated differential cryptanalysis, meet-in-the-middle attacks, rotational cryptanalysis, and slide attacks.

…including external cryptanalysis. The first external cryptanalysis of Chaskey was presented by Gaëtan Leurent (Inria, France) at ESC 2015 (paper, slides). He demonstrated a practically verified attack on 6 rounds with D=225 and T=229, and sketched an attack on 7 rounds with D=245–248. Because of the novel techniques used in his attack (differential-linear cryptanalysis together with state-of-the-art improvements), we expect a large academic interest in Chaskey in the near future. Nevertheless, we are confident that the full 8-round Chaskey will remain unbroken.

Chaskey is small. On an ARM Cortex-M4, Chaskey can be implemented in 402 bytes of ROM. This is about ten times smaller than the smallest available AES-128-ECB implementation on this platform.

Chaskey is flexible. Chaskey has been designed to perform well on a wide range of 8-bit, 16-bit and 32-bit microcontrollers. Short tags are supported: the best attack in this case is tag guessing. Furthermore, Chaskey does not require nonce values, and is secure against timing attacks on all platforms.

Chaskey is free. Chaskey is patent-free and its source code is available without restrictions on its use: click to download a portable, a speed-optimized, a size-optimized or an 8-bit Chaskey reference implementation in C. Björn Haase wrote an optimized implementation for the ARM Cortex-M0, which reaches 9.77 cycles/byte for 128-byte messages. We thank Damian Gryski for a Chaskey implementation in Go, Bart Mennink for a Chaskey implementation in Python, and Pavel Werl for a  Chaskey implementation in C#.

Description

A brief description of Chaskey is given below. For more details, see the full paper: ePrint 2014/386.

Chaskey takes a message m, and splits it into message blocks m1, m2, …, m, of 128 bits each. It also takes a 128-bit key K, from which two 128-bit subkeys K1 and K2 are derived, each using a 128-bit shift and a 128-bit conditional XOR.

Let rightt denote the truncation of a 128-bit value to t bits. If the last message block m is complete, Chaskey iterates a permutation π as follows:

Chaskey (complete last message block)

If the last message block m is incomplete, Chaskey is defined as follows:

Chaskey (fractional last message block)

The permutation π used in Chaskey consists of eight applications of the following round function:

Chaskey permutation (one round)

Note that π is definitely not an ideal permutation. For example, it is easy to find a fixed point: π(0)=0. However, one of the main innovations of Chaskey is to wrap π inside an Even-Mansour block cipher, in order to overcome a wide variety of distinguishing attacks on π. Another major innovation of Chaskey is to minimize the number of program variables, which significantly reduces register pressure.