Hashing Functions

發佈日期: 作者:

一種透過雜湊函數（Hash Function）將任意長度的輸入（例如文字、檔案）轉換成固定長度輸出的過程，這個輸出稱為雜湊值或訊息摘要（Message Digest）。流程如下

  1. 你有一段訊息（例如一段文字、一個檔案）。
  2. 將這段訊息輸入到雜湊函數（例如 SHA-256）。 雜湊函數輸出一個固定長度的訊息摘要。
  3. 如果訊息被改動（即使只改一個字元），重新計算的摘要會完全不同。

例子：

  • 輸入：”myPassword”
  • SHA-256 雜湊：34819d7beeabb9260a5c854bc85b3e44c07e1c5e6a8b8a4b6f7a9b2c3d4e5f6
  • 即使輸入改一個字元（如 “myPassword1″），雜湊值會完全不同。

特性：

  • 固定長度：不論輸入多長，輸出長度固定（例如 SHA-256 總是輸出 64 字元）。
  • 單向性：無法從雜湊值反推原始輸入。
  • 抗碰撞性：不同輸入應產生不同雜湊值，難以找到兩個不同輸入產生相同雜湊值。
  • 快速計算：一般雜湊函數（如 SHA-256）設計為計算快速。

用途：

  • 驗證資料完整性（例如檢查檔案是否被篡改）。
  • 儲存密碼（例如網站用戶密碼的雜湊值）。
  • 數位簽章（生成訊息摘要後簽署）。

應用：驗證下載檔案的完整性

假設你想從一個網站下載一個軟體（例如 setup.exe），網站提供這個檔案的 SHA-256 訊息摘要來確保你下載的檔案沒被篡改。下面是運作過程：

步驟 1：網站生成訊息摘要

  • 網站上的原始檔案：setup.exe（假設內容是一些程式碼，檔案大小 10MB）。
  • 網站用 SHA-256 雜湊函數計算檔案的訊息摘要： 5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8
  • 網站公開這個摘要值：5e884898…（64 字元長）。

步驟 2：你下載檔案並驗證

  • 你下載了 setup.exe 到你的電腦。
  • 你用 SHA-256 雜湊函數（可用工具如 sha256sum 或線上計算器）計算下載檔案的摘要：
    • 如果檔案未被篡改，計算結果會是： 5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8
    • 你比對自己的計算結果與網站提供的摘要，發現完全一致，證明檔案完整無誤。

步驟 3：模擬篡改的情況

  • 假設有個惡意網站偷偷修改了 setup.exe，加入了病毒（例如改了一小段程式碼）。
  • 你再次計算被篡改檔案的摘要： a1b2c3d4e5f67890abcdef1234567890abcdef1234567890abcdef1234567890
  • 這次摘要完全不同（與網站提供的 5e884898… 不符），你立刻知道檔案被改動，不能信任。

雜湊函數的分類與用途

  • 通用雜湊函數（MD5、SHA-1、SHA-2、SHA-3、RIPEMD-160）：
    • 快速計算，適合檔案完整性驗證、數位簽章的訊息摘要。
    • 例如：SHA-256 用於數位簽章，驗證電子合約完整性。
  • 密碼雜湊函數（Bcrypt、PBKDF2、Argon2、Scrypt）：
    • 慢速計算，加鹽值，專為密碼儲存設計，抗彩虹表和暴力破解。
    • 例如：Bcrypt 用於網站密碼資料庫。
    • 關於更多細節可參考 https://systw.net/note/archives/2447

常見雜湊函數

名稱格式（十六進位字元數）例子（Hash(“hello”)）
MD5
rivest1992,較MD4複雜,慢,128位元摘要長度,處理512bit區塊單位,可處理無限長度訊息		325d41402abc4b2a76b9719d911017c592
SHA-1
1993,160位元摘要長度,處理512bit區塊單位,可處理小於263bit長度訊息		40aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d
SHA-256642cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
SHA-3 (256)643338be694f50c5f338814986cdf0686453a888b84f424d792af4b9202398f392
RIPEMD-160
160位元摘要長度,處理512bit區塊單位,可處理無限長度訊息,結構和sha-1類似		40108f07b8382412612c048d07d13f814118445acd
Bcrypt60（含鹽值等）$2b$12$6b3zCj6n7oW9x9z6k1v2q…（隨鹽值變化）

雜湊碰撞

Hash Collision是指當兩個不同的輸入訊息（例如 訊息A 和 訊息B）經過同一雜湊函數計算，得到相同的雜湊值，即稱為碰撞。

  • 例如：Hash(“訊息A”) = Hash(“訊息B”)，但 訊息A ≠ 訊息B。

在密碼學中，Hash 函數被用於確保資料的完整性（Integrity）、真實性（Authenticity）和不可否認性（Non-repudiation）。在這些應用中，Hash 碰撞會帶來災難性的後果。

案例1，數位簽章 (Digital Signatures)：

  • 問題： 數位簽章是透過對資料的 Hash 值進行加密來實現的。如果攻擊者能找到兩份內容不同但 Hash 值相同的檔案（一份是合法檔案 M1，另一份是惡意檔案 M2，且 Hash(M1)=Hash(M2)）。
  • 後果： 攻擊者可以讓發送者簽署合法的 M1，但由於 Hash 值相同，這個簽章對 M2 也有效。接收者會誤以為惡意檔案 M2 也是經由合法簽署的，這會導致資料被篡改而無法被察覺，破壞了資料的完整性和真實性。

案例2，密碼儲存 (Password Storage)：

  • 問題： 網站通常不會直接儲存使用者的明文密碼，而是儲存密碼的 Hash 值。當使用者登入時，輸入的密碼會被 Hash 後與儲存的 Hash 值比對。
  • 後果： 如果 Hash 函數存在容易被利用的碰撞弱點，攻擊者理論上可以找到一個與合法密碼 Hash 值相同的不同密碼。這雖然不直接洩露原始密碼，但可能允許攻擊者用一個「碰撞密碼」成功登入帳戶。雖然這種情況較為複雜且通常需要額外的攻擊技巧，但仍會削弱密碼保護的安全性。

MD5 和 SHA-1 的碰撞問題：

  • MD5：
    • 128 位元輸出，碰撞機率較高。
    • 例子：
      • 駭客生成兩個檔案：file1.pdf（無害）和 file2.pdf（含惡意程式碼），兩者 MD5 雜湊值相同。
      • 用戶下載 file1.pdf 驗證通過，但駭客偷偷替換為 file2.pdf，用戶無法察覺。
    • 現況：因碰撞問題，MD5 已不建議用於安全應用（如數位簽章）。
  • SHA-1：
    • 160 位元輸出，理論上比 MD5 安全，但仍不夠。
    • 例子：駭客偽造 SSL 證書，找到兩個證書（合法和惡意）產生相同 SHA-1 雜湊，欺騙瀏覽器信任惡意網站。
    • 現況：SHA-1 已不安全，禁用於大多數安全應用。