Side channel analysis of SPECK

Abstract

SPECK is a family of lightweight block ciphers developed by Beaulieu et al. of the US National Security Agency (NSA) for the Internet of Things (IoT). It is an ARX-based design with a Feistel-like structure which supports keys of size ranging from 64 bits to 256 bits. SPECK has been standardised by ISO/IEC for radio frequency identification (RFID) devices. It has drawn the attention of many cryptanalysts and several cryptanalysis results have been published. In this paper, carry flag attacks on the full SPECK ciphers are presented. Depending on the key size and block size, the complexities of our attacks, to nearly ensure success, vary from $2^{59}$ time and $2^{14}$ data to $2^{227}$ time and $2^{62}$ data.

Keywords

SPECK lightweight cipher carry flag attack

1. Introduction

The SPECK family of ciphers. SPECK is a family of lightweight block ciphers designed by Beaulieu et al. of the US NSA “as an aid for securing applications in very constrained environments where AES may not be suitable” [6]. The design principle to use basic operations such as modular addition, bitwise XOR and circular shifts has made them remarkably simple and highly flexible across the platforms. SPECK has 10 constituent ciphers, each corresponding to a unique combination of key size and block size. The key size varies from 64 bits to 256 bits whereas the block size ranges from 32 bits to 128 bits. The use of modular addition operation for nonlinearity has made SPECK well optimised for software applications. The ISO/IEC specifies a crypto suite for SPECK for their air interfaces standards for RFID devices [27]. To be used on low-end Android Go devices, Google added SPECK to Linux Kernel 4.17 [32] but eventually it was removed from Linux Kernel 4.20 and subsequent versions [12,36].

Related works. Given the possibility for widespread deployment in lightweight applications, SPECK has been studied extensively during the recent years. In 2014, Abed et al. presented differential attacks on 10, 12, 15, 15 and 16 rounds of SPECK ciphers with block sizes 32, 48, 64, 96, and 128 bits, respectively [1]. They also reported rectangle attacks which could work on 11 and 18 rounds of SPECK ciphers with 64- and 256-bit keys, respectively [1]. In the same year, Biryukov et al. also proposed differential cryptanalysis of reduced-round SPECK which could be used to attack 16 rounds of SPECK ciphers with a block size of 64 bits [10]. Later, Dinur published an improved differential cryptanalysis of SPECK which increased the number of rounds that can be attacked by 1, 2, or 3, for 9 out of 10 reduced-round members of the family, while significantly improving the complexity of the previous best-known attack on the remaining reduced-round member [14].

The first known attacks on full SPECK ciphers were by Tupsamudre et al. who presented a differential fault analysis on SPECK which recovers the n-bit subkey of the final round using $n / 3$ bit faults on an average [42]. Tupsamudre et al.’s differential fault attacks were further improved by Huo et al., whose attacks required a more practical random fault model and lesser number of fault injections compared to the earlier attacks [26]. In 2015, Yuan et al. reported the first known linear cryptanalysis on reduced-round SPECK ciphers [45]. In 2016, Fu et al. proposed differential attacks on reduced-round SPECK ciphers with block sizes 48, 64, 96 and 128 bits, which were better than the earlier differential attacks in terms of the number of rounds attacked [20]. The differential attacks were further improved by Song et al. by increasing the number of rounds that can be attacked for ciphers with block sizes 96 and 128 bits, and reducing the attack complexities in the remaining cases [41]. In 2016, Feng et al. published fault attacks on SPECK ciphers which were better than the earlier attacks of the same type [16].

In 2017, Liu et al. proposed a SAT / SMT model for rotational-XOR cryptanalysis in ARX primitives and used it to present distinguishers on reduced-round SPECK with block sizes 32 and 48 bits which have better probabilities than the previously known differential characteristics [33]. In 2019, Ge et al. reported correlation power analysis on unprotected software implementations of SPECK ciphers [21]. In the same year, Hou et al. presented a tool to perform automated differential fault analysis on the software implementations of block ciphers and used the same to attack the implementations of SPECK ciphers [24]. Reduced-round SPECK ciphers were subjected to a few more attacks during the years 2019 and 2020 such as impossible differential cryptanalysis, differential cryptanalysis, integral cryptanalysis and linear cryptanalysis [11,15,25,29–31,38].

A comparative analysis of the best-known key recovery attacks on the SPECK ciphers, including the attacks presented in this paper, is listed in Table 1. The first parameter used to compare the attacks is the number of rounds of SPECK that can be targeted; greater the number of rounds, better is the attack. Among the attacks that target the same number of rounds, the best will be the one that requires the minimum number of fault injections, and have the minimum data and time complexities. It can be seen from Table 1 that the number of rounds targeted by the best-known non-implementation attacks ranges from 14 to 25 for different members of the SPECK family [41]. All the attacks on the full SPECK ciphers target their implementations, and the attacks presented in this paper are the best among them, as far as we know.

Table 1
Comparative analysis of the best-known key recovery attacks (with a success rate of $99.99 %$ ) on the SPECK ciphers

Block size (in bits) Key size (in bits) # rounds attacked / total Attack requirements Year

32 64 11 / 22 $2^{30.1}$ CPs, $2^{46.7}$ time 2014 [1]

14 / 22 $2^{31}$ CPs, $2^{63}$ time 2014 [14]

22 / 22 6 faulty bits, $2^{48}$ time 2014 [42]

22 / 22 5 faults 1 , $2^{48}$ time 2015 [26]

14 / 22 $2^{30.47}$ CPs, $2^{62.47}$ time 2016 [41]

22 / 22 $2^{14}$ data, $2^{59}$ time 2020 (This paper)

48 72 12 / 22 $2^{45}$ CPs, $2^{45.3}$ time 2014 [1]

12 / 22 $2^{43}$ CPs, $2^{43}$ time 2014 [10]

14 / 22 $2^{41}$ CPs, $2^{65}$ time 2014 [14]

22 / 22 8 faulty bits 1 , $2^{48}$ time 2014 [42]

22 / 22 5 faults 1 , $2^{48}$ time 2015 [26]

15 / 22 $2^{46}$ CPs, $2^{70}$ time 2016 [20]

15 / 22 $2^{45.31}$ CPs, $2^{69.31}$ time 2016 [41]

22 / 22 $2^{22}$ data 2 , $2^{63}$ time 2020 (This paper)

48 96 12 / 23 $2^{45}$ CPs, $2^{45.3}$ time 2014 [1]

12 / 23 $2^{43}$ CPs, $2^{43}$ time 2014 [10]

15 / 23 $2^{41}$ CPs, $2^{89}$ time 2014 [14]

23 / 23 8 faulty bits 1 , $2^{72}$ time 2014 [42]

23 / 23 5 faults 1 , $2^{72}$ time 2015 [26]

16 / 23 $2^{46}$ CPs, $2^{94}$ time 2016 [20]

16 / 23 $2^{45.31}$ CPs, $2^{93.31}$ time 2016 [41]

23 / 23 $2^{22}$ data 2 , $2^{87}$ time 2020 (This paper)

64 96 15 / 26 $2^{61}$ CPs, $2^{61.1}$ time 2014 [1]

16 / 26 $2^{64}$ CPs, $2^{73}$ time 2014 [10]

18 / 26 $2^{61}$ CPs, $2^{93}$ time 2014 [14]

26 / 26 11 faulty bits 1 , $2^{64}$ time 2014 [42]

26 / 26 6 faults 1 , $2^{64}$ time 2015 [26]

19 / 26 $2^{63}$ CPs, $2^{95}$ time 2016 [20]

19 / 26 $2^{61.56}$ CPs, $2^{93.56}$ time 2016 [41]

26 / 26 $2^{30}$ data 2 , $2^{83}$ time 2020 (This paper)

64 128 15 / 27 $2^{61}$ CPs, $2^{61.1}$ time 2014 [1]

16 / 27 $2^{64}$ CPs, $2^{73}$ time 2014 [10]

19 / 27 $2^{61}$ CPs, $2^{125}$ time 2014 [14]

27 / 27 11 faulty bits 1 , $2^{96}$ time 2014 [42]

27 / 27 6 faults 1 , $2^{96}$ time 2015 [26]

20 / 27 $2^{63}$ CPs, $2^{127}$ time 2016 [20]

20 / 27 $2^{61.56}$ CPs, $2^{125.56}$ time 2016 [41]

27 / 27 $2^{30}$ data 2 , $2^{115}$ time 2020 (This paper)

96 96 15 / 28 $2^{89}$ CPs, $2^{89.1}$ time 2014 [1]

16 / 28 $2^{85}$ CPs, $2^{85}$ time 2014 [14]

28 / 28 16 faulty bits 1 , $2^{48}$ time 2014 [42]

28 / 28 7 faults 1 , $2^{48}$ time 2015 [26]

19 / 28 $2^{88}$ CPs, $2^{88}$ time 2016 [20]

20 / 28 $2^{95.94}$ CPs, $2^{95.94}$ time 2016 [41]

28 / 28 $2^{46}$ data 2 , $2^{75}$ time 2020 (This paper)

96 144 16 / 29 $2^{90.9}$ CPs, $2^{135.9}$ time 2014 [1]

17 / 29 $2^{85}$ CPs, $2^{133}$ time 2014 [14]

29 / 29 16 faulty bits 1 , $2^{96}$ time 2014 [42]

