早前香港泛民政黨搞特首初選,引來一些私隱安全的爭議,例如身份證號碼的外洩問題。泛民的香港互聯網協會會長莫乃光稱,他們會運用 hash 技術,去保障市民私隱,避免身份證號碼外洩。本文會深入淺出,簡單介紹 hash 技術,並指出其安全性問題。
本文主要分為正文和附註。正文是對 hash 的簡單介紹,我希望一般人能看得明白。而附註部份則包含技術細節,但比較深奧,不是人人可以看明白。
在此先聲明,本人是香港科技大學資訊科技碩士(註一),以下所言,絕非泛泛的空談(註二)(註三)。
外界有甚麼私隱的憂慮?
- 泛民團體能得到投票者的身份證清單。
- 若發生意外,或被黑客入侵,投票者的身份證清單就會外洩。
甚麼是 hash 技術?
Hash 技術是透過一系列複雜的數式和程序,把一串資料轉化成一個簡短的數值。在資訊科技中,hash 技術是非常基本的常識。任何 IT 人都一定會知道 hash 技術。如果不知道,就沒資格自稱 IT 人。
Hash 的算法有很多種,例如 MD5 / SHA-1 / CRC32,原理和慨念都差不多。本文主要會以 MD5 做例子。(註四)
以下是 MD5 的部份實例。一般的 IT 人都習慣看十六進制的 MD5 數值,但為了方便一般的讀者,我也會展示十進制的結果以作參考。
原文 | MD5 (十進制) | MD5 (十六進制) |
Apple |
211859036441461519383052513295366044732 |
9f6290f4436e5a2351f12e03b6433c3c |
apple |
41499123188802761002464065009245263231 |
1f3870be274f6c49b3e31a0c6728957f |
Orange |
192223576784283470402484290296281237729 |
909cea0c97058cfe2e3ea8d675cb08e1 |
The quick brown fox jumps over the lazy dog |
210103647840849757586127012022035159510 |
9e107d9d372bb6826bd81d3542a419d6 |
MD5 和其他一般的 hash 算法,都有以下的特性:
- Hash 數值看起來就像高深的數字,一般人可能會被嚇怕,但其實沒有意義。(註五)
- 不論何時,只要輸入的資料相同,計算出來的 hash 數值亦都相同。完全不涉及任何隨機的成份。(註六)
- 即使輸入的資料有些微的不同,結果也會出現極大的變化。例如 Apple 和 apple 的分別。
- 輸出的數字必定在某個範圍之內。MD5 的範圍是 0 - 340282366920938463463374607431768211455。(註七)
- 輸入的資料可以極度長,你甚至可以把全套金庸作品化為短短的 hash。
- 無法從 hash 數值把資料還原(下文會討論字典攻擊)。你可以把一套金庸作品化為一個短短的 hash 數值,卻不能把短短的 hash 數值還原成一套金庸作品。
- 在極極極極極端少數的情況下,兩組不同的資料輸入,經過同一個 hash 算法,可能會得出完全相同的 hash 數值。這就是所謂的 hash 衝突。但發生機會實在極極極極極端微。在 MD5 發生 hash 衝突的機會,比連中五次六合彩還要低。(註八)
Hash 技術的最主要用途,是檢查資料在儲存和傳輸中途,有沒有出錯,有沒有被修改。
例如,甲某把「Apple」發給乙某,並附上它的 MD5「9f6290f4436e5a2351f12e03b6433c3c」。後來陰差陽錯,送到乙某手上時卻變成了「apple」。乙某計算「apple」的 MD5「1f3870be274f6c49b3e31a0c6728957f」,和之前的 MD5 不相同,乙某就知道傳輸過程出了問題。(註十九)
一些人上載數百 MB 的電影上網時(犯法),也會附上 MD5 數值。下載者可以透過檢查檔案的 MD5 數值,來確認檔案有沒有出問題。另外一些 P2P 的傳輸軟件,例如 BT,都會內置 hash 數值,並自動檢查檔案沒有出錯。
另外,hash 還可以做密碼驗証。如果你的銀行密碼是 Apple,銀行不會直接儲存 Apple 這個字,而是它的 hash。因為是 hash,銀行就不能還原變回密碼,但可以對客戶做到密碼驗証,達到最佳的保安。(註九)(註十)
由以上可見,hash 能夠用非常小的成本,來確保資訊的安全。在資訊科技中是非常方便的技術,亦是資訊科技的常識。
泛民如何使用 hash 技術,來檢証身份証號碼?
例如小明去投票,把身份證輸入到電腦,電腦就會先把他的身份証號碼變成 hash 數值,然後系統就會搜索資料庫。由於小明是第一次投票,資料庫沒有該 hash 數值,我們就能確認小明沒有投過票。小明投票後,系統就會把那個 hash 數值輸入到資料庫中。
然後如果小明再去投票,再次把身份證輸入到電腦,再次計算出 hash 數值。但這時系統會從資料庫中找到相同的 hash 數值,即代表他已經投過票。
hash 技術有甚麼問題?
如果把 Hash 技術,運用在選舉的身份証檢查,我們一般有兩個主要考慮的問題:
第一個會考慮的問題,是 hash 衝突。
正如之前提到,hash 數值是有可能出現衝突的。假設小美有連中五次六合彩的幸運,和小明身份證的 hash 相撞。小明投票後,到小美投票時,系統會從小美的身份證,計算到和小明身份證相同的 hash 數值。由於此時資料庫已經有小明身份證的 hash,系統就會以為小美已經投了票,產生美麗的誤會。
但發生以上問題的機會,亦微乎其微。假設身份證都是一個英文字母再加六個數字的組合(註十一),有 26000000 個變化。而 26000000 個身份證號碼,出現相同 MD5 數值的機會,卻仍遠遠低於連中三次六合彩(註十二)。更何況香港人口只有 710 萬,MD5 衝突機會更少,所以這個問題可以無視。
第二個會考慮的問題,是資料還原的問題。之前雖然說過,我們不能用短短的 MD5 數值來還原一部金庸作品。但若套用在選舉的身份證,卻會輕易地被「字典攻擊」把身份證號碼還原。
要發動「字典攻擊」,只需一部普通的家用電腦,花一點時間製作 26000000 的身份証 hash 轉換表:
身份證 (註十一) | MD5 (十六進制) |
A000000(A) | 3e5d53ecf650f2f253a95dc725bc8c44 |
A000001(A) | bd18aaf50431f42c3c4a2179ba0c90c7 |
A000002(A) | 9b56ad94e96bd75e6e1d1fc10d74fa33 |
... |
Z999999(A) | 26cee21d763191b4af4c20aacb28a5ad |
如果泛民的資料庫中,出現 bd18aaf50431f42c3c4a2179ba0c90c7,他就是 A000001(A)。如是這般,我們就能找出所有投過票的人的身份證。(註二十)
應付「字典攻擊」有很多方法,其中一個方法名叫「salt」(註十三)。它是由使用者輸入的字串,來影響 hash 數值。如下(註十四):
身份証 | 原 MD5 | Salt=A | Salt=B |
A000000(A) |
3e5d53ecf650f2f253a95dc725bc8c44 |
b1b6241efd48a508e893efbc5364ce61 |
197ef08e6bd12a69060880d7c34ef11c |
A000001(A) |
bd18aaf50431f42c3c4a2179ba0c90c7 |
ed4b4820a17a875de4bac4104bd96a6b |
a6db096939edb5aaaa3542d620448e60 |
A000002(A) |
9b56ad94e96bd75e6e1d1fc10d74fa33 |
2cf76cfc24da72c084419090cde00a67 |
fc7e42a868ffc205947f19175e67441c |
... |
Z999999(A) |
26cee21d763191b4af4c20aacb28a5ad |
638f60e278cf30b06038a41b7392c6b6 |
ff182d9109570e84cc1dd6c1c1710767 |
如上所見,只需要一個簡單的 salt,就能使整個 MD5 數值表出現大大的變化。Salt 此時就像一個密碼。即使整個身份証資料庫被搬走,只要 Salt 夠長夠複雜(註十五),泛民又能把 salt 好好保存,其他人也無法得到那堆選民身份證。(註十六)
但是,如果某某同時擁有 salt 和資料庫,他還是能把投票者的身份証號碼還原。方法像之前提及過的「字典攻擊」做法,利用那個 salt 製作 26000000 個身份証 hash 的轉換表,就能得到所有投票者的身份証號碼。
而現時有能力利用以上方法,把所有參與選舉的市民的身份証號碼還原的,就是主辦初選的泛民團體本身。
於是結論就是:如果主辦團體缺德,他們就可以把投票者的身份証號碼挖出來。如果主辦團體無能,洩露資料庫,hash 方法及其 salt,整個身份証號碼清單隨時會被公緒於世。簡單而言,hash 根本沒有解決本文最初提出的兩個憂慮。
我們可以怎麼辦?
我把 hash 甚麼的說了這麼久,結果還是回歸最根本的問題:你是否相信主辦團體?
如果你不相信他們,那麼 hash 就沒有意義。即使他們說使用了驚天地泣鬼神宇宙無敵的安全措施,你都可以懷疑他們有後門,你都可以懷疑他們會犯錯。你甚至可以懷疑義工能過目不忘,把每張身份證都用腦袋記住。如果你不相信他們,甚至認為他們已經投共,那麼有沒有 hash 根本沒有關係。
如果你相信他們,那麼 hash 也一樣沒有意義。在區議會和立法會選舉,政府也沒有使用甚麼 hash,所有工作人員都清楚看到選民的列表,誰有投票,誰沒有投票,甚麼名字,甚麼身份證號碼。你這樣仍不會擔心自己的私隱,就是因為你相信政府。如果你能像信任政府那樣信任主辦團體,那麼有沒有 hash 根本沒有關係。(註十七)
既然問題和 hash 無關,所以和本文主題亦無關了。(註十八)
歡迎分享及轉載本文,請註明出處: http://blog.luzi82.com/2012/01/hash.html
註一:我相信一般的電腦學士,高級文憑,甚至對 IT 有認識的中學畢業生,都明白這些道理。
註二:科幻電影的電腦奇才可以瞬間破解 256 位元的密碼。嘿嘿嘿。我不敢說沒有這種人啦。聽說有人發個正念,電腦病毒就拜拜了。
註三:網上某文章稱 SHA-1 可以被輕易破解。姑且不論該文章是否真實。我隨便在一部白痴的 i7 870,用白痴的 single thread 跑白痴的 bash script,計算 26000000 個 MD5 數值做字典攻擊,也不需要兩個鐘。
註四:即使泛民在選舉中使用更高位元的 hash 方式,面對本文提及的「字典攻擊」,亦完全沒有幫助。
註五:本來是打算以 CRC32 做例,短小精桿看起來不太可怕。但如果用它來對照身份證,hash 衝突機會超大。
註六:如果使用 salt,salt 數值就必需固定,才能得出相同的 hash 數值。另外,不同的 hash 算法有不同的 hash 數值。以 Apple 為例:
算法 | 十六進制結果 |
MD5 | 9f6290f4436e5a2351f12e03b6433c3c |
CRC32 | 68efff54 |
SHA-1 | 476432a3e85a0aa21c23f5abd2975a89b6820d63 |
註七:不同的算法,hash 數值範圍也會有不同:
算法 | hash 數值範圍 |
MD5 | 0 - 340282366920938463463374607431768211455 |
CRC32 | 0 - 4294967295 |
SHA-1 | 0 - 1461501637330902918203684832716283019655932542975 |
註八:128 位元 hash 衝突的機會率:2^(-128)=2.9e-39 ,連中五次六合彩的機會率:(49C6)^-5=1.9e-36 。
註九:任何有經營網上服務的人,例如香港人網討論區,都應該明白這個道理。如果不明白,我會為你們會員的私隱感到非常不安。
註十:面對字典攻擊,可以使用 salt 防禦。但 salt 不能保護身份証號碼,述於後文及註十六。
註十一:身份証結尾括號內的是驗証碼,本身有一定規律,本文不作深入討論。
註十二:26M 個身份証號碼出現相同 MD5 的機會率:1-(2^128)P(26M)/((2^128)^26M)<1-(((2^128)-26M)/(2^128))^26M=2.0e-24 。連中三次六合彩的機會率:(49C6)^-3=3.7e-22
註十三:其他防範「字典攻擊」的方法:例如把身份証號個整個反轉,效果和 salt 相同。但和 salt 的問題一樣,只要方法給洩露出去,就會失去保護作用。
註十四:本例子的 salt 類型為 HMAC。
註十五:如果 salt 不夠長不夠複雜,攻擊者還是能透過暴力算法,把 salt 挖出來。如果攻擊者知道其中一位投票者的實際身份證號碼,如自己親身投票,那麼挖 salt 的速度會更快。
註十六:一般電腦或網上討論區,在記憶賬號密碼 hash 時,一般都會在不同的賬號,使用不同的 salt,然後把 salt 不經加密存放在資料庫中。這個做法有個好處,就是使攻擊者無法利用字典攻擊,同時取得所有賬號的密碼,大大增加攻擊者的成本。而且不會製造新的保安漏洞。但在泛民初選中,由於系統要檢查選民有沒有投過票,就必須支持搜索功能。但如果每張身份證都使用不同的 salt,資料庫就無法從 hash 進行搜索。因此這個方法在泛民初選並不適用。
註十七:身份證本身來自政府,私隱沒甚麼好擔心的。但從最近的造票事件看,若政府不是無能,就是缺德。
註十八:IT 除了研究算法,軟件和硬件的安全隱定以外,還有操作者管理者的能力和操守。雖然莫乃光聲稱系統安全,但他也只是說技術層面而已。他說找了「專家」保障私隱安全,那「專家」又是誰呢?是要動輒花上數百萬的資訊保安公司,是會寫 PHP 網頁的中學生,還是他自己?在我們 IT 界,一些人為節省成本偷工減料,找中學生寫程式是司空見慣的事。而莫乃光乃堂堂香港互聯網協會會長,不似會做這種有違專業操守的勾當。但任何一位負責任的 IT 人,都不會贊成使用義工提供的私人電腦,去做登記身份證的工作,亦有損專業形象。
另外,香港的泛民陣營,都是登記為「有限公司」營運。而根據香港的法例,任何有限公司搜集個人私隱,都必需得到書面同意。然而今次的選舉過程卻沒有做這個。所以,任何人或組織,包括反對選舉的人民力量,都可以以此控告主辦團體。但如果他們這樣做,就會令以後的初選蒙上陰影。
註十九:雖然 hash 可以讓收訊者發現資料出現問題,但無法把資料修復或還原。如果發生問題,一般的做法是要求對方把訊息重發,或重新把檔案下載。
註二十:其實不論登記系統是用甚麼方法,甚至是個外星人的黑盒,只要它能快速確認某個 ID 是不是已經被登記,這種系統就已經稱不上安全。例如,我想知道小明有沒有投票,只要把他的身份證丟去系統確認一下就可以了。假如有暴徒突然佔領香港,要找出所有投票者,他們可以再次把那個系統搬出來,強迫全香港人驗身份証,就能找出所有投票者。這思考進路不但簡單,亦不需要研究 hash 的特性,就能得出結論。但是本文章主題既然是 hash,所以就由 hash 角度出發吧。其中一個規避「全民驗証問題」的方法,是使系統變得極不快速,例如花一分鐘去驗証一個人,暴徒就必須花四十九年去驗証 26000000 個身份證號碼。但即使系統變得這麼慢,暴徒還是可以花一分鐘,去驗証小明這個人有沒有投過票,因為這本身已經是該系統設計的最根本原則。如果設計者嘗試把每個人的驗証時間再拉長,例如一小時,那麼在正式初選時,每位選民也必需花一小時去投票,是沒有可能的。