【上課筆記】資訊安全導論 - Ch5、Ch6

Ch5

Advanced Encryption Standard (AES) :
- 所有操作都以Bytes執行
- 所有運算都在$GF(2^8)$中執行
- 有限Field運算複習 :
  1. 除法要求每個非零元素都要有乘法反元素
  2. 使用mod運算的$Z_{2^n}$不是Field
  3. $GF（2^n）$中的每個多項式都可以用一個n-bit number表示
- 輸入規格 : 16 Bytes
- Key長度 : 16、32或64 Bytes
- 回合數依照Key的長度:
- AES資料結構 :
  - 主要資料結構 :
    1. 皆為16 Bytes的矩陣
    2. 有順序關係
  - Key結構 :
    1. 從16 Bytes延伸為176 Bytes(16*16)，也稱為44 words(1 word = 4 Bytes)
- 簡介 :
  - 第0回合 : AddRoundKey
  - 第1~n-1回合 : SubBytes、ShiftRows、MixColumns和AddRoundKey
  - 最後一回合 : SubBytes、ShiftRows和AddRoundKey
- 詳細重點 :
  1. 在做處理時，會把整個資料切成一個矩陣
  2. 鑰匙會延伸成44個Word，每4個Word當一個回合金鑰
  3. 加解密過程開始和結束都用AddRoundKey → 唯一使用到Key的階段 → 其他階段不增加安全性
  4. 每個階段都易於反轉
  5. 加解密的階段都相同，但加密演算法$\neq$解密演算法
  6. 加解密最後一回合都只有三個階段，這是AES特殊的地方，可以讓密碼可逆
Substitute Byte (Substitution) :
- 使用S-box將輸入的Byte轉成新的Byte
  - EX : $S_{1,1}$={95} → S-box找第9行第5列 → 找到$S’_{1,1}$={2A}
- S-box可以預防已知密碼分析攻擊 :
  1. 輸入輸出之間的低相關性
  2. Invertible(可逆性) : IS-box[S-box(a)] = a
  3. Not self-inverse(不會自我反轉) : S-box(a) $\neq$ IS-box(a)
  4. 使用乘法反元素 → Nonlinearity(非線性)
    EX : S-box({95}) = {2A}, IS-box({95}) = {AD}
