學校課程/資訊安全

資訊安全 小考筆記

contents

  1. 1. Problem
  2. 2. Notes
    1. 2.1. Part 1
    2. 2.2. Part 2
    3. 2.3. Part 3
    4. 2.4. Part 4
    5. 2.5. Part 5
    6. 2.6. Part 6
    7. 2.7. Part 7
    8. 2.8. Part 8

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 2

區段加密具有相當大的強度，當一次加密 64 bits 時，可以達到的對應種類高達 (2^64)!，沒有辦法將這種表格存放在記憶體，因為也要消耗 2^64 bits。

因此有 Shannon’s idea，利用 substitution (S-box)、permutation (P-box) 來完成對應，藉由 S-P 的組合，提供 混淆(confusion) 和 差異 (diffusion)。組合的效應遠比想像中的還大，儘管組合的方法數遠小於 (2^64)!，連兆分之一都不到，但簡單的概念可以在 64KB 記憶體大小內完成，效應上算相當划算。

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。

至於 DES 為什麼可以正確加解密，定義對於所有的任意明文 A, B，產生的密文 E(A) != E(B)。若明文差異在 L(i)，則在 R(i+1) 一定會不同。若明文差異在 R(i)，則在 key 相同，做 L(i+1) = R(i) XOR key 時，L(i+1) 也必定會不同。

Part 4

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

為什麼 OFB 不能重新使用 key + IV 呢？原因是因為 已知明文攻擊 (Known plaintext attack) 。假設每一天都重新啟動，那麼攻擊者可以在事後得到密文對應的明文 (可能隔天才知道，儘管對應仍然是很難的)，那麼可以藉由數學概念來完成解密，無須考慮 key 是什麼內容。

$$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}$$

假設 i 和 j 重複使用 key，那麼會發生已知密文$C_{i}, C_{j}$ (傳輸上一定會被發現) 和已知明文$P_{i}$，只要夾擊做 XOR，就可以直接得到$P_{j}$，當已知明文相當長時，竊取的效果就越好。

Part 5

比較 CFB 和 OFB。

特性\模式 CFB OFB
自同步 (self-synchronization) 可 不可
錯誤擴散 (error propagation) 有 無
預先計算 (preprocess key) 不可 可
隨機存取 (random access) 可 不可
資訊安全性 (message security) 高 低
  • 自同步 (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

因此 AES 可以在 8-bits CPU 上有更好的實作效能，所需要的 clock cycle 會比較短。

Part 8

假設有兩個明文的 漢明距離 (Hamming distance) 為 1，在 128 bits 中有一個 1 bits 不同，意即$H(P, Q) = 1$。

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，因此差異並不會改變。

最後，在 Round 2 時，能得到平均 64 bits 的差異。加密的明文一次 128 bits，差異期望值也就是一半的情況 64 bits，因此很快地就能達到期望的差異性。在隨後的 Round X 中，差異會在 64-bits 上下浮動都是有可能的。