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.
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.
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.
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.
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.
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.
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
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
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
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）
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.
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 -
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
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
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
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
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.
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
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
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
itorym
kentaitakura
masatoto
rpc
datascientistsociety
hargon24
geshi0820
yukinobaba
upura
aks3g
beomi
litalicolab
kneath
addyosmani
productmarketing
panda_program
lara
bkeepers
carmenintech
danielanewman
geoffreycrofte
eileencodes
trallard
![Kimura et al.’s Work [KEI+22, KEI+23] 35 On the Effects](https://files.speakerdeck.com/presentations/5b0dc770e07a4b5aabc67c9deac6bf71/slide_35.jpg){kind=link}
