[IT-Security-1] 完整性 Integrity

Integrity

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

Hash定義

• compression: output都是固定長度 
• ease of computation: 給定 $h$ 及input $x$，$h(x)$ 容易求得 
• $h(x)$ 可以被稱作: hash value, message digest, fingerprint 
• Hash 不可能是 injective (輸出的個數比輸入多) 

鴿籠定理 

一般化：若有 $n$ 個籠子，有 $kn+1$ 隻鴿子，則至少有一個籠子有多於 $k$ 隻鴿子 

Preimage resistant: 

給定 $y$，很難找到 $x$ 使得 $h(x)=y$ 

Second preimage resistant:

給定 $x,h(x)$，很難找到 $x'\neq x$ 使得 $h(x')=y$ 

Collision resistant: 

很難找到任兩個 $x,x'$使得 $h(x)=h(x')$ 

有 Preimage resistant 及 Collision resistant (implies Second preimage resistant) 性質即稱為 cryptographic hash function 

• Proof: 
• Collision resistant $\Rightarrow$ 2nd pre-image resistant
• 矛盾證明 
• 假設滿足Collision但不滿足2nd pre-image resistant 
• 給定$x$，表示有一個$x’$使得$h(x’)=h(x)$
  (by def of 2nd pre-image resistatnt) 
• 則跟 collision resistant 的假設矛盾 
• Collision resistance $\nRightarrow$ pre-image resistance
• 假設 $g$ 是 Collision resistant 的 n-bit hash 函數 
• 定義 $$h(x)=\begin{cases}1 ||0^kx\ \text{if the bitlength of x is}\leq n\ \text{with }k=n-log_2(x)\ 0s \\ 0 || g(x) \text{if the bitlength of x is}>n\end{cases}$$
• 1串連在 $x$ 長度小於 $n$ 的時候的前面
  0串連在 $x$ 長度大於 $n$ 的時候的前面
• 範例：
  $n=10$
  $x=101011$，則 $h(x)=1000101011$
  $x=11101011001$，則$h(x)=0\text{xxxxxxxxx}$
  $\text{xxxxxxxxx}$是collision resistant

• 則此 $h(x)$ 是Collision resistant但不是pre-image resistance 
• 若長度小於 $n$ 時可以推測出 $h(x)$ 為何
• 但長度小於 $n$ 時，若 $x$ 不同 $h(x)$ 值不同；且在長度大於 $n$ 時，0開頭的 $h(x)$ 是collistion resistant

Birthday Problem 

最少需要幾個同學 $k$ ，才能在機率 $P$ 之下解下列問題 (天數: $N=365$) 

$1^{st}$ problem

固定生日 $y$，找到一個同學的生日是 $y$ 

• 證明： 
• 找一個同學生日不在 $y$ 的機率：$1-\frac{1}{N}$
• $k$ 個同學生日不在 $y$ 的機率：$(1-\frac{1}{N})^k$ 
• $k$ 個同學中至少一個生日為 $y$ 的機率：$1-(1-\frac{1}{N})^k$ 
• 估計值 $1-x\approx e^{-x}$ for $x\ll 1$
• $P\approx 1-e^{-\frac{k}{N}}$ 
• $k\approx ln(\frac{1}{1-P})N$ 
• $k\approx 253$ 

$2^{nd}$ problem

• 找到一個同學 $x$ 生日為 $y$，找到另一個同學生日為 $y$ 
• $P\approx 1-e^{-\frac{k-1}{N}}$ 
• $k\approx ln(\frac{1}{1-P})N+1$ 
• $k\approx 254$ 

$3^{rd}$ problem

• 找到任兩個同學生日同天
• $P\approx 1-e^{-\frac{k(k-1)}{2N}}$
• $k\approx \frac{1+\sqrt{1-4ln(1-P)2N}}{2}$
• $k\approx 23$ 

根據$1^{st}$ birthday problem，我們知道暴力破解 pre-image resistant 需要 $0.69\times 2^n$ 的時間，其 $n$ 為 image 的 bitlength 

🔎 $O(2^n)$ 的時間複雜度找到 preimage 的機率為 $\frac{1}{2}$ 

$2^{nd}$ preimage resistant 的破解亦相似，時間複雜度為 $O(2^n)$ 
Collistion resistant的破解時間複雜度為 $O(2^{\frac{n}{2}})$

MD5 

• 雜湊函數
• 2011年MD5已經不能再被使用，因為collision resistant需要被滿足(被破解，很容易找到collision) 