29 / 29 7 faults 1 , $2^{96}$ time 2015 [26]

20 / 29 $2^{88}$ CPs, $2^{136}$ time 2016 [20]

21 / 29 $2^{95.94}$ CPs, $2^{143.94}$ time 2016 [41]

29 / 29 $2^{46}$ data 2 , $2^{123}$ time 2020 (This paper)

128 128 16 / 32 $2^{116}$ CPs, $2^{111.1}$ time 2014 [1]

17 / 32 $2^{113}$ CPs, $2^{113}$ time 2014 [14]

32 / 32 22 faulty bits 1 , $2^{64}$ time 2014 [42]

32 / 32 8 faults 1 , $2^{64}$ time 2015 [26]

22 / 32 $2^{120}$ CPs, $2^{120}$ time 2016 [20]

23 / 32 $2^{125.35}$ CPs, $2^{125.35}$ time 2016 [41]

32 / 32 $2^{62}$ data 2 , $2^{99}$ time 2020 (This paper)

128 192 18 / 33 $2^{125.9}$ CPs, $2^{182.7}$ time 2014 [1]

18 / 33 $2^{113}$ CPs, $2^{177}$ time 2014 [14]

33 / 33 22 faulty bits 1 , $2^{128}$ time 2014 [42]

33 / 33 8 faults 1 , $2^{128}$ time 2015 [26]

23 / 33 $2^{120}$ CPs, $2^{184}$ time 2016 [20]

24 / 33 $2^{125.35}$ CPs, $2^{189.35}$ time 2016 [41]

33 / 33 $2^{62}$ data 2 , $2^{163}$ time 2020 (This paper)

128 256 18 / 34 $2^{125.9}$ CPs, $2^{182.7}$ time 2014 [1]

19 / 34 $2^{113}$ CPs, $2^{241}$ time 2014 [14]

34 / 34 22 faulty bits 1 , $2^{192}$ time 2014 [42]

34 / 34 8 faults 1 , $2^{192}$ time 2015 [26]

24 / 34 $2^{120}$ CPs, $2^{248}$ time 2016 [20]

25 / 34 $2^{125.35}$ CPs, $2^{253.35}$ time 2016 [41]

34 / 34 $2^{62}$ data 2 , $2^{227}$ time 2020 (This paper)

Block size (in bits)	Key size (in bits)	# rounds attacked / total	Attack requirements	Year
32	64	11 / 22	$2^{30.1}$ CPs, $2^{46.7}$ time	2014 [1]
14 / 22	$2^{31}$ CPs, $2^{63}$ time	2014 [14]
22 / 22	6 faulty bits, $2^{48}$ time	2014 [42]
22 / 22	5 faults 1 , $2^{48}$ time	2015 [26]
14 / 22	$2^{30.47}$ CPs, $2^{62.47}$ time	2016 [41]
22 / 22	$2^{14}$ data, $2^{59}$ time	2020 (This paper)
48	72	12 / 22	$2^{45}$ CPs, $2^{45.3}$ time	2014 [1]
12 / 22	$2^{43}$ CPs, $2^{43}$ time	2014 [10]
14 / 22	$2^{41}$ CPs, $2^{65}$ time	2014 [14]
22 / 22	8 faulty bits 1 , $2^{48}$ time	2014 [42]
22 / 22	5 faults 1 , $2^{48}$ time	2015 [26]
15 / 22	$2^{46}$ CPs, $2^{70}$ time	2016 [20]
15 / 22	$2^{45.31}$ CPs, $2^{69.31}$ time	2016 [41]
22 / 22	$2^{22}$ data 2 , $2^{63}$ time	2020 (This paper)
48	96	12 / 23	$2^{45}$ CPs, $2^{45.3}$ time	2014 [1]
12 / 23	$2^{43}$ CPs, $2^{43}$ time	2014 [10]
15 / 23	$2^{41}$ CPs, $2^{89}$ time	2014 [14]
23 / 23	8 faulty bits 1 , $2^{72}$ time	2014 [42]
23 / 23	5 faults 1 , $2^{72}$ time	2015 [26]
16 / 23	$2^{46}$ CPs, $2^{94}$ time	2016 [20]
16 / 23	$2^{45.31}$ CPs, $2^{93.31}$ time	2016 [41]
23 / 23	$2^{22}$ data 2 , $2^{87}$ time	2020 (This paper)
64	96	15 / 26	$2^{61}$ CPs, $2^{61.1}$ time	2014 [1]
16 / 26	$2^{64}$ CPs, $2^{73}$ time	2014 [10]
18 / 26	$2^{61}$ CPs, $2^{93}$ time	2014 [14]
26 / 26	11 faulty bits 1 , $2^{64}$ time	2014 [42]
26 / 26	6 faults 1 , $2^{64}$ time	2015 [26]
19 / 26	$2^{63}$ CPs, $2^{95}$ time	2016 [20]
19 / 26	$2^{61.56}$ CPs, $2^{93.56}$ time	2016 [41]
26 / 26	$2^{30}$ data 2 , $2^{83}$ time	2020 (This paper)
64	128	15 / 27	$2^{61}$ CPs, $2^{61.1}$ time	2014 [1]
16 / 27	$2^{64}$ CPs, $2^{73}$ time	2014 [10]
19 / 27	$2^{61}$ CPs, $2^{125}$ time	2014 [14]
27 / 27	11 faulty bits 1 , $2^{96}$ time	2014 [42]
27 / 27	6 faults 1 , $2^{96}$ time	2015 [26]
20 / 27	$2^{63}$ CPs, $2^{127}$ time	2016 [20]
20 / 27	$2^{61.56}$ CPs, $2^{125.56}$ time	2016 [41]
27 / 27	$2^{30}$ data 2 , $2^{115}$ time	2020 (This paper)
96	96	15 / 28	$2^{89}$ CPs, $2^{89.1}$ time	2014 [1]
16 / 28	$2^{85}$ CPs, $2^{85}$ time	2014 [14]
28 / 28	16 faulty bits 1 , $2^{48}$ time	2014 [42]
28 / 28	7 faults 1 , $2^{48}$ time	2015 [26]
19 / 28	$2^{88}$ CPs, $2^{88}$ time	2016 [20]
20 / 28	$2^{95.94}$ CPs, $2^{95.94}$ time	2016 [41]
28 / 28	$2^{46}$ data 2 , $2^{75}$ time	2020 (This paper)
96	144	16 / 29	$2^{90.9}$ CPs, $2^{135.9}$ time	2014 [1]
17 / 29	$2^{85}$ CPs, $2^{133}$ time	2014 [14]
29 / 29	16 faulty bits 1 , $2^{96}$ time	2014 [42]
29 / 29	7 faults 1 , $2^{96}$ time	2015 [26]
20 / 29	$2^{88}$ CPs, $2^{136}$ time	2016 [20]
21 / 29	$2^{95.94}$ CPs, $2^{143.94}$ time	2016 [41]
29 / 29	$2^{46}$ data 2 , $2^{123}$ time	2020 (This paper)
128	128	16 / 32	$2^{116}$ CPs, $2^{111.1}$ time	2014 [1]
17 / 32	$2^{113}$ CPs, $2^{113}$ time	2014 [14]
32 / 32	22 faulty bits 1 , $2^{64}$ time	2014 [42]
32 / 32	8 faults 1 , $2^{64}$ time	2015 [26]
22 / 32	$2^{120}$ CPs, $2^{120}$ time	2016 [20]
23 / 32	$2^{125.35}$ CPs, $2^{125.35}$ time	2016 [41]
32 / 32	$2^{62}$ data 2 , $2^{99}$ time	2020 (This paper)
128	192	18 / 33	$2^{125.9}$ CPs, $2^{182.7}$ time	2014 [1]
18 / 33	$2^{113}$ CPs, $2^{177}$ time	2014 [14]
33 / 33	22 faulty bits 1 , $2^{128}$ time	2014 [42]
33 / 33	8 faults 1 , $2^{128}$ time	2015 [26]
23 / 33	$2^{120}$ CPs, $2^{184}$ time	2016 [20]
24 / 33	$2^{125.35}$ CPs, $2^{189.35}$ time	2016 [41]
33 / 33	$2^{62}$ data 2 , $2^{163}$ time	2020 (This paper)
128	256	18 / 34	$2^{125.9}$ CPs, $2^{182.7}$ time	2014 [1]
19 / 34	$2^{113}$ CPs, $2^{241}$ time	2014 [14]
34 / 34	22 faulty bits 1 , $2^{192}$ time	2014 [42]
34 / 34	8 faults 1 , $2^{192}$ time	2015 [26]
24 / 34	$2^{120}$ CPs, $2^{248}$ time	2016 [20]
25 / 34	$2^{125.35}$ CPs, $2^{253.35}$ time	2016 [41]
34 / 34	$2^{62}$ data 2 , $2^{227}$ time	2020 (This paper)

Faults are induced in the last round.

Number of encryptions are assumed to be well below the birthday bound.

Processor flag cryptanalysis. In [28], Kelsey et al. introduced processor flag cryptanalysis, a new class of side channel attacks. Nearly every modern microprocessor has the status register, a collection of flag bits that store information about the state of the processors and information on operations performed by their ALUs [2]. Carry flag is one such flag bit that indicates carry overflow in unsigned integer arithmetic. For instance, when two unsigned integers are added, the carry flag is set (to 1) if a carry is generated by the addition at the most significant bit position and the flag is cleared (i.e., 0) otherwise.

