CRYPTREC-EX-2601-2016

Security Analysis of ChaCha20-Poly1305 AEAD
KDDI Research, Inc.
February 2017

Contents
1 Executive Summary

2

2 Algorithm Description
2.1 ChaCha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Poly1305 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 ChaCha20-Poly1305 AEAD . . . . . . . . . . . . . . . . . . . . .

3
3
4
5

3 Security Analyses
3.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Analysis on ChaCha Structure . . . . . . . . . . . . . . . . . . .
3.2.1 Invertibility . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2 Structual difference from Salsa20 . . . . . . . . . . . . . .
3.3 Cryptanalysis on ChaCha . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Differential Analysis . . . . . . . . . . . . . . . . . . . . .
3.3.2 Linear Cryptanalysis and Distinguishing Attack . . . . . .
3.3.3 Guess and Determine Analysis . . . . . . . . . . . . . . .
3.3.4 Time-Memory-Data Tradeoff Attack . . . . . . . . . . . .
3.3.5 Algebraic Attack . . . . . . . . . . . . . . . . . . . . . . .
3.3.6 Attacks on Initialization Process . . . . . . . . . . . . . .
3.3.7 Analysis on Period . . . . . . . . . . . . . . . . . . . . . .
3.3.8 Side-Channel Attack . . . . . . . . . . . . . . . . . . . . .
3.4 Analysis on Poly1305 . . . . . . . . . . . . . . . . . . . . . . . . .
3.5 Analysis on ChaCha20-Poly1305 AEAD . . . . . . . . . . . . . .

7
7
7
8
8
10
10
18
18
19
19
20
20
21
25
26

4 Conclusion

32

1Chapter 1

Executive Summary
This report presents a security evaluation of the ChaCha20-Poly1305 Authenticated Encryption with Associated Data (AEAD). The combination of ChaCha
and Poly1305 is proved to be secure authenticated encryption scheme assuming
ChaCha and Poly1305 are secure algorithms. Additionally, Poly1305 is provento be ε-almost-∆-universal i.e., a secure universal hash function. We thus evaluate the security of ChaCha against existing attacks.
We showed that no efficient differential analysis, linear cryptanalysis anddistinguish attack, guess and determine analysis, algebraic attack, and attacks
on initialization process exist against ChaCha. Time-Memory-Data tradeoff
attack and side-channel attack apply to ChaCha; however, we can deal withthese attacks with practical countermeasures. We thus concluded that we canidentify no weaknesses in ChaCha20-Poly1305 AEAD.

2

Chapter 2

Algorithm Description
We describe the algorithm of ChaCha, Poly1305, and ChaCha20-Poly1305 AEAD.

2.1

ChaChaChaCha [NL15] operates on 32-bit words, takes as input a 256-bit key K =(k0 , k1 , k2 , k3 , k4 , k5 , k6 , k7 ) and a 32-bit counter C = (c0 ), and produces a sequence of 512-bit keystream blocks1 . This function acts on the 4 × 4 matrix of
32-bit words written as;
x0 x1 x2 x3
 x4 x5 x6 x7 X= x8 x9 x10 x11 
x12 x13 x14 x15

σ0 σ1 σ2 σ3
 k0 k1 k2 k3 =
 k4 k5 k6 k7 
c0 n0 n1 n2The σ and τ are constants where(τ0 , τ1 , τ2 , τ3 ) = (0x61707865, 0x3120646E, 0x79622D36, 0x6B206574)
and(σ0 , σ1 , σ2 , σ3 ) = (0x61707865, 0x3320646E, 0x79622D32, 0x6B206574).
The keystream block Z is defined as; Z = X + X (20) , where X (r) =Roundr (X) with the round function of ChaCha and + is word-wise addition
modulo 232 . If Z = X + X (r) , it is called “r-round ChaCha” or “ChaChar”.
The round function consists the following non-linear operations that are called
1 The original version of ChaCha [Ber08a] suport both 128-bit and 256-bit key. However,128-bit key is out of scope in the IETF version [NL15]. The nonce and counter have 64-bit
length and they are stored (x12 , x13 ) and (x14 , x15 ) respectively in the original version of
ChaCha.

3

Algorithm 1 ChaCha
Input: Key K, Counter C, and Nonce N
Output: Keystream Z
Generate initial matrix X using K, C, and Ny←X
for i ← 0 to 9 do/* Column Round */(x0 , x4 , x8 , x12 ) ← quarterround (x0 , x4 , x8 , x12 )(x5 , x9 , x13 , x1 ) ← quarterround (x5 , x9 , x13 , x1 )(x10 , x14 , x2 , x6 ) ← quarterround (x10 , x14 , x2 , x6 )(x15 , x3 , x7 , x11 ) ← quarterround (x15 , x3 , x7 , x11 )/* Diagonal Round */(x0 , x5 , x10 , x15 ) ← quarterround (x0 , x5 , x10 , x15 )(x1 , x6 , x11 , x12 ) ← quarterround (x1 , x6 , x11 , x12 )(x2 , x7 , x8 , x13 ) ← quarterround (x2 , x7 , x8 , x13 )(x3 , x4 , x9 , x14 ) ← quarterround (x3 , x4 , x9 , x14 )end forZ ←X +yreturn Z
quarter round functions. A vector (a, b, c, d) of four words is transformed as;
a=a+b
d=d⊕a
d = (d)≪16
c=c+d
b=b⊕c
b = (b)≪12
a=a+b
d=d⊕a
d = (d)≪8
c=c+d
b=b⊕c
b = (b)≪7
The quarter-round functions are applied to the columns (x0 , x4 , x8 , x12 ), (x5 , x9 , x13 , x1 ),(x10 , x14 , x2 , x6 ) and (x15 , x3 , x7 , x11 ) in odd round, and diagonals (x0 , x5 , x10 , x15 ),(x1 , x6 , x11 , x12 ), (x2 , x7 , x8 , x13 ) and (x3 , x4 , x9 , x14 ) in even rounds. Algorithm 1 describes the complete procedure of ChaCha.

2.2

Poly1305

Poly1305 [Ber05b] is a cryptographic message authentication code (MAC) proposed by Bernstein. The input to Poly1305 is a 256-bit one-time key and an
arbitrary-length message. The output is a 128-bit tag. Algorithm 2 shows thedetailed description of Poly1305. The input key has 256-bit length and is di4

Algorithm 2 Poly1305
Input: Key K and Message M
Output: Tag T
16(m[0], m[1], . . . , m[d − 1]) ← Md ← dlen(M )/16e
16(r, s) ← Kr ← r&0x0FFFFFFC0FFFFFFC0FFFFFFC0FFFFFFF
for i ← 0 to d − 1 dom[i] ← m[i] + 28len(m[i])end forT ← m[0]for i ← 1 to d − 1 do
T ← (r · T + m[i]) mod (2130 − 5)end forT ← (T + s) mod 2128
return T
Algorithm 3 ChaCha20-Poly1305 AEAD
Input: Key K, Nonce N , Authentication data A, and Message M
Output: Ciphertext C and Tag T
z ← CC-Poly-KS(K, N, len(M ))C ←M ⊕z
T ← CC-Poly-T(K, N, A, C)
return (C, T )vided to two 128-bit keys r and s. The algorithm clamps 22-bits of r. The
output tag is ((m[0]rn + m[1]rn−1 + · · · + m[n]) mod (2130 − 5) + s) mod 2128 ,where M [i] is i-th 16-bit chunk of the input message M .

2.3

ChaCha20-Poly1305 AEAD

ChaCha20-Poly1305 is an authenticated encryption with additional data algorithm. The input data are a 256-bit key K; a 96-bit nonce N ; arbitrary
length authenticated data A, and an arbitrary length message M . Algorithm 3
describes the complete procedure of ChaCha20-Poly1305 AEAD and Fig. 2.1
shows the overall structure. Algorithm 4 and 5 show its subroutines.

5Figure 2.1: ChaCha20-Poly1305 AEAD

Algorithm 4 CC-Poly-KS
Input: Key K, Nonce N and Input length L
Output: Keystream Zb ← dL/64e
for i ← 0 to b − 1 doz[i] ← ChaCha(K, i + 1, N )
end P
for
b−1
z ← i=0 z[i] · 2512i
Z ← trancate(l, z)
return Z

Algorithm 5 CC-Poly-T
Input: Key K, Nonce N , Authentication data A, and Message M
Output: Tag Tk ← trancate(32, ChaCha(K, 0, N ))y←Ay ← y + M · 2128dlen(A)/16ey ← y + len(A) · 2128(dlen(A)/16e+dlen(M )/16e)y ← y + len(M ) · 2128(dlen(A)/16e+dlen(M )/16e+1/4)
T ← Poly1305(k, y)return T

6

Chapter 3

Security Analyses
3.1

Related Work

Crowley [Cro06] presented a differential cryptanalysis on reduced round Salsa20/5
that uses a 3-round differential and requires 2165 time complexity and work and26 plaintexts. Fischer et al. [FMB+ 06] exploited a 4-round differential to attack Salsa20/6 within 2177 time complexity. Tsunoo et al. [TSK+ 07] attacked
Salsa20/7 within 2190 time complexity using a 4-round differential, and broke
Salsa20/8 with 2255 time complexity. Aumasson et al. [AFK+ 08] reduced thetime complexity to 2151 for Salsa20/7 and 2251 . for Salsa20/8 still using a 4round differential. They also presented that ChaCha6 and ChaCha7 can be
attacked with time complexity 2139 and 2248 , respectively. Shi et al. [SZFW12]
proposed improved attack based on second-order differential with 2148 timecomplexity for Salsa20/7, 2250 . for Salsa20/8, 2136 for ChaCha6 and 2246.5
for ChaCha7. Maitra [Mai16] showed a chosen IV cryptoanalysis and the timecomplexity of the attack can be reduced to 2245.5 for Salsa20/8 and 2239 for
ChaCha7. Mouha and Preneel [MP13] proposed a method to search for optimal
differential characteristics for ARX ciphers and applied it to find characteristics
Salsa20/3. Choudhuri and Maitra [CM16] evaluate the security of Salsa and
ChaCha against differential cryptanalysis using a hybrid model of non-linear
round functions and linear approximation. The summary of existing attacks
is shown in Table 3.1. They concluded that Salsa20/12 and ChaCha12 are
sufficient for 256-bit keys under the attack model.
Procter [Pro14] demonstrated that the combination of ChaCha and Poly1305
is a secure authenticated encryption scheme assuming ChaCha is a pseudorandom function (PRF), and Poly1305 is ε-almost-∆-universal. Imamura and
Iwata [KI16] show key-recovery attack and forge attack are possible in a noncemisuse situation where the same nonce is repeatedly used.

