# 資訊安全：從入門到入土 [0x03] - 密碼學 (1/2)

本章主要分成兩個部分，分別是**雜湊 (Hashing)** 和 **加密 (Encryption)**。

>[!Warning]
密碼學是一個非常大的研究領域，這邊提到的只是冰山一角。

## 目錄

[TOC]

## 雜湊 (Hashing)
雜湊 (Hashing) 這個詞，曾經被誤解為人名而翻譯成「哈希」。為了避免混淆，本文將統一使用「雜湊」來表示。

在開始之前，我們先來了解一些重要的術語吧！

### 重要術語
* **雜湊 (Hash)** - 雜湊是雜湊函數的輸出結果。當我們提到「雜湊」這個動作時，意思是生成某些數據的雜湊值。
* **編碼 (Encoding)** - 這不是加密，只是一種數據表示方式，比如 Base64 或十六進制。編碼是可逆的。
* **明文 (Plaintext)** - 加密或雜湊之前的數據，通常是文本，但也可以是照片或其他檔案。
* **暴力破解 (Brute force)** - 通過嘗試所有可能的密碼或密鑰來攻擊加密系統。
* **密碼分析 (Cryptanalysis)** - 通過尋找底層數學的弱點來攻擊加密系統。


>[!Important]問題1
>Q1: Base64 是加密 (encryption) 還是編碼 (encoding)?
>A1: 編碼 (encoding)

### 什麼是雜湊函數 (Hash Function)?
雜湊函數和加密其實有很大的不同，雜湊沒有密鑰，設計上也讓幾乎不可能（或者說非常困難）從輸出逆推出原始的輸入。🔐

簡單來說，雜湊函數接受任何大小的輸入資料，然後生成一個固定大小的雜湊值 (digest)。這個輸出是隨機的，而且幾乎無法預測他會是什麼。
即使輸入只改變了一點點（甚至是一位元），產生的雜湊值也會有很明顯的變化。這樣的設計讓雜湊函數在計算上相對快速，且反向計算非常困難。

雜湊函數的輸出會被編碼成原始位元組，常見的編碼方式有 Base64 或十六進制。通常解碼這些編碼值並不會發現有用的資訊。

>*圖源：https://www.thetechedvocate.org/cryptographic-hash-function/*

#### 為什麼雜湊這麼重要？
在網路世界中，雜湊是非常常見的技術。例如：當你登錄 Instagram 時，其實就是在利用雜湊來驗證你的密碼。

也就是說，你和雜湊的接觸比你想像的要多得多，尤其是在處理密碼時。

#### 雜湊碰撞 (Hash Collision)
雜湊碰撞指的是兩個不同的輸入產生了相同的輸出。

雜湊函數的設計目的是為了盡量避免這種情況，但由於鴿籠原理 (The Pigeonhole Principle)，這種情況是無法完全避免的。
這個原理說明雜湊函數的輸出值是有限的，但輸入卻可以是任意大小。舉個例子，如果你有 128 隻鴿子和 96 個鳥籠，那麼有些籠子勢必會有超過 1 隻以上的鴿子。🐦🏠

