[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
Security Considerations for SHA-1 and MD5

留言

張貼留言

這個網誌中的熱門文章