談密碼破解的「暴力法」和「字典法」

日前在臉書引述聯合報一則關於密碼破解的新聞，原意是無病呻吟一番，抱怨在記性逐漸消退的這把年紀，還不斷有人要求拉長密碼，免得三兩下被駭客破解，導致出醜露乖破財失身等不良後果。不想引來一番議論。臉書適合三言兩語即時對話，長篇大論顯得累贅。相信很多非技術背景的旁觀者看得霧煞煞，有如禪門公案。這裡試著把一些觀念講得明白些，一方面自己做個筆記，免得五年、十年後忘個精光。

新聞內容講的是幾個駭客做的實驗，對某網站近兩萬個帳戶的密碼清單加以攻擊，被破解的帳戶，當然就門戶洞開了。實驗中採用若干攻擊手法，新聞提到「暴力法」和「字典法」，都是馬步功，但據說成果豐碩，因此標題下了結論：「破解不難」。然後語重心長告誡諸看官，最少要用11字以上密碼云云。

盤古開天之初，所謂密碼清單，就是「帳戶名稱－明文密碼」的對照表，如「張三－1111；李四－22222；王五－333；...」依此類推。很顯然的，這種密碼清單萬一被盜，竊賊不費吹灰之力便可登堂入室。後來幾經演變，清單內容要求必須加密；其中密碼部份，常用所謂雜湊（Hashing）函數處理。雜湊函數可以想像成一部絞肉機，原先不管那個部位什麼來源的肉塊，處理後都變成一坨糊糊難以辨認的肉泥。它有兩項特點，其一是結果（稱為雜湊值）的長度固定，不論輸入文字是長是短，輸出都是同樣長度的亂碼，可以避免破解者藉密碼長度進行猜測。其次，也是最重要的，雜湊函數可以由原文產生固定雜湊值，但不可逆向推導；也就是說，由雜湊值不可能反推出原文。即使密碼清單被盜，竊賊也無法解出密碼原文，因此被認為是安全的。

至於驗證系統，也不需要保存原文，密碼清單只記錄雜湊值；使用者輸入密碼原文後，以雜湊函數算出雜湊值，和清單比對，正確就放行。至於在網路上傳遞密碼，必須採用其他安全機制以防洩漏，則不在本文討論之列。

道高一尺魔高一丈，仗著現代電腦的強大計算能力，儘管無法由雜湊值還原，只要有密碼清單，加上正確的絞肉機，也就是雜湊函數，破解者可以投入任意組合的明文，只要最後得出相同的雜湊值，那段明文便是通關密碼。這就是新聞中所說的駭客實驗。真實世界中，密碼清單並沒有那麼容易盜取，雜湊函數也不可能是公開的那幾種，至少也要加以變造。如何保衛這兩樣東西，是系統安全的另一項課題，也不在本文討論之列。

接下來要討論的，是破解者手中已經握有記錄帳戶名稱和雜湊值的密碼清單，以及該系統用來產生雜湊值的雜湊函數，憑這兩樣東西，要怎麼猜出用戶密碼原文。

最簡單的是所謂暴力法，說穿了便是窮舉法，從最基本的1,2,3,4開始，把所有可能組合，都餵進雜湊函數，再將產出的雜湊值和清單比對。假設有無窮盡的時間和計算能力，總有一天，一定能找出答案。現實則不太可能，組合數量隨密碼長度呈指數增加，必須把範圍加以限縮。通常容許用做密碼的，包括大小寫字母和阿拉伯數字，大部份標點可以排除。以64個可用字元為基礎（26*2+10+2）估算，一碼有64種組合，兩碼是64的平方，依此類推。以新聞中算到六碼，也就是64的六次方，約687億種組合，兩分半鐘掃過一遍，算是可以接受。只是每多一碼，時間要再乘以64，慢慢就會變得不切實際。

所有破解方法，無非希望在有限時間內，以合理的方式降低猜測次數，提高命中機率（以數學來說，就是設法將指數（Nn）發散的組合數，變成階層（N!）甚至倍數（Nx））。新聞中提到的字典法便是其中之一。一般人記憶無意義字元組合（如fH6aOw）的能力有限，假設密碼超過某個長度，就必須使用輔助記憶手段。有意義的單字是不錯的選擇，可以輕易拉長，卻仍然記得住，如MyDictionaryContains100000Words。字典法則是針對這種記憶手段的攻擊招數，也就是以單字而非字元為單位，進行排列組合，當密碼長度增加時，可以有效降低組合數。

當然，用戶選擇密碼時，未必會那麼乖，拿字典原封不動搬來用。可能用大小寫、附帶數字、加減字母、錯漏字、交錯反轉等各種方式加以抖亂，運用字典法時，也要對這些可能性做對應調適。原則上以容易記憶者優先，如首字母大寫，附加年份日期等。再考慮人性，譬如說密碼長度超過32字元，可能是自虐狂才會做的事（我做過，所以我知道），因此組合超過某個限度，就慢慢來或根本不理會。長度低於6者，前面用暴力法，已經在兩分半鐘內解決，也不必再考慮。講起來好像很複雜，但考慮得愈多，可排除的排列組合也會愈多，所花的時間會更少，命中率則會提高。新聞中說在五個多小時內，算出七到九成密碼，應該代表這套字典法，已經達到某種程度的成熟。

