信息安全導(dǎo)論課程-ch03-對稱算法DES

密碼編碼學(xué)與網(wǎng)絡(luò)安全

電子工業(yè)出版社2006-20071第3章對稱算法DES3.1分組密碼算法原理 ↓3.2DES算法 ↓3.3DES強度 ↓3.4差分分析和線性分析 ↓3.5分組密碼設(shè)計原理 ↓* 3.ADESin/etc/passwd ↓* 3.BDESinOpenSSL ↓2密碼技術(shù)發(fā)展1918，WilliamF.Friedman，TheIndexofCoincidenceandItsApplicationsinCryptography1949，ClaudeShannon，TheCommunicationTheoryofSecrecySystems1967，DavidKahn，TheCodebreakers1970s，NBS/NIST，DES（90s,AES）1976，Diffie,Hellman，NewDirectoryinCryptography1984，C.H.Bennett，QuantumCryptography:PublicKeyDistributionandCoinTossing1985，N.Koblitz，EllipticCurveCryptosystem2000，AES33.1分組密碼算法原理分組密碼算法BlockCipher明文被分為固定長度的塊(即分組)，對每個分組用相同的算法和密鑰加解密分組一般為n＝64比特，或更長(Padding)密文分組和明文分組同樣長對某個密鑰可以構(gòu)造一個明密文對照表Codebook(SubstitutionTable)所以分組的長得至少64比特才好密鑰空間2^k<<可逆映射個數(shù)(2^n)!4序列密碼算法(流密碼算法)流密碼算法StreamCipher每次可以加密一個比特適合比如遠(yuǎn)程終端輸入等應(yīng)用流密碼可用偽隨機數(shù)發(fā)生器實現(xiàn)密鑰做為隨機數(shù)種子，產(chǎn)生密鑰流keystream(不重復(fù),或極大周期)XOR(plaintext，key-stream)One-timePad5比較基本區(qū)別粒度8字節(jié)分組vs.1比特或1字節(jié)各自適應(yīng)不同的應(yīng)用數(shù)據(jù)格式Padding對相同的明文分組，總是輸出相同的密文分組； 而流密碼卻輸出不同的密文比特流密碼一般快很多分組密碼多些，是主流分組密碼也可以用作流模式安全性對比6BlockCipherPrinciples00001110000101000010110100110001010000100101111101101011011110001000001110011010101001101011110011000101110110011110000011110111000011100001001100100100001110000100000101011100011010100111111110000111100111011010100110110110110010111101001011100000

乘積密碼：

重復(fù)使用代替和置換，實現(xiàn)混亂和擴散。7Feistel(DES)加密框架明文分組的長n＝2w分左右兩半L0R0密鑰K產(chǎn)生子鑰：K→k1，k2，…，kr

r是輪數(shù)，比如16輪⊕是異或函數(shù)XORp⊕x⊕x=p函數(shù)F是散列混亂函數(shù)可以是手工精心構(gòu)造的查表函數(shù)8 Feistel網(wǎng)絡(luò)9

Feistel解密10Feistel–‘for’Loop加密計算序列

L0＝左半 R0＝右半

L1＝R0 R1＝L0⊕F(k1,R0) L2＝R1 R2＝L1⊕F(k2,R1) L3＝R3 R3＝L2⊕F(k3,R2) … Li＝Ri-1 Ri＝Li-1⊕F(ki,Ri-1) … Ln＝Rn-1 Rn＝Ln-1⊕F(kn,Rn-1)

密文即（Ln，Rn）解密計算112輪解密舉例假設(shè)n＝2輪，C＝（L2，R2） 加密 明文＝半＋半＝L0+R0 L1＝R0 R1＝L0⊕F(k1,R0) L2＝R1 R2＝L1⊕F(k2,R1)解密 密文＝半＋半＝L2＋R2 R1＝L2 L1＝R2⊕F(k2,R1) R0＝L1 L0＝R1⊕F(k1,R0)

明文＝L0＋R0L1＝R2⊕F(k2,R1)＝L1⊕F(k2,R1)⊕F(k2,R1)＝L1L0＝R1⊕F(k1,R0)＝L0⊕F(k1,R0)⊕F(k1,R0)＝L012Feistel偽代碼明文m長度n＝2t，記為m0m1，每個長度為t密鑰k產(chǎn)生r個子密鑰k1,k2,...,kr加密E m：

fori=2tor+1do 0,1 mi＝mi-2XORf(mi-1,ki-1) i,i+1<-ki

得密文（mr，mr+1） r,r+1<-kr解密D fori=rto1do mi-1＝mi+1XORf(mi,ki)

或

fori=r-1to0do mi＝mi+2XORf(mi+1,ki+1)

＝miXORf(mi+1,ki+1)XORf(mi+1,ki+1)

