第八講 數(shù)據(jù)加密標準（des）

1、第八講 數(shù)據(jù)加密標準(DES),1974年，IBM 向美國國家標準局(NBS)提交了一個名為 LUCIFER的加密算法。NBS將其轉(zhuǎn)給了國家安全局 (NSA) 進行審定，之后就得到了一個名為數(shù)據(jù)加密標準DES的算法。1977年，NBS 正式將其用于無限制級的政府通訊。,從1975年起，圍繞DES的爭論就沒有停止。許多學者擔心NSA無形的手對算法產(chǎn)生的干預(yù)。如： (1) NSA可能修改算法以安裝陷門。 (2) NSA將原先的

2、128位密鑰縮短到56位。 (3) 算法內(nèi)部的運行機理始終沒有得到明確解釋。例如，差分分析。 許多NSA設(shè)計算法的原理在90年代逐漸清晰起來，但在70年代這些的確另人迷惑。,DES已經(jīng)使用了三十多年，因此，2000年，國家標準與技術(shù)研究所(NIST)決定使用新的系統(tǒng)代替DES。但是DES仍然值得研究，它代表了一類曾經(jīng)非常流行的對稱加密算法。 DES是分組密碼，每個分組為64比特數(shù)據(jù)。 64比特明文通過加密最后成為

3、64比特密文。 DES 的核心是一個被稱為Feistel系統(tǒng)的部件。,本講提要,簡化DES型算法 差分分析 DES DES不是一個群 破譯DES 口令安全,1 簡化 DES型算法,一輪 Feistel系統(tǒng),一輪 Feistel系統(tǒng)(續(xù)),一輪 Feistel系統(tǒng) (續(xù))函數(shù) f(Ri-1，Ki),一輪Feistel系統(tǒng)(續(xù))擴張函數(shù),,S-盒,一輪Feistel系統(tǒng)(續(xù)),2 差分分析,思路：通過適當選擇明文得到密文比較

4、它們的差異以推導出使用的密鑰。我們從前面的操作可以看出密鑰與E(Ri-1)進行異或得到結(jié)果，因此，我們可以通過再次異或移除由密鑰引入的部分隨機性。,2.1 針對三輪的差分分析,2.1 針對三輪的差分分析(續(xù)),2.1 針對三輪的差分分析(續(xù)),2.1 針對三輪的差分分析(續(xù)),2.2 針對四輪的差分分析,四輪差分分析是建立在三輪基礎(chǔ)之上的，但是要擴展到四輪還需要使用一些統(tǒng)計方面的知識。這里我們關(guān)注S-盒的一些弱點。,2.2 針對四輪的差

5、分分析 (續(xù)),2.2 針對四輪的差分分析 (續(xù)),2.2 針對四輪的差分分析 (續(xù)),2.3 關(guān)于差分分析,(1) 我們注意到前面的例子表明差分攻擊至少和強力攻擊有相同的速度。然而，對于更優(yōu)異的系統(tǒng)如DES ，在一定的輪數(shù)下，差分攻擊的效率將明顯快于搜索全部密鑰空間的強力攻擊。 (2) Mitsuru Matsui 發(fā)明了另一種名為線性攻擊的分析方法。這一攻擊使用線性估計來描述分組密碼的行為。線性分析可以看作是一種效率改進的新

6、型差分分析 (理論上需要大約 243 明-密文對) 。但是并沒有證據(jù)顯示其可以有效的在實際中攻擊DES。,3 DES,DES的密鑰通常寫為64比特，但每8比特有一位奇偶效驗位，可以忽略，因此，實際只有56比特。算法只使用不超過64位的標準算術(shù)操作和邏輯操作，所以在70年代僅使用硬件就可以容易地實現(xiàn)算法。算法的重復(fù)特性非常適合專用芯片執(zhí)行。起初采用軟件執(zhí)行的DES顯得笨拙，但目前的軟件執(zhí)行效果也相當不錯。,3.1 DES 算法描述,3.1

7、 DES 算法描述(續(xù)),3.2 初始計算,3.3 函數(shù) f(Ri-1， Ki),3.3 函數(shù) f(Ri-1，Ki) (續(xù)),3.3 函數(shù) f(Ri-1， Ki) (續(xù)),3.3 函數(shù) f(Ri-1， Ki) (續(xù)),3.4 密鑰變換,3.4 密鑰變換 (續(xù)),3.5 DES的安全,DES存在關(guān)于密鑰長度、疊代次數(shù)、S-盒設(shè)計準則的問題。特別是S-盒以常量形式給出，但并未明確說明這些常量為何以這種形式出現(xiàn)。雖然IBM聲稱這些是經(jīng)過17年

8、大量密碼分析得出的結(jié)果，但是人們還是十分擔心NSA的介入可能為算法安裝陷門以利于其解密。,3.5 DES的安全 (續(xù)) 在90年代初期，IBM 終于公開了S-盒設(shè)計的基本原理。 (1) 每個S-盒為6比特輸入和4比特輸出。這是1974年芯片處理數(shù)據(jù)的最大能力。 (2) S-盒的輸出不應(yīng)該和輸入接近線性的函數(shù)關(guān)系。 (3) S-盒的每一行都應(yīng)該包括全部0到15這16個數(shù)字。 (

9、4) 如果輸入每個S-盒的兩個數(shù)據(jù)有一位不相同，則輸出必須有至少兩位不同。,3.5 DES的安全 (續(xù)) (5) 如果兩個S-盒輸入的前兩位不同但最后兩位相同，則輸出必不相等。 (6) 對于每個給定的異或XOR值存在32種可能的輸入對。這些輸入對可以得到相應(yīng)異或XOR 輸出。所有這些輸出不得有8個的值完全相同。 這一原則顯然是用來阻止差分分析的。 (7) 這一原則與(6)類似，只是這里考慮3個S-盒的情況。