3.2

Analysis on ChaCha Structure

ChaCha is similar not to conventional stream cipher algorithms but ARX-type
block ciphers. The structure of ChaCha should be understood as block cipher
algorithm and analyze it focusing on the round function.

7

3.2.1Invertibility

The quarter-round function of ChaCha contains only additions, exclusive-or,
and constant-distance rotations. These basic operations can be described asfollows;
add : (x, y) 7→ (x + y, y),xor : (x, y) 7→ (x ⊕ y, y),rotl : x 7→ (x)≪n ,and they are invertible:
add−1 : (x, y) 7→ (x − y, y),xor−1 (= xor) : (x, y) 7→ (x ⊕ y, y),rotl−1 (= rotr) : x 7→ (x)≫n .
The quarter-round function of ChaCha is thus invertible, and the inverse quarterround function is given as;b = (b)≫7
b=b⊕c
c=c−d
d = (d)≫8
d=d⊕a
a=a−b
b = (b)≫12
b=b⊕c
c=c−d
d = (d)≫16d=d⊕aa = a − b.
The round function of ChaCha consists of four quarter-round functions anddistinct 4-tuples of words are processed with the quarter-round functions. Thus,
the round function is also invertible. There is no entropy loss in the process of
the round function.
Note that the entire key-generation process is not necessarily invertible. The
keystram Z is calculated as X +X (20) and irreversible addition irradd : (x, y) 7→(x + y) is used.

3.2.2

Structual difference from Salsa20

The Salsa20 algorithm is described as follows;
Sala20 Algorithm The stream cipher Salsa20 [Ber08b] operates on 32-bit
words, takes as input a 256-bit key K = (k0 , k1 , k2 , k3 , k4 , k5 , k6 , k7 ) or 128-bit
key K = (k0 , k1 , k2 , k3 ) and a 64-bit nonce N = (n0 , n1 ) and counter C =8

(c0 , c1 ), and produces a sequence of 512-bit keystream blocks. This function
acts on the 4 × 4 matrix of 32-bit words written as;
x0 x1 x2 x3
 x4 x5 x6 x7 X= x8 x9 x10 x11 
x12 x13 x14 x15
τ0 k0 k1 k2k τ n n 


 3
1
0
1



 (K is a 128-bit key)



c
c
τ
k

0
1
2
4


 k k k
τ3
5
6
7

= 

σ
k
k
k
0
0
1
2





k3 σ1 n0 n1  (K is a 256-bit key)



c
c
σ
k

0
1
2
0



k1 k2 k3 σ3The σ and τ are constants where(τ0 , τ1 , τ2 , τ3 ) = (0x61707865, 0x3120646E, 0x79622D36, 0x6B206574)
and(σ0 , σ1 , σ2 , σ3 ) = (0x61707865, 0x3320646E, 0x79622D32, 0x6B206574).
The keystream block Z is defined as; Z = X + X (20) , where X (r) =Roundr (X) with the round function of Salsa20 and + is word-wise addition
modulo 232 . If Z = X + X (r) , it is called “r-round Salsa20” or “Salsa20/r”.
The round function consists the following nonlinear operations that are called
quarter round functions. A vector (a, b, c, d) of four words is transformed as;
b = b ⊕ ((d + a)≪7 )c = c ⊕ ((a + b)≪9 )d = d ⊕ ((b + c)≪13 )a = a ⊕ ((c + d)≪18 )The quaterround function are applied to columns (x0 , x4 , x8 , x12 ), (x5 , x9 , x13 , x1 ),(x10 , x14 , x2 , x6 ) and (x15 , x3 , x7 , x11 ) in odd round, and rows (x0 , x1 , x2 , x3 ),(x5 , x6 , x7 , x4 ), (x10 , x11 , x8 , x9 ) and (x15 , x12 , x13 , x14 ) in even rounds. Algorithm 6 describes the complete procedure of Salsa20.
Deference from Salsa20 The quarter-round function of ChaCha contains
four additions, four exclusive-ors and four constant-distance rotations of 32-bit
words, similar to that of Salsa20. However, ChaCha increases the amount ofdiffusion in the quarter-round functions comparing with Salsa20. Figure 3.1 and3.2 shows the quarter round function of ChaCha and Salsa20. Each input word
is updated twice in ChaCha quarter-round function whereas each word is update
once in Salsa20 quarter-round function. Furthermore, ChaCha quarter-round
function gives each input word a chance to affect each output word similar to
Salsa20 quarter-round function.
9

Algorithm 6 Salsa20
Input: Key K, Counter C, and Nonce N
Output: Keystream Z
Generate initial matrix X using K, C, and Ny←X
for i ← 0 to 9 do/* Column Round */(x0 , x4 , x8 , x12 ) ← quarterround (x0 , x4 , x8 , x12 )(x5 , x9 , x13 , x1 ) ← quarterround (x5 , x9 , x13 , x1 )(x10 , x14 , x2 , x6 ) ← quarterround (x10 , x14 , x2 , x6 )(x15 , x3 , x7 , x11 ) ← quarterround (x15 , x3 , x7 , x11 )/* Row Round */(x0 , x1 , x2 , x3 ) ← quarterround (x0 , x1 , x2 , x3 )(x5 , x6 , x7 , x4 ) ← quarterround (x5 , x6 , x7 , x4 )(x10 , x11 , x8 , x9 ) ← quarterround (x10 , x11 , x8 , x9 )(x15 , x12 , x13 , x14 ) ← quarterround (x15 , x12 , x13 , x14 )end forZ ←X +yreturn Z
The rotation distance in the quarter-round function is 16, 12, 8, 7 in ChaCha
and 7, 9, 13, 18 in Salsa20. There is no report on security difference due to therotation distances. Three distances can be divided by 4 and two can be divided
by 8 in ChaCha. The change of rotations distance may contribute to improving
the performance in embedded environments with 8-bit or 4-bit CPU.

3.3

Cryptanalysis on ChaCha

3.3.1

Differential Analysis

Differential cryptanalysis introduced by Biham and Shamir [BS93] is now used
as a general method for analyzing various cryptographic primitives including
stream ciphers. Currently, almost all cryptanalysis of Salsa20 and Chacha are
based on the technique of differential analysis.
The most general idea of differential attacks is to exploit pairs of plaintexts
with certain differences which yield other certain differences in the corresponding
ciphertexts (or any internal states of the cipher) with a non-uniform distribution.
Specifically, consider a system with input an n-bit string X = [X1 , X2 , . . . , Xn ]and output an n-bit string Y = [Y1 , Y2 , . . . , Yn ]. Denote a pair of input as(X 0 , X 00 ) and the corresponding pair of output as (Y 0 , Y 00 ), respectively. The
input difference is denoted by ∆X = X 0 ⊕ X 00 where “⊕” may represent any
binary operation on n-bit strings which defines the difference between the two
operands and is, in its most general form, the bitwise Exclusive-OR operation. The difference between X 0 and X 00 is ∆X = [∆X1 , ∆X2 , . . . , ∆Xn ] where∆Xi = Xi0 ⊕ Xi00 with Xi0 and Xi00 being the i-th bit of X 0 and X 00 , respectively.
Similarly, ∆Y = Y 0 ⊕ Y 00 = [∆Y1 , ∆Y2 , . . . , ∆Yn ] is the output difference. Differential cryptanalysis tries to identify a scenario where a particular ∆Y occurs
given a particular ∆X with a probability differing much from uniform. Note10

Figure 3.1: Quarter-round function of ChaChathat the probability Pr[∆Y |∆X] can be either much greater than or less thanthe uniform probability. When such ∆Y exists, we call the pair (∆X, ∆Y ) a
differential. Such a differential can be used either to distinguish the ciphertext
from randomness or to help recover the key used by the cipher.
To recover the (partial) key of the cipher, we work backward from an output
by guessing a part of secret key (we call subkey from now on). More specifically
we feed the cipher with many chosen plaintexts consisting of pairs of plaintexts
with a difference ∆X to generate the ciphertexts C and try to decrypt theseciphertexts using all possible subkeys to get the internal states Y . By checking
the frequency that ∆Y occurs, we can select the correct subkey with high probability. If our guess of the subkey is not the correct one, then the frequency of∆Y equals the probability of ∆Y in the differential analysis is highly impossible.
But for the correct guess, we will observe a frequency of ∆Y quite close to its
conjectured value Pr[∆Y |∆X].
Truncated differential analysis In the above discussion we treat the output difference ∆Y as an n-bit string. But as shown by Knudsen [Knu95]it is notalways necessary to predict the full n bit value of the output difference. Sometimes even a 1-bit value in the output difference suffices for the cryptanalysis.
Such kind of differential which only predicts parts of an n-bit value is called atruncated differential.

11

Figure 3.2: Quarter-round function of Salsa20
Cryptanalysis of Salsa20
Crowley [Cro06] presented the first attack of 256-bit Salsa20/5 using the technique of truncated differential analysis in 2005. Crowley identified a differential
which as a biased bit in the output difference in the third round of Salsa20
core function. The attack only uses chosen IV, i.e, the nonce (n0 , n1 ) and thecounter (c0 , c1 ). The truncated differential (∆X, ∆Y ) Crowley has found is thefollowing one;




0
0
0 0
∗
∗ ∗ ∗
0

0
0 0
∗
∗ ∗ ∗
 3rounds,∆X = 
