密碼技術本質解析

單向函數

散列算法是單向函數。也就是說，它們接收一個明文字符串，將它轉換成一小段無法用來重建原始明文的密文。顯然，要使這種函數起作用，轉換中必需丟失一些數據。

乍聽上去，單向函數似乎沒有用，因為您無法從單向計算的密文中找回明文。為什麼要計算一個無法解開的密碼呢？當然，幾乎是單向的函數是非常有用的，因為從本質上講，所有的公鑰函數都是帶“天窗”的單向函數。公鑰密碼術的良好候選函數，是那些在一個方向上容易計算，而在另一個方向上除非您知道某些秘密否則極難計算的函數。因此，我們發現公鑰算法是基於因式分解和其它較難的數學竅門的。

散列函數 正如結果所表明，真正的單向函數也是有用的。這些函數通常叫做 散列函數，其結果通常稱為 密碼散列值、 密碼校驗和、 密碼指紋或 消息摘要。此類函數在許多密碼協議中起著重要作用。

其構思就是接收一段明文，然後以一種不可逆的方式將它轉換成一段（通常更小）密文。理論上，所有可能的明文將散列成一個唯一的密文，但實際上通常發生的不是那樣。大多數時候，幾乎有無窮多個不同的字符串可以產生完全相同的散列值。但是，對於一個好的密碼散列函數來說，在實踐中應該很難有兩個可理解的字符串散列相同的值。好的散列函數的另一個特性是輸出不以任何可辨認的方式反映輸入。

散列函數通常產生恆定大小的摘要。許多算法產生很小的摘要，但是，算法的安全性很大程度上取決於結果摘要的大小。我們推薦選擇那些提供不小於 128 位摘要的算法。SHA-1 提供 160 位散列，是一種可以使用的好散列函數。

可以使用散列函數來確保數據完整性，這很象傳統的校驗和。如果您公開發布一個文檔的有規律密碼散列，則任何人都可以檢驗該散列，假設他們知道散列算法的話。人們在實踐中使用的大多數散列算法是公開發布和為人熟知的。再次提醒您，，使用專用密碼算法，包括散列函數，通常是一個壞主意。

因特網分發 考慮一下分發在因特網上的軟件包的情況。在不遠的過去，通過 ftp 得到的軟件包是與校驗和關聯的。其思想是下載軟件，然後運行一個程序來計算您的校驗和版本。然後可以將自行計算的校驗和與 ftp 網站上得到的校驗和相比較，以確定兩者匹配並確保傳輸連接上（over the wire）的數據完整性（各種各樣）。問題是這種過時的方法根本就不加密。首先，有許多校驗和技術可以惡意修改下載程序，並可能導致修改過的程序產生完全相同的校驗和。其次，帶有其相關聯（保護極差）校驗和的軟件包的“特洛伊”版本可以輕易地在 ftp 網站上發布。密碼散列函數可以用做老式校驗和算法的隨便替代物。它們具有一個優點，就是使篡改投遞代碼變得極其困難。

預先警告您 ― 這種分發方案還有一個問題。如果作為軟件消費者，不知何故下載了錯誤的校驗和，您會怎麼辦？例如，假設我們分發了“xyzzy”軟件包。一天夜裡，一些黑客闖入了分發機器，並將 xyzzy 軟件換成了一個稍作修改的版本，其中包含惡意的特洛伊木馬。攻擊者也將我們公開分發的散列替換成帶有特洛伊副本的散列發行版。此時，當某個無辜的用戶下載目標軟件包時，將得到惡意的副本。受害者也下載了密碼校驗和，並針對軟件包測試它。它進行檢測，而惡意代碼看起來安全可供使用。顯然，如果我們不能確保散列本身不被修改，僅僅散列不能成為完整的解決方案。簡而言之，我們需要一種認證散列的方法。

認證問題

在我們考慮認證問題時，可能出現兩種情況。我們可能希望每種情況都可以驗證散列。如果是這樣，我們可以使用基於 PKI 的數字簽名，這將在下面討論。或者，我們希望限定誰能驗證散列。例如，假設我們向 sci.crypt 新聞組發送了一封匿名信，其中投遞了一種專用加密算法的全部源代碼，但是希望只有我們最親密的朋友才能驗證我們投遞了消息。可以使用消息認證代碼（MAC）來達到這個目的。

消息認證代碼

MAC 通過使用一種共享秘鑰起作用，接收方端使用它的一個副本。該密鑰可以用於認證可疑數據。發送方必須擁有秘鑰的另一個副本。MAC 有幾種工作方式。第一種方式是在計算摘要之前，將秘鑰並置到數據末尾。如果沒有秘鑰，則無法確認數據未經改動。另一種計算更復雜的方式是照常計算散列，然後再使用對稱算法（如 DES）加密散列。要認證散列，必須首先對它解密。

MAC 在許多其它環境中也很有用。如果您希望不使用加密而實現基本消息認證（也許是由於效率原因），MAC 是完成該任務的合適工具。即使您已經使用了加密，MAC 也是一種確保加密位流在傳輸中免遭惡意修改的極佳方法。

如果仔細設計，好的 MAC 可以幫助解決其它公共協議問題。許多協議在遭受所謂的 回放攻擊（或者 捕獲-回放攻擊）期間，明顯存在一個普遍問題。假設我們向銀行發送一個請求，要求從我們的帳戶劃撥 50 美元到 John Doe 的銀行帳戶。如果 John Doe 攔截了通信，他可以稍後向銀行發送一個相同的消息副本！有時銀行會認為我們發送了兩個請求。