10、(詳細論述，參見 “D. Coppersmith, The data encryption standard and its strength against attacks"),4 DES 不是一個群,選擇兩個密K1和K2加密明文P得到EK2(EK1(P))。這樣的做法是否可以增加安全性？如果攻擊者有足夠的存儲空間，這樣做提供的安全保障有限。進一步，如果兩次加密等于單次加密，密碼的安全性將比我們想象的還要弱。例如，這一條件要

11、是對DES成立，那么窮盡搜索256的密鑰空間將被搜索大約228的密鑰空間所替代。,5 破譯DES,5.1 DES已顯老邁 (1) 1977年，Diffie和Hellman 估計如果花費2千萬美元制造一臺機器大約僅需一天就可以破譯DES。 (2) 1993年，Wiener利用開關(guān)技術(shù)設(shè)計了更加有效的破譯DES設(shè)備。 (3) 到1996年逐漸形成了三種破譯DES的基本方法。一種方法是利用分布計算。一種是

12、設(shè)計專用攻擊芯片。折中的方法是使用可編程邏輯門陣列。,5.1 DES已顯老邁(續(xù)) (4) 分布計算方法破譯DES變得十分流行，特別是在Internet興起和壯大的情況下。1997年，RSA數(shù)據(jù)安全公司開展了破譯DES密鑰和其加密消息的競賽。僅僅5個月，Rocke Verser 就在搜索了25% 的密鑰空間后發(fā)現(xiàn)密鑰。接下來，RSA 數(shù)據(jù)安全公司又開展了第二次競賽。結(jié)果用時39天搜索了密鑰空間的85%發(fā)現(xiàn)了對應(yīng)密鑰。,5.1 DE

13、S已顯老邁(續(xù)) (5) 1998年，電子領(lǐng)域基金會(EFF)展開了一項名為DES破譯的計劃。計劃的基本思想是：一般使用的計算機對于完成破譯DES的任務(wù)來說不是最優(yōu)的。計劃使用的結(jié)構(gòu)是硬件用來判定排除大量不可能的密鑰并返回那些可能的密鑰。軟件則用來處理每一個可能的密鑰，判定這些密鑰是否確實為密碼系統(tǒng)使用的密鑰。結(jié)果是計劃使用1500個芯片平均在大約4.5天可以完成對DES 的破譯。,5.1 DES已顯老邁(續(xù)) (6) 有傳

14、言說根據(jù)預(yù)先處理的不同，NSA可以在3到5分鐘成功破譯DES。而在機器方面的開銷僅有5萬美元。 #上述結(jié)果說明對于90年代晚期的計算技術(shù)而言，加密系統(tǒng)使用56比特的密鑰顯得過短，不能提供強有利的安全保護。,5.2 增加安全性的DES變化,5.2 增加安全性的DES變化 (續(xù)),6 口令安全,問題. 口令一般與每一個實體相關(guān)聯(lián)，是一個6到10或更多的方便記憶的字符串?？诹钣蓪嶓w和系統(tǒng)共享。為了獲得訪問系統(tǒng)資源的權(quán)限(例如，計算帳戶

15、，打印機，或軟件應(yīng)用)， 實體輸入身份-口令對。系統(tǒng)則核實對于相應(yīng)的身份和口令輸入是否正確。如果正確，系統(tǒng)就按照身份分配實體相應(yīng)的訪問授權(quán)。系統(tǒng)通過實體展示其掌握口令秘密來將其與聲稱身份掛鉤。,6.1 口令方案存儲口令文件加密口令文件,6.1 口令方案(續(xù)) (3) 降低口令映射速度 (4) 口令加鹽 為了使口令猜測攻擊無效，每一個口令條目都增加t比特的隨機串叫做鹽，將鹽和口令一同作為單向函數(shù)的輸入?？诹頗ash值

16、和鹽一同記入口令文件，以供驗證使用。 (5) 口令短語,6.2 常見攻擊 (1) 重放固定口令 (2) 窮盡搜索口令 攻擊的成功依賴于在成功發(fā)現(xiàn)口令之前需要驗證的口令數(shù)量以及每次驗證測試所需要的時間。 (3) 口令猜測或字典攻擊 在線/離線口令猜測攻擊,6.3 實例 – UNIX口令系統(tǒng),6.3 實例 – UNIX口令系統(tǒng)(續(xù)) (1) 口令鹽。UNIX口令鹽是將12位的

17、隨機串與用戶選擇口令關(guān)聯(lián)。這 12位的隨機串做為DES的標準擴展函數(shù)E的一個變量，提供4096種不同的變化情形，也就是鹽的第1比特對應(yīng)輸入的第1比特和第25比特，第2比特對應(yīng)輸入的第2比特和第26比特如此下去。如果鹽比特值為1，則輸入的相對應(yīng)位做交換，如果鹽比特值為0，則保持不變。Hash口令值和鹽都保存在系統(tǒng)口令文件的一條目錄之中。對于單個用戶而言，口令的安全并沒有增加，但對于字典攻擊整體口令文件而言，對于每一個可能口令卻增加了409