- S-box結構 :
  1. 先把要輸入S-box的矩陣，切成一個個Byte
  2. 找出該Byte在$GF(2^8)$中的乘法反元素
  3. 轉成二進位後，通過以下轉換 :
    ![](https://i.imgur.com/PNIKFF9.png
    - 矩陣1 : 欲輸入Byte的二進位(順序 : B7→B0)
    - 矩陣2 : 使用了$$b_i’=b_i\bigoplus b_{(i+4)mod\quad n}\bigoplus b_{(i+5)mod\quad n}\bigoplus b_{(i+6)mod\quad n}\bigoplus b_{(i+7)mod\quad n}$$
    - 矩陣3 : 為63轉為二進位(01100011)

Shift Row (Permutation) :
- 第n列左移位移量
  
  1st 0
  
  2nd 1
  
  3rd 2
  
  4th 3
- 完成後，讓每個column的4 Bytes皆來自不同的column

第n列	左移位移量
1st	0
2nd	1
3rd	2
4th	3

MixColumn (Substitution) :
- 相乘後做XOR
- 矩陣的係數確保每列Byte之間的良好混合

AddRoundKey (Substitution) :
- 輸入陣列的每一列跟回合金鑰的該Word做XOR
- 要盡量簡單，並要能影響每一個bit

Key Expansion :
- w[i] = w[i-1] $\bigoplus$ w[i-4]
- 當i為4的倍數時，則會變成w[i] = (w[i-1] → Funtion g) $\bigoplus$ w[i-4]
- Fuction g :　
  1. RotWord : 將一個Word的所有Byte左移一格
  2. SubWord : 通過S-box
  3. XOR : 再和Rcon[j](Round Constant)做XOR
- Round Constant :　
  - 是個Word，共4 Bytes
  - Rcon[j] = (RC[j], 0, 0, 0)
  - RC[1] = 1, RC[j] = 2 ∙ RC[j-1](在GF(2⁸)中使用乘法)
  - 每回合的Round Constant移除了對稱/相似的性質
- Equivalent Inverse Cipher :
  - 加解密分為兩種 :
    1. transformations的順序不同，但Key的格式相同
    2. Equivalent Inverse Cipher
  - Interchange :
    - 加密順序 :　SubBytes → ShiftRows → MixColumns → AddRoundKey
    - 解密順序 : InvShiftRows → InvSubBytes → AddRoundKey → InvMixColumns

Ch6

DES面對暴力攻擊時相當脆弱 → 可使用AES或多次DES來抵抗
Double DES :
- Key長度 : 56*2 = 112 bits
- 公式 : $C = E(K_2,E(K_1, P))$
- 優點 : 可以產生至少2⁵⁶種組合(因為Key為56 bits)
- 缺點 : Meet-in-the-Middle Attack
Meet-in-the-Middle Attack(中途相遇攻擊) :
- 攻擊流程 :
  1. 已知明文P與密文C
  2. 公式 : $X = E(K_1, P) = D(K_2, C)$
  3. 生成2⁵⁶個K1的組合，並利用P加密產生2⁵⁶個X1組合
  4. 生成2⁵⁶個K2的組合，並利用C解密產生2⁵⁶個X2組合
  5. 去對照X1和X2，進而獲得正確的K1和K2
- 此種攻擊方式能對抗任何區塊加密法
- Double DES攻擊成本 : 2⁵⁶只稍微大於Single DES攻擊成本 : 2⁵⁵而已
Triple-DES with Two-Keys :
- 示意圖 :
- 公式 :
- 順序 : 加密 → 解密 → 加密
- Key長度為56 * 2 = 112 bits
- 優點 : 目前尚無實際的密碼分析攻擊
- 對其暴力破解的成本為2¹¹²
Triple DES with Three Keys :
- 公式 : $C = E(K_3, D(K_2, E(K_1, P)))$
- Key長度為56 * 3 = 168 bits
- 對其暴力破解的成本為2¹¹²

Modes of Operation(工作模式)

用途 :
1. 增強密碼算法的效果
2. 使該算法適用於應用程式
Electronic codebook (ECB) :
- 每次加解密都輸入一個Block，並使用相同Key
- Codebook : 給定特定的Key，每個明文Block都有自己特定的密文
- 如果訊息長度大於Block，則將其分割(最後一個Block若有需要再填充)
- 公式 : $C_j=E(K, P_j)\quad P_j=D(K, C_j)\quad j=1,…,N$
- 優點 : 適合傳送DES或AES的Key
- 缺點 : 相同的明文會產生相同的密文
Cipher block chaining (CBC) :
- 加密 : 先跟前一個密文做XOR再加密
- 解密 : 先解密再跟後一個密文做XOR
- 使用同把鑰匙
- 公式 :
- Initialization vector (IV)
  1. 加密第一回合/解密最後一回合使用
  2. 雙方都知道，得保護好
Cipher feedback (CFB) :
- 解密為同張圖，但箭頭往回指
- 明文會切成s bits的分段用於傳輸
- 可以將Block Cipher變成Stream Cipher
- 加解密都使用Encryption Funtion
- 公式 :
Output feedback (OFB) :
- 加密 : 前一個明文做完加密後，到這回合再加密一次，最後再跟這次的明文做XOR
- 具有典型stream cipher的結構，因為IV和Key產生stream of bits，再跟明文做XOR
- 優點 : 在傳輸中，bit error不會傳遞
- 缺點 : 比CFB更容易受到Message stream modification attack(竄改資料內容攻擊)
CFB vs OFB :
- CFB OFB
  
  XOR後的Output為下次的Input 加密後的Output為下次的Input
  
  以s-bit subset做運算 P和C都以完整區塊做運算
Counter (CTR) :
- Counter長度 = 明文Blcok長度
- Counter每回合都不一樣(一回合+1)
- 不須使用Padding(填充)
- 確保Counter值得唯一性 : 每回合+1
- 優點 :
  1. 不依賴明文or密文的輸入
  2. 只需要加密演算法即可