In 2000, the first known attack that exploits the carry flag was presented by Kelsey et al. on RC5 [28]. Later in 2002, Gomuffłkiewicz et al. presented attacks on IDEA and Twofish [22]. These attacks exploited the Hamming weight of the sequence of carry bits and the authors conjectured that simple power analysis can be used to extract this information. Subsequently, in 2008, Fouque et al. presented carry flag attacks on public key implementations of RSA and ECC based cryptosystems with exponent randomisation countermeasure [19]. They demonstrated that the carry flag can be detected by studying the electromagnetic side channel of the implementation using differential power analysis. In 2009, Fouque et al. presented another carry flag attack which could recover the secret keys used in public key schemes such as DSA and ECDSA signature schemes, and Schnorr and GPS authentication and signature schemes [18]. In order to detect the carry, they injected a fault during the computation of the carry using methods like glitch injection, clock speed up or laser fault injection. The most recent carry flag attack, which is on Streebog, was presented by Sekar in 2015 [40].

Contributions of this paper. SPECK is a cipher of importance as it is an ISO standard for RFID devices and a potential candidate to secure lightweight applications. This gave us enough motivation to examine its security. After unsuccessfully trying several cryptanalytic methods to analyse SPECK, it was eventually found that SPECK is vulnerable to carry flag attacks. This technique, originally proposed by Kelsey et al. [28], is fairly well-known and thoroughly explored in a few papers [18,19,22,40]. Hence, we were motivated to further examine the vulnerability of SPECK to this class of attacks. Despite the use of modular addition in the round function of SPECK, to the best of our knowledge, there are no published results analysing the resistance of unprotected SPECK implementations to carry flag attacks. Our attacks, that work on the full ciphers, at the best recover the key in $2^{59}$ time with $2^{14}$ data corresponding to a success rate of $99.99 %$ . The only other full-round attacks on SPECK are due to [26,42] and [16], however, these are based on much stronger assumptions. Our attack model uses a weak assumption that the attacker can either detect the carry flag at the end of encryption or key expansion, or detect the bit-flips in the carry flag after the modular addition in the final round. This makes our attacks more feasible when compared to the fault attacks of [16,26,42]. The complexities of our key recovery attacks for a success rate of 99.99% are given in Table 1.

Organisation of the paper. The paper is organised as follows. Section 2 describes the ciphers along with the notation and convention that is followed. The motivational observations for SPECK are presented in Section 3. Our attacks on the encryption phase and key expansion phase of SPECK are presented in Section 4 and Section 5, respectively. The methods to detect the carry flag, scope of improving the attack complexities and countermeasures are discussed in Section 6. We conclude in Section 7.

2. Specifications of the ciphers

Table 2 lists the notation and convention followed throughout the paper.

Table 2
Notation and convention

Symbol / notation Meaning

$x_{(j)}$ $(j + 1)$ th bit of x ( $j = 0$ denotes the least significant bit)

$⊞_{w}$ addition modulo $2^{w}$ where w is the word size in bits

$⊟_{w}$ subtraction modulo $2^{w}$ where w is the word size in bits

⊕ exclusive OR

$⋘ i$ Cyclic left rotation by i bits

$⋙ i$ Cyclic right rotation by i bits

∥ Concatenation of two binary strings

$F_{j} (x)$ $(j + 1)$ th least significant byte of x

LSB Least significant bit

MSB Most significant bit

Symbol / notation	Meaning
$x_{(j)}$	$(j + 1)$ th bit of x ( $j = 0$ denotes the least significant bit)
$⊞_{w}$	addition modulo $2^{w}$ where w is the word size in bits
$⊟_{w}$	subtraction modulo $2^{w}$ where w is the word size in bits
⊕	exclusive OR
$⋘ i$	Cyclic left rotation by i bits
$⋙ i$	Cyclic right rotation by i bits
∥	Concatenation of two binary strings
$F_{j} (x)$	$(j + 1)$ th least significant byte of x
LSB	Least significant bit
MSB	Most significant bit

2.1.

{SPECK}_{m, n}

The lightweight block cipher ${SPECK}_{m, n}$ uses an n-bit key K, and has a block size of m bits and word size of $\frac{m}{2}$ bits. The ${SPECK}_{m, n}$ encryption consists of r rounds and the $(i + 1)$ th round function is given by $E_{k_{i}} (a_{i}, b_{i}) = (((a_{i} ⋙ α) ⊞_{\frac{m}{2}} b_{i}) \oplus k_{i}$ , $(((a_{i} ⋙ α) ⊞_{\frac{m}{2}} b_{i}) \oplus k_{i}) \oplus (b_{i} ⋘ β))$ , where $k_{i}$ is the $(i + 1)$ th round key of size $\frac{m}{2}$ bits, $a_{i}$ and $b_{i}$ are the $\frac{m}{2}$ -bit inputs of the $(i + 1)$ th round, and α and β are round constants. The inverse of the $(i + 1)$ th round function, which will be used for decryption, is given by $D_{k_{i}} (a_{i + 1}, b_{i + 1}) = (((a_{i + 1} \oplus k_{i}) ⊟_{\frac{m}{2}} (a_{i + 1} \oplus b_{i + 1}) ⋙ β) ⋘ α$ , $(a_{i + 1} \oplus b_{i + 1}) ⋙ β)$ , where $a_{i + 1}$ and $b_{i + 1}$ are the $\frac{m}{2}$ -bit outputs of the $(i + 1)$ th round. The $(i + 1)$ th round function of ${SPECK}_{m, n}$ is shown in Fig. 1. There are 10 choices for the pair (m, n) and the parameters r, α and β corresponding to each of them are given in Table 3. ${SPECK}_{m, n}$ operates in 3 phases: key expansion, encryption and decryption.

Fig. 1.

The $(i + 1)$ th round of ${SPECK}_{m, n}$ .

Table 3

Parameters of ${SPECK}_{m, n}$

$(m, n)$	r	α	β
$(32, 64)$	22	7	2
$(48, 72)$	22	8	3
$(48, 96)$	23	8	3
$(64, 96)$	26	8	3
$(64, 128)$	27	8	3
$(96, 96)$	28	8	3
$(96, 144)$	29	8	3
$(128, 128)$	32	8	3
$(128, 192)$	33	8	3
$(128, 256)$	34	8	3

Key expansion. The key schedule algorithm (Algorithm 1) takes K as input and generates the subkeys $k_{0}, k_{1}, \dots, k_{r - 1}$ .

Algorithm 1

Key schedule of ${SPECK}_{m, n}$

Encryption. The encryption algorithm (Algorithm 2) takes as inputs $k_{0}, k_{1}, \dots, k_{r - 1}$ and the plaintext block $P_{1} ∥ P_{2}$ and generates the ciphertext block $C_{1} ∥ C_{2}$ ( $P_{1}$ , $P_{2}$ , $C_{1}$ and $C_{2}$ are $\frac{m}{2}$ -bit words).

Algorithm 2

Encryption of ${SPECK}_{m, n}$

Decryption. The decryption algorithm (Algorithm 3) takes as inputs $k_{0}, k_{1}, \dots, k_{r - 1}$ and the ciphertext block $C_{1} ∥ C_{2}$ and generates the plaintext block $P_{1} ∥ P_{2}$ .

Algorithm 3

Decryption of ${SPECK}_{m, n}$

3. Motivational observation

The final round of encryption of ${SPECK}_{32, 64}$ is shown in Fig. 2. Let x and y, which are distributed uniformly at random, be the inputs to the modular addition in the final round of ${SPECK}_{32, 64}$ , z be the sum of x and y modulo $2^{16}$ , $c_{i + 1}$ be the carry generated at the $(i + 1)$ th bit position of the addition modulo operation, where $0 ⩽ i ⩽ 15$ (for instance, outgoing carry at the LSB position is denoted by $c_{1}$ ), $c_{out}$ be the carry flag at the end of the encryption and $C_{1} ∥ C_{2}$ be the ciphertext block generated. We assume that $c_{out}$ equals $c_{16}$ . The allowed values of the Boolean variables $x_{(i)}$ , $y_{(i)}$ , $c_{i}$ , $z_{(i)}$ and $c_{i + 1}$ are tabulated in Table 4. The truth table clearly shows that $c_{i}$ and $z_{(i)} \oplus 1$ are biased towards $c_{i + 1}$ .

Fig. 2.

Final round of encryption of ${SPECK}_{32, 64}$ .

Table 4

Truth table showing the allowed values of the Boolean variables $x_{(i)}$ , $y_{(i)}$ , $c_{i}$ , $z_{(i)}$ and $c_{i + 1}$