0 0x80000000 0 0 −−−−−→ ∆Y = ∗∗ ∗ ∗
00
0 00x02002802 ∗ ∗ ∗with a theoretic probability 2−12 . But In his experiments Crowley observed amuch higher probability of about 2−9 for this truncated probability in practice.
Using this differential Crowley amounted a key recover attack which works tworounds backwards from a ciphertext by guessing 160 relevant key bits. This
attack requires 2165 work and 26 keystreams.
Fischer et al. [FMB+ 06] reported an attack on 256-bit Salsa20/6. This
attack used a similar technique of truncated differential analysis as comparedwith Crowley. But Fischer et al. has found a differential with a biased bit in the
output difference in the fourth round which helped to push the attack against
a further round.
To find a differential path for the four rounds Salsa, Fischer et al. first intro12

duced an alternative LinSalsa20 primitive which replaces the addition modulo
232 in Salsa20 with bitwise XOR and then analyzed some low-weight differential path for LinSalsa20. Under the condition that addition does not yielda carry, LinSalsa20 behaves the same as the actual Salsa 20. Using this observation they successfully applied the differential path found in LinSalsa20 toSalsa20 and mounted a key recovery attack on Salsa20/6. They also observed
non-randomness for Salsa until round 7. Their attack on 256-bit Salsa20/6
used a differential found after four rounds operation of Salsa20, and work two
rounds backward by guessing 160 relevant key bits. This attack requires 2177
computational complexity and 216 keystreams.
Tsunoo et al. [TSK+ 07] used the characteristics of differential of modulo
addition [LM01] to rigorously compute the differential probabilities for each bit
in the round 4 internal state of Salsa20. They found the following two 4-rounddifferentials to have the most biased probability of approximately (1−2−5.24 )/2;




0 0 0
0
∗ 0x00400000 ∗ ∗0 0 0 0x80000000 4rounds∗∗ ∗ −−−−−→ ∆Y1 = ∗,
∆X1 = 
0 0 0

∗
0
∗
∗ ∗
0 0 0
0
∗
∗
∗ ∗


0

0

∆X2 = 0x80000000
0



0 0 0
∗
∗
0 0 0
4rounds−−−−−→ ∆Y2 = 
0 0 0
∗
0 0 0
∗

∗
∗
∗
∗

∗
0x00400000
∗
∗


∗
∗
.
∗
∗

Then using these differentials they reported a key recovery attack by working
3 rounds backwards from Salsa20/7. They used nonlinear approximation of
integer addition to reduce the guessing space for relative key bits to 171. Their
attack requires 2184 work and 211.4 keystreams. They also reported a 2255
complexity attack using 210 keystreams with probability 44% to narrow down
the correct key of Salsa20/8. However, this can hardly be considered as a
useful attack because it is effectively slower than the brute force attack. Since
exhaustive search succeeds with probability 50% within the same number oftrials, with much less data and no additional computations [AFK+ 08].
Aumasson et al. [AFK+ 08] proposed attacks on Slasa20/8 and Salsa20/7
and Chacha6. Their attack used the notion of probabilistic neutral bits (PNB)
introduced by Biham and Chen [BC04] to split key bits into two subsets as
the relevant key bits which can be filtered by observations of a biased output
differential and the less significant key bits which are determined by exhaustive
search. Their attacks on Salsa20 worked four rounds forwards to find the biased
bit in the differential and.
Aumasson et al.’s attack on 256-bit Salsa20/7 uses the following 4-rounddifferential with a median bias |ε∗d | = 0.131.




0 0 0
0
∗ 0x02000000 ∗ ∗0 0 0 0x00010000 4rounds∗∗ ∗ −−−−−→ ∆Y = ∗.
∆X = 
0 0 0

∗
0
∗
∗ ∗
0 0 0
0
∗
∗
∗ ∗
Using this differential the attack worked 3 rounds backwards by guessing This
attack requires 2151 work and 226 keystreams. Their attack on 128-bit Salsa20/7
13

used the same 4-round differential and broke Salsa20/7 within 2111 time and221 keystreams. The same 4-round differential was used to attack Salsa20/8
by working four rounds backward. This attack requires 2251 -operation and 231
keystreams.
Following the work of Aumasson et al., Shi et al. [SZFW12] consider a
new type of distinguisher called column (row) chaining distinguishers (CCD)
which can efficiently make use of the biases of multiple differential trails andthe matrix structure of the cipher. Besides, they found new high probability
second-order differential trails that were not covered by previous results. They
also generalized the notion of PNB to probabilistic neutral vectors (PNV) which
explore the properties against more than one flipped input bit. These newtechniques and notions can effectively improve both time and data complexityof previous attacks against both Salsa and ChaCha. For example, one of thehighly biased 4-round second-order differential of Salsa is as follows;


0
0 0
0

0
0 0 0x00080000
∆X = 
0x00400000 0 0

0
0
0 0
0


∗ 0x10000000 ∗ ∗
∗
∗
∗ ∗
4rounds.
−−−−−→ ∆Y = 
∗
∗
∗ ∗
∗
∗
∗ ∗
Their attack on 256-bit Salsa20/5 used five 3-round differentials by working
two rounds backward from a 5-round keystream block. This attack can break
Salsa20/5 within time 255 and data 210 . Their attack on 256-bit Salsa20/6 usedfour 4-round differentials as the chaining distinguisher by working two rounds
backward from Salsa20/6 and requires 273 operations and 216 keystreams. To
attack 256-bit Salsa20/7, they used the same 4-round differential as that of
Aumasson et al. This attack requires 2148 operations and 224 keystreams. The
same differential was used to attack 256-bit Salsa20/8 with a time complexityof 2250 and data complexity of 227 . Finally, they showed an attack on 128-bit
Salsa20/7 using the same 4-round differential which requires 2109 operations and219 keystreams.
In 2015, Maitra[MPM15, Mai16] improved the complexity of attacking Salsa
and ChaCha. In [MPM15], Maitra revisited the single bit differentials for 4round Salsa and found better biases which are more significant than previously
published ones. He also revisited technique of PNB used in Aumasson et al.
[AFK+ 08] and observed that in practice the median of certain biases are 4
times more than what was observed by Aumasson. Maitra further explored thetradeoff between carefully choosing more PNBs at the cost of accepting lessprobability for distinguishing the correct key from the wrong keys. A combination of the above process resulted in an attack on 256-bit Salsa20/8 with 2247.2
work and 227 keystreams. In a subsequent work [Mai16], Maitra reported chosen IV cryptanalysis on reduced round Salsa and ChaCha. In [Mai16], Maitra
follows his previous idea of exploring more PNBs to obtain better results for the
cryp tanalysis of Salsa and Chacha. He also showed how to exploit specific IVs(the nonces and counters) corresponding to the secret key which can help improve the attack of Aumasson et al. [AFK+ 08]. His attack on 256-bit Salsa20/8
14

used the following 4-round differential by working 4 rounds backwards.




0 0 0
0
∗ 0x02000000 ∗ ∗0 0 0 0x0x00010000 4rounds∗∗ ∗ −−−−−→ ∆Y = ∗.
∆X = 
0 0 0


0
∗
∗
∗ ∗
0 0 0
0
∗
∗
∗ ∗
The attacks requires 2245.5 work and 222.5 keystreams.
Cryptanalysis on ChaCha
Due to the similar design of ChaCha and Salsa20, the cryptanalysis on Salsa
discussed above also apply to ChaCha. However, since ChaCha are designed
to achieve a quick diffusion, it is suggested harder to break than Salsa. This isevidenced by the published attacks on Salsa and ChaCha.
The initial attack on ChaCha was started by Aumasson et al. [AFK+ 08]
using the technique of probabilistic neutral bits (PNB). Aumasson et al. used
the following 3-round differential to attack ChaCha6 and ChaCha7:




0
0
0 0
∗ ∗ ∗
∗
0
∗ ∗ ∗
0
0 0
∗3rounds−.
∆X = 
−−−−→ ∆Y = 
0


0
0 0
∗ ∗ ∗ 0x80000000
0 0x04000000 0 0∗ ∗ ∗∗The attack on 256-bit ChaCha6 worked three rounds backward from the 6-roundkeystream block and required 2139 operations and 230 keystreams. By working
four rounds backwards from ChaCha7, they could successfully attack 256-bit
ChaCha7 using time 2248 and data 227 . Same experiments were done on the
128-bit variants. Their attack on 128-bit ChaCha6 can break it within 2107 timeand 230 keystreams. However, their method failed on 128-bit ChaCha7.
The tools of Shi et al. [SZFW12], column chaining distinguisher (CCD)
and probabilistic neutral vectors (PNV) also applies to the analysis of reduced
ChaCha. They used the same 3-round differential as that of Aumasson et al.
[AFK+ 08] to attack ChaCha6 and ChaCha7. Due to the generalized techniques
and notions compared with [AFK+ 08], their attacks have better complexity.
Specifically for 256-bit ChaCha6, their attack requires 2136 operations and 228
keystreams; their attack can break 256-bit ChaCha7 within time 2246.5 and data
227 , and their attack on 128-bit ChaCha6 uses 2105 work and 228 keystreams.
They did not report results on attacks for 128-bit ChaCha7.
The latest improvement on the attacks against reducing ChaCha came from
Maitra [Mai16] in 2015. The attack used the same tools for attacking Salsa20
such as exploring more PNBs to obtain better results and exploit specific IVs
corresponding to the secret key. Maitra improved the complexity of the attackon 256-bit ChaCha7 to 2239 operations and 224 keystreams.
Differential-Linear Cryptanalysis
Differential-linear cryptanalysis discovered by Langford and Hellman [LH94]
uses the idea to combine the techniques of differential cryptanalysis and linear
analysis to derive bias for the underlying cipher up to more rounds. It usuallydivides the cipher E into two parts E = E1 ◦E0 . Differential-linear cryptanalysis
15