從上述說明可以瞭解，愈不規律的密碼愈難猜；如果沒有半點規則可循，只能用暴力法，那麼只需要11個字元，而不是32個，以目前計算能力，就足以累死破解者，故應該還算安全。然而11個無規律字元，卻超過多數人的記憶能力。一方面電腦計算能力持續飇高，另方面人腦記憶力卻很難長進；我認為單純使用文數字密碼的場合，道消魔長的相對變化，時間不會很久。

有朋友提到，重複原始密碼以增加長度是否可行，例如abc123abc123。遺憾的是，對輔助記憶雖然有幫助，但對於抵抗字典法攻擊卻沒什麼大用。因為「重複」是電腦強項，當我利用某些規則，產生特定文數字組合的時候，把它重複幾次丟進絞肉機試試看，是毫不費勁的事。「重複」是倍數而非指數，多幾次也無所謂。何況由於密碼長度限制，愈長的原文，所需重複次數愈少。因此純就密碼安全來說，只需要第一段夠長夠亂，就行了，重複意義不大。

也有朋友提到，利用注音或其他中文輸入法所產生的鍵盤碼當做密碼原文，好處是看起來夠亂，而英文字典也絕對找不到。我的看法則不盡然。倘若應用國語辭典，每個漢字相當英文單字，其實肉眼看來亂糟糟的密碼，對電腦來說都是有跡可循。利用字典法的操作原則，同樣可以對鍵盤碼密文發動攻擊。而且由於中文輸入法的若干特性，未必會比英數字的複雜度高。譬如注音鍵盤碼用到41個字元，但其中五個很少、或不允許用於密碼，如ㄥ（’/’），又剛好都是韻母（母音），可以大量排除可能組合。又如倉頡輸入法，完全沒用到數字，排列組合也會大幅受限。因此我認為這種做法雖有助於記憶，抵抗力卻未必如想像中高。

由於對付的是整批密碼清單，可以用暴力法或字典法好整以暇進行攻擊，而且清單愈長，愈可能收穫豐碩。原因很簡單，可以想像如果針對特定一個帳戶，要找出其密碼所花時間，最差狀況，大約也是查遍所有組合，和找出兩萬個帳戶的密碼相差無幾。何況還有雜湊函數的「碰撞」問題。原來雜湊函數雖然保證每一段原文只會產生一組雜湊值，但每一組雜湊值卻未必只對應一段特定原文，意思是說，倘若樣本夠多的話，有機會找出兩組以上的密碼原文，產生同一組雜湊值。換句話說，不見得需要找出「真正的」鑰匙，只要找出「能開門的」鑰匙就行。當然這種瞎貓碰上死老鼠的事並不多見，只是清單愈長而字典愈大，發生碰撞的機率就愈高罷了。

或許你會覺得，整批密碼清單被盜走的糗事，應該不常發生才對。這要從兩方面來看。就攻擊者一方，通常是循序漸進，像金融機構安全措施比較嚴謹，密碼輸入錯誤若干次就會鎖死，不是發起攻擊的好對象。多半由防衛薄弱的中小型網站先下手，重點突破取得密碼清單，加以破解，大批個人資料就不難得手。在用戶這方面，出於惰性以及記憶力不足，多數人會使用類似甚至相同的帳號密碼。有了你的個資帳密，要撬開其他門戶就相對容易。隨著突破點愈來愈多，重要機構淪陷的風險也會隨之昇高。當你聽到新聞說，某家大銀行信用卡資料失竊的時候，其實前面已經不知攻破多少地方。因此專家通常會建議，避免用相同帳密，密碼要長而且亂，才能有效遏止駭客入侵。

麻煩的是，一般人如我，那裡有那麼好的記性呢？我自己曾經登錄的各式網站，沒有一百也有八十；雖然常用的不過十來個，卻依然經常攪混。更別提不常用，甚至很久沒用的，有時候突然問我一個兩百年前設定的問題，糟糕的是，別說答案，有時連問題是什麼都不記得。（真有人這樣問：你當初開戶時設定的問題是什麼？）

（寫得太長，沒寫完便擱下，後來忘掉，從未發表）

 

2013.5.30 13:40:13 （留言處已經掛了，應該在談類似主題）

 

如果hashed password list和 hashing 程序都曝光，剩下的當然只是時間問題。網路安全不能只靠演算法，各種可能漏洞都要防護才行。長密碼固然有效，但人腦負荷太重，也會有副作用。
我自己用過長達32字元的密碼，之所以記得住，因為那是出自手邊書籍特定頁面的第一句。在PC上用一陣子還好，有一天需要在手機輸入，就成了夢魘了。後來只好一切從簡。