$x_{(i)}$	$y_{(i)}$	$c_{i}$	$z_{(i)}$	$c_{i + 1}$
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Based on this observation, we compute the bias of $z_{(i)} \oplus 1$ towards $c_{out}$ for any $i \in {15, 14, \dots, 0}$ . It is reasonable to assume that $x_{(i)}$ , $y_{(i)}$ and $c_{i}$ are independent, and all the possible outcomes given in Table 4 are mutually exclusive. Let $Pr (x_{(i)} = 0) = Pr (y_{(i)} = 0) = \frac{1}{2}$ and $Pr (c_{i} = 0) = ρ_{i}$ . From Table 4, we deduce the following: $\begin{array}{l} (1) & Pr (c_{i} \oplus c_{i + 1} = 0) = 3 \cdot \frac{ρ_{i}}{4} + 3 \cdot \frac{1 - ρ_{i}}{4} = \frac{3}{4}, \\ (2) & Pr (z_{(i)} \oplus c_{i + 1} = 1) = 3 \cdot \frac{ρ_{i}}{4} + 3 \cdot \frac{1 - ρ_{i}}{4} = \frac{3}{4} . \end{array}$ Let $Pr (c_{i + 1} \oplus c_{out} = 0) = q_{i + 1}$ . From (1) and (2), we get: $\begin{array}{l} (3) & \begin{matrix} Pr (c_{i} \oplus c_{out} = 0) & = Pr (c_{i} \oplus c_{i + 1} = 0) \cdot Pr (c_{i + 1} \oplus c_{out} = 0) \\ + Pr (c_{i} \oplus c_{i + 1} = 1) \cdot Pr (c_{i + 1} \oplus c_{out} = 1) \\ = \frac{3}{4} q_{i + 1} + \frac{1}{4} (1 - q_{i + 1}) \\ = \frac{2 q_{i + 1} + 1}{4}, \end{matrix} \\ (4) & \begin{matrix} Pr (z_{(i)} \oplus c_{out} = 1) & = Pr (z_{(i)} \oplus c_{i + 1} = 1) \cdot Pr (c_{i + 1} \oplus c_{out} = 0) \\ + Pr (z_{(i)} \oplus c_{i + 1} = 0) \cdot Pr (c_{i + 1} \oplus c_{out} = 1) \\ = \frac{3}{4} q_{i + 1} + \frac{1}{4} (1 - q_{i + 1}) \\ = \frac{2 q_{i + 1} + 1}{4} . \end{matrix} \end{array}$ Since $c_{16} = c_{out}$ , we get: $\begin{array}{l} (5) & Pr (z_{(15)} \oplus c_{out} = 1) = \frac{3}{4}, \\ (6) & Pr (c_{15} \oplus c_{out} = 0) = \frac{3}{4} . \end{array}$ Equations (3), (4) and (6) gives: $\begin{array}{l} (7) & Pr (z_{(14)} \oplus c_{out} = 1) = \frac{5}{8}, \\ (8) & Pr (c_{14} \oplus c_{out} = 0) = \frac{5}{8} . \end{array}$ Similarly, probabilities that $z_{(i)} \oplus c_{out} = 1$ for the remaining values of i can be computed by recursively applying (3) and (4), and are tabulated in Table 5.

Table 5

Probabilities that $z_{(i)} \oplus c_{out} = 1$ , for $15 ⩾ i ⩾ 0$ , in ${SPECK}_{32, 64}$

i	$Pr (z_{(i)} \oplus c_{out} = 1)$
15	$0.5 + 2^{- 2}$
14	$0.5 + 2^{- 3}$
13	$0.5 + 2^{- 4}$
12	$0.5 + 2^{- 5}$
11	$0.5 + 2^{- 6}$
10	$0.5 + 2^{- 7}$
9	$0.5 + 2^{- 8}$
8	$0.5 + 2^{- 9}$
7	$0.5 + 2^{- 10}$
6	$0.5 + 2^{- 11}$
5	$0.5 + 2^{- 12}$
4	$0.5 + 2^{- 13}$
3	$0.5 + 2^{- 14}$
2	$0.5 + 2^{- 15}$
1	$0.5 + 2^{- 16}$
0	$0.5 + 2^{- 17}$

4. Key recovery

In this section, we will see how an attacker, who has access to the encryption device of ${SPECK}_{32, 64}$ , exploits the bias present in the distribution of $z_{(i)} \oplus c_{out}$ to recover K with a complexity lesser than that of exhaustive search. At the end of each encryption, the attacker observes the ciphertext as well as the carry flag. Then she makes a guess ${\hat{k}}_{21 (i)}$ for $k_{21 (i)}$ , where $15 ⩾ i ⩾ 0$ . Based on the guess, she computes ${\hat{z}}_{(i)} : = C_{1 (i)} \oplus {\hat{k}}_{21 (i)}$ and in turn $b_{i} : = {\hat{z}}_{(i)} \oplus c_{out}$ . Since $z_{(i)} \oplus c_{out}$ is biased towards 1, her guess will be right only when $b_{i}$ is also biased towards 1.

Let N denote the number of $b_{i}$ ’s available to the attacker (collected from different cipher texts), $β_{i}$ denote the distribution of $B_{i} : = \sum_{N} b_{i}$ , $p_{i} = Pr (b_{i} = 1)$ , $β_{i}^{'}$ denote the distribution of $B_{i}$ if $b_{i}$ ’s were biased towards 0 and $p_{i}^{'} = 1 - p_{i}$ . For any given i, if the $b_{i}$ ’s are independent and identically distributed random variables (i.i.d.) then $B_{i}$ has a binomial distribution. The means ( $μ_{i}$ , $μ_{i}^{'}$ ) and standard deviations ( $σ_{i}$ , $σ_{i}^{'}$ ) of the distributions $β_{i}$ , $β_{i}^{'}$ are given by: $μ_{i} = N p_{i}$ , $μ_{i}^{'} = N p_{i}^{'}$ , $σ_{i} = \sqrt{N p_{i} (1 - p_{i})}$ and $σ_{i}^{'} = \sqrt{N p_{i}^{'} (1 - p_{i}^{'})}$ . If N is large, one can approximate each binomial distribution with the normal distribution having the same mean and standard deviation.

Given this, if $| μ_{i} - μ_{i}^{'} | > t_{i} (σ_{i} + σ_{i}^{'}) ⟹ N > 0.25 {t_{i}}^{2} / {(p_{i} - 0.5)}^{2}$ , the attacker can determine whether $b_{i}$ is biased towards 1 or 0 with success probability $ω_{i}$ , where $ω_{i}$ is the value given by the cumulative distribution function at $μ_{i} + t_{i} σ_{i}$ .1

¹
The cumulative distribution function $ϕ (x)$ of the standard normal distribution is given by $ϕ (x) = \frac{1}{\sqrt{2 π}} \int_{- \infty}^{x} e^{- t^{2} / 2} d t$ .

t_{i}

is 3.28, the bias can be determined with

99.99 %

success rate (since the cumulative distribution function gives the value 0.9999 at

μ_{i} + 3.62 σ_{i}

) and

0.01 %

false positive rate.2

Since $ϕ (\infty) = 1$ , 100% success rate will be theoretically possible only at ∞.

The number of samples required to determine if

b_{i}

is biased to 1 or 0, for any i such that

15 ⩾ i ⩾ 0

, with an upper bound

2^{32}

(since the block size is 32) are listed in Table 6. The attacker will be able to recover the 13 most significant bits of

k_{21}

with more than

99.99 %

success rate by observing

2^{29.7}

encryptions. The values of

p_{i} - 0.5

t_{i}

and the success probabilities

ω_{i}

, for any i such that

15 ⩾ i ⩾ 0

, when

N = 2^{30}

are listed in Table 7.

Table 6

Data requirements for ${SPECK}_{32, 64}$ (corresponding to 0.9999 success probability) to determine if $b_{i}$ is biased to 1 or 0, for $15 ⩾ i ⩾ 0$