01
uses a differential δi −−→δo and a linear approximation χi −−→χo and build trials
or characteristics for both half individually, where δi (δo ) is the input (output)
difference for the first half of the cipher E0 and χi (χo ) is the input (output)
mask for the second half of the cipher E1 , respectively.
Recently Choudhuri and Maitra [CM16] developed a differential-linear cryptanalysis on reduced round Salsa20 and ChaCha. This is known as currently themost effective attack on reduced round Salsa20 and ChaCha published so far.
The improvement of their attack mainly comes from the idea of using multi-bit
differentials instead of the single-bit truncated differentials in existing works.
By considering the linear combination of multi-bit in the output difference,
Choudhuri and Maitra have successfully identified high biases in Salsa20 after
six rounds and ChaCha after five rounds, which demonstrates a two rounds ofimprovement for both the ciphers over previous cryptanalytic results. Theirresults of attacks on 256-bit Salsa20 and ChaCha can be listed as follows:EE• 5-round Salsa20: time complexity 28 and data complexity 28 .
• 6-round Salsa20: time complexity 232 and data complexity 232 .
• 7-round Salsa20: time complexity 2137 and data complexity 261 .
• 8-round Salsa20: time complexity 2244.9 and data complexity 296 .
• 4-round ChaCha: time complexity 26 and data complexity 26 .
• 5-round ChaCha: time complexity 216 and data complexity 216 .
• 6-round ChaCha: time complexity 2116 and data complexity 2116 .
• 7-round ChaCha: time complexity 2237.7 and data complexity 296 .
Note: Biham and Carmeli [BC14] proposed a new technique of partitioning
the data set to improve the performance of linear cryptanalysis against FEAL8X. Recently this partitioning technique was generalized by Leurent [Leu16] tomulti-bit partitioning and also to differential cryptanalysis. Leurent applied
the generalized partitioning technique to the cryptanalysis of an ARX-stylemessage authentication code, Chaskey and got significant improvement. The
Choudhuri-Maitra differential-linear attack was inspired by the work of Leurent
but without the partitioning technique. Therefore we assume there is room for
improvement of the differential-linear cryptanalysis on ChaCha and Salsa using
the partitioning technique.
Rotational Cryptanalysis
Rotational cryptanalysis [KN10, KNP+ 15]is a probabilistic analysis especiallyapplicable to word oriented ciphers which use almost rotation-invariant operations. ChaCha is one example of the ARX cipher family which use only (modular) Addition, Rotation and Xor operations.
It can be viewed as a special case of differential attack. But the difference
metrics is now defined by rotational difference other than the classic xor difference.
To launch a rotational attack, one starts from a rotational pair, i.e. twostates X and X 0 where the words of X 0 are all rotations of the words of X
16

by a fixed amount. If the corresponding outputs for such rotational pair also
form a rotational pair with a probability higher than in the case of a random
permutation, then this bias can be utilized to distinguish the cipher from arandom permutation, and it can further lead to key recovery attack.
However, one crucial requirement of rotational cryptanalysis is that the constants used in the cipher construction must be rotation-invariant, i.e. the constants must preserve their values when rotated [KNP+ 15]. In the design ofSalsa20 and ChaCha, the constants are carefully selected to be non-symmetricto prevent any use of rotational pairs [Ber05a].
Boomerang Attack
Boomerang attack [Wag99] is another differential-style attack which exploits
the differential in half of the rounds to boost the bias of certain differential
characteristics.
The attack divides the cipher E into two parts E = E1 ◦ E0 , where E0
represents the first half of the cipher and E1 represents the second half. In orderto lunch boomerang attack one needs to find differential characteristics for thetwo halves of the cipher respectively. Denote ∆ → ∆0 a differential characteristic
for E0 and 5 → 50 a differential characteristic for E1−1 . Consider four plaintexts
P, P 0 , Q, Q0 and their corresponding ciphertexts C, C 0 , D, D0 . The plaintexts
and ciphertexts are generated in the following way: 1), generate P 0 = P ⊕∆; 2), get the encryption C, C 0 of P, P 0 with two chosen-plaintext queries; 3),
generate D, D0 as D = C ⊕ 5 and D0 = C 0 ⊕ 5; 4), decrypt D, D0 to get
the corresponding plaintexts Q, Q0 with two adaptive chosen-ciphertext queries.
The four plaintexts P, P 0 , Q, Q0 generated in the above manner are called aquartet. The property of the quartet is that P, P 0 satisfy the characteristic
for E0 , P, Q and P 0 , Q0 satisfy the characteristic for E1−1 and Q, Q0 satisfy thecharacteristic for E0−1 , ∆0 → ∆. Then using this quartet we can distinguish thecipher from a random permutation and can further lunch key recovery attack.
But one disadvantage of the boomerang attack is that it inherently requires the ability to perform both chosen-plaintext query and adaptive chosenciphertext query simultaneously which may limit the application in a practical attack. Also, it is not obvious how boomerang attack can be applied to
ChaCha since the construction of ChaCha uses fixed constants at pre-defined
locations in the initial state. The implication is that when using an adaptive
chosen-ciphertext query, the altered ciphertext may not lead to a valid plaintext. Currently, there is no report on successful boomerang attack on ChaCha
or Salsa20.
Security Evaluation of Salsa20 and ChaCha
Though several attacks have been developed against reduced Salsa20 and ChaCha,to the best of our knowledge there has been no report on the weakness of fullround Salsa20/20 or ChaCha. Recently Choudhuri and Maitra [CM16] evaluated the security of Salsa20 and ChaCha against differential cryptanalysis. In
their analysis, they introduced the hybrid model for the evaluation of differential
cryptanalysis of Salsa20 and ChaCha. In the hybrid model, the initial rounds
are run using the nonlinear function as in the real cipher, but subsequent rounds
are run using the linearized counterpart. To utilize this hybrid model they first17

examine the biases in the cipher after a few forward rounds and then estimate
an upper bound on the number of rounds till such biases can be observed. Because Salsa20 and ChaCha both use only use modular addition and XOR, it ispossible to upper bound the absolute values of the biases of Salsa20 and ChaChaby those of the linearized counterparts. Combining both the forward biases andbackward biases, they claimed that Salsa20/12 and ChaCha12 are sufficient toprovide security against certain kinds of differential cryptanalysis for 256-bit
keys.

3.3.2

Linear Cryptanalysis and Distinguishing Attack

The quarter-round function of ChaCha consists of four additions. We have alinear expression of the round function by approximating these additions by
exclusive-or operations.
Sarkar [Sar09] evaluated the probability of the i-th bits of S (n) = X (0) +(1)
X + · · · + X (n−1) and L(n) = X (0) ⊕ X (1) ⊕ · · · ⊕ X (n−1) are identical; that
(n)
(n)
(n)
(2)
is, γi = Pr[Si = Li ]. The probability γi equals to (1 + 2−i )/2 for n = 2.
32
Let x and y be integers over GF (2 ). The probability x + y = x ⊕ y holds
is given as;
31
Y(2)
Pr[x + y = x ⊕ y] =γi = 2−29.75 .
i=0

The quarter-round functions of ChaCha is given in section 3.2.3 and each function contain more than one addition. The maximum linear probability of thequarter-round function is thus bounded by 2−29.75 . Note that equivalence between addition and exclusive-or does not always hold, and the upper bound isindependent of the number of addition. We ignore the rotate operations of thequarter-round functions in this estimate. The maximum linear probability of
20-round ChaCha is bounded by (2−29.75 )20 = 2−595 . We conclude that linear
cryptanalyses and distinguishing attacks on ChaCha are not effective.

3.3.3

Guess and Determine Analysis

We first analyze the quarter-round function. The quarter-round function is described as follows:

aj+1 = (aj + bj ) + (bj ⊕ (cj + (dj ⊕ (aj + bj ))≪16 ))≪12 )bj+1 = ((bj ⊕ (cj + (dj ⊕ (aj + bj ))≪16 ))≪12 )⊕ ((cj + (dj ⊕ (aj + bj ))≪16 ) + ((((dj ⊕ (aj + bj ))≪16 )⊕ ((aj + bj ) + (bj ⊕ (cj + (dj ⊕ (aj + bj ))≪16 ))≪12 )))≪8 ))≪7
cj+1 = (cj + (dj ⊕ (aj + bj ))≪16 ) + ((((dj ⊕ (aj + bj ))≪16 )⊕ ((aj + bj ) + (bj ⊕ (cj + (dj ⊕ (aj + bj ))≪16 ))≪12 )))≪8 )dj+1 = (((dj ⊕ (aj + bj ))≪16 )⊕ ((aj + bj ) + (bj ⊕ (cj + (dj ⊕ (aj + bj ))≪16 ))≪12 )))≪8
Each output value aj+1 , bj+1 , cj+1 , dj+1 is calculated from all input values(aj , bj , cj , dj ). If adversary obtain all output values, the adversary has to guess18

at least three 32-bit input values in order to obtain remaining one 32-bit input
value. Even though the above guess-and-determine approach applies to one
round operation using the quarter function, the adversary has to guess 3 × 4
32-bit values to break two rounds operation that consists of the column round
operation and the diagonal round operation. Furthermore, keystream bit iscalculated after adding initial state bits as Z ← X + X (20) . Thus, a guess-anddetermine approach cannot recover an initial key with reason a computational
cost.

3.3.4

Time-Memory-Data Tradeoff Attack

Baic ideas of time-memory-data tradeoff attack against a stream cipher areproposed by Babbage [Bab95] and Golić [Gol97]. Birkov and Shamir [BS00]
proposed an advanced scheme that combines the basic ideas and an attack
against a block cipher [Hel80].
They show the tradeoff formula as follows;
T M 2 D2 = N 2 ,P = N/D(D2 ≤ T ≤ N ).

