Ch11

  • Hash Fucntions :

    • 接受可變長度之block : $M$，並產生固定長度之Hash Value : $h=H(M)$
      • $P$ : Padding、$L$ : Length Field(可以增加安全性)
    • 目標 : Data Integrity($M$的任何更改都會導致Hash Value的更改)
    • 應用 :
      1. Message Authentication Code (MAC) :
        • MAC = $E(K, H(M))$
          • 結合Hash和Encryption
          • 使用到可變長度訊息$M$與金鑰$K$
          • 產生固定長度之輸出
      2. Digital Signature :
        • 建立於MAC基礎上
        • $E(PR_a , H(M))$ :
          • 使用A的私鑰加密
          • 提供++認證性++與++數位簽章++
        • $E(K,[M||E(PR_a , H(M))])$ :
          • 使用A的私鑰加密
          • 之後$h$加上$M$，跟金鑰$K$做加密
          • 提供++認證性++、++數位簽章++與++安全性++
      3. 單向密碼檔案 : 將輸入密碼的Hash Value與儲存之Hash Value進行比較，以驗證用戶身分
      4. 檢測病毒或入侵 :
        1. 儲存每個文件的H（F）並保護所有Hash Value
        2. 可以利用重新計算H（F），來確定文件是否已被修改
        3. 入侵者需要同時更改F，但不能更改H（F）
      5. 建構PRF或PRNG :
        • Hash-based PRF常用於生成對稱金鑰
    • Function比較 :
      • Simple XOR :
        • 流程 :
          1. 將輸入切為n bits的Block
          2. 反覆將一個Block進行一次處理以產生n bits的Hahs Value
          3. 每個Block進行XOR : $$C_i=B_{i1}\oplus B_{i2}\oplus…\oplus b_{im}$$
          4. 對於每個bit位置產生簡單的奇偶性，也就是縱向冗餘校驗(LRC)
        • 優點 : 檢查隨機資料的Data Integrity非常有效
        • 缺點 :
          • 資料錯誤但Hash Value沒變的機率為$2^{-n}$
          • 如果資料格式能夠預測，XOR的效果會更差
      • RXOR :
        • 流程 :
          1. 將n bits的Hash Value設為0
          2. 連續處理每個n bits的Block：
            • 將當前Hash Value右移一位
            • 將Block與Hash Value進行XOR
        • 優點 :
          • 將輸入更完全地「隨機化」
          • 克服輸入中出現任何的規律
      • Simple XOR using CBC :
        • 由於每項可以按任何順序進行XOR，因此如果對Block 順序進行置換，則Hash Value不會更改
    • Requirements and Security :
      • 問題 :
        • Preimage(原像) :
          • $h=H(x)$函式為多對一
          • 對於任何給定的$h$，通常會有多個原像(preimages)
        • Collision(碰撞) :
          • 當$x≠y$但$H(x)= H(y)$，碰撞即發生
          • 因為使用$H$來確保Data Integrity，所以碰撞顯然是不可發生的
        • 假設輸入資料長度為$b$，Hash Value長度為$n$，則每個Hash Value平均會產生$2^{b-n}$個原像
      • 要求 :
        • Weak hash function : 滿足前五項
        • Strong hash function :
          • 滿足前六項
          • 防止A產生訊息給B簽章的攻擊
          • 防止Birthday Paradox
        • Preimage Resistant(one-way property) : 給定$h$無法找到$y$，即$H(y)= h$
        • Second Preimage Resistant(weak collision resistant) : 給定$x$，無法通過$H(y)= H(x)$來找到$y≠x$
        • Collision Resistantstrong collision resistant) : 無法找到$H(y)= H(x)$的任何對$(x,y)$
      • 攻擊手法 :
        • 假設Hash Value長度為$m$，則所需工作量為 :
          Preimage Second Preimage Collision
          $2^m$ $2^m$ $2^{m/2}$
        • Brute-Force Attacks :
          1. Preimage & Second Preimage :
            • 攻擊者平均必須嘗試$2^{m-1}$個$y$值
          2. Collision :
            • 攻擊者平均必須嘗試$2^{m}$個$y$值
            • Birthday Paradox :
              • 如果從$0$到$N-1$範圍內的均勻分佈中選擇隨機變量，則在做出$\sqrt{N}$個選擇後遇到重複元素的機率超過$0.5$
        • Cryptanalysis :
          • 測量Hash演算法對密碼分析的抵抗力
          • Iterated Hash Function Structure :
            • 結構 :
              • 將輸入資料$M$拆解為$L$個固定$b$ bits的Block($Y_0,Y_1,…,Y_{L-1}$)
              • $F$ : 壓縮函式
              • 最後的Block包含輸入資料的總長度
              • 攻擊涉及分析回合之間的變化模式
              • 如果$F$具有Collision Resistant，則迭代Hash函式也有
              • 減少設計安全Hash函式的問題
            • Hash Functions Using DES & CBC :
              • 產生Hash值太小(64 bits)之原因
                1. Direct Birthday Attack
                2. Meet-in-the-middle Attack

  • Secure Hash Algorithm (SHA) :

    • 基於Hash函式MD4產生160 bits Hash Value（SHA-0）
    • SHA-512 :
      • 輸入 : 1024 bit的Blocks
      • 輸出 : 一個512 bits的Hash Value
      • 流程 :
        1. Padding$P$ : 10*
        2. Length$L$
        3. 初始化Hash Buffer : 512 bits的Buffer可以表示為8個64 bits的暫存器（abcdefgh）
        4. 將訊息$M$加上$P$與$L$，切成1024 bit的Block
        5. 經過流程後輸出
      • 公式 :
        • $IV$ : abcdefgh Buffer中的初始值
        • $abcdefgh_i$ : abcdefgh Buffer目前的值，也就是上一回合產生的$H_i$
        • $N$ : Blocks的數量
        • $SUM_{64}$ : word-by-word addition modulo 2^64^
        • $MD$ : 最終的Hash Value
      • $F$ :
        • 將1024 bits的Block切成80個Word，並經過80回合的加密
    • SHA-3 :
      • Sponge Construction :
        • 允許可變長度的輸入或輸出，可用於 :
          • Hash函式(固定長度輸出)
          • PRNG(固定長度輸入)
          • 其他密碼分析功能
        • Input :
          • 將$n$ bits的Input切為$k$個長度為$r$ bits的Block
          • 用Padding填充缺少的空格 :
            • Simple padding : 1 0*
            • Multirate padding : 1 0* 1
        • Output :
          • 所需的輸出bit數，決定生成輸出的Blcok數
          • 如果期望的輸出是$\ell$個bits，則要產生$j$個Block，使得$(j-1)r\lt\ell\le jr$
        • 流程 :
          • 初始化 :
            • 準備$b$ bits的0($b=r+c$)
          • Absorbing phase(吸收階段) :
            1. Padding : 將輸入Block填充$c$ bits的0
            2. 做XOR
            3. 經過iteration function $f$，產生$s$
            4. $s$為下一回合XOR的值
          • Squeezing phase(釋放階段) :
            1. 假設$\ell\le b$，則保留$s$的前$\ell$ bits作為$Z_0$
            2. 重複執行$f$來更新$s$
            3. 繼續進行$(j-1)$次迭代，直到$(j-1)r\lt\ell\le jr$
      • Iteration Function $f$ :
        • 函式$f$將Input的1600 bits分為5x5的矩陣(每格為64 bits)
        • 經過24 rounds的處理
        • 每個round都有5 steps