MD5 和 SHA1 曾經遭遇過攻擊，並且因工程上的雜湊碰撞而變得不再安全。
不過，至今還沒有攻擊能在兩個算法中同時產生碰撞。如果你比較 MD5 和 SHA1 的雜湊，你會發現他們的結果是不同的。
MD5 碰撞可以參考[這裡](https://www.mscs.dal.ca/~selinger/md5collision/)，SHA1 碰撞則可以查看[這裡](https://shattered.io/)。

因此，你不應該依賴這兩種算法來雜湊密碼或重要數據。

>[!Important]問題 1
>Q1: MD5 雜湊函數的輸出大小是多少字節？
>A1: 16

>[!Important]問題 2
>Q2: 雜湊碰撞是可以避免的嗎？
>A2: 否

>[!Important]問題 3
>Q3: 如果有一個 8 位元的雜湊輸出，可能的雜湊數量有多少？
>A3: 256

### 雜湊的用途
那麼，雜湊有什麼實際用途呢？讓我們來探討一下吧！

在網路安全的世界裡，雜湊主要有兩大用途：
1. **驗證數據的完整性**
2. **驗證密碼**

下面我們來看看這些用途是如何運作的。

#### 雜湊在密碼驗證中的應用

大多數網路應用都需要在某個時候驗證用戶的密碼 (例如：用戶登入)。如果這些密碼以明文形式儲存，你可能已經看到過一些公司資料庫外洩的新聞，這些事件往往會引發嚴重的後果。🤯

例如：Kali 上的 "rockyou.txt" 這個字典。

這個字典來自一家名為 MySpace 公司，他們內部的密碼以明文形式儲存，後來發生數據洩漏。這個文字檔中包含了超過 1400 萬個密碼，這些密碼中的一些甚至不是用戶的實際密碼（如果你有興趣，可以按長度排序來查看）。

Adobe 也發生過一次代表性的數據洩漏事件。那次事件中，密碼是用加密而非雜湊來保護的，但使用的加密方式不夠安全，結果明文密碼很快就被恢復了。
如果你想了解更多，可以參考[這篇](https://www.informationsecurity.com.tw/article/article_detail.aspx?tv=21&aid=7655)。

另外就是 LinkedIn 的數據洩漏事件中，他們使用了 SHA1 來驗證密碼，而 SHA1 在使用 GPU 計算時非常快速。

密碼本身無法被加密，因為加密需要儲存**密鑰**。如果有人獲得了密鑰，他們就能解開密碼。因此，**使用雜湊來儲存密碼是更安全的選擇**。這樣即使數據庫被洩漏，攻擊者也需要破解每一個雜湊值才能找出密碼，這聽起來是不是更安全一些呢？🔐

但是這邊會有一個問題：如果兩個用戶使用相同的密碼，因為雜湊函數總是將相同的輸入轉換為相同的輸出，這就代表如果有一個雜湊被破解，攻擊者可能會得到多個帳號的密碼。

這就產生了「彩虹表」這種工具。
>*圖源：https://www.thesecurityblogger.com/understanding-rainbow-tables/*

**彩虹表 (Rainbow table)** 是一種將雜湊對應到明文密碼的查詢表，這樣你可以快速找到某個雜湊值對應的密碼。儘管建立彩虹表需要花費不少時間，但他可以節省破解雜湊時花費的時間。

下面是一些例子，幫助你理解彩虹表的運作方式：

| Hash | Password |
| -------- | -------- |
| `02c75fb22c75b23dc963c7eb91a062cc` | zxcvbnm |
| `b0baee9d279d34fa1dfd71aadb908c3f` | 11111 |
| `c44a471bd78cc6c2fea32b9fe028d30a` | asdfghjkl |
| `d0199f51d2728db6011945145a1b607a` | basketball |
| `dcddb75469b4b4875094e14561e573d8` | 000000 |
| `e10adc3949ba59abbe56e057f20f883e` | 123456 |
| `e19d5cd5af0378da05f63f891c7467af` | abcd1234 |
| `e99a18c428cb38d5f260853678922e03` | abc123 |
| `fcea920f7412b5da7be0cf42b8c93759` | 1234567 |

像 [Crackstation](https://crackstation.net/) 這樣的網站使用巨大的彩虹表來快速破解沒有**鹽 (salt)** 的密碼雜湊。在已排列好的列表中可以非常迅速的進行查詢，比起嘗試破解雜湊快很多。⚡

#### 如何防範彩虹表

為了防範彩虹表，我們會在密碼中加入**鹽 (salt)** 🧂。鹽的數值是隨機產生的，而且儲存在資料庫中，每位用戶的鹽值都是獨一無二的。這樣即便用戶使用相同的密碼，每個用戶的密碼雜湊也會不同。


諸如 bcrypt 和 sha512 會自動處理這個過程。

>[!Important]問題 1
>Q1: 使用彩虹表破解雜湊值 "`d0199f51d2728db6011945145a1b607a`" 的明文密碼是什麼？
>A1: basketball

>[!Important]問題 2
>Q2: 使用線上工具破解雜湊值 "`0c09da79784db99e87994ae6a7e0d87fdfcd1913f5d45d0b1c3ed975`" 的明文密碼是什麼？
>A2: sha224

>[!Important]問題 3
>Q3: 是否應該對密碼進行加密？
>A3: 否

### 分辨密碼雜湊

識別不同類型的密碼雜湊是很重要的，雖然像 [hashID](https://pypi.org/project/hashID/) 這樣的自動化工具或 ChatGPT 可以協助識別雜湊格式，但有時候準確性可能不盡人意 (~~絕大部分應該都可以用 ChatGPT 分辨出來~~)，這種時候結合上下文再配合工具也不失為一種好方法。

例如：如果你在網頁應用的數據庫中發現了一個雜湊，那麼他就可能是 MD5 而非 NTLM。

#### Unix 風格的密碼雜湊

Unix 風格的密碼雜湊比較容易識別，因為他們通常有一個明確的前綴。這個前綴會告訴你生成該雜湊使用的算法。

標準格式是 `$format$rounds$salt$hash`。

以下是一些常見的 Unix 風格密碼前綴及其對應的算法：

| Prefix | Algorithm |
| -------- | -------- |
| `$1$` | md5crypt（用於 Cisco 裝置和較舊的 Linux/Unix 系統）|
| `$2$, $2a$, $2b$, $2x$, $2y$` | Bcrypt（常用於網頁應用）|
| `$6$` | sha512crypt（大多數 Linux/Unix 系統的預設算法）|

在 Windows 中，密碼雜湊存儲在 SAM（安全帳戶管理器）中。雖然 Windows 會阻止普通用戶導出這些雜湊，但像 mimikatz 這樣的工具還是可以達成這個目標，另外這裡還會分為 NT 雜湊和 LM 雜湊。

#### 識別雜湊格式

對於其他雜湊類型，通常需要根據長度、編碼方式或生成他們的應用程式來進行研究，或是直接問 ChatGPT。

想要找到更多的雜湊格式和密碼前綴，可以參考 [hashcat 的範例頁面](https://hashcat.net/wiki/doku.php?id=example_hashes)。

>[!Important]問題 1
>Q1: `sha512crypt($6$)` 預設會跑多少次迴圈？
A1: 5000

>[!Important]問題 2
>Q2: Citrix Netscaler 雜湊在 Hashcat 中的 Example hashes 是什麼？
A2: 1765058016a22f1b4e076dccd1c3df4e8e5c0839ccded98ea

>[!Important]問題 3
>Q3: Windows NTLM 雜湊長度有多少個字符？
A3: 32

### 密碼破解
破解密碼聽起來可能很複雜，但其實有些工具可以幫助我們簡化這個過程。

#### 破解密碼雜湊

上面提到過，彩虹表可以用來破解沒有加鹽的雜湊，那麼如果~~他很鹹的話呢~~？🧂

雜湊本身是無法「解密」的，因為他不是加密。破解雜湊其實是通過對大量不同的輸入進行雜湊（像 rockyou 這樣的密碼字典），然後把可能的鹽值添加到輸入中，再和目標雜湊進行比對。

Hashcat 和 John the Ripper 這兩種工具就是使用這種方法。💣


**John the Ripper** 可參考[這裡]()，Hashcat 使用方法請自行搜尋。

#### 開始破解吧！
這邊會提供一些雜湊值，你可以使用任何工具來破解這些雜湊。

>[!Important]問題 1
>Q1: 破解雜湊值 "`$2a$06$7yoU3Ng8dHTXphAg913cyO6Bjs3K5lBnwq5FJyA6d01pMSrddr1ZG`" 的明文密碼是什麼？
A1: 85208520

>[!Important]問題 2
>Q2: 破解雜湊值 "`9eb7ee7f551d2f0ac684981bd1f1e2fa4a37590199636753efe614d4db30e8e1`" 的明文密碼是什麼？
A2: halloween

>[!Important]問題 3
>Q3: 破解雜湊值 "`$6$GQXVvW4EuM$ehD6jWiMsfNorxy5SINsgdlxmAEl3.yif0/c3NqzGLa0P.S7KRDYjycw5bnYkF5ZtB8wQy8KnskuWQS3Yr1wQ0`" 的明文密碼是什麼？
A3: spaceman

>[!Important]問題 4
>Q4: 破解雜湊值 "`b6b0d451bbf6fed658659a9e7e5598fe`" 的明文密碼是什麼？
A4: funforyou

### 完整性檢查中的雜湊技術

#### 完整性檢查
雜湊技術在檢查檔案是否被修改方面非常有用。只要輸入相同的數據，就會得到一致的雜湊值。即使只有一位元的變動，雜湊值也會顯著改變。這使得雜湊成為檢查檔案是否被更改或檢驗檔案是否正確下載的理想工具。✅

例如：如果兩張圖片的雜湊值相同，那麼他們就是同一張圖片。

#### 雜湊訊息鑑別碼 (HMAC, Hash-based Message Authentication Code)
HMAC 是一種使用加密雜湊函數來驗證數據真實性和完整性的方法。通過使用秘密金鑰和雜湊算法來生成雜湊值，HMAC 可以確保創建者的身份和訊息未被修改或損壞。

>[!Important]問題 1
>Q1: [amd64 Kali 2019.4 ISO](http://old.kali.org/kali-images/kali-2019.4/) 的 SHA1 校驗和是多少？
A1: "`186c5227e24ceb60deb711f1bdc34ad9f4718ff9`"

>[!Important]問題 2
>Q2: `HMAC-SHA512 (key = $pass)` 的 hashcat 模式編號是多少？
A2: 1750

### 參考資料
https://tryhackme.com/room/hashingcrypto101