Salsa Core Function Salsa stream cipher Salsa n ARX-based stream cipher u ARX: Addition-Rotation-XOR construction n designed by Bernstein in 2005 n one of the finalists for the eSTREAM software portfolio 2 Introduction (1/8)
Salsa Core Function Salsa stream cipher and Rotational Cryptanalysis Salsa n ARX-based stream cipher u ARX: Addition-Rotation-XOR construction n designed by Bernstein in 2005 n one of the finalists for the eSTREAM software portfolio 5 Introduction (4/8) Rotational Cryptanalysis [KN10, KNP+15] n A probabilistic attack that follows the evolution of a so-called rotational pair through the rounds of a function (or a cipher) u Rotational pair: 𝑋, ⃖ 𝑋 = 𝑋, 𝑋 ⋘ 𝑟 , 𝑋, ⃗ 𝑋 = 𝑋, 𝑋 ⋙ 𝑟 u Rotational probability: Pr 𝐹(𝑋) = 𝐹 ⃖ 𝑋 , Pr 𝐹(𝑋) = 𝐹 ⃗ 𝑋 [KN10] Dmitry Khovratovich and Ivica Nikolic. Rotational Cryptanalysis of ARX. FSE 2010. [KNP+15] Dmitry Khovratovich et al. Rotational Cryptanalysis of ARX Revisited. FSE 2015.
Salsa Core Function Motivations: Rotational Cryptanalysis of Salsa Core Function Cryptanalysis of Salsa n mainly differential cryptanalysis u attack only up to 8 rounds (out of 20 rounds) n No study has yet applied rotational cryptanalysis to ARX-based stream ciphers including ChaCha (https://eprint.iacr.org/2020/1049, received 31 Aug 2020) 6 Introduction (5/8)
Salsa Core Function Motivations: Rotational Cryptanalysis of Salsa Core Function Cryptanalysis of Salsa n mainly differential cryptanalysis u attack only up to 8 rounds (out of 20 rounds) n No study has yet applied rotational cryptanalysis to ARX-based stream ciphers including ChaCha (https://eprint.iacr.org/2020/1049, received 31 Aug 2020) 7 Introduction (6/8) Rotational Cryptanalysis of ARX-based Stream Ciphers n practically difficult to obtain a rotational pair of all inputs. u Salsa and ChaCha utilize constant as one of their inputs. n The core function of one encryption scheme is often implemented in another to design symmetric-key primitives. u e.g., SOSEMANUK ← Serpent, BLAKE2 ← ChaCha, SNOW-V ← AES n It is important to clarify whether Salsa core function has a fatal weakness to rotational cryptanalysis.
Salsa Core Function Outline of the Talk 10 1. Preliminaries n Salsa stream cipher n Rotational Cryptanalysis 2. Rotational Cryptanalysis of the Salsa Core Function n Experimental Observations n Our lemmas, theorem, and prediction n Experimental Verifications 3. A Weakness of the Salsa Permutation 4. Conclusion
Salsa Core Function Rotational Cryptanalysis 13 Preliminaries (3/7) Lemma 1 ([Daum05, Corollary 4.12]) 1. If we suppose an 𝑛-bit word 𝐴 to be fixed and an 𝑛-bit word 𝐵 to be chosen uniformly at random, then we obtain Pr 𝐴 + 𝐵 ⋘ 𝑟 = 𝐴 ⋘ 𝑟 + 𝐵 ⋘ 𝑟 = 𝟐!𝒏 𝟐𝒏!𝒓 − 𝑨𝑹 𝟐𝒓 − 𝑨𝑳 , where 𝐴& = 𝑎'!(, … , 𝑎'!) and 𝐴* = 𝑎'!)!(, … , 𝑎+ for 𝐴. 2. If we suppose two 𝑛-bit words 𝐴 and 𝐵 to be chosen uniformly at random, then we obtain Pr 𝐴 + 𝐵 ⋘ 𝑟 = 𝐴 ⋘ 𝑟 + 𝐵 ⋘ 𝑟 = 𝟏 𝟒 𝟏 + 𝟐𝒓!𝒏 + 𝟐!𝒓 + 𝟐!𝒏 . For 𝑛 = 32 and 𝑟 = 1, we obtain the rotational probabilities for the first and second types of modular addition in Lemma 1 as 𝟐!𝟏.𝟐𝟒𝟓 and 𝟐!𝟏.𝟒𝟏𝟓. Rotational probabilities of rotation and XOR: Pr 𝐴 ⋘ 𝑟( ⋘ 𝑟1 = 𝐴 ⋘ 𝑟1 ⋘ 𝑟( = 𝟏 , Pr 𝐴⨁𝐵 ⋘ 𝑟 = 𝐴 ⋘ 𝑟 ⨁ 𝐵 ⋘ 𝑟 = 𝟏 .
Salsa Core Function Rotational Cryptanalysis 14 Preliminaries (4/7) Theorem 1 ([KN10, Theorem 2]): Let 𝑞 be the number of modular additions in an ARX-based primitive that has an arbitrary number of rotations and XORs. Then, the rotational probability of the ARX- based primitive is 𝒑2 𝒒 , where 𝑝2 denotes the rotational probability of modular addition depending on the word size 𝑛 and the rotation amount 𝑟. Fact1: The rotational probability of the ARX-based primitive can be obtained by simply counting the number of the second type of modular additions in Lemma 1.
Salsa Core Function Rotational Cryptanalysis 15 Preliminaries (5/7) Fact2: The rotational probability may not follow Theorem 1 when the output of modular addition becomes the input of another, called chained modular addition. Theorem 1 ([KN10, Theorem 2]): Let 𝑞 be the number of modular additions in an ARX-based primitive that has an arbitrary number of rotations and XORs. Then, the rotational probability of the ARX- based primitive is 𝒑2 𝒒 , where 𝑝2 denotes the rotational probability of modular addition depending on the word size 𝑛 and the rotation amount 𝑟. Fact1: The rotational probability of the ARX-based primitive can be obtained by simply counting the number of the second type of modular additions in Lemma 1.
Salsa Core Function Rotational Cryptanalysis 17 Preliminaries (7/7) Fact2: The rotational probability may not follow Theorem 1 when the output of modular addition becomes the input of another, called chained modular addition. Theorem 1 ([KN10, Theorem 2]): Let 𝑞 be the number of modular additions in an ARX-based primitive that has an arbitrary number of rotations and XORs. Then, the rotational probability of the ARX- based primitive is 𝒑2 𝒒 , where 𝑝2 denotes the rotational probability of modular addition depending on the word size 𝑛 and the rotation amount 𝑟. Fact1: The rotational probability of the ARX-based primitive can be obtained by simply counting the number of the second type of modular additions in Lemma 1. Lemma 2 ([KNP+15, Lemma 2]) Let 𝑎(, … , 𝑎4 be 𝑛-bit words chosen at random and let 𝑟 be the rotation amount. Then Pr( 𝑎( + 𝑎1 ⋘ 𝑟 = 𝑎( ⋘ 𝑟 + 𝑎1 ⋘ 𝑟 ∧ ⋯ ∧ 𝑎( + ⋯ + 𝑎4 ⋘ 𝑟 = 𝑎( ⋘ 𝑟 + ⋯ + 𝑎4 ⋘ 𝑟 ) = 𝟏 𝟐𝒏𝒌 𝒌 + 𝟐𝒓 − 𝟏 𝟐𝒓 − 𝟏 𝒌 + 𝟐𝒏!𝒓 − 𝟏 𝟐𝒏!𝒓 − 𝟏 .
Salsa Core Function Outline of the Talk 18 1. Preliminaries n Salsa stream cipher n Rotational Cryptanalysis 2. Rotational Cryptanalysis of the Salsa Core Function n Experimental Observations n Our lemmas, theorem, and prediction n Experimental Verifications 3. A Weakness of the Salsa Permutation 4. Conclusion
Salsa Core Function Experimental Observations: Toy Model Construct a toy model of the Salsa core function n a word size of 8 bits (instead of 32 bits) u The rotational probability can be obtained from all the input/output rotational pairs with 232 trials, which can execute an exhaustive search. 19 Rotational Cryptanalysis of the Salsa Core Function (1/9) The quarterround function (Toy model of the Salsa Core Function) The function family 𝑓5 is defined by 𝑓5 𝑎, 𝑏, 𝑐, 𝑟 = 𝑎 + 𝑏 ⋘ 𝑟 ⨁𝑐. Then 𝑏 = 𝑓( 𝑎, 𝑑, 𝑏, 7 = 𝑎 + 𝑑 ⋘ 7 ⨁𝑏, 𝑐 = 𝑓1 𝑏, 𝑎, 𝑐, 5 = 𝑏 + 𝑎 ⋘ 5 ⨁𝑐, 𝑑 = 𝑓6 𝑐, 𝑏, 𝑑, 3 = 𝑐 + 𝑏 ⋘ 3 ⨁𝑑, 𝑎 = 𝑓7 𝑑, 𝑐, 𝑎, 1 = 𝑑 + 𝑐 ⋘ 1 ⨁𝑎. The function family 𝐹5 is defined as follows: 𝐹( = 𝑓(, 𝐹1 = 𝑓1 ∘ 𝑓(, 𝐹6 = 𝑓6 ∘ 𝑓1 ∘ 𝑓(, 𝐹7 = 𝑓7 ∘ 𝑓6 ∘ 𝑓1 ∘ 𝑓(
Salsa Core Function Rotational Probability of Function Family 𝑭𝒊 22 Rotational Cryptanalysis of the Salsa Core Function (4/9) Properties of the Salsa Core Function 1. One variable remains the same and becomes the input of the two consecutive modular additions. 2. The rotational probability throughout the function matches the one after the output of the last modular addition. ⋘ 7 𝑎 𝑏 𝑐 𝑑 𝑎′ 𝑏′ 𝑐′ 𝑑′ ⋘ 5
Salsa Core Function Rotational Probability of Function 𝑭𝟐 23 Rotational Cryptanalysis of the Salsa Core Function (5/9) Lemma 3 Let 𝑃 ⋅, 𝑛, 𝑟 be a rotational probability of the first type of modular addition in Lemma 1, that is, 𝑷 𝑨, 𝒏, 𝒓 = 𝟐%𝒏 𝟐𝒏%𝒓 − 𝑨𝑹 𝟐𝒓 − 𝑨𝑳 . Then, the rotational probability of function 𝐹" is given as follows: Pr 𝐹1 𝑎, 𝑏, 𝑐, 𝑑 = 𝐹1 ⃖ 𝑎, 𝑏, ⃖ 𝑐, ⃖ 𝑑 = 2!' K 8∈ +,( 3 𝑃 𝑎, 𝑛, 1 M 𝑃 𝑎, 𝑛, 1 , where Symbol ‘←’ represents the left rotation by one bit, and thus the rotation amount is r = 1. (Proof Sketch) Our proof is based on two properties of the Salsa core function. 1. One variable remains the same and becomes the input of the two consecutive modular additions. u We use the rotational probability for the first type of modular addition in Lemma 1. 2. The rotational probability throughout the function matches the one after the output of the last modular addition. □
Salsa Core Function Rotational Probability of Functions 𝑭𝟑 and 𝑭𝟒 24 Rotational Cryptanalysis of the Salsa Core Function (6/9) Lemma 4 The rotational probability of function 𝑭𝟑 is given by Pr 𝐄< = => 𝐄4 => 𝐄5 M Pr 𝐄@ , where Pr 𝐄@ is given by Lemma 3 and Pr 𝐄6 is given by Pr 𝐄( in the proof of Lemma 3. 𝐄6: 𝑓( 𝑎, 𝑑, 𝑏, 7 = 𝑓( ⃖ 𝑎, ⃖ 𝑑, 𝑏, 7 , 𝐄@: 𝐹1 𝑎, 𝑏, 𝑐, 𝑑 = 𝐹1 ⃖ 𝑎, 𝑏, ⃖ 𝑐, ⃖ 𝑑 , 𝐄<: 𝐹6 𝑎, 𝑏, 𝑐, 𝑑 = 𝐹6 ⃖ 𝑎, 𝑏, ⃖ 𝑐, ⃖ 𝑑 , 𝐄A: 𝐹7 𝑎, 𝑏, 𝑐, 𝑑 = 𝐹7 ⃖ 𝑎, 𝑏, ⃖ 𝑐, ⃖ 𝑑 . Theorem 2 The rotational probability of function 𝑭𝟒 is given by Pr 𝐄A = => 𝐄4 => 𝐄5 M Pr 𝐄< , where Pr 𝐄< is given by Lemma 4, Pr 𝐄@ is given by Lemma 3, and Pr 𝐄6 is given by Pr 𝐄( in the proof of Lemma 3.
Salsa Core Function Experimental Verifications 25 Rotational Cryptanalysis of the Salsa Core Function (7/9) Theorem 1 ([KN10, Theorem 2]): Let 𝑞 be the number of modular additions in an ARX-based primitive that has an arbitrary number of rotations and XORs. Then, the rotational probability of the ARX- based primitive is 𝒑2 𝒒 , where 𝑝2 denotes the rotational probability of modular addition depending on the word size 𝑛 and the rotation amount 𝑟. Fact1: The rotational probability of the ARX-based primitives can be obtained by simply counting the number of the second type of modular additions in Lemma 1.
Salsa Core Function Experimental Verifications 26 Rotational Cryptanalysis of the Salsa Core Function (8/9) Prediction 1: Let 𝑞 be the number of Salsa core functions that has four modular additions. Then, the rotational probability of the Salsa-type ARX primitive is 𝒑2 𝒒 , where 𝑝2 denotes the rotational probability of the Salsa core function depending on the word size 𝑛 and the rotation amount 𝑟. Fact3: If our prediction is correct, we can easily analyze the rotational probability of the Salsa-type ARX primitives by simply counting the number of Salsa core functions. Theorem 1 ([KN10, Theorem 2]): Let 𝑞 be the number of modular additions in an ARX-based primitive that has an arbitrary number of rotations and XORs. Then, the rotational probability of the ARX- based primitive is 𝒑2 𝒒 , where 𝑝2 denotes the rotational probability of modular addition depending on the word size 𝑛 and the rotation amount 𝑟. Fact1: The rotational probability of the ARX-based primitives can be obtained by simply counting the number of the second type of modular additions in Lemma 1.
Salsa Core Function Experimental Verifications 27 Rotational Cryptanalysis of the Salsa Core Function (9/9) Table 4. A comparison between the experimental and theoretical values (log2 ) for the original version of the Salsa core function when the rotation amount is r = 1. The value in parentheses is the predicted value based on Prediction 1. # of modular additions 1 2 3 4 5 6 7 8 Experimental value -1.415 -2.263 -3.263 -4.206 -5.169 -6.126 -7.086 -8.043 Theoretical value -1.415 -2.263 -3.111 -3.959 -- -- -- (-7.918) # of modular additions 9 10 11 12 13 14 15 16 Experimental value -9.000 -9.959 -10.918 -11.875 -12.831 -13.790 -14.753 -15.712 Theoretical value -- -- -- (-11.877) -- -- -- (-15.836) # of modular additions 17 18 19 20 21 22 23 24 Experimental value -16.669 -17.634 -18.580 -19.530 -20.495 -21.446 -22.417 -23.415 Theoretical value -- -- -- (-19.795) -- -- -- (-23.754) The experimental values are not always correct because we could not execute an exhaustive search. n They are considered to be sufficiently accurate as rough estimation.
Salsa Core Function Outline of the Talk 28 1. Preliminaries n Salsa stream cipher n Rotational Cryptanalysis 2. Rotational Cryptanalysis of the Salsa Core Function n Experimental Observations n Our lemmas, theorem, and prediction n Experimental Verifications 3. A Weakness of the Salsa Permutation 4. Conclusion
Salsa Core Function Salsa stream cipher 30 A Weakness of the Salsa Permutation (2/5) By simply counting the number of the Salsa core functions, the rotational probability of the Salsa permutation can be computed based on Prediction 1. n 𝒑2 = 𝟐!𝟑.𝟗𝟓𝟗 from Theorem 2. Salsa permutation comprises four Salsa core functions in each round. n The rotational probability of the 𝑅-round Salsa is 𝒑2 𝟒𝑹 = 𝟐!𝟑.𝟗𝟓𝟗 𝟒𝑹 .
Salsa Core Function ChaCha stream cipher 32 A Weakness of the Salsa Permutation (4/5) According to the study in [KNP+15], the 𝑅-round ChaCha permutation has exactly 8 chains of 2𝑹 modular additions in each chain. n The rotational probability of the 𝑅-round ChaCha permutation can be obtained from Lemme 2 (chained modular addition).
Salsa Core Function Outline of the Talk 34 1. Preliminaries n Salsa stream cipher n Rotational Cryptanalysis 2. Rotational Cryptanalysis of the Salsa Core Function n Experimental Observations n Our lemmas, theorem, and prediction n Experimental Verifications 3. A Weakness of the Salsa Permutation 4. Conclusion
itorym
beomi
hponka
o_ob
fta98
a1da4
sankaku0724
upura
ikurochkin
yukinobaba
langstat
takasumasakazu
sosk
scottboms
aarron
chrislema
eitanlees
brad_frost
3n
lara
tanoku
colly
tammyeverts
addyosmani
vanstee
