第八講 數(shù)據(jù)加密標(biāo)準(zhǔn)（des）

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

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

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

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

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

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

7、 DES 算法描述(續(xù)),3.2 初始計(jì)算,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)于密鑰長(zhǎng)度、疊代次數(shù)、S-盒設(shè)計(jì)準(zhǔn)則的問(wèn)題。特別是S-盒以常量形式給出，但并未明確說(shuō)明這些常量為何以這種形式出現(xiàn)。雖然IBM聲稱這些是經(jīng)過(guò)17年

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

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

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

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

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

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

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

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

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

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