張仁俊 (Jen-Chun Chang) 國立台北大學 資訊工程學系 通訊工程研究所 電機工程研究所 區塊加密法的攻擊與設計 張仁俊 (Jen-Chun Chang) 國立台北大學 資訊工程學系 通訊工程研究所 電機工程研究所
『密碼系統』的分類 Symmetric, Asymmetric Block cipher, Stream cipher Symmetric Cryptosystems Asymmetric Cryptosystems Block cipher, Stream cipher Block cipher (without memory) Stream cipher (with memory) 台北大學資訊工程系 編碼與密碼實驗室
Symmetric Cryptosystems 台北大學資訊工程系 編碼與密碼實驗室
Symmetric Cryptosystems 台北大學資訊工程系 編碼與密碼實驗室
Asymmetric Cryptosystems 台北大學資訊工程系 編碼與密碼實驗室
Block v.s. Stream ciphers memory 台北大學資訊工程系 編碼與密碼實驗室
『攻擊』的分類 Ciphertext-Only attack (密文攻擊) Known-Plaintext attack (已知明文攻擊) Chosen-Plaintext attack (自選明文攻擊) Chosen-Ciphertext attack (自選密文攻擊) 台北大學資訊工程系 編碼與密碼實驗室
『安全』的種類 Unconditional security Computational security Provable security Everlasting security 台北大學資訊工程系 編碼與密碼實驗室
Block cipher 的攻擊 最常見且廣泛有效的攻擊 Linear attack Differential attack 以SPN cipher為例 Easy to understand 台北大學資訊工程系 編碼與密碼實驗室
A necessary condition for candidates of AES (Advanced Encryption Standard) is to be strong enough under Linear attack Differential attack AES (Rijndael) Design principle? Security analysis? 台北大學資訊工程系 編碼與密碼實驗室
Linear attack 台北大學資訊工程系 編碼與密碼實驗室
Differential attack 台北大學資訊工程系 編碼與密碼實驗室
SPN 架構 台北大學資訊工程系 編碼與密碼實驗室
SPN 架構 台北大學資訊工程系 編碼與密碼實驗室
SPN cipher Block size: 16 Key size: 16×5 ? (5 × 16-bit sub-keys) Number of rounds: 4 In each round Substitution Permutation Key mixing 台北大學資訊工程系 編碼與密碼實驗室
SPN cipher Substitution (S-box) 台北大學資訊工程系 編碼與密碼實驗室
SPN cipher Permutation 台北大學資訊工程系 編碼與密碼實驗室
台北大學資訊工程系 編碼與密碼實驗室
SPN cipher Why permutation in round 4 is omitted? useless Why a sub-key k5 is applied? Protect S41, S42, S43, S44 台北大學資訊工程系 編碼與密碼實驗室
SPN cipher Decryption Encrypt and decrypt procedures are S-boxes are inversed Sub-keys are applied in reversed order Encrypt and decrypt procedures are Slightly different 台北大學資訊工程系 編碼與密碼實驗室
Linear attack Known-plaintext attack The basic idea: To find an expression of the form which holds with high or low probability 台北大學資訊工程系 編碼與密碼實驗室
Linear attack Linear probability bias = PL － 1/2 台北大學資訊工程系 編碼與密碼實驗室
Linear attack Given: 台北大學資訊工程系 編碼與密碼實驗室
Linear attack Then : 台北大學資訊工程系 編碼與密碼實驗室
Linear attack That is: 台北大學資訊工程系 編碼與密碼實驗室
Linear attack 台北大學資訊工程系 編碼與密碼實驗室
Linear attack A question: Suppose that x1, x2, x3 are pair-wise independent, are x1⊕x2, x2⊕x3 independent? 台北大學資訊工程系 編碼與密碼實驗室
Linear attack 台北大學資訊工程系 編碼與密碼實驗室
Linear attack 台北大學資訊工程系 編碼與密碼實驗室
Linear attack 台北大學資訊工程系 編碼與密碼實驗室
Linear attack Properties of LAT +8 in the top left corner Other elements in the top row and first column are all 0. Sum of any row or column must be +8 or -8. (Problem: Prove it! ) An ideal S-box is clearly not achievable. 台北大學資訊工程系 編碼與密碼實驗室
Linear attack Use approximations of the S-boxes: 台北大學資訊工程系 編碼與密碼實驗室
台北大學資訊工程系 編碼與密碼實驗室
Linear attack Final version of the linear approximation 台北大學資訊工程系 編碼與密碼實驗室
Linear attack Target partial subkey Correct partial subkey to be guessed Correct partial subkey Expression holds with prob far from ½. Incorrect partial subkey Expression holds with prob close to ½. 台北大學資訊工程系 編碼與密碼實驗室
Linear attack 10000 known plaintext-ciphertext pairs For each guess of target partial subkey 台北大學資訊工程系 編碼與密碼實驗室
Linear attack 台北大學資訊工程系 編碼與密碼實驗室
Linear attack We hope Complexity of attack Why? The magnitude of the bias in S-boxes, larger. The number of active S-boxes, fewer. Complexity of attack Why? 台北大學資訊工程系 編碼與密碼實驗室
Differential attack Chosen-plaintext attack The basic idea: To find a differential which occurs with a high probability 台北大學資訊工程系 編碼與密碼實驗室
Differential attack 台北大學資訊工程系 編碼與密碼實驗室
Differential attack 台北大學資訊工程系 編碼與密碼實驗室
Differential attack Properties of DDT Sum of any row or column is 2n=16. All elements are even. The top right corner is always 2n=16. All other elements in the first row and first column are 0. An ideal S-box is clearly not achievable. 台北大學資訊工程系 編碼與密碼實驗室
Differential attack Keyed and unkeyed S-boxes have the same DDT. 台北大學資訊工程系 編碼與密碼實驗室
Differential attack Differentials used 台北大學資訊工程系 編碼與密碼實驗室
台北大學資訊工程系 編碼與密碼實驗室
Differential attack Target partial subkey Correct partial subkey to be guessed Correct partial subkey Differentials occurs with high prob. Incorrect partial subkey Differentials occurs with prob close to 0. 台北大學資訊工程系 編碼與密碼實驗室
Differential attack 10000 chosen plaintext/ciphertexts 5000 chosen plaintext/ciphertexts pairs For each guess of target partial subkey How to speed up the computation? 台北大學資訊工程系 編碼與密碼實驗室
Differential attack 台北大學資訊工程系 編碼與密碼實驗室
Differential attack We hope Complexity of attack Why? The differential probability of S-boxes, larger. The number of active S-boxes, fewer. Complexity of attack Why? 台北大學資訊工程系 編碼與密碼實驗室
Block cipher研究的重點 S-box Permutation Key scheduling (Subkey generation) Minimize the max value in LAT Minimize the max value in DDT Permutation Make the number of active S-boxes larger Key scheduling (Subkey generation) Make subkeys more independent 台北大學資訊工程系 編碼與密碼實驗室
Block cipher的參考文獻 Conferences & Journals Search Keywords Crypto Eurocrypt Journal of Cryptology IEEE Transactions on Information Theory Designs, Codes, and Cryptography Search Keywords block cipher, S-box, key scheduling 台北大學資訊工程系 編碼與密碼實驗室