# 資訊安全 小考筆記

## Problem

1. Follow

1. What is a monoalphabetic cipher ?
2. How large is the key space of the monoalphabetic cipher applied to English (just consider lower case letters) ?
3. What is the main security weakness of a monoalphabetic cipher ?
4. Please provide at least 4 approaches to prevent the above weakness.
2. 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 ?

3. The S-box of DES round operation is not invertable, but why DES can decrypt ?

4. Follow

1. Please explain the OFB mode.
2. In the OFB mode, we never reuse the same sequence (key+IV). If we reuse the key, then the attacker can recover message. Please describe very precisely (mathematiclly with symbols) how the attack works.
5. Please compare the CFB mode the OFB mode by providing a table indicating at least 5 of their advantage and corresponding disadvantage.

6. 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?

7. Describe the details (as much as you remember) of AES operation and describe how efficiently implement AES on an 8-bit CPU ?

8. How avalanche happens in AES within the first tow rounds ?

## Notes

### Part 1

monoalphabetic cipher 簡單來說比凱薩加密難一點，從每個字母都 shift 固定的數量來說，變成變動式的。換句話說就是單純的英文字母替換 (substitute)。由於要維持可逆的解密，替換必須符合一對一，所以方法數為 26! = 403291461126605635584000000

• 壓縮明文，破壞語言特性，但是壓縮算法有儲存的字典部分，仍可能發生字典結構被攻擊，進而進行解壓縮。
• 增加垃圾字，撥點冗詞穿插在其中，把頻率不均的問題消彌。
• 多個字符一起加密，相對於單一字母的替換，可以同時替換兩個以上，如 AA -> WT 之類的。
• 使用多種替換，在不同時刻使用不同的替換表，同樣地可以把頻率問題解決。
• 參照後續區段加密的一些技巧，如 CFB、OFB … 等，讓替換表進行變動。

### Part 3

DES 的 S-box 屬於不可逆的操作 (8-bits to 6-bits)，然而 DES 在解密時，不需要將 S-box 往回推導，也就是不需要逆向操作，因為加密的 key 來自於 master key 和另一段的訊息 L(i) ，最後用 key 加密 R(i) 得到 L(i+1)。解密時，只需要將 R(i+1) (L(i) 會變成 S(i+1))帶入 S-box，就能重新產生出 key。

### Part 4

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

$$C_{i} = P_{i} \text{ XOR } O_{i} \\ C_{j} = P_{j} \text{ XOR } O_{i} \\ C_{i} \text{ XOR } C_{j} = P_{i} \text{ XOR } P_{j}$$

### Part 5

• 自同步 (self-synchronization) ，不用告知對方加密狀態，可以藉由數次的傳輸訊息，自動地將兩邊的狀態一致，在此之前會造成一段雜訊。斷線時，不必重複使用 IV 讓兩邊同步 (狀態相同時，才能正確解密)。
• 錯誤擴散 (error propagation) ，也因為自同步的設計，導致在同步前都會有雜訊，或者在訊息被攻擊者竄改時，會影響該週期的狀態 ($C_{i-k}, C_{i-k+1}, ..., C_{i-1}$ )。
• 預先計算 (preprocess key) ，預先計算 key 可以加快加解密速度，同時便可支持平行運算，這原因是因為 message-independent/dependent 之間的差異，狀態不依靠正在傳遞的訊息時，就可以預先處理。
• 隨機存取 (random access) ，當要解析某個密文時，CFB 可以往前查找密文$C_{i-k}, C_{i-k+1}, ..., C_{i-1}$，得到當前的解密器所需要的狀態，放上 master key 就能進行解密。OFB 辦不到這一點，狀態不依賴訊息，那就要知道當前是哪個回合，從 IV 開始推導狀態，若密文在第 n 個位置，需要 O(n) 的時間來得到狀態，相對於 CFB 的 O(k) = O(1)來說相當耗時。
• 資訊安全性 (message security) ，由於狀態與訊息獨立，會導致被攻擊者竄改內容時不易發現。在 CFB 中，由於依賴傳遞的訊息，當攻擊者竄改某個密文時會造成錯誤擴散，影響的解密時的明文不只一個，這也讓安全性提高。可以說是一體兩面的特性。

### Part 6

• CFB 狀態為 master key +$C_{i-k}, C_{i-k+1}, ..., C_{i-1}$
• CTR 狀態為 master key + counter

CFB 解密某個密文時，往前查找密文即可解密。CTR 知道密文 offset 便可得到 counter。在獲得資訊上都是 O(k) 常數，因此支持隨機存取。

OFB 辦不到這一點，狀態不依賴訊息，那就要知道當前是哪個回合，從 IV 開始推導狀態，若密文在第 n 個位置，需要 O(n) 的時間來得到狀態，相對於 CFB 的 O(k) = O(1)來說相當耗時。

CFB 和 CTR 到底誰的隨機存取能力好呢？若檔案儲存會切割成數個，那 CFB 的隨機存取能力就更高一點。CTR 必須計算 offset，相較於 CFB 的紀錄架構會稍微地麻煩。

### Part 7

AES 的計算結構都落在 GF(2^8)，一個 cell 的內容都是 GF(2^8)

• substitue 需要 8-bits to 8-bits
• shift rows 對於 8-bit 關聯不大 (移動記憶體的位置)
• mixColume 上是 8-bits x 8-bits
• add round key 對於每一個 cell XOR 8-bit keys

### Part 8

Step\Round Round 1 Round 2
Substitue bytes 4 bits 16 bits
Shift rows 4 bits 16 bits
Mix Columes 16 bits 64 bits
Add Round key 16 bits 64 bits
• 在 Substitue bytes 步驟時，S-box 會設計成期望當有一個 1-bits 不同，則替換出來的結果會有 4-bits 不同 (一個 cell 具有 8-bits。替換 8-bits 時，差異最少 0 bits、最多 8-bits，期望值是 4-bits)。
• 在 Shift rows 步驟時，單純移動 cell 不影響差異。
• 在 Mix Columes 步驟時，每一個 colume 會根據上一個 colume 的 4 個元素相互影響，因此會增加 4 倍。
• 在 Add Round key 步驟時，由於 XOR 相同的 key，因此差異並不會改變。