[IT-Security-1] 對稱式密碼學 Symmetric Encryption

Symmetric Encryption

Notes from RWTH Aachen University course
“IT security 1” Wintersemester 2019/20
professor: Meyer, Ulrike Michaela

Kerckhoff’s Principle

除了key之外，即使整個系統是公開的，這個密碼系統仍是安全的

相反的如果隱藏密碼系統的設計則是「security through obscurity」

Perfect Secrecy

明文

$P \in\mathcal{P}$ 及密文

$C \in\mathcal{C}$ ：

$Pr(P|C)=Pr(P)$

$\mathcal{K}$ : Key space

隱含 $|\mathcal{K}|\geq|\mathcal{C}|\geq|\mathcal{P}|$
相等的關係式

$Pr(C|P)=Pr(C)$
$Pr(C|P_1)=Pr(C|P_2)$

Shannon’s Theorem

假設

$|\mathcal{K}|=|\mathcal{C}|=|\mathcal{P}|$ ，且

$Pr(P)\geq 0$

此加密系統提供Perfect secrecy

$\Leftrightarrow$ 所有

$K$ 出現機率相等且存在唯一一個

$K$ 使得

$E_K(P)=C$

$(\Rightarrow):$ 假設存在一個 $C$ ，使得沒有 $K$ 符合 $E_K(P)=C$ ，則 $P(P|C)=0$
和Perfect secrecy定義矛盾: $Pr(P|C)=Pr(P)>0$
因為 $K$ 和 $C$ 一樣多，若 $K$ 不是uniformly選擇，則給定 $C$ 會有某些 $P$ 出現機率較高，跟Perfect secrecy矛盾
$(\Leftarrow):$ 若滿足 $K$ 出現機率相等且存在唯一一個 $K$ 使得 $E_K(P)=C$
則對所有 $P$ 而言 $Pr(C|P)=1/|\mathcal{K}|$
則 $Pr(C|P_1)=Pr(C|P_2)=1/|\mathcal{K}|$ ，是perfect secrecy的定義

Vernam’s One-Time Pad

滿足perfect secrecy的例子

Encryption:

$E_k(P)=P\oplus K$

Decryption:

$D_k(C)=C\oplus K$

Confusion 混淆

使每個 bit 的密文和 key 之間的關係變得複雜

Diffusion 擴散

改變一個 bit 的明文，密文也會盡可能的混亂

對稱式加密 Symmetric Encryption

DES

1977年被發表被NIST定為標準
64-bit key (其中8個bits為parity，實際用56個bits) 和 64-bit block
1999 年只用 22 小時就破解
缺點是 Key length 太短

2DES

用兩個不同的 key $k_1,k_2$ 執行兩次 DES
問題：Key size 非兩倍
Meet-in-the-middle-attack:

假設明文和密文對為： $DES_{k_2}(DES_{k_1}(P))=C$
則用 $2^{56}$ 的 DES 時間破解 $DES_{k_1}(P)=Z$
再用 $2^{56}$ 的 DES 時間破解 $DES_{k_2}(Z)=C$
總共 DES 的操作為 $2^{57}$

known-plaintext attack

3DES

兩個不同的變形：3-key 3DES 和 2-key 3DES
第一次用 $k_1$ 加密，第二次用 $k_2$ 解密，第三次用 $k_3$ 加密
3-key 3DES: $k_1,k_2,k_3$ 都不同，有效 key size 112-bit
2-key 3DES: $k_1=k_3$ ，有效 key size 80-bit

AES

目標：比 3DES 安全及有效率
key size: 128, 192, 256 bit
block size: 128 bit
operations:

Byte substitution (BS): 用S-BOX取代byte
Key addition (KA): 用128-bit round key做XOR運算
Shift row (SR): 平移row，每個row平移的數量不一
Mix column (MC): 乘法在 $GF(2^8)$ ，module $x^8+x^4+x^3+x+1$

ECB mode (Electronic Code Book)

有了 block cipher 機制後，若明文長度多於 block 長度，該如何處理？
EBC 是將明文切成區塊大小，最每個block獨立加密
Encryption: $C_i=E_k(P_i)$
Decryption: $P_i=D_k(C_i)$
缺點: 相同明文會有相同的密文
密文的重組和刪除無法被偵測到
需要 padding

CBC mode (Cipher Block Chaining)

將明文切成區塊大小，根據前面計算的密文再 XOR 下個區塊的明文
用一新的 IV，所以即使明文相同，密文仍不同
IV= $C_0$
Encryption: $C_i=E_k(P_i\oplus C_{i−1})$
Decryption: $P_i=D_k(C_i)\oplus C_{i−1}$
優點: 密文的刪除和重組可以被偵測
若傳輸 C2 有誤，只會影響 P2 和 P3，其他還是可以正常解密
需要padding

CFB mode (Cipher Feedback Mode)

根據密文生成key stream
IV public, IV= $C_0$
Encryption: $C_i=E_k(C_{i−1})\oplus P_i$
Decryption: $P_i=E_k(C_{i−1})\oplus C_i$

OFB mode (Output Feedback Mode)

key stream不受明文影響
key stream可以被pre-compute，如果已知IV的話
IV public
Encryption: $Ci=E^i_k(IV)\oplus P_i$
$E^i_k(IV)=IV$ 加密 $i$ 次
Decryption: $Pi=E^i_k(IV)\oplus C_i$
不需要 complete block 就可以加解密 $\Rightarrow$ 適合平行
把 block cipher 轉成 stream cipher

CTR mode (Counter Mode)

沒有feedback，可以平行執行
IV public
Encryption: $C_i=E_k(IV+i)\oplus P_i$
Decryption: $P_i=E_k(IV+i)\oplus C_i$
不需要 complete block
把 block cipher 轉成 stream cipher

Stream cipher

對每個 bit 做跟 key 的 XOR 運算
目標：用 pseudo-random number generator (PRNG)
$E_k(P)=P\oplus PRNG(IV,k)$
優點：

計算快速
沒有 perfect secrecy，若運用恰當可以跟 block cipher 一樣安全
PRNG 理論上是不可預測的 (不給定seed的話)

缺點：

沒有完整性 Integrity (XOR運算有結合率和交換率)
如果一個 key 用兩次會有危險 (因為 XOR 同個字串兩次會是0)
$(P_1\oplus PRNG(IV,K))\oplus (P_2\oplus PRNG(IV,K))=P_1\oplus P_2$
若知道 $P_1$ 有可能破解 $P_2$

IV 通常和密文同時傳遞，只有接收人和傳送人有 key
$PRNG(IV,K)$ 產生的 bit stream 被稱為 key stream

RC4

簡單、快速、被廣泛使用
key scheduler phase:
K 為input，生成256 bit的陣列
key Stream Generator phase:
產生key stream
不夠random
RC4不該被使用了

Cryptographically Secure PRNG

secure $\Rightarrow$ pass the next bit text
給定所有 $k$ 個 output，預測下一個 output 的機率不能大於 $1/2$

Basics:

Buchmann: Einführung in die Kryptographie (7. Auflage), Springer Verlag, 2016
Stallings: Cryptograhy and Network Security, Part 2 on Symmetric Encryption, 7th edition, Pearson Global Edition, 2017

ITVV