栗子現場直播 千篇一栗
有很多簡單的道理,若不是被遺忘,不是察覺不到,就是知易行難。

2012年1月10日 星期二

Hash

早前香港泛民政黨搞特首初選,引來一些私隱安全的爭議,例如身份證號碼的外洩問題。泛民的香港互聯網協會會長莫乃光稱,他們會運用 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 數值。如下(註十四):

身份証原 MD5Salt=ASalt=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 為例:

算法十六進制結果
MD59f6290f4436e5a2351f12e03b6433c3c
CRC3268efff54
SHA-1476432a3e85a0aa21c23f5abd2975a89b6820d63

註七:不同的算法,hash 數值範圍也會有不同:

算法hash 數值範圍
MD50 - 340282366920938463463374607431768211455
CRC320 - 4294967295
SHA-10 - 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 個身份證號碼。但即使系統變得這麼慢,暴徒還是可以花一分鐘,去驗証小明這個人有沒有投過票,因為這本身已經是該系統設計的最根本原則。如果設計者嘗試把每個人的驗証時間再拉長,例如一小時,那麼在正式初選時,每位選民也必需花一小時去投票,是沒有可能的。

9 則留言:

匿名 提到...

How about double hash or triple hash?

栗子捌貳 提到...

double/triple hash 沒有用。我還是能在短時間內,製作 26000000 個 hash 的 table。

李小路 提到...

我想知多少少有關個salt既function
可唔可以自定個salt放係邊?
同埋,如果話主辦單位要用salt既話,個salt既位數係佢決定,or可以每個人自己簡入幾多個?
btw,md5係唔係fix左32個位(16進制計)

Sam Wong 提到...

Dictionary Attack係一定得係呢個Scenario中係一定Feasible的,因為泛民的系统本身也要準備一天讓全港市民投票。換句話 - Worst case - 只要有整個系统的資源,用一天的時間Dictionary就全出來了。

Sam Wong 提到...

Dictionary Attack係一定得係呢個Scenario中係一定Feasible的,因為泛民的系统本身也要準備一天讓全港市民投票。換句話 - Worst case - 只要有整個系统的資源,用一天的時間Dictionary就全出來了。

栗子捌貳 提到...

回李小路:
不同的系統,有不同的放置 salt 方式。例如 Unix 密碼,就是完整放在密碼 hash 旁邊。有些人則會把它放在程式之內。
而在選舉中,salt 值必需固定,才能做身份証驗証工作。亦因為如此,這個值不能由選民去輸入。如果由選民輸入salt的話,如果他重新投票時,選不同的 salt 值,系統就認不出他之前有投票過。
MD5 一定是 32 個位。

栗子捌貳 提到...

回李小路:
忘了說。莫乃光稱,iPad會先把身份證化為hash後,才經網絡上傳到伺服器。如果有salt,它應該是放在iPad那邊。而所有iPad上的salt都是相等。

李小路 提到...

好...大致明白...等我拎黎放入我份project度做security果part先wwww(拖走

史迪 提到...

如在政府下執行,是有了多一層保障─法律!

當然,退一步,當法律你也不相信時,那也沒有甚麼好信了.....