＝mi唯一的非線性結(jié)構(gòu)就是F可以重復(fù)使用兩個變量即可13Feistel參數(shù)特性分組大小密鑰大小循環(huán)次數(shù)一般僅幾輪是不夠的，得十幾輪才好，如16輪子鑰產(chǎn)生算法越復(fù)雜越好輪函數(shù)Round關(guān)鍵其他考慮速度（尤其是軟件實現(xiàn)的速度）便于分析（使用簡潔的結(jié)構(gòu)）14Feistel類算法舉例DES、CAST、Blowfish/(Twofish?)、RC6(/5)不是Feistel結(jié)構(gòu)的AES、IDEA*絕大數(shù)分組密碼屬于或類似Feistel結(jié)構(gòu)多輪每輪有XOR（或能恢復(fù)的操作）輪函數(shù)153.2DESDataEncryptionStandard1971IBMHorstFeistel－Lucifer→DES，key由128bit→56bit1973NBS，77NISTFIPS-46－NBS/NIST、IBM、NSA1994最后一次延長到1999年－AES取代之參數(shù)Feistel體制分組密碼分組大小64bit，密鑰大小56bit，輪數(shù)16輪S-Boxes *16DES17密鑰置換選擇-1

KeyPermutedChoiceOne(PC-1)574941332517981585042342618161025951433527241911360524436326355473931231540762544638302248146615345372956211352820124647×8K的56比特重新排列，成為C0D0

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636418Keyi(48bit)C0D0

…C15D15

19PC-214171124153281562110231912426816727201324152313747553040514533484449395634534642503629328×6未入選的：9、18、22等每輪從56比特中選取48比特即為Ki，并同時左移Roundnumber123456789116Bitsrotated112222221222222120初始置換及逆置換InitialPermutation（IP/IP-1）5850423426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725初始明文按照IP重排；16輪后的密文按照IP-1重排即為最后密文oddeven21輪OneRound22擴展置換ExpansionPermutation3212345456789891011121312131415161716171819202120212223242524252627282928293031321Ri的32bit→48bit兩邊的是重復(fù)選中的6×823輪函數(shù)RoundFunction24S盒S-Boxes：1/4兩邊2比特選擇行號中間4比特選擇列號25S-Boxes：5-826從S盒出來后重排：PermutationFunction P8×4 167202129122817 11523265183110 282414322739 1913306221142527DESReview28 一個DES計算實例p=0123456789ABCDEFk=133457799BBCDFF1

……

c=85E813540F0AB40529使用OpenSSL庫的DES函數(shù)明文64bit “plaintxt”8字節(jié)Key56bit “password”取低7bits×8

手工運算

vs. voidDES_ecb_encrypt(const_DES_cblock*input, DES_cblock*output, DES_key_schedule*ks, intenc);密文8B 3297230f813edaaf303.3DES安全強度對DES的爭議集中在密鑰空間太小Keyspace從Lucifer的2^128降到DES的2^56DESChallengeIII,22hours15minutesS盒S-BoxesS盒的設(shè)計準(zhǔn)則？陷門？trapdoorsbyNSA(?) “Formsurprisetosuspicion”從驚喜(甚至能夠抵御很后來才發(fā)現(xiàn)的各種攻擊)到懷疑(n年前就如此厲害的NSA現(xiàn)在究竟有多厲害)31密鑰大小KeySize2^56≈7×10^161Mkeys/Secondmeans1000yearsSpecialmachinedesignedWienerCost/timetable >Recentnewsin1997onInternetinafewmonths(Rocke,96days)in1998ondedicatedh/winafewdays (DESII-2EFF,56hrs)in1999abovecombinedin22hrs15mins “DeepCrack”byEFF32窮舉(蠻力)攻擊Cost/Time表Keysearchmachineunit expectedsearchtime $100,000 35hours $1,000,000 3.5hours $10,000,000 21mins<EfficientDESKeySearch>wiener93efficient.pdfABruteForceSearchofDESKeyspace

按照NIST的提議，98年以后DES不應(yīng)繼續(xù)使用3DES、AES、RC5、IDEA等33“DeepCrack”HardwareCrackerDevelopedbythe ElectronicFrontierFoundationCostUS$210,000$80,000design$210,000materials(chips,boards,chassisetc)34VLSIChipDevelopedbyAdvanced WirelessTechnologies24searchunitsperchip40MHz16cyclesperencryption2.5millionkeys/sBoardcontains64chips6cabinetsholding29boards35DeepCrackSystem90billionkeys/s37,000searchunitsc.f.DistributedNet’s34billionkeys/sControlledbyPCcheckspossibleallASCIIcandidatesolutionsfromthesearchunitsSolvedRSA’sDES-IIIin22hoursJan18,199936蠻力攻擊對明文內(nèi)容的要求*問題：如何辨別出來？ 對給定的某個密文，任何一個密鑰都可以解密出一個可能的明文，但是其中應(yīng)該只有一個是正確的明文。 必須事先知道明文的結(jié)構(gòu)，比如已經(jīng)知道這是文字文本、源程序（圖像、聲音、壓縮的？）如果有兩個密鑰，解密出來的兩個明文都有意義？可能性極小因為密鑰空間2^k<<可逆映射個數(shù)(2^n)!Onetimepad就是讓對手分辨不出哪個更像正確明文37S盒特性SizeInputN×outputM8×32，butDES6×42^N→MbitsincontrasttoDES’s2^2×2^4→4NonlinearBentfunctionS-boxes’evolutionBlowfish,butDES’sisman-madeavoidanalyzeinadvance38Avalanche

