張仁俊 (Jen-Chun Chang) 國立台北大學 資訊工程學系 通訊工程研究所 電機工程研究所

Presentation on theme: "張仁俊 (Jen-Chun Chang) 國立台北大學 資訊工程學系 通訊工程研究所 電機工程研究所"— Presentation transcript:

1 張仁俊 (Jen-Chun Chang) 國立台北大學 資訊工程學系 通訊工程研究所 電機工程研究所
區塊加密法的攻擊與設計 張仁俊 (Jen-Chun Chang) 國立台北大學 資訊工程學系 通訊工程研究所 電機工程研究所

2 『密碼系統』的分類 Symmetric, Asymmetric Block cipher, Stream cipher
Symmetric Cryptosystems Asymmetric Cryptosystems Block cipher, Stream cipher Block cipher (without memory) Stream cipher (with memory) 台北大學資訊工程系 編碼與密碼實驗室

3 Symmetric Cryptosystems
台北大學資訊工程系 編碼與密碼實驗室

4 Symmetric Cryptosystems
台北大學資訊工程系 編碼與密碼實驗室

5 Asymmetric Cryptosystems
台北大學資訊工程系 編碼與密碼實驗室

6 Block v.s. Stream ciphers
memory 台北大學資訊工程系 編碼與密碼實驗室

7 『攻擊』的分類 Ciphertext-Only attack (密文攻擊) Known-Plaintext attack (已知明文攻擊)
Chosen-Plaintext attack (自選明文攻擊) Chosen-Ciphertext attack (自選密文攻擊) 台北大學資訊工程系 編碼與密碼實驗室

8 『安全』的種類 Unconditional security Computational security
Provable security Everlasting security 台北大學資訊工程系 編碼與密碼實驗室

9 Block cipher 的攻擊 最常見且廣泛有效的攻擊 Linear attack Differential attack
以SPN cipher為例 Easy to understand 台北大學資訊工程系 編碼與密碼實驗室

10 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? 台北大學資訊工程系 編碼與密碼實驗室

11 Linear attack 台北大學資訊工程系 編碼與密碼實驗室

12 Differential attack 台北大學資訊工程系 編碼與密碼實驗室

13 SPN 架構 台北大學資訊工程系 編碼與密碼實驗室

14 SPN 架構 台北大學資訊工程系 編碼與密碼實驗室

15 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 台北大學資訊工程系 編碼與密碼實驗室

16 SPN cipher Substitution (S-box) 台北大學資訊工程系 編碼與密碼實驗室

17 SPN cipher Permutation 台北大學資訊工程系 編碼與密碼實驗室

18 台北大學資訊工程系 編碼與密碼實驗室

19 SPN cipher Why permutation in round 4 is omitted?
useless Why a sub-key k5 is applied? Protect S41, S42, S43, S44 台北大學資訊工程系 編碼與密碼實驗室

20 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 台北大學資訊工程系 編碼與密碼實驗室

21 Linear attack Known-plaintext attack The basic idea:
To find an expression of the form which holds with high or low probability 台北大學資訊工程系 編碼與密碼實驗室

22 Linear attack Linear probability bias = PL － 1/2 台北大學資訊工程系 編碼與密碼實驗室

23 Linear attack Given: 台北大學資訊工程系 編碼與密碼實驗室

24 Linear attack Then : 台北大學資訊工程系 編碼與密碼實驗室

25 Linear attack That is: 台北大學資訊工程系 編碼與密碼實驗室

26 Linear attack 台北大學資訊工程系 編碼與密碼實驗室

27 Linear attack A question: Suppose that x1, x2, x3 are pair-wise independent, are x1⊕x2, x2⊕x3 independent? 台北大學資訊工程系 編碼與密碼實驗室

28 Linear attack 台北大學資訊工程系 編碼與密碼實驗室

29 Linear attack 台北大學資訊工程系 編碼與密碼實驗室

30 Linear attack 台北大學資訊工程系 編碼與密碼實驗室

31 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. 台北大學資訊工程系 編碼與密碼實驗室

32 Linear attack Use approximations of the S-boxes: 台北大學資訊工程系 編碼與密碼實驗室

33 台北大學資訊工程系 編碼與密碼實驗室

34 Linear attack Final version of the linear approximation 台北大學資訊工程系
編碼與密碼實驗室

35 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 ½. 台北大學資訊工程系 編碼與密碼實驗室

36 Linear attack 10000 known plaintext-ciphertext pairs
For each guess of target partial subkey 台北大學資訊工程系 編碼與密碼實驗室

37 Linear attack 台北大學資訊工程系 編碼與密碼實驗室

38 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? 台北大學資訊工程系 編碼與密碼實驗室

39 Differential attack Chosen-plaintext attack The basic idea:
To find a differential which occurs with a high probability 台北大學資訊工程系 編碼與密碼實驗室

40 Differential attack 台北大學資訊工程系 編碼與密碼實驗室

41 Differential attack 台北大學資訊工程系 編碼與密碼實驗室

42 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. 台北大學資訊工程系 編碼與密碼實驗室

43 Differential attack Keyed and unkeyed S-boxes have the same DDT.
台北大學資訊工程系 編碼與密碼實驗室

44 Differential attack Differentials used 台北大學資訊工程系 編碼與密碼實驗室

45 台北大學資訊工程系 編碼與密碼實驗室

46 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. 台北大學資訊工程系 編碼與密碼實驗室

47 Differential attack 10000 chosen plaintext/ciphertexts 5000 chosen plaintext/ciphertexts pairs For each guess of target partial subkey How to speed up the computation? 台北大學資訊工程系 編碼與密碼實驗室

48 Differential attack 台北大學資訊工程系 編碼與密碼實驗室

49 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? 台北大學資訊工程系 編碼與密碼實驗室

50 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 台北大學資訊工程系 編碼與密碼實驗室

51 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 台北大學資訊工程系 編碼與密碼實驗室