The five key parameters are defined as followings:• N : the size of the search space• P : the time required by preprocessing phase of the attack• M : the amount of random access memory• T : the time required by real-time phase of the attack• D: the amount of real-time data available to the attack
Hong and Saker [HS05] evaluate the security of stream cipher with IV basedon the tradeoff. The size of the search space is N = 2k+v where k and v are thebit length of the key and IV, respectively.
In the original version of ChaCha takes a 256-bit key and 64-bit nonce andN = 2320 . Thus, P = N 3/4 = 2240 , D = N 1/4 = 280 , M = N 1/2 = 2160 ,and T = N 1/2 = 2160 satisfies the above the tradeoff formula, the total timecomplexity of the attack P + T ≈ 2240 is less than 2256 .
In the IFIT version of ChaCha takes a 256-bit key and 96-bit nonce andN = 2352 . A time-memory-data tradeoff attack is theoretically possible against
the version of ChaCha. For example, P = N 2/3 = 2234.67 , D = N 1/3 = 2117 ,M = N 1/2 = 2176 , and T = N 1/2 = 2176 satisfies the above the tradeoff
formula, the total time complexity of the attack P + T ≈ 2234.67 is less than
2256 . However, we can limit the amount of the real-time data up to 296 to havea total time is greater than 2256 . Table 3.2 shows the typical parameter of thetime-memory-data tradeoff attack.

3.3.5

Algebraic Attack

The algebraic degree and the number of terms in the ANF of the component
Boolean functions of modular addition can be obtained as follows [BS05]:19

d(fi ) = i + 1
n(fi ) = 2i + 1
Every round has at least four 32-bit additions; thus after 20 round operations, d and n can be expected to be sufficiently large, and any algebraic attacks
are not efficient for breaking ChaCha. Currently, no algebraic attack is found.

3.3.6

Attacks on Initialization Process

There is no difference between an initialization process and a keystream generation process of ChaCha. The cipher has initial key loading process, and thekey, iv and counter values are loaded for every keystream generation. Thus, no
specific attack on the initialization process exists on ChaCha.

3.3.7

Analysis on Period

We estimate the variety of the output keystream of ChaCha to evaluate theperiodicity. ChaCha is assumed to be a random function in this analysis.
The input of the IETF version of ChaCha is a 256-bit key, a 32-bit block
counter, and a 96-bit nonce; thus, the number of elements in the input setof ChaCha is 2384 The number of possible elements in the output set is up
to 2384 . Let these elements be y1 , y2 , …, y2384 . We introduce probabilistic
variables Y1 , Y2 , …, Y2384 . The probabilistic value Yi is 1 if there exists an
input x such that yi = ChaCha(x) or 0 otherwise. Now, we define a variable
Y = Y1 + Y2 + · · · + Y2384 . The expectation value E[Y ] is the average numberof elements in the output set.
E[Y] can be evaluated as;
E[Y ] = E[Y1 + Y2 + · · · + Y2384 ]= E[Y1 ] + E[Y2 ] + · · · + E[Y2384 ]= 2384 E[Y1 ],by the identity of the variables.
On the other hand, E[Y1 ] can be calculated as;E[Y1 ] = 1 − (1 − 2−384 )2384≈ 1 − e−1
≈ 0.632.
Note that (1 − 2−384 )2 ≈ e−1 is the probability that y1 does not appear in
output set with 2384 inputs.
Thus, E[Y] can be estimated as (1 − e−1 )2384 and keystream of ChaCha hasvariety of 2383 . We expect to have 2191.5 keystreams without collision according
to the birthday paradox theory. The IETF version of ChaCha can generate up
to 232 keystreams within the same key and nonce, and it is expected that noshorter periods would be found.
384

20

3.3.8Side-Channel Attack

We evaluate the security of ChaCha against side channel attacks including single/differential power analysis, cache timing attack, and fault injection attack.
Power Analysis
Single Power Analysis The quarter-round function of ChaCha contains
fixed-distance rotations. The fixed-distance rotation operation can be implemented using two bit-shift operations or (x)≪n = ((x)n )⊕((x)(W −n) ) where
W is the bit-length of a word. The bit-shift operations are vulnerable to simple
power analysis [Koc09].
Each word of the key is stored into arrays in the initial matrix generation
process. An adversary may get the Hamming weight of the words using thepower consumption information.
A masking countermeasure can protect these analyses.
Differential Power Analysis We evaluate the security of ChaCha against
the correlation power analysis [BCO04] which is a variant of differential power
analyses. We assume that an adversary can control the counter C = (c0 ) andnonce N = (n0 , n1 , n2 ).
The first four instructions in the quaterround (x0 , x4 , x8 , x12 ) in the firstround is as followings;
x0 ← σ0 + k0
x12 ← c0 ⊕ (σ0 + k0 )x12 ← (c0 ⊕ (σ0 + k0 ))≪16x8 ← k4 + ((c0 ⊕ (σ0 + k0 ))≪16 )The adversary focus on the second instruction and measure the power consumption by changing c0 . One can find the value of k0 using correlation power
analysis based on hamming-distance or hamming-weight model. Now, the adversary can control the value of (c0 ⊕ (σ0 + k0 ))≪16 ) after knowing k0 and findk4 from the third instruction. One must use hamming-weight model since theprevious value of x8 is k4 and unknown.
The first four instructions in the quaterround (x5 , x9 , x13 , x1 ) in the firstround is as followings;
x5 ← k1 + k5
x1 ← σ2 ⊕ (k1 + k5 )x1 ← (σ2 ⊕ (k1 + k5 ))≪16
x13 ← n0 + ((σ2 ⊕ (k1 + k5 ))≪16 )The adversary gets k1 + k5 by controlling n0 in the fourth instruction.
The first two instructions in the quaterround (x10 , x14 , x2 , x6 ) in the firstround is as followings;
x10 ← k6 + n1
x6 ← k2 ⊕ (k6 + n1 )21

The adversary finds k6 by controlling n1 in the first instruction, then gets k2 bycontrolling (k6 + n1 ).
The first four instructions in the quaterround (x15 , x11 , x11 , x7 ) in the firstround is as followings;
x15 ← n2 + σ3
x11 ← (k7 ⊕ (n2 + σ3 ))x11 ← (k7 ⊕ (n2 + σ3 ))≪16x7 ← k3 + ((k7 ⊕ (n2 + σ3 ))≪16 )The adversary finds k7 by controlling (n2 + σ3 ) in the second instruction thengets k2 by controlling ((k7 ⊕ (n2 + σ3 ))≪16 ) in the fourth instruction.
The adversary knows the value of k0 , k1 + k5 , k2 , k3 , k4 , k6 , and k7 after
completing the correlation power analysis. Thus, one can get the entire key byguessing k1 , which impose 232 time complexity. This analysis can be protectedwith a masking countermeasure.
Cache Timing Attack
ChaCha implementation takes constant time on a huge variety of CPUs. The
execution time is input-independent since ChaCha does not contain varianttime operation such as S-box. Cache timing analysis against ChaCha is thus asdifficult as pure cryptanalysis of the ChaCha output.
Fault Injection Attack
The key stream of ChaCha is calculated as the addition of the initial matrix X
and the matrix X (20) processed by the round function. The initial matrix X or
matrix X (20) is output if the addition instruction is skipped by a fault injection
attack.
Step 1 Skip one of the add instructions that add words of the initial matrix X andthe matrix processed by the round-function X (20) . The value of one wordin the keystream changes if one of the add instructions correctly; then,store the word. The step fails if multiple values of words in the keystreamchange, i.e., multiple instructions or some instructions in round functions
are skipped.
Step 2 Repeat Step 1 until obtaining the changed values of all of the word in the
keystream.
Step 3 Generate a matrix from the word obtained in Step 1. The matrix is ether
X or X (20) . We can distinguish the matrix by checking orthogonal words
x0 , x5 , x10 , and x15 . The matrix is X if the orthogonal words are σ0 , σ1 ,σ2 , and σ3 and go to Step 5. The matrix is X (20) otherwise and go to
Step 4.
Step 4 Calculate X from X (20) using the inverse round function.
Step 5 Extract the key from the words x4 , x5 , x6 , x7 , x8 , x9 , x10 , x11 in X.

22

Algorithm 7 Implementation 1 of ChaCha
Input: Key K, Counter C, and Nonce N
Output: Keystream Z
X ← Initial Matrix(K, C, N )Z←X
X ← X (20)for i ← 0 to 15 dozi ← zi + xi
end forreturn Z
Algorithm 8 Implementation 2 of ChaCha
Input: Key K, Counter C, and Nonce N
Output: Keystream Z
X ← Initial Matrix(K, C, N )Z ← X (20)for i ← 0 to 15 dozi ← zi + xi
end forreturn Z
Bar-El et al. [BECN+ 06] and Trichina and Korkiyan [TK10] demonstrates
that instruction skip can be achieved with a laser pulse. Dehbaoui et al. [DDR+ 12]
and Morno et al. [MDH+ 13] shows instruction skip using an electromagnetic
pulse. Korak and Hoefler [KH14], Endo et al. [EHH+ 14], and Yuce et al [YGS15]
proposed instruction skip based on a glitchy clock signal.
Algorithm 7 and 8 shows the implementations of ChaCha. An adversary
can obtain the elements of the initial matrix X or the matrix X (20) processedby the round function by skipping the add instruction of the first or second
implementation, respectively.
A countermeasure against this sort of attacks is to separate variables; thatis, distinct variables store the inputs and output of the addition. Consider an
addition z ← x+y. The addition returns the initial value of variable z even if theaddition is skipped. Thus, the adversary can get neither the value of variables
x and y. Algorithm 9 shows the implementation using countermeasure basedon variable separation.
We should note that variable separation in source-code level does not work
Algorithm 9 Countermeasure for fault injection analysis
Input: Key K, Counter C, and Nonce N
Output: Keystream Z
X ← Initial Matrix(K, C, N )Y ← X (20)for i ← 0 to 15 dozi ← xi + yi
end forreturn Z

23

int add(int x, int y){
int z;
z = x + y;return z;}
Figure 3.3: Variable separation in source-code level
add:

pushl
movl
subl
movl
movl
addl
leave
ret

%ebp
%esp, %ebp
$16, %esp
8(%ebp), %edx
12(%ebp), %eax
%edx, %eax