SHA-1 

• 雜湊函數
• 2017年，SHA-1的collision被找到，不能再被使用 
• 找到Collision有什麼壞處？
  對 Digital signatures、message authentication codes、modification detection codes、Key derivation functions (Integrity) 有影響 

SHA-2 

尚未被完全破解，建議使用SHA-3 - Bitlength: 224, 256, 384 and 512 

SHA-3 

• 2015年 Keccak 被選為 SHA-3 
• 較少的 round，因此比SHA-2更有效率 
• input 可以無限長( SHA-2, SHA-1, MD5 不行) 

Modification Detection Code 

• 訊息直接傳輸 $M_1$ 與透過 Hash $H_s(M_1)$之後傳輸 
• 檢查訊息經接收方Hash $H_r(M_1)$ 之後是否與 $H_s(M_1)$ 相同 

Message Authentication Codes (MAC) 

• 通訊雙方用key去Hash訊息 
• 若Hash完結果一樣則視為是認定的傳送方送的訊息 
• function: $MAC_k(x)$ 
• 優點: 
• 容易計算 
• 壓縮 
• computation resistant: 如果沒有 $k$ 則難以找到pair $(x',MAC_k(x'))$

為何用MD5的MAC $h(k||M)$ 不安全? 

• 給定pair $M,h(k||M)$
• 我們可以很容易找到pair $M',h(k||M')$ 
• 因為MD5會 pad M，每個 block 會依序餵進 compression function 裡，更新 internal state，最後 output final state 
• 只要用初始狀態為 $h(k||M)$ 就可以建構任何message $M'$的MAC 

HMAC 

• 優點: 
• 可建構MAC 
• Hash在軟體中比encrypt快 
• library多 
• 可以替換其他Hash function 
• $HMAC_K (M)=h(K\oplus opad∥h(K\oplus ipad∥M))$
  攻擊者無法控制 input
  $opad,ipad$ 是常數，使得他們 Hamming distance 最大

CMAC 

• 用block cipher $E_k$ 
• 訊息被切成 $n$ 份每份 $b$ bits 
• 若 $M_n$ 未滿 $b$ bits 則 padding $10^k$ 
• 運用 CBC mode 
• 除了最後一個block用sub-key $k_1$ mask 如果 $M_n$ 沒有被 padding，反之用 sub-key $k_2$ $\Rightarrow$ Masking

為何需要masking?

• 若 $M,P$ 為兩個one block訊息則 
• $MAC(M)=E_k(M)$
• $MAC(P)=E_k(P)$ 
• $MAC(M ∥ (P \oplus MAC(M))) \\ = E_K (E_K(M \oplus 0^b) \oplus P ⨁ MAC(M)) \\= E_K(P \oplus MAC(M) \oplus MAC(M)) \\= E_K(P)$
• 有辦法從短的已知的message偽造出長的message 

Replay problem 

MAC有可能會被重複使用 

需要timestamp或Nonce 

• 使用Counter 
• 只有在counter較之前大的時候接收 
• 問題：需要同步counter，若package無法依序抵達 
• 使用Nonce 
• Number used once 
• counter就是一種nonce(但不是random nonce) 
• Alice可先傳nonce，再傳有nonce的MAC 

保障integrity及encryption 

1. Encrypt, then MAC

• 用 $k_1$ 對明文Encrypt，再用 $k_2$ 對密文MAC，密文跟MAC接在一起 

2. Encrypt and MAC

• 用 $k_1$ 對明文Encrypt，用 $k_2$ 對明文MAC，兩著接在一起 
• 會被攻擊 

3. MAC, then Encrypt 

• 用 $k_2$ 對明文MAC，用 $k_1$ 加密 $\text{plaintext||MAC}$
• 會被攻擊 

4. 用有integrity protection的加密方式 

• Galoise Counter Mode (GCM) 
• CountermodewithCBCMAC (CCM) 

GCM 

• CBC-MAC, CMAC不能平行化，GCM可以 
• IV可以是任意長度 
• 有效率

Basic Reading

• Forouzan, Introduction to cryptography and network security, Chapter 11

Details on the mentioned algorithms

• MD5: specified in RFC 1321 
• SHA-1: specified in FIPS Pub 198-1
• CMAC: NIST Special Publication 800-38B
• HMAC: specified in FIPS Pub 198-1

Security Considerations for SHA-1 and MD5

• SHA-1
• MD-5

NIST SHA-3 competition

Specification of GCM mode 

Specification of CCM mode