EffectinDES(A)P1：00000…0(64bit)P2：10000…0(相差1bit)K：00000011001011 01001001100010 00111000011000 00111000110010(B)K1：…(56bit)K2：…(相差1bit)P：…(64bit)39DES弱密鑰DES弱密鑰：4(子密鑰相同)

0101010101010101 00000000000000

1F1F1F1FE0E0E0E0 eq 0000000FFFFFFF

E0E0E0E01F1F1F1F FFFFFFF0000000

FEFEFEFEFEFEFEFE FFFFFFFFFFFFFFDES半弱密鑰：12（兩個子密鑰，互為加解密）

01FE01FE01FE01FE FE01FE01FE01FE01

1FE01FE00EF10EF1 E01FE01FF10EF10E

01E001E001F101F1 vs E001E001F101F101

1FFE1FFE0EFE0EFE FE1FFE1FFE0EFE0E

011F011F010E010E 1F011F010E010E01

E0FEE0FEF1FEF1FE FEE0FEE0FEF1FEF1DES可能的弱密鑰：24（四個子密鑰）…403.4差分分析和線性分析蠻力攻擊計時攻擊差分分析線性分析正面分析密碼算法的新技術(shù)， 在很多算法上取得很好的效果41差分分析DifferentialCryptanalysisBiham,Shamir(‘S’)1991NSA,1974攻擊實例對8輪DES，只需微機幾分鐘對16輪DES，復(fù)雜度為2^47需這么多的選擇明文，使本方法只有理論意義DifferentialCryptanalysisoftheFull16-roundDES42線性分析LinearCryptanalysis對DES攻擊進展需要2^47個已知明文雖比選擇明文容易，但仍只具有理論意義LinearCryptanalysisRES/LINANA.HTMGoogle(“ATutorialonLinearandDifferentialCryptanalysis”)43DES其他DES肯定能破譯不單是RSAchallengeDES算法仍值得信賴但是關(guān)鍵場合不要用DES對一般個人用戶仍是安全的RSAchallenge反而給了信心DES還是AES，或者其他DES模塊仍廣泛存在，AES還沒有普及如果軟件實現(xiàn)，任何一個經(jīng)過考驗的算法都好DES/3DES、AES、RC4、RC5、IDEA、BlowfishFree/Open443.5分組密碼的設(shè)計原理DESDesignCriteria設(shè)計準(zhǔn)則asreportedbyCoppersmithin[COPP94]7criteriaforS-boxesprovidefornon-linearityresistancetodifferentialcryptanalysisgoodconfusion3criteriaforpermutationPprovideforincreaseddiffusion45分組密碼設(shè)計原理輪數(shù)輪函數(shù)FS盒雪崩效應(yīng)密鑰使用方法子鑰衍生方法雪崩效應(yīng)46輪函數(shù)F及S盒的設(shè)計輪函數(shù)F雪崩效應(yīng)準(zhǔn)則 strictavalanchecriterion獨立準(zhǔn)則 bitindependencecriterionS盒構(gòu)造方法隨機方法隨機加測試方法人工構(gòu)造方法數(shù)學(xué)構(gòu)造方法

47查閱和學(xué)習(xí)Google(“Engima興亡”)Google(“ENIGMA傳奇”)DESChallenge

D基于互聯(lián)網(wǎng)的分布式并行破譯項目483.ADESin/etc/passwdfile‘passwd’formatusername:passwd:UID:GID:full_name:directory:shell{FromShadow-Password-HOWTO}account:password:UID:GID:GECOS:directory:shell{FromRH8}shadow/etc/passwdpasswd--->*/etc/shadowpasswdusername:passwd:last:may:must:warn:expire:disable:reservedsampleusername:Npge08pfz4wuk:503:100:FN:/home/username:/bin/shusername:x:503:100:FN:/home/username:/bin/sh 1/2username:Npge08pfz4wuk:9479:0:10000:::: 2/249crypt()函數(shù)crypt#define_XOPEN_SOURCE#include<unistd.h> char*crypt(constchar*key,constchar*salt);passwdspace128-32-’7f’=95個可用字符95^nsalt兩個字符，每個可從[a-zA-Z0-9./]中選出來，即有4096種不同取值抵制字典攻擊中的預(yù)算值50crypt()描述從passwd到keypadding形成8字符的組每組產(chǎn)生56bits＝8×7的密鑰如果多于1組，則XOR累計重復(fù)加密64比特0到25回中間置換，受salt控制，計有4096種不同的置換輸出2＋11字符2字符是明碼salt11字符是編碼后的DES的64bits輸出密文51crypt()Fig52PasswdCracker基于字典的口令猜測攻擊字典的構(gòu)造普通字典×用戶相關(guān)的詞語JohntheRipperpasswordcracker

L0phtCrack

更多安全工具53Zipcrackersamp