On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers

This slide was presented at CSCML 2024.

Transcript

1. On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers CSCML 2024 Hayato Watanabe1, Ryoma Ito2, Toshihiro Ohigashi1,2 1 Tokai Univresiry, 2 NICT
2. Background 1 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers The importance of proving security in symmetric-key cipher design ⚫ The newly released cipher should be resistant to all known attacks, e.g., ◆ differential, linear, impossible differential, zero-correlation linear, integral attacks, etc. A vast number of potential candidate ciphers ⚫ Analyzing the security of all candidate ciphers may be very time-consuming. Automated tools have made this time-consuming task relatively easy, but 1. it requires high-level expertise in analysis and modeling methods; 2. modeling methods differ depending on the attack vectors; 3. unknown vulnerabilities may be overlooked due to coding mistakes. There have been several cases where unknown vulnerabilities unexpected for the designers were discovered.
3. Background 2 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers The importance of proving security in symmetric-key cipher design ⚫ The newly released cipher should be resistant to all known attacks, e.g., ◆ differential, linear, impossible differential, zero-correlation linear, integral attacks, etc. A vast number of potential candidate ciphers ⚫ Analyzing the security of all candidate ciphers may be very time-consuming. Automated tools have made this time-consuming task relatively easy, but 1. it requires high-level expertise in analysis and modeling methods; 2. modeling methods differ depending on the attack vectors; 3. unknown vulnerabilities may be overlooked due to coding mistakes. There have been several cases where unknown vulnerabilities unexpected for the designers were discovered.
4. Background 3 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers The importance of proving security in symmetric-key cipher design ⚫ The newly released cipher should be resistant to all known attacks, e.g., ◆ differential, linear, impossible differential, zero-correlation linear, integral attacks, etc. A vast number of potential candidate ciphers ⚫ Analyzing the security of all candidate ciphers may be very time-consuming. Automated tools have made this time-consuming task relatively easy, but 1. it requires high-level expertise in analysis and modeling methods; 2. modeling methods differ depending on the attack vectors; 3. unknown vulnerabilities may be overlooked due to coding mistakes. There have been several cases where unknown vulnerabilities unexpected for the designers were discovered.
5. Motivation 4 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers Neural network-based output prediction (NN) attacks [KEI+22, KEI+23] 1. it does not require high-level expertise in analysis and modeling methods; 2. it has the potential to handle all attack vectors; 3. it is less prone to coding mistakes because it requires only input/output interfaces. [KEI+22] Kimura et al. Output Prediction Attacks on Block Ciphers Using Deep Learning. In AIoTS 2022. [KEI+23] Kimura et al. A Deeper Look into Deep Learning-based Output Prediction Attacks Using Weak SPN Block Ciphers. In Journal of Information Processing. Target (block size) NN Differential Linear Small PRESENT with original S-box (16 bits) 5 4 5 Small PRESENT with weak S-box1 (16 bits) 11 11 9 Small PRESENT with weak S-box2 (16 bits) 8 7 8 Maximum number of attackable rounds for NN, differential, and linear attacks. NN attacks have the potential to be a helpful tool for symmetric-key cipher design, especially S-box-based ciphers.
6. Motivation 5 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers Neural network-based output prediction (NN) attacks [KEI+22, KEI+23] 1. it does not require high-level expertise in analysis and modeling methods; 2. it has the potential to handle all attack vectors; 3. it is less prone to coding mistakes because it requires only input/output interfaces. [KEI+22] Kimura et al. Output Prediction Attacks on Block Ciphers Using Deep Learning. In AIoTS 2022. [KEI+23] Kimura et al. A Deeper Look into Deep Learning-based Output Prediction Attacks Using Weak SPN Block Ciphers. In Journal of Information Processing. Target (block size) NN Differential Linear Small PRESENT with original S-box (16 bits) 5 4 5 Small PRESENT with weak S-box1 (16 bits) 11 11 9 Small PRESENT with weak S-box2 (16 bits) 8 7 8 Maximum number of attackable rounds for NN, differential, and linear attacks. NN attacks have the potential to be a helpful tool for symmetric-key cipher design, especially S-box-based ciphers.
7. Our Target: Simon32 6 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers AND-Rotation-XOR-based cipher Round Function ⚫ 𝑓 𝑥 = 𝑥 ⋘ 𝑎 ∧ 𝑥 ⋘ 𝑏 ⊕ 𝑥 ⋘ 𝑐 ⚫ 𝐿𝑖 = 𝑓 𝐿𝑖−1 ⊕ 𝑅𝑖−1 ⊕ 𝑘𝑖 ⚫ 𝑅𝑖 = 𝐿𝑖−1 ∧ AND ⋘ left rotation ⊕ XOR 𝑛 word size (𝑛 = 16) 2𝑛 block size (2𝑛 = 32) 𝑚𝑛 key size (𝑚𝑛 = 64) 𝑎, 𝑏, 𝑐 rotation parameter 𝑎, 𝑏, 𝑐 = 1,8,2 is used for Simon32
8. Related Works 7 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers [KLT15] Kolbl et al. Observations on the SIMON Block Cipher Family. In Crypto 2015. [KSTI18] Kondo et al. On the Design of SIMON Block Cipher: Integral Attacks and Impossible Differential Attacks against SIMON Variants. In IEICE Trans. 2018. The Kolbl-Leander-Tiessen work [KLT15] ⚫ Identified the optimal rotation parameter (𝑎, 𝑏, 𝑐) for Simon32 variants in terms of differential and linear attacks. ⚫ Found some optimal parameter sets for Simon32 variants. ⚫ Concluded that the default parameter (1,8,2) seems to be not always optimal. The Kondo-Sasaki-Todo-Iwata work [KSTI18] ⚫ Extended Kolbl et al.’s work to integral and impossible differential attacks. ⚫ Clalified which rotation parameter is optimal for Simon32. These works focused only on specific attacks and do not address all attack vectors ⚫ The “optimal” rotation parameters identified in these works may not truly be optimal.
9. Questions 8 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers 1. Which structures in Simon-like ciphers are vulnerable to NN attacks? ✓ 𝑎 = 𝑐 or 𝑏 = 𝑐 ✓ 𝑛 − 𝑎 = 𝑐 or 𝑛 − 𝑏 = 𝑐 2. What types of vulnerabilities are detected by NN attacks? ✓ NN attacks have the possibility of detecting vulnerabilities caused by integral attacks. 3. If a vulnerability is detected, can we figure out its root cause? ✓ The lowest diffusion property ✓ Highly biased linear approximations 4. How resistant are the vulnerable ciphers to key recovery attacks? ✓ Vulnerable to Matsui’s algorithm 1
10. Contributions 9 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers 1. Which structures in Simon-like ciphers are vulnerable to NN attacks? ✓ 𝑎 = 𝑐 or 𝑏 = 𝑐 with 0 or 𝑛/2 ✓ 𝑛 − 𝑎 = 𝑐 or 𝑛 − 𝑏 = 𝑐 2. What types of vulnerabilities are detected by NN attacks? ✓ NN attacks have the possibility of detecting vulnerabilities caused by integral attacks. 3. If a vulnerability is detected, can we figure out its root cause? ✓ The lowest diffusion property ✓ Highly biased linear approximations 4. How resistant are the vulnerable ciphers to key recovery attacks? ✓ Vulnerable to a linear key recovery attacks based on Matsui’s algorithm 1
11. Neural Network Model Generation 10 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers Create model For plaintext recovery
12. Neural Network Model Generation 11 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers Learning Training data （plaintext/ciphertext pair） Update model Create model For plaintext recovery KPA setting Black-box model Only an input/output interface is used
13. Neural Network Model Generation 12 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers Learning Prediction Training data （plaintext/ciphertext pair） Update model Create model For plaintext recovery KPA setting Black-box model Only an input/output interface is used For predicting plaintext No duplicates in training and test data Predict plaintext Metrics: average match rate Test data （ciphertext）
14. A Condition for a Successful NN Attacks 13 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers [BJV04] Baigneres et al. How Far Can We Go Beyond Linear Cryptanalysis?. In Asiacrypt 2004. Theorem 1 ([BJV04, Theorem 6]) Let 𝑍1 , … , 𝑍𝑛 be independent and identically distributed random variables over the set ℤ of distribution 𝐃, 𝐃0 and 𝐃1 be two distributions of same support which are close to each other, and 𝑛 be the number of samples of the best distinguisher between 𝐃 = 𝐃0 or 𝐃 = 𝐃1 . Let 𝑑 be a real number such that 𝑛 = 𝑑 σ𝑧∈ℤ 𝜀𝑧 2 𝑝𝑧 where 𝑝𝑧 and 𝑝𝑧 + 𝜀𝑧 are probabilities of a random variables 𝑧 following 𝐃0 and 𝐃1 . Then, the overall probability of error is 𝑃𝑒 ≈ 𝛷 − 𝑑/2 , where 𝛷 ∙ is the distribution function of the standard normal distribution. The average match rate is derived by computing the predicted probabilities for each bit and then calculating the average value of all the predicted probabilities for 2𝑛 bits. ⚫ NN attacks are successful when the average match rate is 0.505 or higher. ⚫ The confidence level of this condition is about 0.7.
15. Example Case 14 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers An Experimental Result of the NN attack for a Simon32 vatiant with (4,1,12). The average match rate is derived by computing the predicted probabilities for each bit and then calculating the average value of all the predicted probabilities for 2𝑛 bits. ⚫ NN attacks are successful when the average match rate is 0.505 or higher. ⚫ The confidence level of this condition is about 0.7. Round Average Match Rate success ( ) or failure (-) 1 0.99047 2 0.57558 3 0.55783 4 0.54309 5 0.52027 6 0.51634 7 0.51215 8 0.50619 9 0.50413 -
16. Hyperparameters 15 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers [KEI+22] Kimura et al. Output Prediction Attacks on Block Ciphers Using Deep Learning. In AIoTS 2022. We follow the hyperparameters used in Kimura et al.s’ work. [KEI+22] Number of training data† 215 Number of test data† 215 Method LSTM Number of nodes for input/output layer‡ 32 Number of hidden nodes 300 Number of hidden layers 1 Loss function Mean squared error Optimizer Adam Initial value of learning rate 0.01 Batch size 250 Number of epochs 100 † Number of plaintext/ciphertext pairs (no duplicates in training and test data) ‡ Block size
17. Experimental Results 16 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers
18. Experimental Results 17 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers
19. Experimental Results 18 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers
20. Experimental Results 19 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers
21. Experimental Results 20 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers 𝒂 = 𝒄 or 𝒃 = 𝒄 𝒏 − 𝒂 = 𝒄 or 𝒏 − 𝒃 = 𝒄
22. A Comprehensive Analysis of Vulnerable Structure 21 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers
23. A Comprehensive Analysis of Vulnerable Structure 22 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers
24. A Comprehensive Analysis of Vulnerable Structure 23 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers
25. A Comprehensive Analysis of Vulnerable Structure 24 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers
26. A Comprehensive Analysis of Vulnerable Structure 25 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers 𝟎 or 𝟖 (= 𝒏/𝟐)
27. Effect of a Rotation Parameter with ”𝑎 = 𝑐” or ”𝑏 = 𝑐” 26 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers 𝑓(𝑥) Original Simon32 𝑓 𝑥 = 𝑥 ⋘ 𝑎 ∧ 𝑥 ⋘ 𝑏 ⊕ 𝑥 ⋘ 𝑐
28. Effect of a Rotation Parameter with “𝑎 = 𝑐” or “𝑏 = 𝑐” 27 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers 𝑓(𝑥) መ 𝑓(𝑥) Original Simon32 Rotation parameter: “𝑎 = 𝑐” መ 𝑓 𝑥 = 𝑥 ⋘ 𝑎 ∧ 𝑥 ⋘ 𝑏 ⊕ 𝑥 ⋘ 𝑎 መ 𝑓 𝑥 = 𝑥 ⋘ 𝑎 ∧ 𝑥 ⋘ 𝑏 ⊕ 11 … 11 መ 𝑓 𝑥 = 𝒙 ⋘ 𝒂 ∧ ¬(𝒙 ⋘ 𝒃) 𝑓 𝑥 = 𝑥 ⋘ 𝑎 ∧ 𝑥 ⋘ 𝑏 ⊕ 𝑥 ⋘ 𝑐
29. Effect of a Rotation Parameter with ”0” or ”𝒏/𝟐” 28 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers Diffusion property for the rotation parameter (1,0,1). Verify the diffusion property ⚫ (1,0,1), including “𝑎 = 𝑐” and “0” ⚫ (5,2,2), including ”𝑏 = 𝑐” ⚫ (1,8,2), original parameter Based on the propagation rules ⚫ Initialize ⚫ Rotation/Swap ⚫ AND ⚫ XOR ⚫ Stop
30. Example Simulation Result 29 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers Simulation results for the rotation parameter (1,0,1).
31. Example Simulation Result 30 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers Simulation results for the rotation parameter (1,0,1).
32. Example Simulation Result 31 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers Simulation results for the rotation parameter (1,0,1).
33. Summary of Simulation Results 32 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers Summary of our simulation results for (1,0,1), (5,2,2), and (1,8,2). No. Rotation Parameter #rounds† Note 1 (1,0,1) 24 including “a=c” and “0” 2 (5,2,2) 13 including “b=c” 3 (1,8,2) 7 original parameter † Number of rounds for satisfying the full diffusion property
34. Summary 33 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers 1. Which structures in Simon-like ciphers are vulnerable to NN attacks? ✓ 𝑎 = 𝑐 or 𝑏 = 𝑐 with 0 or 𝑛/2 ✓ 𝑛 − 𝑎 = 𝑐 or 𝑛 − 𝑏 = 𝑐 2. What types of vulnerabilities are detected by NN attacks? ✓ NN attacks have the possibility of detecting vulnerabilities caused by integral attacks. 3. If a vulnerability is detected, can we figure out its root cause? ✓ the lowest diffusion property ✓ highly biased linear approximations 4. How resistant are the vulnerable ciphers to key recovery attacks? ✓ Vulnerable to a linear key recovery attacks based on Matsui’s algorithm 1
35. Appendix On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers 34
36. Kimura et al.’s Work [KEI+22, KEI+23] 35 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers For example: Small PRESENT with original S-box ⚫ The maximum number of attackable rounds for the NN attack is 5 ⚫ The maximum number of attackable rounds for the differential attack is 4 ⚫ The maximum number of attackable rounds for the linear attack is 5 Target (block size) NN Differential Linear Small PRESENT with original S-box (16 bits) 5 4 5 Small PRESENT with weak S-box1 (16 bits) 11 11 9 Small PRESENT with weak S-box2 (16 bits) 8 7 8 Maximum number of attackable rounds for NN, differential, and linear attacks. The NN attack is comparable to the higher of the maximum number of attackable rounds for differential or linear attack. [KEI+22] Kimura et al. Output Prediction Attacks on Block Ciphers Using Deep Learning. In AIoTS 2022. [KEI+23] Kimura et al. A Deeper Look into Deep Learning-based Output Prediction Attacks Using Weak SPN Block Ciphers. In Journal of Information Processing.
37. How to Handle Secret Keys 36 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers Learning Prediction Training data （plaintext/ciphertext pair） Update model Create model For plaintext recovery Single-key setting Test data （ciphertext） The same key used in the training data
38. A Condition for a Successful NN Attacks 37 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers [BJV04] Baigneres et al. How Far Can We Go Beyond Linear Cryptanalysis?. In Asiacrypt 2004. Theorem 1 ([BJV04, Theorem 6]) Let 𝑍1 , … , 𝑍𝑛 be independent and identically distributed random variables over the set ℤ of distribution 𝐃, 𝐃0 and 𝐃1 be two distributions of same support which are close to each other, and 𝑛 be the number of samples of the best distinguisher between 𝐃 = 𝐃0 or 𝐃 = 𝐃1 . Let 𝑑 be a real number such that 𝑛 = 𝑑 σ𝑧∈ℤ 𝜀𝑧 2 𝑝𝑧 where 𝑝𝑧 and 𝑝𝑧 + 𝜀𝑧 are probabilities of a random variables 𝑧 following 𝐃0 and 𝐃1 . Then, the overall probability of error is 𝑃𝑒 ≈ 𝛷 − 𝑑/2 , where 𝛷 ∙ is the distribution function of the standard normal distribution. ⚫ 𝑃𝑒 = 1 − 0.7 = 0.3 ≈ 𝛷 − 𝑑/2 ≈ 𝛷 0.53 ∴ 𝒅 ≈ 𝟏. 𝟏𝟐 ⚫ 𝒏 = 𝟐𝟏𝟓, 𝒑𝟎 = 𝟎. 𝟓 𝑛 = 𝑑 𝜀0/𝑝0 ∴ 𝜺𝟎 = 𝟎. 𝟎𝟎𝟒𝟏𝟑 ⋯ 𝑃 𝑒 : error probability, 0.7: confidence level of the successful conditiontes, 𝑛: # test data, 𝑝0 : the average match rate for random guess, 𝑝0 + 𝜀0 : the average match rate for the NN attack
39. SAT/CP-based Automated Tools 38 On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers Many automated tools are available as open-source to search for various types of distinguishing attacks. We customize and use the following tools: ⚫ The maximum number of rounds for differential and linear distinguishing attacks is evaluated by Sun et al.’s SAT-based tool1. ⚫ The maximum number of rounds for impossible differential and zero-correlation linear distinguishing attacks is evaluated by Hadipour et al.’s CP-based tool2. ⚫ The maximum number of rounds for integral distinguishing attack is evaluated by Hadipour et al.’s SAT-based tool3. 1 https://github.com/SunLing134340/Accelerating_Automatic_Search 2 https://github.com/hadipourh/zeroplus 3 https://github.com/hadipourh/mpt
40. Definitions of Propagation Rules On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers 39