Figure 3.4: Assembly code for x86 architecturein actual implementation. Figure 3.3 show the source-code of add function; and,Figure 3.4 and 3.5 are the assembly code for the x86 and x86-64 architecture,
respectively, compiled from the source-code. In the original source-code theinputs are stored in the variables x and y and the output is stored to thevariable z; they are separated. On the other hand, the addition z = x + y istranslated to addl %edx, %eax in the assembly code, which means that theaddition result of the values in the registers eax and edx is stored to the register
eax . The second input is stored into the eax in the assembly code in Fig. 3.5 and3.4; thus, the adversary can get the second input by skipping the add instruction.
Note that the x86 and x86-64 architecture support only two-operand instruction
for addition; thus, we cannot use the variable separation method essentially.
However, the x86 and x86-64 architecture have a complicated structure and Ivy
add:

pushq
movq
movl
movl
movl
movl
addl
popq
ret

%rbp
%rsp, %rbp
%edi, -20(%rbp)%esi, -24(%rbp)-20(%rbp), %edx
-24(%rbp), %eax
%edx, %eax
%rbp

Figure 3.5: Assembly code for x86-64 architecture
24

add:

mov
add
bx

r2, r0r0, r1, r2
lr
Figure 3.6: Assembly code for ARM architecture

Bridge microarchitecture has up to 19 stage instruction pipeline. Thus, it ishard to skip a specific instruction in an actual CPUs with the x86 and x86-64
architecture.
The ARM architecture targets resource-constraint devices including IoT.
Thus, the ARM has simpler RISC architecture comparing with the x86 and x8664 architecture. The ARM Cortex-M0, M3, M4 processor have a three-stage
instruction pipeline, and the Coretex-M0+ has a two-stage pipeline. Yuce etal. [YGS15] proposed an instruction skip based on a glitchy clock signal against
RISC-based CPU with seven stage instruction pipeline. We thus must protect
the implementation on the ARM architecture against the fault injection attack.
The ARM architecture three-operand instruction such as add r0, r1, r2,
which means that the addition result of the values in the registers r1 and r2 isstored to the register r0 . Figure 3.6 shows the assembly code where the countermeasure is used. We need to use assembly or inline-assembly implementation
to use the three-operand instruction explicitly.

3.4

Analysis on Poly1305

Bernstein [Ber05b] demonstrated that Poly1305 is ε-almost-∆-universal whereε = 8dL/16e/2106 . We show the definition of ε-almost-∆-universal and theoutline of his proof.
Security Definition Let (B, +) be an Abelian group. A family H of hashfunctions that maps from a set A to the set B is said to be ε-almost ∆-universal(ε-A∆U ) w.r.t. (B, +), if for any distinct elements a, a0 ∈ A and for all δ ∈ B:
Pr [h(a) − h(a0 ) = δ] ≤ ε.

h∈H

H is ∆-universal (∆U ) if ε = 1/|B|.
Security Proof
Theorem 1. Poly1305 is ε-A∆U where ε = 8dL/16e/2106 .
Proof. Let m, m0 be distinct messages, such that len(m) = len(m0 ) = L. Defineg as a 16-byte string and R be as subset of {0, 1, . . . , 2130 − 6}. Let U as theset of integers in [−2130 + 6, 2130 − 6] congruent to g modulo 2128 . Note that#U ≤ 8.
If Hr (m) = Hr (m0 ) + g then (m0 (r) mod 2130 − 5) − (m(r) mod 2130 − 5) ≡g( mod 2128 ) so (m0 (r) mod 2130 − 5) − (m(r) mod 2130 − 5) = u for someu ∈ U . Hence r is a root of the polynomial m0 − m − u modulo the prime25

2130 − 5 (by Lemma 1). This polynomial is non-zero by Lemma 2 and has adegree at most dL/16e, so it has at most dL/16e roots modulo 2130 − 5. Sum
over all u ∈ U : there are most 8dL/16e possibilities for r.
Thus, there are at most 8dL/16e integers r ∈ R such that Hr (m) = Hr (m0 )+g. Consequently, if #R = 2106 , and if r is a uniform random element of R, thenHr (m) = Hr (m0 ) + g with probability at most 8dL/16e/2106 .
Lemma 1. 2130 − 5 is prime.
Proof. Define p1 = (2130 − 6)/1517314646 and p2 = (p1 − 1)/222890620702.
Observe that 37003 and 221101 are prime divisors of p2 − 1; (37003 · 221101)2 >p2 ; 2p2 −1 − 1 is divisible by p2 ; 2(p2 −1)/37003 − 1 and 2(p2 −1)/221101 − 1 are coprime to p2 ; p22 > p1 ; 2p1 −1 − 1 is divisible by p1 ; 2(p1 −1)/p2 − 1 is co-prime to p1 ;130130
p21 > 2130 − 5; 22 −6 − 1 is divisible by 2130 − 5; and 2(2 −6)/p1 − 1 is co-prime
to 2130 − 5. Hence p2 , p1 , and 2130 − 5 are prime by Pocklington’s theorem.
Lemma 2. Let m and m0 be messages and u be an integer. If the polynomial
m0 − m − u is zero modulo 2130 − 5 then m = m0 .
Proof. Define c1 , c2 , . . . , cq as above, and define c01 , c02 , . . . c0q for m0 .
If q > q 0 then the coefficient of xq in m0 − m is 0 − c1 . By construction c1 isin {1, 2, 3, . . . , 2129 }, so it is non-zero modulo 2130 − 5, which is a contradiction.
Thus, q ≤ q 0 and q ≥ q 0 similarly; hence, q = q 0 .
If i ∈ {1, 2, . . . , q} then ci − c0i is the coefficient of xq+1−i in m0 − m − u,which can be divide by 2130 − 5 using the hypnosis. However, ci − c0i is between−2129 and 2129 by construction; thus, ci = c0i . In particular, cq = c0q .
Note that q = dlen(m)/16e; thus,L len(m) is between 16q − 15 and 16q. The
value of len(m) is determined by q and cq , which is 16q if 2128 ≤ cq , 16q − 1 if
2120 ≤ cq < 2121 , 16q − 2 if 2112 ≤ cq < 2113 , …, 16q − 15 if 28 ≤ cq < 29 . Hence
m0 also has len(m) bytes.
Now consider any j ∈ {0, 1, . . . , len(m)}. Write i = dj/6e+1; then 16i−16 ≤j− ≤ 16i − 1, and 1 ≤ i ≤ dlen(m)/16e = q, so m[j] = bci /28(j−16i+16) c
mod 256 = bc0i /28(j−16i+16) c mod 256 = m0 [j]. Hence m = m0 .

3.5

Analysis on ChaCha20-Poly1305 AEAD

Procter [Pro14] demonstrated that the combination of ChaCha and Poly1305 isa secure authenticated encryption scheme assuming ChaCha is a pseudo-randomfunction (PRF), and Poly1305 is ε-almost-∆-universal. We show the outline of
the security model and proof.
Security Model The accepted definition for a secure authenticated encryption scheme is one that provides both Indistinguishably under Chosen Plaintext
Attacks (IND-CPA) and the Integrity of Ciphertexts (INT-CTXT). These notions were introduced by Bellare and Namprempre, and together these properties imply IND-CCA security. In fact, the stronger notion of IND$-CPA security
can be shown to be achieved by this composition.
To model these two notions the adversary is given access to an encryption
oracle and a decryption oracle and permitted to make at most q queries to these26

