雜湊值速度探討
Hashing Speed
2019-11-27 by 高田鑑識
資料的指紋：雜湊值(Hash)
如何將一個檔案或一組資料，用一個簡單的方式給予一個唯一的ID來辨識？128-bit MD5的雜湊值是業界通用的一個方式．128-bit大約是340兆兆兆，雖然實際可以使用的識別數量沒那麼多，碰撞(Collision)的情況（兩個不同的資料產生相同的雜湊值）在平方根的340兆兆兆後會發生，但一個很大數字的平方根還是一個很大數字．
Cellebrite的PA，也有使用MD5 Hash來快速篩選檔案．每一個手機或電腦上皆有很多預設的系統圖檔或聲音擋等等，為了讓鑑識或調查人員在閱讀報告時不要有過多的干擾，PA預設在開啟“圖檔”選項時會將已知的系統檔案忽略（如下圖）．
圖一、篩選已知圖檔
另外，國用的Project VIC也是一個很好的Hash應用例子，這個組織主要的目的是防止兒童遭受性侵害．當有兒童性侵或戀童僻的嫌疑犯時，有很大機會可以在他們的電腦或手機上找到從網站或暗網下載的不雅兒童照片或影片．而Project VIC有一個線上的資料庫，儲存了這些檔案的雜湊值．由於所有圖片或影片資料皆已Hash化，除了可以讓檢調人員快速使用鑑識軟體比對嫌疑人或犯罪人裝置上的資料外，也可避免Project VIC這些資料的不當散播．國外的檢調單位除了可以共享這些Hash化的資料外，PA也可以將可疑的資料匯出至Project VIC資料庫，分享至鑑識社群來打擊性剝削的犯罪．
好的雜湊值函數，可避免資料被竄改
一個設計優良的雜湊函數(Hash Function)，當原始資料即使有小部分被篡改，計算後的雜湊值與原本資料的雜湊值會有很大的改變。不幸的是，MD5雜湊函數經過時間的考驗後，已被中國的山東大學數學家找出讓兩個不同檔案但碰撞後產出相同雜湊值的方式。如果有興趣可以參考這份說明．（連接）
這有如一個人的身份識別，如指紋或虹膜可輕易被複製，若管制的場域是透過生物驗證就可輕易被進入，或重要資料被竊取．所以若有重要的資料需要檢核唯一性，需採用比MD5 (1991)或SHA-1 (1995)更新的演算法來確保不被偷換．
什麼是好的雜湊值函數設計
檢驗和(Checksum)的計算速度很重要，因為Checksum通常會與傳輸相關的應用有關．如網路TCP每個封包傳輸前皆會計算Checksum值，並置於TCP的表頭Checksum欄位裡．如果接收端收到的資料計算後與原始欄位的Checksum值不同，就會丟棄並要求重傳．該Checksum的函數若消耗大量的CPU，會讓傳輸過程變慢．這樣的情況如果發生在DisplayPort上，後果可能造成殘影甚至無法正常顯示畫面，因為它的傳輸尖峰速率可高達17Gbps．
圖二、TCP 表頭格式
不過好的雜湊函式反而剛好相反，要越慢越好，且必須耗費大量的CPU並可自由調整結果產生的速度(通常透過迴圈調整）．因為當雜湊值可越快被運算出結果，也代表著越快被暴力破解．很不幸的，僅管早期的雜湊函式有預估摩爾定律成長的速度，但沒預見到GPU運算能力在最近幾年的激烈發展．
GPU帶來的衝擊有多大，這邊列出同期的CPU與GPU在計算雜湊值的運算能力
每秒GPU的運算能力可以是CPU的150倍以上，若再加平行運算，暴力破解找出MD5或SHA-1的碰撞結果可以輕易達成．
註：Mc/s: Mega cycle per second
雜湊值與密碼
接著來談談密碼，因為雜湊值與密碼有著親密的關係。 一般而言，密碼或信用卡號等重要資訊，並不會採明碼的方式儲存於資料庫內．且因為彩虹表(Rainbow Table)，這些重要的資訊也不會單純的用雜湊值的方式儲存．一般來說標準的做法皆是雜湊值＋「鹽」的方式來儲存，即使整個資料庫被竊取，也可以保護重要資料不被揭露．
如果在不加「鹽」的情況下，以下是用一般GPU顯卡暴力破解不同長度的密碼所需的時間
| all 6 character password MD5s | 3 seconds |
| all 7 character password MD5s | 4 minutes |
| all 8 character password MD5s | 4 hours |
| all 9 character password MD5s | 10 days |
| all 10 character password MD5s | ~625 days |
如果採用GPU平行運算，每增加一張顯卡可大幅縮短破解時間．而加「鹽」的方式有很多種，如用戶密碼後面增加20字元以上的亂數英數、密碼與密碼中塞入「鹽」、每個用戶的「鹽」都不一樣等等，這邊就不概述．
「鹽」被盜取了怎麼辦？
如果整個資料庫被駭客竊取了，即使密碼用了雜湊值＋「鹽」去保護，很有可能加入「鹽」的函式也會被駭客找出．這時候駭客只要有足夠的GPU運算能力，暴力破解用戶密碼僅是短短幾天的事．而對用戶來說，最好的保護自己密碼的方式是：
- 使用長度大於12字元（雖然很難記住）．
- 使用特殊符號．
- 每個網站皆採用不同密碼註冊．（可透過如Keepass軟體協助）
如果您是開發者：
- 採用bcypt或PBKDF2函式來記錄任何重要的資料．
這些新的雜湊值函式是經過特別設計，難以在GPU上運行。不要使用任何其他計算雜湊值的函式。幾乎所有其他方式都容易受到GPU陣列的暴力破解，而GPU每年只會變得更快，平行運算更容易，暴力破解開發更簡易。
iPhone的Passcode可否採用GPU破解？
是否可以採用GPU來破解iPhone的螢幕鎖？
從上一篇「如何竊取iPhone資料?」可以得知，iOS裝置最重要的金鑰皆儲存於Secure Enclave內，並沒有任何方式可以讀取到這些資料（UID與Passcode)．而且每次使用者輸入螢幕鎖的密碼時，iOS裝置在計算雜湊值是採用PBKDF2函式來運算，每次大約耗時0.08秒．另外iOS裝置還有另一個保護方式，即使駭客有辦法繞過Bootloader並在iOS裝置上直接執行一個暴力破解密碼的APP，另一個Force Delay的機制也會啟用，並限制每10分鐘才可以嘗試一次密碼雜湊值驗證．以下為破解iOS密碼的時間預估．
圖三、暴力破解Passcode
