[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