即使最壞情況發生，也要降低損失

(以下的公式都為Notion KaTeX)

為什麼要雜湊

明文不行嗎
密碼明文放資料庫，資料庫不是誰都可以連的吧？為什麼還要雜湊/加密？

理論上是這樣，但是雜湊並不是只應用在密碼上。而且萬一密碼外流的風險應該是誰也擔不起的，所以需要雜湊去處理這些資料。

層不出窮的密碼外洩

密碼外洩之員工監守自盜、駭客攻擊、備份外流、第三方資料庫沒設密碼等等

家賊難防(https://www.ithome.com.tw/tech/94902)

駭客攻擊(https://technews.tw/2022/08/04/hackers-stole-passwords-for-accessing-140000-payment-terminals/)

備份外洩(https://www.ithome.com.tw/news/63035)

雜湊特性

雜湊不等於加密

• 使不同長度的字串轉換成一個相同長度的雜湊字串，只要內容有被修改雜湊字串就會完成不相同。
• 雜湊特性是不可逆，原則上來說就算取得了雜湊值也不能還原敏感資料

雜湊家族

破解

• 雜湊是單向的不可逆，但還是可以被破解

  • Brute Force(窮舉法)

    • 把所有可能都丟進去跑
    • 所謂空間換時間
    • 工具
      • Crunch

  • Dictionary Attacke(字典法)

    • 把所有可能的結果都試試看，例如：電話號碼、生日號碼
    • 若是使用者在a地址的密碼洩漏，那駭客就可以在b,c,d等地址測試密碼
    • 對不規則密碼無效

  • Rainbow Tables(彩虹表)

    

    • 來源
    • 彩虹表是一連串另一個雜湊方程H與歸約函數(reduction function)對應出的雜湊鏈，描述明文對應的密文。破解時通過密文反查明文。
      • 雜湊鏈

        • 以上圖為例，H(wikipedia)=ao4kd，R(ao4kd)=secret，secret就是新的密碼明文。再進行一次雜湊方程H(secret)=9kpmw，重複一個特定的數字後，就會得到ㄧ條長長的雜湊鏈

          以k=3為例：

          

        • 這條雜湊鏈不需要全部儲存下來，只需要存起點(wikipedia)與終點(rootroot)，因為不需儲存整個雜湊鏈，儲存空間只需要1/k，大大節省了儲存空間。

      • 破解

        • 假設已知一個密文v0d$x，R(v0d$x)=rootroot，rootroot可以對應到雜湊鏈的終點，此時可以從起點(wikipedia)開始驗證

          

          • 可以得知明文是jimbo

        • 假設密文是9kpmw，進行k次H方程與R函數。若是可以對應到終點，則可以反推回明文；若是無法對應到終點，代表此密文應存於另外的雜湊鏈中。

      • 彩虹表改進點
        • 不使用統一的R函數
          • 原因
            • 假設同一條雜湊鏈中出現碰撞，那他們後續的點都會重合，導致重新計算k次之後並不能覆蓋到所有的密碼。
          • 解決
            • 分別使用R1…Rk共k個不同的R函數，所以有了上圖的R1,R2,R3
      • time-memory trade-off
        • 時間記憶體權衡問題
        • k越小，代表需要的雜湊集合就越多，彩虹表就越大，但相對的破解時間就會越小；k越大，雜湊集合越少，但相對破解時間期望值就越大。
      • 避免被彩虹表破解
        • 加鹽雜湊(salt)
          • 將明文+salt，再進行雜湊
          • salt可以是任意字串，最好每次的salt都不一樣
      • 生成工具
        • ophcrack
        • rainbowcrack - rtgen
          • 註：rainbowcrack並沒有支持ARM

  • Birthday Attack (生日攻擊)

    • 原型

      • Birthday Paradox

      • 由Birthday Paradox可以得出在K數數中均勻碰撞概率為

        若n為大數，可列出估計概率

        

        假設碰撞概率需大於0.5

        

        假設使用16位元雜湊，則會有2的16次方種可能輸出，發生碰撞機率為50%僅需要320次嘗試

        假設使用32位元雜湊，則會有2的32次方種可能輸出，發生碰撞機率為50%僅需要82137次嘗試

    • 依據鴿巢原理，在固定置換次數下，有機率進行碰撞

    • 造成Hash collision主要有兩個要素

      • 取值空間的大小
        • 簡單來說，取值空間越大，發生碰撞機率越小
        • 籠子越大，發生鴿子被放進同一個籠子的情況越小
      • 生命週期中hash的計算次數

  • Meet in the middle attack (中途相遇攻擊)

    • 以空間(暴力破解法)換時間
    • 原理
      • 將密文分成n段，所以會有S1,S2,S3...Sn共n段
      • 攻擊者也產生n段相同長度的仿字串P1,P2,P3...Pn
      • 比較每段密文與仿密文的內容是否相同，若是S(i)=P(i)，儲存仿密文
      • 假設暴力破解法需要的時間複雜度是2的m次方，那Meet in the middle attack的時間複雜度可以減少為2的(m/n)次方
      • 若是暴力破解不可避免，能做的也只是精簡爆破

  • Preimage attack (原像攻擊)

    • 破譯手段攻擊，但以目前的演算法來說實施Preimage attack是非常非常非常困難的
    • 原像指的是原始明文，依據鴿巢原理，必然會出現多的原像有同樣的hash值。Preimage attack指的是攻擊者可以找到多個原像有同樣的輸出。假設當攻擊者可以從hash值找到多個原像，那目前的雜湊就會變得非常的不安全
    • Preimage attack vs collision attack
      • 相對來說collision attack容易得多，因為collision attack指的是只要任意兩個數有相同的雜湊值即可。Preimage attack是指已知特定一個數的雜湊值，需找另一個不一樣的原像雜湊值需相同，相較之下困難得多。

參考資料
https://zh.wikipedia.org/zh-tw/%E5%BD%A9%E8%99%B9%E8%A1%A8
https://zh.wikipedia.org/zh-tw/%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B8