信息安全導論課程-ch03-對稱算法DES.ppt

密碼編碼學與網絡安全 電子工業(yè)出版社2006 2007 第3章對稱算法DES 3 1分組密碼算法原理 3 2DES算法 3 3DES強度 3 4差分分析和線性分析 3 5分組密碼設計原理 3 ADESin etc passwd 3 BDESinOpenSSL 密碼技術發(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 AES 3 1分組密碼算法原理 分組密碼算法BlockCipher明文被分為固定長度的塊 即分組 對每個分組用相同的算法和密鑰加解密分組一般為n 64比特 或更長 Padding 密文分組和明文分組同樣長對某個密鑰可以構造一個明密文對照表Codebook SubstitutionTable 所以分組的長得至少64比特才好密鑰空間2 k 可逆映射個數(shù) 2 n 序列密碼算法 流密碼算法 流密碼算法StreamCipher每次可以加密一個比特適合比如遠程終端輸入等應用流密碼可用偽隨機數(shù)發(fā)生器實現(xiàn)密鑰做為隨機數(shù)種子 產生密鑰流keystream 不重復 或極大周期 XOR plaintext key stream One timePad 比較 基本區(qū)別粒度8字節(jié)分組vs 1比特或1字節(jié)各自適應不同的應用數(shù)據格式Padding對相同的明文分組 總是輸出相同的密文分組 而流密碼卻輸出不同的密文比特流密碼一般快很多分組密碼多些 是主流分組密碼也可以用作流模式安全性對比 BlockCipherPrinciples 00001110000101000010110100110001010000100101111101101011011110001000001110011010101001101011110011000101110110011110000011110111000011100001001100100100001110000100000101011100011010100111111110000111100111011010100110110110110010111101001011100000 乘積密碼 重復使用代替和置換 實現(xiàn)混亂和擴散 Feistel DES 加密框架 明文分組的長n 2w分左右兩半L0R0密鑰K產生子鑰 K k1 k2 krr是輪數(shù) 比如16輪 是異或函數(shù)XORp x x p函數(shù)F是散列混亂函數(shù)可以是手工精心構造的查表函數(shù) Feistel網絡 Feistel解密 Feistel for Loop 加密計算序列L0 左半R0 右半L1 R0R1 L0 F k1 R0 L2 R1R2 L1 F k2 R1 L3 R3R3 L2 F k3 R2 Li Ri 1Ri Li 1 F ki Ri 1 Ln Rn 1Rn Ln 1 F kn Rn 1 密文即 Ln Rn 解密計算 2輪解密舉例 假設n 2輪 C L2 R2 加密明文 半 半 L0 R0L1 R0R1 L0 F k1 R0 L2 R1R2 L1 F k2 R1 解密密文 半 半 L2 R2R1 L2L1 R2 F k2 R1 R0 L1L0 R1 F k1 R0 明文 L0 R0 L1 R2 F k2 R1 L1 F k2 R1 F k2 R1 L1 L0 R1 F k1 R0 L0 F k1 R0 F k1 R0 L0 Feistel偽代碼 明文m長度n 2t 記為m0m1 每個長度為t密鑰k產生r個子密鑰k1 k2 kr加密Em fori 2tor 1do0 1mi mi 2XORf mi 1 ki 1 i i 1 ki得密文 mr mr 1 r r 1 kr解密Dfori rto1domi 1 mi 1XORf mi ki 或fori r 1to0domi mi 2XORf mi 1 ki 1 miXORf mi 1 ki 1 XORf mi 1 ki 1 mi 唯一的非線性結構就是F 可以重復使用兩個變量即可 Feistel參數(shù)特性 分組大小密鑰大小循環(huán)次數(shù)一般僅幾輪是不夠的 得十幾輪才好 如16輪子鑰產生算法越復雜越好輪函數(shù)Round關鍵其他考慮速度 尤其是軟件實現(xiàn)的速度 便于分析 使用簡潔的結構 Feistel類算法舉例 DES CAST Blowfish Twofish RC6 5 不是Feistel結構的AES IDEA 絕大數(shù)分組密碼屬于或類似Feistel結構多輪每輪有XOR 或能恢復的操作 輪函數(shù) 3 2DES DataEncryptionStandard1971IBMHorstFeistel Lucifer DES key由128bit 56bit1973NBS 77NISTFIPS 46 NBS NIST IBM NSA1994最后一次延長到1999年 AES取代之參數(shù)Feistel體制分組密碼分組大小64bit 密鑰大小56bit 輪數(shù)16輪S Boxes DES 密鑰置換選擇 1KeyPermutedChoiceOne PC 1 57494133251798158504234261816102595143352724191136052443632635547393123154076254463830224814661534537295621135282012464 7 8 K的56比特重新排列 成為C0D0 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364 Keyi 48bit C0D0 C15D15 PC 2 1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932 8 6未入選的 9 18 22等 每輪從56比特中選取48比特即為Ki 并同時左移 Roundnumber12345678910111213141516Bitsrotated1122222212222221 初始置換及逆置換 InitialPermutation IP IP 1 58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157 40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725 初始明文按照IP重排 16輪后的密文按照IP 1重排即為最后密文 odd even 輪OneRound 擴展置換ExpansionPermutation 3212345456789891011121312131415161716171819202120212223242524252627282928293031321 Ri的32bit 48bit兩邊的是重復選中的 6 8 輪函數(shù)RoundFunction S盒S Boxes 1 4 兩邊2比特選擇行號中間4比特選擇列號 S Boxes 5 8 從S盒出來后重排 PermutationFunction P8 41672021291228171152326518311028241432273919133062211425 DES Review 一個DES計算實例 p 0123456789ABCDEFk 133457799BBCDFF1 c 85E813540F0AB405 使用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 密文8B3297230f813edaaf 3 3DES安全強度 對DES的爭議集中在密鑰空間太小Keyspace從Lucifer的2 128降到DES的2 56DESChallengeIII 22hours15minutesS盒S BoxesS盒的設計準則 陷門 trapdoorsbyNSA Formsurprisetosuspicion 從驚喜 甚至能夠抵御很后來才發(fā)現(xiàn)的各種攻擊 到懷疑 n年前就如此厲害的NSA現(xiàn)在究竟有多厲害 密鑰大小KeySize 2 56 7 10 161Mkeys Secondmeans1000yearsSpecialmachinedesignedWienerhttp www3 sympatico ca wienerfamily Michael Cost timetable Recentnewsin1997onInternetinafewmonths Rocke 96days in1998ondedicatedh winafewdays DESII 2EFF 56hrs in1999abovecombinedin22hrs15mins DeepCrack byEFF 窮舉 蠻力 攻擊Cost Time表 Keysearchmachineunitexpectedsearchtime 100 00035hours 1 000 0003 5hours 10 000 00021minswiener93efficient pdfABruteForceSearchofDESKeyspace DeepCrack HardwareCracker DevelopedbytheElectronicFrontierFoundationCostUS 210 000 80 000design 210 000materials chips boards chassisetc VLSIChip DevelopedbyAdvancedWirelessTechnologies24searchunitsperchip40MHz16cyclesperencryption2 5millionkeys sBoardcontains64chips6cabinetsholding29boards DeepCrackSystem 90billionkeys s37 000searchunitsc f DistributedNet s34billionkeys sControlledbyPCcheckspossibleallASCIIcandidatesolutionsfromthesearchunitsSolvedRSA sDES IIIin22hoursJan18 1999 蠻力攻擊對明文內容的要求 問題 如何辨別出來 對給定的某個密文 任何一個密鑰都可以解密出一個可能的明文 但是其中應該只有一個是正確的明文 必須事先知道明文的結構 比如已經知道這是文字文本 源程序 圖像 聲音 壓縮的 如果有兩個密鑰 解密出來的兩個明文都有意義 可能性極小因為密鑰空間2 k 可逆映射個數(shù) 2 n Onetimepad就是讓對手分辨不出哪個更像正確明文 S盒特性 SizeInputN outputM8 32 butDES6 42 N MbitsincontrasttoDES s2 2 2 4 4NonlinearBentfunctionS boxes evolutionBlowfish butDES sisman madeavoidanalyzeinadvance AvalancheEffectinDES A P1 00000 0 64bit P2 10000 0 相差1bit K 00000011001011010010011000100011100001100000111000110010 B K1 56bit K2 相差1bit P 64bit DES弱密鑰 DES弱密鑰 4 子密鑰相同 0101010101010101000000000000001F1F1F1FE0E0E0E0eq0000000FFFFFFFE0E0E0E01F1F1F1FFFFFFFF0000000FEFEFEFEFEFEFEFEFFFFFFFFFFFFFFDES半弱密鑰 12 兩個子密鑰 互為加解密 01FE01FE01FE01FEFE01FE01FE01FE011FE01FE00EF10EF1E01FE01FF10EF10E01E001E001F101F1vsE001E001F101F1011FFE1FFE0EFE0EFEFE1FFE1FFE0EFE0E011F011F010E010E1F011F010E010E01E0FEE0FEF1FEF1FEFEE0FEE0FEF1FEF1DES可能的弱密鑰 24 四個子密鑰 3 4差分分析和線性分析 蠻力攻擊計時攻擊差分分析線性分析正面分析密碼算法的新技術 在很多算法上取得很好的效果 差分分析DifferentialCryptanalysis Biham Shamir S 1991NSA 1974攻擊實例對8輪DES 只需微機幾分鐘對16輪DES 復雜度為2 47需這么多的選擇明文 使本方法只有理論意義DifferentialCryptanalysisoftheFull16 roundDES 線性分析LinearCryptanalysis 對DES攻擊進展需要2 47個已知明文雖比選擇明文容易 但仍只具有理論意義LinearCryptanalysis DES其他 DES肯定能破譯不單是RSAchallengeDES算法仍值得信賴但是關鍵場合不要用DES對一般個人用戶仍是安全的RSAchallenge反而給了信心DES還是AES 或者其他DES模塊仍廣泛存在 AES還沒有普及如果軟件實現(xiàn) 任何一個經過考驗的算法都好DES 3DES AES RC4 RC5 IDEA BlowfishFree Open 3 5分組密碼的設計原理 DESDesignCriteria設計準則asreportedbyCoppersmithin COPP94 7criteriaforS boxesprovidefornon linearityresistancetodifferentialcryptanalysisgoodconfusion3criteriaforpermutationPprovideforincreaseddiffusion 分組密碼設計原理 輪數(shù)輪函數(shù)FS盒雪崩效應密鑰使用方法子鑰衍生方法雪崩效應 輪函數(shù)F及S盒的設計 輪函數(shù)F雪崩效應準則strictavalanchecriterion獨立準則bitindependencecriterionS盒構造方法隨機方法隨機加測試方法人工構造方法數(shù)學構造方法 查閱和學習 Google Engima興亡 Google ENIGMA傳奇 DESChallenge 3 ADESin etc passwd file 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 sh1 2username Npge08pfz4wuk 9479 0 10000 2 2 crypt 函數(shù) crypt define XOPEN SOURCE includechar crypt constchar key constchar salt passwdspace128 32 7f 95個可用字符95 nsalt兩個字符 每個可從 a zA Z0 9 中選出來 即有4096種不同取值抵制字典攻擊中的預算值 crypt 描述 從passwd到keypadding形成8字符的組每組產生56bits 8 7的密鑰如果多于1組 則XOR累計重復加密64比特0到25回中間置換 受salt控制 計有4096種不同的置換輸出2 11字符2字符是明碼salt11字符是編碼后的DES的64bits輸出密文 crypt Fig PasswdCracker 基于字典的口令猜測攻擊字典的構造普通字典 用戶相關的詞語JohntheRipperpasswordcracker Zipcrackersample AdvancedZIPPasswordRecoverystatistics EncryptedZIP file sdjfks zipTotalpasswords 2 091 362 752Totaltim