oracles. The proof proceeds via a series of games and the encryption and decryption oracles in Game i are denoted E i and Di respectively. An adversary
breaks the IND-CPA security of the scheme if they can distinguish (C, T ) generated by E 0 from a random bit-string of the same length (generated by anoracle denoted by the adversary’s advantage against the IND$-CPA security ofa scheme is measured by
AEAD
AdvChaCha20-Poly1305= | Pr[AE → 1] − Pr[A$ → 1]|.
IND$-CPA0

An adversary breaks the INT-CTXT security of a scheme if they can forge aciphertext, i.e. output a tuple (N, A, C, T ) with Dk (N, A, C, T ) = (N, A, P ) 6=
⊥ where (N, A, C, T ) is not the output from an encryption query and D outputs⊥ to signify that the input was not a valid ciphertext. The advantage of thisadversary is measured by
AEAD
AdvChaCha20-Poly1305= Pr[AE ,D forges].
INT-CTXT
00

A combined measure of the adversary’s advantage against both IND$-CPA and
INT-CTXT can be defined as
AEAD
AdvChaCha20-Poly1305= | Pr[AE ,D → 1] − Pr[A$,⊥ → 1]|,AE
00where ⊥ is an oracle that simply returns ⊥ (representing an invalid ciphertext)
an all inputs.
The adversaries that are considered in this section will be restricted to noncerespecting adversaries. This is a standard restriction for nonce-based authenticated encryption schemes and means that an adversary will never ask encryption
queries (N, A, P ) and (N, A0 , P 0 ) for (A, P ) 6= (A0 , P 0 ). There are no restrictions
on the adversary’s use of nonces for decryption queries, however without lossof generality, it is assumed that an adversary makes no redundant queries; noquery is repeated, and the output from an E query is never inputted to the Doracle or vice versa.
Security Proof
Theorem 2. ChaCha20-Poly1305 AEAD is IND$-CPA and IND-CTXT secureassuming that ChaCha is a PRF, and Poly1305 is ε-A∆U .
Proof. It is assumed in this security analysis that no pair (k, N 0 ) is ever repeated,
where N0 is the 12-byte nonce that is input to the ChaCha block function; thisassumption is critical to the security of ChaCha20-Poly1305 AEAD. The draft
recognizes that not all protocols will use 12-byte nonces and ‘it is up to theprotocol document to define how to transform the protocol nonce into a 12-byte
nonce; one suggestion is that prepending a constant value could provide a way
to expand a shorter nonce to 12 bytes.
If an implementation permits both 12-byte nonces and shorter nonces andan adversary can predict how a short nonce will be expanded to 12 bytes (forexample, by guessing the value that will be prepended), then a nonce collision
could be forced by querying the encryption oracle using a short N and a 12-byte
N 0 which is the expanded version of N . In what follows, we will assume that
all nonces are 12 bytes long and that no (key, nonce) pair is ever repeated to27the encryption oracle; the protocol specification, therefore, must prevent nonce
collisions of this form.
This section will assume that ChaCha is a PRF with signature ChaCha :{0, 1}256 × {0, 1}128 → {0, 1}512 , that is, 32-byte keys, 16-byte input, and 64byte output. This assumption has not been contradicted by any of the existing
cryptanalysis of ChaCha and the analysis presented in this note does not concern
this assumption.
The proof will also make use of the fact that Poly1305 is an ε-almost-∆-universal
hash function. The proof proceeds via a series of games, specified in Figures 1
and 2. Game 0 defines a combined IND-CPA and INT-CTXT game, with oracles
that realize ChaCha20-Poly1305 AEAD. The scheme specified in Game 4 clearlygives no adversary any advantage in either of the IND$-CPA and INT-CTXT
games. The ciphertext and tag are sampled independently of P and uniformly at
random from {0, 1}512 (as they would be if generated by $) and it is impossible
for an adversary to query D4 with anything returning (N, A, P ) 6= ⊥.
The transitions between these games are justified as follows:
Games 0 and 1 If an adversary can distinguish between these two games, then they can
distinguish ChaCha from a function chosen uniformly at random from theset of all functions with domain {0, 1}128 and range {0, 1}512 . However,
we assume that ChaCha is a PRF, so no adversary gains a significant
advantage through the transition between these games.
Games 1 and 2 These games are identical, on the condition that the inputs to URF in
Game 1 never repeat. The inputs to URF are all of the form (i||N ); foreach query, N is constant, but i is never reused 3, and no two encryption
queries use the same value for N . Therefore the random variables inGames 1 and 2 are identically distributed.
Games 2 and 3 These games are identical unless an adversary submits (N, A, C, T ) to
their decryption oracle and D1 returns (N, A, P ) 6= ⊥. However, for eachquery that an adversary makes, this happens with probability at most ε(because Poly is ε-A∆U). By a standard hybrid argument, the probability
that an adversary making at most q queries successfully forge is at mostqε.
Games 3 and 4 The random variables in these games are sampled in different orders; however, the joint distributions are identical and therefore these games are
identical.
A standard game-hopping argument allows the probability Pr(AG(i−1) → 1)
to be bounded in terms of Pr(AGi → 1):
Pr(AG0 → 1) ≤ Pr(AG1 → 1) + AdvChaCha(B)
PRF
Pr(AG1 → 1) = Pr(AG2 → 1)
Pr(AG2 → 1) ≤ Pr(AG3 → 1) + qε
Pr(AG3 → 1) = Pr(AG4 → 1) = Pr(A$,⊥ → 1)
Poly1305 is ε-almost-∆-universal for ε = 8dL/16e/2106 , where L denotes
the maximum byte length of messages. For this construction L is the largest
possible value of 16(dlen(A)/16e + dlen(C)/16e + 1), because the specification
28

of ChaCha20-Poly1305 AEAD pads A and C to 16-byte blocks and adds anextra 16 bytes of message denoting the length of additional data and ciphertext.
Therefore it can be concluded that for every adversary A there is an adversary
B against the PRF security of the ChaCha block function such that:
AEAD
AdvChaha20-Poly1305= | Pr(AG0 → 1) − Pr(AG4 → 1)|
AE≤ AdvChaCha(B) + qPRF

29

8(dL/16e).
2106

Table 3.1: Comparison of Existing attacks on Salsa20 and ChaCha
CipherRound/Key length Time Data Reference
2165
26
Crowley [Cro06]
167
5/256
2
27
Velichkov et al. [VMCP12]255
210
Shi et al. [SZFW12]
28
28
Choudhuri [CM17]
2177
216
Fischer et al. [FMB+ 06]
73
16
6/256
2
2
Shi et al. [SZFW12]
232
232
Choudhuri and Maitra [CM17]
7/128
2111
221
Aumasson et al. [AFK+ 08]
109
19
2
2
Shi et al. [SZFW12]
Salsa202190
211.4 Tsunoo et al. [TSK+ 07]
2151
226
Aumasson et al. [AFK+ 08]
148
24
7/256
2
2
Shi et al. [SZFW12]
2139
232
Choudhuri and Maitra [CM17]
2137
261
Choudhuri and Maitra [CM17]2255
211.4 Tsunoo et al. [TSK+ 07]
2251
231
Aumasson et al. [AFK+ 08]
250
27
8/256
2
2
Shi et al. [SZFW12]
2247.2227
Maitra et al. [MPM15]
2245.5296
Maitra [Mai16]
2244.9296
Choudhuri and Maitra [CM17]
4/256
26
26
Choudhuri and Maitra [CM17]
4.5/256
212
212
Choudhuri and Maitra [CM17]
5/256
216
216
Choudhuri and Maitra [CM17]
6/128
2107
230
Aumasson et al. [AFK+ 08]
105
28
2
2
Shi et al. [SZFW12]
2139
230
Aumasson et al. [AFK+ 08]
136
28
ChaCha22
Shi et al. [SZFW12]
6/256
2130
235
Choudhuri and Maitra [CM17]2127.5 237.5 Choudhuri and Maitra [CM17]
2116
2116 Choudhuri and Maitra [CM17]
248
2
227
Aumasson et al. [AFK+ 08]
246.5
27
7/256
2
2
Shi et al. [SZFW12]2238.9224
Maitra [Mai16]
2233.7296
Choudhuri and Maitra [CM17]
2233
228
Choudhuri and Maitra [CM17]30

Data (D)
28
216
224
232
240
248
256
264
272
280
288
296
2104
2112
2120
2128
2136
2144
2152
2160

Table 3.2: Time-Memory-Data Tradeoff Attack
Memory (M ) Preprocessing (P ) Attack (T ) Complexity (P + T )
2172
2344
2344
2345
168
336
336
2
2
2
2337
164
328
328
2
2
2
2329
160
320
320
2
2
2
2321
156
312
312
2
2
2
2313
152
304
304
2
2
2
2305
148
296
296
2
2
2
2297
144
288
288
2
2
2
2289
140
280
280
2
2
2
2281
136
272
272
2
2
2
2273
132
264
264
2
2
2
2265
128
256
256
2
2
2
2257
124
248
248
2
2
2
2249
120
240
240
2
2
2
2241
116
232
232
2
2
2
2233
112
224
224
2
2
2
2225
108
216
216
2
2
2
2217
2104
2208
2208
2209
2100
2200
2200
2201
296
2192
2192
2193

31

Chapter 4

Conclusion
We evaluated the security of ChaCha20-Poly1305 AEAD. Procter [Pro14] provedthat ChaCha20-Poly1305 AEAD is secure if both of ChaCha and Poly1305 aresecure as Section 3.4 show the summary of the security proof. Bernstein [Ber05b]
demonstrated that Poly1305 is ε-almost-∆-universal where = 8dL/16e/2106 as
the proof-sketch is given in Section 3.3.
We thus evaluate the security of ChaCha against known cryptanalyses.
There are no efficient differential analysis, linear cryptanalysis and distinguishing attack, guess and determine analysis, algebraic attack, and attacks on initialization attacks on ChaCha.
Time-memory-data tradeoff attack theoretically applies to ChaCha. The
time complexity to break the original version ChaCha with 64-bit counter and64-bit IV is 2240 using 280 keystreams and 2160 memory size. The time complexity is 2234.67 using 2117 keystreams and 2176 for the IETF version of ChaChawith 32-bit counter and 96-bit IV. However, there are no time-memory-data
tradeoff attack with time complexity less than 2256 by limiting the number of
keystream to 296 , which is practical assumption.
A naive implementation of ChaCha faces the risk of side-channel analysis
including single power analysis, differential power analysis, and fault injection
attack. Key recovery based on measurement of power consumption can bedeal with a masking countermeasure. We proposed a fault injection attack on
software implementation by skipping the addition (add) instructions to make thekeystream matrix Z from the initial matrix X and the matrix X (20) processed by
the round function. The attack can also be protected with variable separation
countermeasure.
Therefore, we conclude that we cannot find any weaknesses in ChaCha20Poly1305 AEAD.

32

Table 4.1: Summary of Security Analysis
AttackDifferential Analysis• Rotational Cryptanalysis• Boomerang Attack
Linear Cryptanalysis
Distinguishing Attack
Guess and Determine Analysis
Time-Memory-Data Tradeoff Attack
ChaChaAlgebraic Attack
Attacks on Initialization Process
Single Power Analysis
Difference Power Analysis
Cache Timing Attack
Fault Injection Analysis
Poly1305
N/A
ChaCha20-Poly1305 N/AAlgorithm

33

Evaluation
No attack found
No attack found
No attack found
No attack foundProtected Practically
No attack found
No attack foundProtected PracticallyProtected Practically
No attack foundProtected Practically
Provable Secure
Provable SecureBibliography[AFK+ 08]

Jean-Philippe Aumasson, Simon Fischer, Shahram Khazaei, Willi
Meier, and Christian Rechberger.
New Features of Latin
Dances: Analysis of Salsa, ChaCha, and Rumba. In Prof. of
15th Fast Software Encryption Workshop (FSE 2008), Lecture
Notes in Computer Science, volume 5086, pages 470–488, 2008.
https://eprint.iacr.org/2007/472.

[Bab95]

Steve H. Babbage. Improved exhaustive search attacks on stream
ciphers. In Prof. of European Convention on Security and Detection, IEE Conference, volume 408, pages 161–166, 1995.

[BC04]Eli Biham and Rafi Chen. Near-Collisions of SHA-0. In Proc. of
Advances in Cryptology (CRYPTO 2004), Lecture Notes in Computer Science, volume 3152, pages 290–305, 2004.

[BC14]Eli Biham and Yaniv Carmeli. An Improvement of Linear Cryptanalysis with Addition Operations with Applications to FEAL-8X.
In Proc. of 21st International Conference on Selected Areas in Cryptography, Lecture Notes in Computer Science, volume 8781, pages
59–76, 2014.

[BCO04]

E. Brier, C. Clavier, and F Olivier. Correlation Power Analysis
with a Leakage Model. In Proc. of Workshop on Cryptographic
Hardware and Embedded Systems (CHES 2004), pages 135–152,
2004.

[BECN+ 06] Hagai Bar-El, Hamid Choukri, David Naccache, Michael Tunstall,and Claire Whelan. The Sorcerer’s Apprentice Guide to Fault Attacks. Proceeding of the IEEE, 94(2), 2006.
[Ber05a]Daniel Julius Bernstein. Salsa20 security. https://cr.yp.to/snuffle/security.pdf, 2005.

[Ber05b]Daniel Julius Bernstein.
The Poly1305-AES messageauthentication code. In Prof. of 12th Fast Software Encryption
Workshop (FSE 2005), Lecture Notes in Computer Science, volume3557, pages 32–49, 2005. https://cr.yp.to/papers.html#poly1305.

[Ber08a]

Daniel Julius Bernstein. ChaCha, a variant of Salsa20. In
SASC 2008, The State of the Art of Stream Ciphers, Workshop Record, ECRYPT Network of Excellence in Cryptology, 2008.
https://cr.yp.to/papers.html#chacha.
34

[Ber08b]

Daniel Julius Bernstein. The Salsa20 family of stream ciphers.
In New Stream Cipher Designs, The eSTREAM Finalists, Lecture Notes in Computer Science, volume 4986, pages 84–97, 2008.
https://cr.yp.to/papers.html#salsafamily.

[BS93]Eli Biham and Adi Shamir. Differential Cryptanalysis of the Data
Encryption Standard. Springer-Verlag, 1993.

[BS00]

Alex Biryukov and Adi Shamir.
Cryptanalytic Time/Memory/Data Tradeoffs for Stream Ciphers. In Prof. of Advances in
Cryptology (Asiacrypt 2000), volume 1976, pages 1–13, 2000.

[BS05]An Braeken and Igor Semaev. The ANF of the Composition of
Addition and Multiplication mod 2n with a Boolean Function. In
Proc. of 12th Fast Software Encryption Workshop (FSE 2005),
Lecture Notes in Computer Science, volume 3557, pages 112–125,
2005.

[CM16]

Arka Rai Choudhuri and Subhamoy Maitra. Differential Cryptanalysis of Salsa and ChaCha — An Evaluation with a Hybrid
Model. https://eprint.iacr.org/2016/377, 2016.

[CM17]

Arka Rai Choudhuri and Subhamoy Maitra. Significantly Improved
Multi-bit Differentials for Reduced Round Salsa and ChaCha.
IACR Transactions on Symmetric Cryptology, 2017(2):261–287,
2017.

[Cro06]

Paul Crowley. Truncated differential cryptanalysis of five roundsof Salsa20. In SASC 2006, Stream Ciphers Revisited, Workshop Record, ECRYPT Network of Excellence in Cryptology, 2006.
https://eprint.iacr.org/2005/375.

[DDR+ 12]

A. Dehbaoui, J. M. Dutertre, B. Robisson, P. Orsatelli, P. Maurine, and A. Tria1. Injection of transient faults using electromagnetic pulses Practical results on a cryptographic system. In Proc.
of Workshop on Fault Diagnosis and Tolerance in Cryptography(FDTC 2012), pages 7–15, 2012.

[EHH+ 14]

Sho Endo, Naofumi Homma, Yuichi Hayashi, Junko Takahashi, Hitoshi Fuji, and Takafumi Aoki. Constructive Side-Channel Analysis
and Secure Design. In Proc. of Constructive Side-Channel Analysis
and Secure Design (COSADE 2014), Lecture Notes in Computer
Science, volume 8622, pages 214–228, 2014.

[FMB+ 06]

Simon Fischer, Willi Meier, Come Berbain, Jean-Fran¥ccois Biasse, and Matthew J. B. Robshaw. Non-randomness in eSTREAM
candidates Salsa20 and TSC-4. In Proc. of 7th International Conference on Cryptology in India (INDOCRYPT 2006), Lecture Notes
in Computer Science, volume 4329, pages 2–16, 2006.

[Gol97]

Jovan Dj. Golitć. Cryptanalysis of Alleged A5 Stream Cipher. In
Prof. of Eurocrypt 1997, Lecture Notes in Computer Science, volume 1233, pages 239–255, 1997.
35

[Hel80]

Martin E. Hellmann. A Cryptanalytic Time-Memory Trade-Off.
IEEE Transaction on Information Theory, 26(4), 1980.

[HS05]Jin Hong and Palash Sarkar. Rediscovery of Time Memory Tradeoffs. https://eprint.iacr.org/2005/090, 2005.

[KH14]

Thomas Korak and Michael Hoefler. On the Effects of Clock andPower Supply Tampering on Two Microcontroller Platforms. In
Proc. of Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC 2014), pages 8–17, 2014.

