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區塊單位,可處理無限長度訊息	32	5d41402abc4b2a76b9719d911017c592
SHA-1 1993,160位元摘要長度,處理512bit區塊單位,可處理小於263bit長度訊息	40	aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d
SHA-256	64	2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
SHA-3 (256)	64	3338be694f50c5f338814986cdf0686453a888b84f424d792af4b9202398f392
RIPEMD-160 160位元摘要長度,處理512bit區塊單位,可處理無限長度訊息,結構和sha-1類似	40	108f07b8382412612c048d07d13f814118445acd
Bcrypt	60（含鹽值等）	$2b$12$6b3zCj6n7oW9x9z6k1v2q…（隨鹽值變化）

---

雜湊碰撞

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

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

MD5 和 SHA-1 的碰撞問題：

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

---

鹽值（Salt）是什麼？

• 定義：鹽值是一個隨機生成的字串，在雜湊前與輸入（通常是密碼）結合，改變雜湊的輸出結果。每次雜湊時，鹽值通常不同，且會與雜湊值一起儲存。
• 作用：
  • 確保即使相同的輸入（密碼）也產生不同的雜湊值，防止某些攻擊方式。
  • 鹽值本身不需保密，通常與雜湊值一起儲存在資料庫中。
• 例子：
  • 密碼：”myPassword”
  • 鹽值：X7y9z0w2k4m6n8p0（隨機生成）
  • 結合後：”myPassword+X7y9z0w2k4m6n8p0″
  • 計算雜湊：SHA-256(“myPassword+X7y9z0w2k4m6n8p0”) = abc123…
  • 儲存：[鹽值: X7y9z0w2k4m6n8p0, 雜湊值: abc123…]

---

不加鹽值的風險

• 問題 1：相同密碼產生相同雜湊：
  • 一般雜湊函數（如 SHA-256）是確定性的，相同輸入總是產生相同輸出。
  • 例如：所有使用 “myPassword” 的用戶，他們的 SHA-256 雜湊值都是 34819d7bee…。
  • 如果駭客竊取資料庫，看到相同的雜湊值，就知道這些用戶密碼相同。
• 問題 2：彩虹表攻擊（Rainbow Table Attack）：
  • 駭客可能使用彩虹表（預計算的雜湊值對應表），將常見密碼（如 “password123″）和其雜湊值儲存。
  • 竊取資料庫後，駭客比對雜湊值即可反查密碼。
  • 例如：如果資料庫儲存 34819d7bee…，駭客查彩虹表，立即知道對應密碼是 “myPassword”。
• 問題 3：暴力破解簡單：
  • 常見密碼（如 “123456”）的雜湊值可能已被預計算，駭客可快速破解。

---

加鹽值如何提高安全性

• 防止相同密碼產生相同雜湊：
  • 每個用戶的密碼都與一個獨特的隨機鹽值結合，即使密碼相同，雜湊值也不同。
  • 例如：
    • 用戶 A：密碼 “myPassword”，鹽值 X7y9z0w2，雜湊 abc123…
    • 用戶 B：密碼 “myPassword”，鹽值 k4m6n8p0，雜湊 def456…
    • 駭客無法從相同雜湊值推測密碼相同。
• 阻斷彩虹表攻擊：
  • 彩虹表是針對純密碼的預計算雜湊表，加入隨機鹽值後，駭客必須為每個鹽值重新計算彩虹表，這幾乎不可能（因為鹽值數量龐大）。
  • 例如：駭客的彩虹表可能包含 “myPassword” -> 34819d7bee…，但不會包含 “myPassword+X7y9z0w2” -> abc123…。
• 增加破解難度：
  • 駭客必須針對每個用戶的鹽值單獨進行暴力破解（逐一嘗試所有可能密碼），而不是用通用的彩虹表。
  • 結合 Bcrypt 等慢速雜湊函數（有工作因子），破解一個密碼可能需要數秒，破解整個資料庫則需要數年。

---

比較加鹽和不加鹽

假設一個網站儲存用戶密碼，比較不加鹽值和加鹽值的效果。

不加鹽值（不安全）

• 用戶 A 和 B 都用密碼 “myPassword”。
• 網站用 SHA-256 計算雜湊：
  • user A：SHA-256("myPassword") = 34819d7bee...
  • user B：SHA-256("myPassword") = 34819d7bee...
• 資料庫儲存：
  user A: 34819d7bee...
user B: 34819d7bee...
• 風險：
  • 駭客竊取資料庫，看到相同雜湊值，立即知道 A 和 B 密碼相同。
  • 駭客用彩虹表查 34819d7bee…，找到對應密碼 “myPassword”，帳號被破解。

加鹽值（安全）

• 用戶 A 和 B 都用密碼 “myPassword”，但網站用 Bcrypt（內建鹽值）。
• 計算過程：
  • user A：salt= X7y9z0w2，Bcrypt => $2b$12$X7y9z0w2...abc123...
  • user B：salt= k4m6n8p0，Bcrypt => $2b$12$k4m6n8p0...def456...
• 資料庫儲存：
  user A: $2b$12$X7y9z0w2...abc123...
user B: $2b$12$k4m6n8p0...def456...
• 安全性：
  • 即使密碼相同，雜湊值不同，駭客無法看出 A 和 B 密碼相同。
  • 彩虹表無效，因為駭客需為每個鹽值重新計算表。
  • Bcrypt 的慢速計算（工作因子）使暴力破解耗時巨大。

驗證過程

• 用戶 A 登錄，輸入 “myPassword”：
  • 網站取出儲刚刚完成
  • 網站用儲存的鹽值 X7y9z0w2 和 Bcrypt 重新計算雜湊，比對與 $2b$12$X7y9z0w2…abc123… 一致，驗證通過。