2015-05-16

資訊安全期中考筆記

1. Problem
2. Notes

筆記錯誤多多，請以僅供參考的角度去質疑

Problem

Please compare the CFB mode the OFB mode by providing a table indicating at least 5 of their advantage and corresponding disadvantage.
This question is about issues of random access of encryption and decryption. Define notations or symbols you need before providing your answer. Please describe how to use CFB mode and CTR mode to randomly encrypt and decrypt a file Why OFB mode is inappropriate to randomly encrypt and decrypt a file?
What is the one-time pad (please provide a figure to explain it) and what is the main security requirement ?
Follow
1. What is the main weakness (disadvantage) of ECB mode ?
2. How CBC resolves this security problem (explained in mathematical approach) ?
Follow
1. Block ciphers process messages in blocks like an extremely large substitution, but this is very difficult to implement for a very big block size. What is Shannon’s idea to realize a block cipher with big block size ?
2. Feistel cipher structure provides a real implementation of Shannon’s idea. Please explain the main features of Feistel cipher structure.
What is the avalanche effect of a block cipher ?
What is the Triple -DES with two keys ? Please explain the process the derive the complexity of meet-in-the-middle attack on Triple-DES with two keys.
For all AES round operations, which operation(s) provides substitution and which operations(s) provides diffusion ?
Please describe the details of BBS pseudorandom number generator.
Below is the pseduo code of RC4. Please design a modified RC4 version with message dependent property of key stream.

init(master_key) // shuffle S-array with master_key
i = j = 0
for each message byte M
    i = (i + 1) mod 256
    j = (j + S[i]) mod 256
    swap(S[i], S[j])
    t = (S[i] + S[j]) mod 256
    C = M xor S[t]

Notes

Part 1

請參照《資訊安全小考筆記》

Part 2

請參照《資訊安全小考筆記》

Part 3

one-time pad 概念圖如下

                +------------+               +------------+               
                | random key |               | random key |               
                | generator  |               | generator  |               
                +------------+               +------------+               
                      |                             |                     
                      |                             |                     
                      | Ki                          | Ki                  
                      |                             |                     
                      |                             |                     
       Pi          +--v--+           Ci          +--v--+       Pi         
------------------>+ XOR +---------------------->+ XOR +----------------> 
                   +-----+                       +-----+                  
                                                                          
                   From Alice                    To Blob

one-time pad 主要是靠 key 不重複使用來維護資料安全，但是雙方同時產生出相同的 random key 是很困難。由於不重複使用，靠一個 random key 的產生提供 random mask 消除明文和祕聞之間的關係。但是雙方都要相同 random key 是相當困難的，通常 generator 是由某個偽隨機數產生器，由演算法產生的到底是不是隨機數呢？

一定要 random key，不能有任何的 dependent、 不能重複 (reuse) ，否則會有 已知明文攻擊 。

Part 4

ECB mode 在相同明文對應相同的密文，這容易受到大多數的攻擊，如收集已知明文或密文所進行的攻擊。由於明文和密文的關係明確，也因此在 圖片資料 加密傳送，會出現 大量重複 的密文。

CBC mode 提供 random mask 的效果

$$C_{-1} = IV \\ C_{i} = E_{k}(C_{i-1} \text{ XOR } P_{i}) \\$$

從$C_{i-1} \text{ XOR } P_{i}$ 操作中可以發現到，讓相同的明文對應到不同的密文 (在前一個密文不同時)，解決 ECB 在相同明文加密只會對應種密文。

Part 5

Shannon’s idea 請參照《資訊安全小考筆記》

Feistel cipher structure 藉由三個規則實作

多個回合 (round)
藉由一半的訊息加密另一半的訊息
兩個半段訊息位置交換

Part 6

Avalanche effect 讓相似的明文 Pi, Pj (漢明距離 $H(Pi, Pj) = 1$ … 之類的) 對應的密文 Ci, Cj 能有相當大的差異 (漢明距離 $H(Ci, Cj) = \text{half-bit}$ 的期望值)，將只有一點不同的差異，擴散到密文的每個地方，放大差異的效果。

Part 7

Triple-DES

$E_{k_{1}}\left [ D_{k_{2}} \left [ E_{k_{1}} \left [ P_{i} \right ] \right ] \right ] = C_{i}$

當指使用兩次的 DES，受到中間相遇法的攻擊，理論上的複雜度與 1 個 DES 一樣，複雜度大約都在 $O(2^{56})$，因此效果並沒有變得更好。然而在 Triple-DES 複雜度就提升到 $O(2^{112})$。

中間相遇法攻擊

$$X = D_{k_{2}} \left [ E_{k_{1}} \left [ P_{i} \right ] \right ] \\ C_{i} = E_{k_{1}} \left [ Y \right ]$$

從已知的明文、密文，目標是讓 $X = Y$，窮舉 key，如果發生 $X = Y$ 則表示找到一組可行的解。窮舉得到 $X$ 的複雜度為 $O(2^{56} \times 2^{56}) = O(2^{112})$，而 $Y$ 則需要 $O(2^{56})$，當 $X = Y$ 符合時，則表示 key 找到！

當然也可以抽換相遇的地點，如下是另外一種

$$X = E_{k_{1}} \left [ P_{i} \right ] \\ C_{i} = E_{k_{1}} \left [ D_{k_{2}} \left [ Y \right ] \right ]$$

不管怎麼切割，都至少要窮舉兩把 key 來得到其中一個相遇結果，複雜度都落在 $O(2^{112})$。如果說對應兩個表的結果需要 $O(log \text{ n})$ 的時間，則複雜度為 $O(112 \times 2^{112})$。

Part 8

Step	Function
Substition Bytes	substitution
Shift Rows	diffusion
Mix Column	diffusion, substitution
Add Round Key	substitution

比較討厭的是 Shift Rows 為什麼提供是 diffusion，明明對於兩個相似明文加密上，漢明距離沒有增加！但是 diffusion 不只是讓差異數量增加，還要考量差異位置的變動，相鄰差異的位置被轉移到兩個遠處，就能提供 diffusion！這會讓攻擊者無從判定差異的對應。

Part 9

Blum Blum Shub

$$X_{i} = X_{i-1}^2 \text{mod } N \\ N = p \times q \\ p, q \text{ is prime nubmer, } \\ p \equiv 3 (\text{mod } 4) \\ q \equiv 3 (\text{mod } 4)$$

Part 10

message dependent RC4

第一版本

i = j = 0, Cprev = 0
for each message byte M
    i = (i + 1) mod 256
    j = (j + S[i]) mod 256
    swap(S[i], S[j])
    t = (S[i] + S[j] + Cprev) mod 256
    C = M xor S[t]
    if sender
        Cprev = C
    if receiver
        Cprev = M

好像不管怎麼寫兩邊似乎都很難相同。

第二版本

i = j = 0, C = 0
for each message byte M
    i = (i + C) mod 256
    j = (j + S[i]) mod 256
    swap(S[i], S[j])
    t = (S[i] + S[j]) mod 256
    C = M xor S[t]

感覺上述的寫法，萬一 C 被竄改，會導致錯誤擴散，而且是全部失效，這讓我非常納悶。

Morris' Blog