回放攻擊

回放攻擊被證實是許多真實世界系統中的普遍問題。幸好，我們可以使用 MAC 的巧妙用法來緩和這種情況。在銀行劃撥示例中，假設我們使用了一種隨秘鑰散列請求的原始 MAC。為了對付回放，我們可以確保散列永遠不同。做到這一點的一個顯而易見的方法是使用時間戳記。

如果服務器發現一個請求的時間戳記過期（比如，超過 60 秒），它將拒絕請求。這或許足夠了，也可能還不夠，因為它還是導致了一個 60 秒的窗口，其中回放攻擊可能 發生。您可能會考慮禁止在同一時間單元發生兩次請求，並緩存關於過去 60 秒以內到達的有效請求的信息。如果您能夠處理這種特殊情況：在同一時間單元裡兩次執行了同一交易，則這種解決方案也許可行。但是存在更簡單的解決方案。當您計算 MAC 時，不僅散列數據和秘鑰，而且散列一個唯一、有序的序列號。遠程主機只需要了解它所處理的最後一個序列號，並確保不處理比下一個預期序列號更舊的請求。這是普遍使用的方法。

在許多情況下，認證其實不是問題。例如，考慮使用密碼散列來認證從控制台登錄到機器的用戶。在許多系統中，當用戶第一次輸入密碼時，實際上並沒有存儲密碼本身。相反，存儲了密碼的密碼散列。因為大多數用戶覺得如果系統管理員不能隨意檢索他們的密碼會更好。假設操作系統是可信的（這是個可笑的大前提），我們可以假設我們的加密散列密碼的數據庫是正確的。當用戶試圖登錄，並輸入密碼時，登錄程序散列它，並將新散列的密碼與存儲的散列比較。如果兩者相等，我們假設用戶輸入了正確密碼，則登錄繼續。

Telnet 協議

可惜，架構設計師和開發人員有時假設認證機制的安全性實際上不是問題，但實際上它是。例如，考慮一下 telnet 協議。大多數 telnet 服務器接收用戶名密碼作為輸入。然後散列密碼，或執行一些類似的轉換，然後將結果與本地數據庫中的比較。問題在於使用 telnet 協議時，密碼在網絡上以明文傳輸。任何能夠使用包嗅探器在網絡線路上偵聽的人都可以發現密碼。telnet 認證提供了很差的保護，潛在攻擊者可以輕易地清除保護。許多著名的協議（包括 FTP、POP3 和 IMAP 的多數版本）都具有類似的破綻百出的認證機制。

其它攻擊

任何好的密碼散列算法應該是這樣的，即使給定一個已知的消息和與它關聯的消息散列，也很難找到替代明文的重復散列。對沖突的故意搜索意味著蠻力攻擊，這通常很難。當攻擊者希望用第二份明文文檔產生除了雜亂無意義的字符串之外的東西時，就尤其困難。

另一種對密碼散列的攻擊比平均蠻力攻擊容易實施得多。考慮下列情況：Alice 向 Bob 顯示了一份文檔和驗證文檔的密碼散列，文檔內容是 Alice 同意為每個小飾品付給 Bob 5 美元。Bob 不想在他的服務器中存儲該文檔，所以他只存儲了密碼散列。Alice 希望只為每個小飾品付 1 美元，所以她想創建第二份文檔，所產生的散列值和 5 美元的那份相同，然後告上法庭，控訴 Bob 多收了她的錢。當她出庭時，Bob 將出示散列值，相信 Alice 的文檔不能散列出那個值，因為這不是她顯示給他的原始文檔。如果其攻擊是成功的，Alice 將能夠證明她所偽造的文檔確實散列出 Bob 存儲的值，法庭將判她勝訴。

但她是如何做到這一點的呢？Alice 使用了所謂的 生日攻擊。在這種攻擊中，她創建了兩份文檔，一份寫著每個小飾品 5 美元，另一份則寫著每個小飾品 1 美元。然後，在每份文檔中，她標識出 n處可以進行表面更改的地方（例如，那些可以用制表符取代空格的地方）。好的 n值通常是最終散列輸出的位長度的一半加 1（所以如果我們指定散列輸出的位長度為 m，則 n= m/2 1）。對於 64 位散列算法，她將在每份文檔中選擇 33 個地方。然後她反復嘗試每份文檔不同的排列，創建和存儲散列值。一般來說，預計她將在散列了大約 2 m/2條消息之後找到散列出相同值的兩份文檔。這比蠻力攻擊要有效得多，如果使用蠻力攻擊，預計她必須散列的消息數為 2 m-1。如果 Alice 執行一次成功的蠻力攻擊需要一百萬年，那麼她也許一周以內就可以完成一次成功的生日攻擊。因此，Bob 應該要求 Alice 使用一種算法，它所產生的摘要大小使得她不能在任何合理的時間之內完成生日攻擊。

如果希望針對生日攻擊獲得和針對蠻力攻擊一樣的安全性，給定一個密鑰長度為 p的對稱密碼，您應該選擇提供大小為 p*2的摘要的散列算法。因此，對於具有很高安全性需求級別的應用程序，要求散列算法產生 256 位甚或 512 位的消息摘要是個好主意。

什麼是適用的好散列算法呢？

我們特別喜歡 SHA-1。Bruce Schneier 也推薦這個算法。但是如果散列