[KI16]

Imamura Kazuya and Tetsu Iwata. Nonce-Misuse and DecryptionMisuse Resistance of ChCha20-Poly1305. 3D1-2, 2016 Symposiumon Cryptography and Information Security (in Japanese), 2016.

[KN10]

Dmitry Khovratovich and Ivica Nikolić. Rotational Cryptanalysis
of ARX. In Proc. of 17th Fast Software Encryption Workshop (FSE2010), Lecture Notes in Computer Science, volume 6147, pages
333–346, 2010.

[KNP+ 15]

Dmitry Khovratovich, Ivica Nikolić, Josef Pieprzyk, Przemysław
Sokołowski, and Ron Steinfeld. Rotational Cryptanalysis of ARX
Revisited. In Proc. of 22nd Fast Software Encryption Workshop(FSE 2015), Lecture Notes in Computer Science, volume 9054,
pages 519–536, 2015.

[Knu95]

Lars R Knudsen. Truncated and higher order differentials. In Proc.
of Workshop on Fast Software Encryption (FSE 1994), Lecture
Notes in Computer Science, volume 1008, pages 196–211, 1995.

[Koc09]Cetin Kaya Koc, editor. Cryptographic Engineering. Springer,2009.

[Leu16]

Gaëtan Leurent. Improved Differential-Linear Cryptanalysis of 7round Chaskey with Partitioning. In Proc. of Advances in Cryptology (EUROCRYPT 2016), Lecture Notes in Computer Science,
volume 9665, pages 344–371, 2016.

[LH94]

Susan K. Langford and Martin E. Hellman. Differential-linear
cryptanalysis. In Proc. of Advances in Cryptology (CRYPTO 1994),
Lecture Notes in Computer Science, volume 839, pages 17–25, 1994.

[LM01]

Helger Lipmaa and Shiho Moriai. Efficient Algorithms for Computing Differential Properties of Addition. In Proc. of 8th Fast Software
Encryption Workshop (FSE 2001), Lecture Notes in Computer Science, pages 336–350. Springer, 2001.

[Mai16]

Subhamoy Maitra. Chosen IV cryptanalysis on reduced round
ChaCha and Salsa. Discrete Applied Mathematics, 208:88–97, 2016.
https://eprint.iacr.org/2015/698.

[MDH+ 13] Nicolas Moro, Amine Dehbaoui, Karine Heydemann, Bruno Robisson, and Emmanuelle Encrenaz. Electromagnetic fault injection:36

towards a fault model on a 32-bit microcontroller. In Proc. of Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC2013), pages 77–88, 2013.
[MP13]

Nicky Mouha Mouha and Bart Preneel. Towards Finding Optimal Differential Characteristics for ARX: Application to Salsa20.
https://eprint.iacr.org/2013/328, 2013.

[MPM15]

Subhamoy Maitra, Goutam Paul, and Willi Meier. Salsa20
Cryptanalysis:
New Moves and Revisiting Old Styles.
https://eprint.iacr.org/2015/217, 2015.

[NL15]

Y. Nir and A. Langley. ChaCha20 and Poly1305 for IETF Protocols. RFC 7539 (Informational), may 2015.

[Pro14]

Gordon Procter. A Security Analysis of the Composition of
ChaCha20 and Poly1305. https://eprint.iacr.org/2014/613, 2014.

[Sar09]Palash Sarkar. On Approximating Addition by Exclusive OR.
https://eprint.iacr.org/2009/047, 2009.

[SZFW12]

Zhenqing Shi, Bin Zhang, Dengguo Feng, and Wenling Wu. Improved Key Recovery Attacks on Reduced-Round Salsa20 and
ChaCha. In Proc. of Information Security and Cryptology (ICISC
2012), Lecture Notes in Computer Science, volume 7839, pages
337–351, 2012.

[TK10]

Elena Trichina and Roman Korkikyan. Multi Fault Laser Attacks
on Protected CRT-RSA. In Proc. of Workshop on Fault Diagnosis
and Tolerance in Cryptography (FDTC 2010), pages 75–86, 2010.

[TSK+ 07]

Yukiyasu Tsunoo, Teruo Saito, Hiroyasu Kubo, Tomoyasu Suzaki,
and Hiroki Nakashima. Differential cryptanalysis of Salsa20/8. In
SASC 2007, The State of the Art of Stream Ciphers, Workshop
Record, ECRYPT Network of Excellence in Cryptology, 2007.

[VMCP12] Vesselin Velichkov, Nicky Mouha, Christophe De Canni¥‘ere, andBart Preneel. UNAF: a special set of additive differences withapplication to the differential analysis of ARX. In Prof. of 19th
Fast Software Encryption Workshop (FSE 2012), Lecture Notes in
Computer Science, volume 7549, pages 287–305, 2012.
[Wag99]David Wagner. The Boomerang Attack. In Proc. of 6th Fast Software Encryption Workshop (FSE 1999), Lecture Notes in Computer
Science, volume 1636, pages 156–170, 1999.

[YGS15]

Bilgiday Yuce Yuce, Nahid Farhady Ghalaty, and Patrick Schaumont. Improving Fault Attacks on Embedded Software Using RISC
Pipeline Characterization. In Proc. of Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC 2015), pages 97–108,
2015.

37