i	${log}_{2} (# samples)$
15	5.7
14	7.7
13	9.7
12	11.7
11	13.7
10	15.7
9	17.7
8	19.7
7	21.7
6	23.7
5	25.7
4	27.7
3	29.7
2	31.7
1	32
0	32

Table 7

Values of $p_{i} - 0.5$ , $t_{i}$ and the success probabilities $ω_{i}$ corresponding to $N = 2^{30}$ , for $15 ⩾ i ⩾ 0$

i	$p_{i} - 0.5$	$t_{i}$	$ω_{i}$
15	$2^{- 2}$	16384	$\sim 1$
14	$2^{- 3}$	8192	$\sim 1$
13	$2^{- 4}$	4096	$\sim 1$
12	$2^{- 5}$	2048	$\sim 1$
11	$2^{- 6}$	1024	$\sim 1$
10	$2^{- 7}$	512	$\sim 1$
9	$2^{- 8}$	256	$\sim 1$
8	$2^{- 9}$	128	$\sim 1$
7	$2^{- 10}$	64	$\sim 1$
6	$2^{- 11}$	32	$\sim 1$
5	$2^{- 12}$	16	$\sim 1$
4	$2^{- 13}$	8	$\sim 1$
3	$2^{- 14}$	4	0.9999
2	$2^{- 15}$	2	0.9772
1	$2^{- 16}$	1	0.8413
0	$2^{- 17}$	0.5	0.6915

If $k_{21}$ , $k_{20}$ , $k_{19}$ and $k_{18}$ are known, the key schedule of ${SPECK}_{32, 64}$ can be reversed using Algorithm 4. Therefore, the unrecovered bits of $k_{21}$ along with $k_{20}$ , $k_{19}$ and $k_{18}$ can be obtained through brute force with a complexity of $2^{51}$ time which in turn leads to the recovery of K.

4.1. Experimental verification

Algorithm 4

Key recovery of ${SPECK}_{m, n}$

Algorithm 5

Subkey recovery of ${SPECK}_{32, 64}$

In order to verify our analysis, the attack on ${SPECK}_{32, 64}$ was simulated. We encrypted $2^{23}$ plaintext blocks generated uniformly at random using an arbitrary key and observed the output carry ( $c_{out}$ ) generated at the end of each encryption.3

The 64 least significant bits of $ξ_{κ} (C)$ form an arbitrary key (for e.g., 0x23f7290ff115eda1) where $ξ_{κ}$ is AES encryption function with a random key κ and C is some constant.

Using Algorithm 5, we set

k_{21 (i)}

as 0, where

15 ⩾ i ⩾ 0

, if

B_{i}

was lying within the confidence interval of

β_{i}

, or 1 otherwise.4

⁴

The critical value used to distinguish between $β_{i}$ and $β_{i}^{'}$ has to ensure that the confidence intervals of the distributions do not overlap.

This process was repeated

2 \times 10^{4}

times. The success rates at which we were able to recover each bit of the subkey are tabulated in Table 8. The C program which can be used to recover the 10 most significant bits of the final subkey of

{SPECK}_{32, 64}

is given in Fig. 3.

4.2. Reducing the time complexity of the attack

The time complexity of our attack can be reduced by utilising the information about the bias in the distribution of $z_{(i)} \oplus c_{out}$ while performing exhaustive search of the unrecovered bits of $k_{21}$ . For instance, if $2^{30}$ $b_{i}$ ’s are available to the attacker then the 13 most significant bits of $k_{21}$ can be recovered with $99.99 %$ success rate where as the recovery of $k_{21 (2)}$ , $k_{21 (1)}$ and $k_{21 (0)}$ will only have $97.72 %$ , $84.13 %$ and $69.15 %$ success rates, respectively (see Table 7). In other words, at least one of the three least significant bits of $k_{21}$ can be recovered with a success rate of $99.89 %$ or at least two of them can be recovered with $94.26 %$ success rate (see (9) and (10)). If we assume that one of the three least significant bits of $k_{21}$ computed using Algorithm 5 is correct, only 7 out of the 8 possible choices of the three bits need to be checked while doing brute force. Similarly, exhaustive search can be limited to 4 out of the 8 possible choices, if it is assumed that any two out of the three least significant bits have been correctly computed. Therefore, the time complexity of the full key recovery attack can be reduced to a factor of $\frac{7}{8}$ with $99.89 %$ success rate or to a factor of $\frac{1}{2}$ with $94.26 %$ success rate. In order to prevent collision attacks [9], designers recommend that “the number of blocks encrypted using a single key for an n-bit block cipher should be kept well under $2^{\frac{n}{2}}$ ” [5]. Taking this into consideration, it is assumed that $2^{14}$ $b_{i}$ ’s are only available to the attacker which, in turn, will increase the time complexity of our attack.5

⁵
${SPECK}_{m, n}$ is assumed to encrypt at the most $2^{m / 2 - 2}$ blocks using a single key so that the collision probability will be below $2^{- 5}$ .

The remaining versions of SPECK can also be attacked similarly and the complexities of our attacks on

{SPECK}_{m, n}

for the success rates

99.99 %

99.89 %

and

94.26 %

are listed in Table 9.

\begin{array}{l} (9) & ω_{a} = 1 - ((1 - ω_{2}) (1 - ω_{1}) (1 - ω_{0})) = 0.9989, \\ (10) & \begin{matrix} ω_{b} & = 1 - ((1 - ω_{2}) (1 - ω_{1}) (1 - ω_{0})) - (ω_{2} (1 - ω_{1}) (1 - ω_{0})) \\ - ((1 - ω_{2}) ω_{1} (1 - ω_{0})) - ((1 - ω_{2}) (1 - ω_{1}) ω_{0}) = 0.9426 \end{matrix}, \end{array}

where

ω_{2}

ω_{1}

and

ω_{0}

are the success probabilities to recover

k_{21 (2)}

k_{21 (1)}

and

k_{21 (0)}

, respectively, and

ω_{a}

and

ω_{b}

are the success probabilities to recover at least one of them and at least two of them, respectively.

Table 8

Success rates of our experiments on ${SPECK}_{32, 64}$ to recover $k_{21 (i)}$ with $2^{23}$ samples, for $15 ⩾ i ⩾ 0$

i	Success rate (%)
15	100
14	100
13	100
12	100
11	100
10	100
9	100
8	100
7	100
6	99.84
5	92.28
4	75.91
3	62.98
2	57.17
1	54.09
0	49.72

Fig. 3.

Program to recover the 10 most significant bits of the final subkey of ${SPECK}_{32, 64}$ .

Table 9

Complexities of the full key recovery attacks on ${SPECK}_{m, n}$ corresponding to the success rates of 99.99%, 99.89% and 94.26%

	Success rate = 99.99%		Success rate = 99.89%		Success rate = 94.26%

Cipher	Data	Time	Data	Time	Data	Time
${SPECK}_{32, 64}$	$2^{14}$	$2^{59}$	$2^{14}$	$2^{58.81}$	$2^{14}$	$2^{58}$
${SPECK}_{48, 72}$	$2^{22}$	$2^{63}$	$2^{22}$	$2^{62.81}$	$2^{22}$	$2^{62}$
${SPECK}_{48, 96}$	$2^{22}$	$2^{87}$	$2^{22}$	$2^{86.81}$	$2^{22}$	$2^{86}$
${SPECK}_{64, 96}$	$2^{30}$	$2^{83}$	$2^{30}$	$2^{82.81}$	$2^{30}$	$2^{82}$
${SPECK}_{64, 128}$	$2^{30}$	$2^{115}$	$2^{30}$	$2^{114.81}$	$2^{30}$	$2^{114}$
${SPECK}_{96, 96}$	$2^{46}$	$2^{75}$	$2^{46}$	$2^{74.81}$	$2^{46}$	$2^{74}$
${SPECK}_{96, 144}$	$2^{46}$	$2^{123}$	$2^{46}$	$2^{122.81}$	$2^{46}$	$2^{122}$
${SPECK}_{128, 128}$	$2^{62}$	$2^{99}$	$2^{62}$	$2^{98.81}$	$2^{62}$	$2^{98}$
${SPECK}_{128, 192}$	$2^{62}$	$2^{163}$	$2^{62}$	$2^{162.81}$	$2^{62}$	$2^{162}$
${SPECK}_{128, 256}$	$2^{62}$	$2^{227}$	$2^{62}$	$2^{226.81}$	$2^{62}$	$2^{226}$

Fig. 4.

Final round of the key expansion phase of ${SPECK}_{32, 64}$ .

5. Attack on key schedule

In this section, we will see how the carry generated at the end of the key expansion phase can be exploited to reduce the complexity of our attack on ${SPECK}_{32, 64}$ . Since the round functions used in key schedule and encryption algorithms are the same, weakness similar to the one mentioned in Section 3 will be present in the key expansion phase too. The final round of the key expansion phase of ${SPECK}_{32, 64}$ is shown in Fig. 4. Let x and y, which are distributed uniformly at random, be the inputs to the modular addition in the final round of the key schedule, z be the sum of x and y modulo $2^{16}$ , $c_{i + 1}$ be the carry generated at the $(i + 1)$ th bit position of the addition modulo operation, where $0 ⩽ i ⩽ 15$ (for example, outgoing carry at the LSB position is denoted by $c_{1}$ ), and $d_{out}$ be the carry flag at the end of the key schedule. The allowed values of the Boolean variables $x_{(i)}$ , $y_{(i)}$ , $c_{i}$ , $z_{(i)}$ and $c_{i + 1}$ are same as those tabulated in Table 4 and from it, we find that $Pr (y_{(i)} = c_{i + 1}) = \frac{3}{4}$ . We assume that $d_{out}$ equals $c_{16}$ and therefore we get, $Pr (y_{(15)} = d_{out}) = \frac{3}{4}$ . In other words, if the attacker is able to observe the carry flag at the end of key expansion phase, the most significant bit of $y = k_{20}$ can be recovered immediately with a success rate of $75 %$ . Combining this information with the attack of Section 4.2, we deduce that from the set of bits including $k_{20 (15)}$ and the three least significant unknown bits of $k_{21}$ , any one can be recovered with $99.97 %$ success rate, any two bits can be recovered with $98.48 %$ success rate or any three bits can be recovered with $84.91 %$ success rate. Similar attacks can be built on the remaining versions of SPECK too. The complexities of the key recovery attacks on ${SPECK}_{m, n}$ corresponding to the success rates of $99.97 %$ , $98.48 %$ and $84.91 %$ are listed in Table 10.6

⁶
Data requirements are same as those listed in Table 9.

Table 10

Complexities of the full key recovery attacks on ${SPECK}_{m, n}$ corresponding to the success rates of 99.97%, 98.48% and 84.91%, under the assumption that the carry flag at the end of the key expansion phase is known

	Success rate = 99.97%		Success rate = 98.48%		Success rate = 84.91%

Cipher	Data	Time	Data	Time	Data	Time
${SPECK}_{32, 64}$	$2^{14}$	$2^{58.9}$	$2^{14}$	$2^{58.46}$	$2^{14}$	$2^{57.32}$
${SPECK}_{48, 72}$	$2^{22}$	$2^{62.9}$	$2^{22}$	$2^{62.46}$	$2^{22}$	$2^{61.32}$
${SPECK}_{48, 96}$	$2^{22}$	$2^{86.9}$	$2^{22}$	$2^{86.46}$	$2^{22}$	$2^{85.32}$
${SPECK}_{64, 96}$	$2^{30}$	$2^{82.9}$	$2^{30}$	$2^{82.46}$	$2^{30}$	$2^{81.32}$
${SPECK}_{64, 128}$	$2^{30}$	$2^{114.9}$	$2^{30}$	$2^{114.46}$	$2^{30}$	$2^{113.32}$
${SPECK}_{96, 96}$	$2^{46}$	$2^{74.9}$	$2^{46}$	$2^{74.46}$	$2^{46}$	$2^{73.32}$
${SPECK}_{96, 144}$	$2^{46}$	$2^{122.9}$	$2^{46}$	$2^{122.46}$	$2^{46}$	$2^{121.32}$
${SPECK}_{128, 128}$	$2^{62}$	$2^{98.9}$	$2^{62}$	$2^{98.46}$	$2^{62}$	$2^{97.32}$
${SPECK}_{128, 192}$	$2^{62}$	$2^{162.9}$	$2^{62}$	$2^{162.46}$	$2^{62}$	$2^{161.32}$
${SPECK}_{128, 256}$	$2^{62}$	$2^{226.9}$	$2^{62}$	$2^{226.46}$	$2^{62}$	$2^{225.32}$

6. Discussion

Vulnerable implementations. The attacks presented in this paper are based on one of the following adversarial assumptions:

AA1: The outgoing carries at the MSB position of modular additions in the final round of encryption phase and key expansion phase agree with the carry flags at the end of the respective phases, and the attacker can detect them.

AA2: The attacker can detect the bit-flips in the carry flag after the modular addition of the final round of encryption phase.

In [4], Beaulieu et al. presented a one-bit-per-clock implementation of SPECK on ASIC in which the modular addition is implemented using a full adder circuit with a carry flag. From this reference implementation, it is inferred that the carry flag is not altered after the modular addition making it vulnerable to our attack as per AA1.

Based on the reference pseudocode provided in [8], SPECK can have two types of software implementations which we call Implementation A and Implementation B. The pseudocodes of the final rounds of the two software implementations of SPECK are given in Table 11. The left circular shift operation that follows the modular addition in Implementation A alters the carry flag making it invulnerable going by AA1. A possible way to keep the carry flag unaffected after the targeted modular addition is to skip the processor instructions related to the left circular shift operation of the final round by introducing timing or voltage glitches as presented in [34,46]. Since the skipped instructions do not affect $C_{1}$ , our attack still works.

Table 11
Pseudocodes of the final rounds of the two software implementations of SPECK, where r is the number of rounds and $(x, y)$ are the inputs to the final round

Implementation A Implementation B

1: $x \leftarrow (x ⋙ α)$ 1: $x \leftarrow (x ⋙ α)$

2: $x \leftarrow x + y$ 2: $t m p \leftarrow (y ⋘ β)$

3: $x \leftarrow x \oplus k_{r - 1}$ 3: $x \leftarrow x + y$

4: $y \leftarrow (y ⋘ β)$ 4: $x \leftarrow x \oplus k_{r - 1}$

5: $y \leftarrow y \oplus x$ 5: $y \leftarrow t m p \oplus x$

6: $(C_{1}, C_{2}) \leftarrow (x, y)$ 6: $(C_{1}, C_{2}) \leftarrow (x, y)$

Implementation A	Implementation B
1: $x \leftarrow (x ⋙ α)$	1: $x \leftarrow (x ⋙ α)$
2: $x \leftarrow x + y$	2: $t m p \leftarrow (y ⋘ β)$
3: $x \leftarrow x \oplus k_{r - 1}$	3: $x \leftarrow x + y$
4: $y \leftarrow (y ⋘ β)$	4: $x \leftarrow x \oplus k_{r - 1}$
5: $y \leftarrow y \oplus x$	5: $y \leftarrow t m p \oplus x$
6: $(C_{1}, C_{2}) \leftarrow (x, y)$	6: $(C_{1}, C_{2}) \leftarrow (x, y)$

To validate it, we compiled the reference implementation of SPECK for 8-bit AVR microcontrollers [7], which is a secure implementation as per AA1, available at the University of Luxembourg Fair Evaluation of Lightweight Cryptographic Systems (FELICS) project [13] after manually removing the processor instructions related to the left circular shift operation of the final round. The execution of the generated hex file in Atmega128 microcontroller was simulated using the AVR simulator simavr and we could confirm that the outgoing carry at the MSB position of modular addition in the final round agrees with the carry flag at the end of encryption as shown in Fig. 5. Since both the implementations provided in Table 11 generate the same output, malicious updating of the microcontroller firmware to include the vulnerable code might remain undetected leading to another possible way to attack an otherwise secure implementation.

Fig. 5.

Simulation of the SPECK implementation for AVR microcontrollers available in the FELICS project [13] to confirm that the outgoing carry at the MSB position of modular addition in the final round agrees with the carry flag at the end of encryption, if the left circular shift operation of the final round is skipped.

The attacker who observes the ciphertext block $C_{1} ∥ C_{2}$ can compute the input to the left circular shift operation as $(C_{1} \oplus C_{2}) ⋙ β$ . If the input is known, she can compute the carry flag at the end of left circular shift. If AA2 is valid, the attacker detects the bit-flips in the carry flag during the left circular shift operation and rightly guesses the outgoing carry of the modular addition. This makes the reference implementation [7] vulnerable, which was secure according to AA1. Nevertheless, going by AA2, the key expansion phase of SPECK cannot be attacked as $l_{r + 1}$ is unknown (see Fig. 4).

Since ${SPECK}_{m, n}$ is intended to be implemented on 8-, 16- and 32-bit microcontrollers [6], the operation $⊞_{\frac{m}{2}}$ will be performed using 8-, 16- and 32-bit additions, respectively. To perform the operation $⊞_{\frac{m}{2}}$ on an ℓ-bit microcontroller, $\frac{m}{2 ℓ}$ ℓ-bit additions, starting from the ℓ least significant bits to the ℓ most significant bits, are required. The final addition will not set the carry flag unless $\frac{m}{2}$ is a multiple of ℓ. Therefore, the assumptions used in this paper will be valid only when ${SPECK}_{m, n}$ is implemented on an ℓ-bit microcontroller where $\frac{m}{2}$ is a multiple of ℓ. The SPECK implementations which are vulnerable to our attacks are listed in Table 12. The possibility of implementing ${SPECK}_{m, n}$ in 64-bit platforms also has been discussed by the designers [6]; in such cases, if 64-bit accumulators are used, ciphers with a block size of 128 bits alone are vulnerable. If the flash memory is large enough to store the round keys, ${SPECK}_{m, n}$ can be implemented without the key expansion phase as suggested by the designers in [7]. In such implementations, our attack on the key schedule as given in Section 5 will not work.

Table 12

Vulnerability of ${SPECK}_{m, n}$ when implemented on ℓ-bit microcontroller, where $ℓ = 8, 16$ or 32

Cipher	$ℓ = 8$	$ℓ = 16$	$ℓ = 32$
${SPECK}_{32, 64}$	Yes	Yes	No
${SPECK}_{48, 72}$	Yes	No	No
${SPECK}_{48, 96}$	Yes	No	No
${SPECK}_{64, 96}$	Yes	Yes	Yes
${SPECK}_{64, 128}$	Yes	Yes	Yes
${SPECK}_{96, 96}$	Yes	Yes	No
${SPECK}_{96, 144}$	Yes	Yes	No
${SPECK}_{128, 128}$	Yes	Yes	Yes
${SPECK}_{128, 192}$	Yes	Yes	Yes
${SPECK}_{128, 256}$	Yes	Yes	Yes

Detecting the carry flag. The success of our attack solely depends on the chances of the adversary to read the carry flag at the end of a key expansion or encryption phase, if we are going by AA1. A complete treatment of the side channel techniques used to obtain the carry flag is beyond the scope of this paper. Nevertheless, we would like to highlight the following methods. An adversary who has the necessary privileges to execute any code of his choice in the encryption device will be able to detect the carry flag by executing the add with carry (ADC) instruction [3] soon after the key expansion or encryption phase. Return-oriented programming is a possible technique that can be used to execute a chosen instruction in the encryption device [37,43,44]. The only challenge will be to execute the code in the same core where the encryption program runs, if it is a multicore processing device, and before the carry flag is potentially affected by any other operation.

Another possible method is to exploit the electromagnetic side channel of the encryption device to detect the carry flag. In [23], Heyszl et al. presented a technique to distinguish the activities of registers by precisely measuring the electromagnetic field of small regions on integrated circuits using high resolution inductive probes. Also, it is practically feasible to distinguish between $0 \to 1$ and $1 \to 0$ bit transitions in certain implementations using electromagnetic analysis [35,39]. Therefore, the attacker can analyse the electromagnetic field of the flag register to detect if the carry flag got set or reset during modular addition.

In [17], Fouque et al. demonstrated an attack on an implementation of HMAC-SHA-1 for a NIOS processor, where the electromagnetic side channel was used to measure the number of bits flipped in a register. The same technique when applied on the flag register enables the attacker to detect the bit-flips in the carry flag, which validates AA2. Yet another method is to inject a fault during the computation of the carry, as explained by Fouque et al. [18] to get the carry information.

Improving the attack. Our work is originally motivated by the following remark due to Kelsey et al. [28]: “There may be cases when we can learn the state of the overflow or carry flag during encryption; if so, this can form a useful side channel. [I]t demonstrates a useful feature of side-channel cryptanalysis: the side-channel can give information about the operations performed instead of the values used. This can work even when the information about the operation yields only minimal information about the values themselves.” It is possible that the attacker has access to other flags too. Overflow and parity flags, in some cases, help reduce the time complexities of our attacks by a factor of four.7

⁷

In an ℓ-bit accumulator, a carry in the $(ℓ - 1)$ th bit sets overflow flag. Carry flag is set when there is an outgoing carry at the MSB position whereas overflow flag is set when there is an incoming carry at the MSB position. Parity flag indicates if the number of ones in the binary representation of the result of the last operation is odd or even.

Another way to improve our attacks is to involve the penultimate round(s). For instance, let us assume that an unprotected implementation of ${SPECK}_{32, 64}$ uses an 8-bit accumulator and the attacker can investigate the four additions from last two rounds. The two penultimate rounds of ${SPECK}_{32, 64}$ are shown in Fig. 6. Let x and y be the inputs to the modular addition in the final round and z be its output. As explained in Section 4, by observing $2^{14}$ encryptions and the corresponding carries generated from $F_{0} (x) + F_{0} (y)$ and $F_{1} (x) + F_{1} (y)$ , five most significant bits of $F_{0} (k_{21})$ and $F_{1} (k_{21})$ can be recovered with $99.99 %$ success rate.

Fig. 6.

Last two rounds of encryption of ${SPECK}_{32, 64}$ .

Using $z = C_{1} \oplus k_{21}$ , five most significant bits of $F_{0} (z)$ and $F_{1} (z)$ can be computed and y is given by $(C_{1} \oplus C_{2}) ⋙ 2$ . Let $x_{u, 5}$ , $y_{u, 5}$ and $z_{u, 5}$ be the five most significant bits of $F_{1} (x)$ , $F_{1} (y)$ and $F_{1} (z)$ , respectively. If ${\hat{x}}_{u, 5}$ denotes $(c_{out} ∥ z_{u, 5}) - y_{u, 5}$ then $x_{u, 5}$ equals ${\hat{x}}_{u, 5} + c_{in}$ , where $c_{out}$ and $c_{in}$ are the carries generated at the 8th and 3rd bit positions of $x_{u} + y_{u}$ , respectively. The four most significant bits of ${\hat{x}}_{u, 5}$ and $x_{u, 5}$ will be equal when the least significant bit of ${\hat{x}}_{u, 5}$ is 0. Since this occurs with probability 0.5, under the assumption that ${\hat{x}}_{u, 5}$ is distributed uniformly at random, in $2^{13}$ out of the $2^{14}$ encryptions observed, we can compute the four most significant bits of $x_{u, 5}$ with $99.99 %$ success rate. Since $C_{1}^{'} = x ⋘ 7$ , where $C_{1}^{'} ∥ C_{2}^{'}$ is the output of the 21st round of ${SPECK}_{32, 64}$ , we get the four bits of $F_{0} (C_{1}^{'})$ corresponding to the known bits of $x_{u, 5}$ . If V represents the known bits and U represents the unknown bits, $F_{0} (C_{1}^{'})$ can be represented as $U V V V V U U U$ in $2^{13}$ encryptions. In each of these encryptions, if the carry flag after the first addition of the 21st round is known then the three bits of $F_{0} (k_{20})$ corresponding to the three most significant known bits of $F_{0} (C_{1}^{'})$ can be recovered with $99.99 %$ success rate.8

⁸

By observing $2^{13}$ encryptions, at the most four bits of $F_{0} (k_{20})$ can be recovered with $99.99 %$ success rate, given that the four most significant bits of $F_{0} (C_{1}^{'})$ are known.

Similar analysis can be used to recover 3 bits of $F_{1} (k_{20})$ . Thus 16 bits of the 64-bit key can be recovered with $99.99 %$ success rate by observing $2^{14}$ encryptions. When the overflow flag information is also exploited, 20 bits of the key can be recovered with the same success rate and complexity.

Countermeasure. A simple method to preclude our attack is to mask the carries generated at the end of the key expansion and encryption phases by introducing low-cost arithmetic operations after step 8 and step 7 of Algorithms 1 and 2, respectively, which permanently set or clear the carry flag. However, the approach fails if the attack model assumes that the attacker can determine the carry flag at any stage of execution of the code or skip the arithmetic operation introduced to mask the outgoing carry of the modular addition.

7. Conclusion

In this paper, we have shown side channel attacks on the SPECK family of block ciphers which is an ISO/IEC standard for RFID devices. Our attacks are applicable on the full ciphers. Although there are a few fault attacks which work on the full SPECK, our attacks are comparatively more feasible due to the weaker assumptions we make. The data requirements for our attacks are well below the respective birthday bounds. Depending on the key size and block size, the complexities of our attacks, to nearly ensure success, vary from $2^{59}$ time and $2^{14}$ data to $2^{227}$ time and $2^{62}$ data. Since the vulnerability of the cipher to our attack depends on the way it is implemented, the details of the vulnerable implementations have also been provided. We have also proposed a countermeasure to preclude our attacks.

References

Abed,

List,

Lucks and

Wenzel, Differential Cryptanalysis of Round-Reduced SIMON and SPECK, in: International Workshop on Fast Software Encryption, Proceedings of FSE 2014, LNCS, Vol. 8540, 2015, pp. 525–545.

Atmel: Atmel AVR 32 Architecture Document, 2011, available at: http://ww1.microchip.com/downloads/en/DeviceDoc/doc32000.pdf.

Atmel: Atmel AVR Instruction Set Manual [OTHER], 2016, available at: http://ww1.microchip.com/downloads/en/DeviceDoc/Atmel-0856-AVR-Instruction-Set-Manual.pdf.

Beaulieu,

Shors,

Smith,

Treatman-Clark,

Weeks and

Wingers, Implementation and Performance of the SIMON and SPECK Lightweight Block Ciphers on ASICs, 2016, available at: https://nsacyber.github.io/simon-speck/papers/simon-speck-asic-2014.pdf.

Beaulieu,

Shors,

Smith,

Treatman-Clark,

Weeks and

Wingers, Notes on the design and analysis of SIMON and SPECK, in: Cryptology ePrint Archive, Report 2017/560, 2017, available at: http://eprint.iacr.org/2017/560.

Beaulieu,

Shors,

Smith,

Treatman-Clark,

Weeks and

Wingers, SIMON and SPECK: Block Ciphers for the Internet of Things, in: NIST Lightweight Cryptography Workshop, 2015, available at: https://csrc.nist.gov/csrc/media/events/lightweight-cryptography-workshop-2015/documents/papers/session1-shors-paper.pdf.

Beaulieu,

Shors,

Smith,

Treatman-Clark,

Weeks and

Wingers, The SIMON and SPECK Block Ciphers on AVR 8-Bit Microcontrollers, in: International Workshop on Lightweight Cryptography for Security and Privacy, Proceedings of LightSec 2014, LNCS, Vol. 8898, 2015, pp. 3–20.

Beaulieu,

Shors,

Smith,

Treatman-Clark,

Weeks and

Wingers, The SIMON and SPECK Families of Lightweight Block Ciphers, in: Cryptology ePrint Archive, Report 2013/404, 2013, available at: http://eprint.iacr.org/2013/404.

Bhargavan and

Leurent, On the Practical (In-)Security of 64-bit Block Ciphers: Collision Attacks on HTTP over TLS and OpenVPN, in: ACM SIGSAC Conference on Computer and Communications Security, Proceedings of CCS, Vol. 2016, 2016, pp. 456–467.

10.

Biryukov,

Roy and

Velichkov, Differential Analysis of Block Ciphers SIMON and SPECK, in: International Workshop on Fast Software Encryption, Proceedings of FSE 2014, LNCS, Vol. 8540, 2015, pp. 546–570.

11.

Coutinho,

R.T.

De Sousa and

Borges, Continuous Diffusion Analysis, IEEE Access 8 (2020), 123735–123745. doi:10.1109/ACCESS.2020.3005504.

12.

Crypto API Dev: Crypto: Speck – remove Speck, 2018, available at: https://git.kernel.org/pub/scm/linux/kernel/git/herbert/cryptodev-2.6.git/commit/?anzwix=1&id=578bdaabd015b9b164842c3e8ace9802f38e7ecc.

13.

Dinu,

Biryukov,

Großschädl,

Khovratovich,

Y.L.

Corre and

Perrin, FELICS – Fair Evaluation of Lightweight Cryptographic Systems, in: NIST Lightweight Cryptography Workshop, 2015, available at: https://www.cryptolux.org/images/8/80/Session7-dinu-paper.pdf.

14.

Dinur, Improved Differential Cryptanalysis of Round-Reduced Speck, in: International Workshop on Selected Areas in Cryptography, Proceedings of SAC 2014, LNCS, Vol. 8781, 2014, pp. 147–164. doi:10.1007/978-3-319-13051-4_9.

15.

A.D.

Dwivedi,

Morawiecki and

Srivastava, Differential Cryptanalysis of Round-Reduced SPECK Suitable for Internet of Things Devices, IEEE Access 7 (2019), 16476–16486. doi:10.1109/ACCESS.2019.2894337.

16.

Feng,

Chen,

Gao,

Fan and

Feng, Improved Fault Analysis on the Block Cipher SPECK by Injecting Faults in the Same Round, in: International Conference on Information Security and Cryptology, Proceedings of ICISC 2016, LNCS, Vol. 10157, 2017, pp. 317–332. doi:10.1007/978-3-319-53177-9_17.

17.

P.A.

Fouque,

Leurent,

Réal and

Valette, Practical Electromagnetic Template Attack on HMAC, in: International Workshop on Cryptographic Hardware and Embedded Systems, Proceedings of CHES 2009, LNCS, Vol. 5747, 2009, pp. 66–80. doi:10.1007/978-3-642-04138-9_6.

18.

P.A.

Fouque,

Masgana and

Valette, Fault Attack on Schnorr Based Identification and Signature Schemes, in: Workshop on Fault Diagnosis and Tolerance in Cryptography, IEEE Proceedings of FDTC 2009, 2009, pp. 32–38. doi:10.1109/FDTC.2009.36.

19.

P.A.

Fouque,

Réal,

Valette and

Drissi, The Carry Leakage on the Randomized Exponent Countermeasure, in: International Workshop on Cryptographic Hardware and Embedded Systems, Proceedings of CHES 2008, LNCS, Vol. 5154, 2008, pp. 198–213. doi:10.1007/978-3-540-85053-3_13.

20.

Fu,

Wang,

Guo,

Sun and

Hu, MILP-Based Automatic Search Algorithms for Differential and Linear Trails for Speck, in: International Workshop on Fast Software Encryption, Proceedings of FSE 2016, LNCS, Vol. 9783, 2016, pp. 268–288.

21.

Ge,

Wang,

Zhu,

Liu,

Shang and

Zhang, Power Analysis and Protection on SPECK and Its Application in IoT, in: International Conference on Security and Privacy in Communication Networks, Proceedings of SecureComm 2019, LNICST, Vol. 305, 2019, pp. 350–362.

22.

Gomuffłkiewicz and

Kutyffłowski, Hamming Weight Attacks on Cryptographic Hardware — Breaking Masking Defense, in: European Symposium on Research in Computer Security, Proceedings of ESORICS 2002, LNCS, Vol. 2502, 2002, pp. 90–103. doi:10.1007/3-540-45853-0_6.

23.

Heyszl,

Mangard,

Heinz,

Stumpf and

Sigl, Localized Electromagnetic Analysis of Cryptographic Implementations, in: Cryptographers’ Track at the RSA Conference, Proceedings of CT-RSA 2012, LNCS, Vol. 7178, 2012, pp. 231–244.

24.

Hou,

Breier,

Zhang and

Liu, Fully Automated Differential Fault Analysis on Software Implementations of Block Ciphers, IACR Transactions on Cryptographic Hardware and Embedded Systems 2019(3) (2019), 1–29.

25.

Huang and

Wang, Automatic Search for the Linear (Hull) Characteristics of ARX Ciphers: Applied to SPECK, SPARX, Chaskey, and CHAM-64, in: Security and Communication Networks 2020, 2020, available at: https://www.hindawi.com/journals/scn/2020/4898612/.

26.

Huo,

Zhang,

Feng and

Wang, Improved Differential Fault Attack on the Block Cipher SPECK, in: IEEE Workshop on Fault Diagnosis and Tolerance in Cryptography, Proceedings of FDTC 2015, 2015, pp. 28–34.

27.

International Organization for Standardization: ISO/IEC 29167-22:2018, 2018, available at: https://www.iso.org/standard/70389.html.

28.

Kelsey,

Schneier,

Wagner and

Hall, Side Channel Cryptanalysis of Product Ciphers, Journal of Computer Security 8(2,3) (2000), 141–158. doi:10.3233/JCS-2000-82-304.

29.

U.M.

Khokhar, Deep Learning-Based Cryptanalysis of Lightweight Block Ciphers, in: Security and Communication Networks 2020, 2020, available at: https://www.hindawi.com/journals/scn/2020/3701067/.

30.

Kim,

Kwon and

Song, Efficient Computation of Boomerang Connection Probability for ARX-Based Block Ciphers with Application to SPECK and LEA, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E103.A(4) (2020), 677–685. doi:10.1587/transfun.2019EAP1083.

31.

Li,

Guo,

Cui and

Xu, Impossible Differential Cryptanalysis of SPECK, in: Chinese Conference on Trusted Computing and Information Security, Proceedings of CTCIS 2018, CCIS, Vol. 960, 2019, pp. 16–31.

32.

Linux kernel source tree: Crypto: Speck – add support for the Speck block cipher, 2018, available at: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=da7a0ab5b4babbe5d7a46f852582be06a00a28f0.

33.

Liu,

De Witte,

Ranea and

Ashur, Rotational-XOR Cryptanalysis of Reduced-round SPECK, IACR Transactions on Symmetric Cryptology 2017(3) (2017), 24–36.

34.

Nashimoto,

Homma,

Hayashi,

Takahashi,

Fuji and

Aoki, Buffer overflow attack with multiple fault injection and a proven countermeasure, Journal of Cryptographic Engineering 7 (2017), 35–46. doi:10.1007/s13389-016-0136-3.

35.

Peeters,

F.X.

Standaert and

J.J.

Quisquater, Power and electromagnetic analysis: Improved model, consequences and comparisons, Integration 40(1) (2007), 52–60. doi:10.1016/j.vlsi.2005.12.013.

36.

Phoronix: Google Decides Not To Use Speck For Disk Encryption, Instead Developing HPolyC, 2018, available at: https://www.phoronix.com/scan.php?page=news_item&px=No-Speck-Yes-HPolyC-Encryption.

37.

Prandini and

Ramilli, Return-Oriented Programming, IEEE Security & Privacy 10(6) (2012), 84–87. doi:10.1109/MSP.2012.152.

38.

Ren and

Chen, Cryptanalysis of Reduced-Round SPECK, IEEE Access 7 (2019), 63045–63056. doi:10.1109/ACCESS.2019.2917015.

39.

Sayakkara,

N.A.

Le-Khac and

Scanlon, A survey of electromagnetic side-channel attacks and discussion on their case-progressing potential for digital forensics, Digital Investigation 29 (2019), 43–54. doi:10.1016/j.diin.2019.03.002.

40.

Sekar, Side Channel Cryptanalysis of Streebog, in: International Conference on Research in Security Standardisation, Proceedings of SSR 2015, LNCS, Vol. 9497, 2015, pp. 154–162.

41.

Song,

Huang and

Yang, Automatic Differential Analysis of ARX Block Ciphers with Application to SPECK and LEA, in: Australasian Conference on Information Security and Privacy, Proceedings of ACISP 2016, LNCS, Vol. 9723, 2016, pp. 379–394.

42.

Tupsamudre,

Bisht and

Mukhopadhyay, Differential Fault Analysis on the Families of SIMON and SPECK Ciphers, in: IEEE Workshop on Fault Diagnosis and Tolerance in Cryptography, Proceedings of FDTC 2014, 2014, pp. 40–48.

43.

N.R.

Weidler,

Brown,

S.A.

Mitchel,

Anderson,

J.R.

Williams,

Costley,

Kunz,

Wilkinson,

Wehbe and

Gerdes, Return-Oriented Programming on a Cortex-M Processor, in: IEEE International Conference on Trust, Security and Privacy in Computing and Communications, Processings of IEEE Trustcom 2017, 2017, pp. 823–832.

44.

N.R.

Weidler,

Brown,

S.A.

Mitchell,

Anderson,

J.R.

Williams,

Costley,

Kunz,

Wilkinson,

Wehbe and

R.M.

Gerdes, Return-oriented programming on a resource constrained device, Sustainable Computing: Informatics and Systems 22 (2019), 244–256.

45.

Yuan,

Zhang and

Wu, Automatic Search for Linear Trails of the SPECK Family, in: Information Security Conference, Proceedings of ISC 2015, LNCS, Vol. 9290, 2015, pp. 158–176.

46.

Yuce,

Schaumont and

Witteman, Fault Attacks on Secure Embedded Software: Threats, Design, and Evaluation, Journal of Hardware and Systems Security 2 (2018), 111–130. doi:10.1007/s41635-018-0038-1.

Side channel analysis of SPECK

Abstract

Keywords

1. Introduction

1 The cumulative distribution function ϕ ( x ) of the standard normal distribution is given by ϕ ( x ) = 1 2 π ∫ − ∞ x e − t 2 / 2 d t .

5 SPECK m , n is assumed to encrypt at the most 2 m / 2 − 2 blocks using a single key so that the collision probability will be below 2 − 5 .

6 Data requirements are same as those listed in Table 9.

References

¹
The cumulative distribution function $ϕ (x)$ of the standard normal distribution is given by $ϕ (x) = \frac{1}{\sqrt{2 π}} \int_{- \infty}^{x} e^{- t^{2} / 2} d t$ .

⁵
${SPECK}_{m, n}$ is assumed to encrypt at the most $2^{m / 2 - 2}$ blocks using a single key so that the collision probability will be below $2^{- 5}$ .

⁶
Data requirements are same as those listed in Table 9.