密码编码学与网络安全：原理与实践-第四版英文-Cryptography-and-Network-Se.ppt

《密码编码学与网络安全：原理与实践-第四版英文-Cryptography-and-Network-Se.ppt》由会员分享，可在线阅读，更多相关《密码编码学与网络安全：原理与实践-第四版英文-Cryptography-and-Network-Se.ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Cryptography and Network SecurityChapter 3Fifth Editionby William StallingsLecture slides by Lawrie BrownChapter 3 Block Ciphers and the Data Encryption StandardAll the afternoon Mungo had been working on All the afternoon Mungo had been working on Sterns code,principally with the aid of the latest

2、Sterns code,principally with the aid of the latest messages which he had copied down at the messages which he had copied down at the Nevin Square drop.Stern was very confident.Nevin Square drop.Stern was very confident.He must be well aware London Central knew He must be well aware London Central kn

3、ew about that drop.It was obvious that they didnt about that drop.It was obvious that they didnt care how often Mungo read their messages,so care how often Mungo read their messages,so confident were they in the impenetrability of the confident were they in the impenetrability of the code.code.Talki

4、ng to Strange Men,Talking to Strange Men,Ruth RendellRuth RendellModern Block Ciphersnow look at modern block ciphersone of the most widely used types of cryptographic algorithms provide secrecy/authentication servicesfocus on DES(Data Encryption Standard)to illustrate block cipher design principles

5、Block vs Stream Ciphersblock ciphers process messages in blocks,each of which is then en/decrypted like a substitution on very big charactersl l64-bits or more 64-bits or more stream ciphers process messages a bit or byte at a time when en/decryptingmany current ciphers are block ciphersl lbetter an

6、alysedbetter analysedl lbroader range of applicationsbroader range of applicationsBlock Cipher Principlesmost symmetric block ciphers are based on a most symmetric block ciphers are based on a Feistel Cipher StructureFeistel Cipher Structureneeded since must be able to needed since must be able to d

7、ecryptdecrypt ciphertext ciphertext to recover messages efficientlyto recover messages efficientlyblock ciphers look like an extremely large block ciphers look like an extremely large substitution substitution would need table of 2would need table of 26464 entries for a 64-bit block entries for a 64

8、-bit block instead create from smaller building blocks instead create from smaller building blocks using idea of a product cipher using idea of a product cipher Ideal Block CipherClaude Shannon and Substitution-Permutation CiphersClaude Shannon introduced idea of substitution-Claude Shannon introduc

9、ed idea of substitution-permutation(S-P)networks in 1949 paperpermutation(S-P)networks in 1949 paperform basis of modern block ciphers form basis of modern block ciphers S-P nets are based on the two primitive S-P nets are based on the two primitive cryptographic operations seen before:cryptographic

10、 operations seen before:l lsubstitutionsubstitution(S-box)(S-box)l lpermutation permutation(P-box)(P-box)provide provide confusionconfusion&diffusiondiffusion of message&key of message&keyFeistel Cipher StructureHorst Feistel devised the feistel cipherl lbased on concept of invertible product cipher

11、based on concept of invertible product cipherpartitions input block into two halvesl lprocess through multiple rounds whichprocess through multiple rounds whichl lperform a substitution on left data halfperform a substitution on left data halfl lbased on round function of right half&subkeybased on r

12、ound function of right half&subkeyl lthen have permutation s halvesthen have permutation s halvesimplements Shannons S-P net conceptFeistel Cipher StructureData Encryption Standard(DES)most widely used block cipher in world adopted in 1977 by NBS(now NIST)l las FIPS PUB 46as FIPS PUB 46encrypts 64-b

13、it data using 56-bit keyhas widespread usehas been considerable controversy over its securityDES Design Controversyalthough DES standard is publicwas considerable controversy over design l lin choice of 56-bit key(vs Lucifer 128-bit)in choice of 56-bit key(vs Lucifer 128-bit)l land because design cr

14、iteria were classified and because design criteria were classified subsequent events and public analysis show in fact design was appropriateuse of DES has flourishedl lespecially in financial applicationsespecially in financial applicationsl lstill standardised for legacy application usestill standa

15、rdised for legacy application useDES Encryption OverviewDES Round Structureuses two 32-bit L&R halvesas for any Feistel cipher can describe as:L Li i =R Ri i11R Ri i =L Li i11 F(F(R Ri i11,K Ki i)F takes 32-bit R half and 48-bit subkey:l lexpands R to 48-bits using perm Eexpands R to 48-bits using p

16、erm El ladds to subkey using XORadds to subkey using XORl lpasses through 8 S-boxes to get 32-bit resultpasses through 8 S-boxes to get 32-bit resultl lfinally permutes using 32-bit perm Pfinally permutes using 32-bit perm PDES Round StructureSubstitution Boxes Shave eight S-boxes which map 6 to 4 b

17、its each S-box is actually 4 little 4 bit boxes l louter bits 1&6(outer bits 1&6(rowrow bits)select one row of 4 bits)select one row of 4 l linner bits 2-5(inner bits 2-5(colcol bits)are substituted bits)are substituted l lresult is 8 lots of 4 bits,or 32 bitsresult is 8 lots of 4 bits,or 32 bitsrow

18、 selection depends on both data&keyl lfeature known as autoclaving(autokeying)feature known as autoclaving(autokeying)example:l lS(18 09 12 3d 11 17 38 39)=5fd25e03S(18 09 12 3d 11 17 38 39)=5fd25e03 DES Key Scheduleforms subkeys used in each roundl linitial permutation of the key(PC1)which initial

19、permutation of the key(PC1)which selects 56-bits in two 28-bit halves selects 56-bits in two 28-bit halves l l16 stages consisting of:16 stages consisting of:rotating rotating each halfeach half separately either 1 or 2 places separately either 1 or 2 places depending on the depending on the key rot

20、ation schedulekey rotation schedule K K selecting 24-bits from each half&permuting them selecting 24-bits from each half&permuting them by PC2 for use in round function F by PC2 for use in round function F note practical use issues in h/w vs s/wDES Decryptiondecrypt must unwind steps of data computa

21、tion decrypt must unwind steps of data computation with Feistel design,do encryption steps again with Feistel design,do encryption steps again using subkeys in reverse order(SK16 SK1)using subkeys in reverse order(SK16 SK1)l lIP undoes final FP step of encryption IP undoes final FP step of encryptio

22、n l l1st round with SK16 undoes 16th encrypt round1st round with SK16 undoes 16th encrypt roundl l.l l16th round with SK1 undoes 1st encrypt round 16th round with SK1 undoes 1st encrypt round l lthen final FP undoes initial encryption IP then final FP undoes initial encryption IP l lthus recovering

23、original data value thus recovering original data value Avalanche in DESAvalanche Effect key desirable property of encryption algwhere a change of one input or key bit results in changing approx half output bitsmaking attempts to“home-in”by guessing keys impossibleDES exhibits strong avalancheStreng

24、th of DES Key Size56-bit keys have 256=7.2 x 1016 valuesbrute force search looks hardrecent advances have shown is possiblel lin 1997 on Internet in a few months in 1997 on Internet in a few months l lin 1998 on dedicated h/w(EFF)in a few days in 1998 on dedicated h/w(EFF)in a few days l lin 1999 ab

25、ove combined in 22hrs!in 1999 above combined in 22hrs!still must be able to recognize plaintextmust now consider alternatives to DESStrength of DES Timing Attacksattacks actual implementation of cipheruse knowledge of consequences of implementation to derive information about some/all subkey bitsspe

26、cifically use fact that calculations can take varying times depending on the value of the inputs to itparticularly problematic on smartcards Differential Cryptanalysisone of the most significant recent(public)advances in cryptanalysis known by NSA in 70s cf DES designMurphy,Biham&Shamir published in

27、 90spowerful method to analyse block ciphers used to analyse most current block ciphers with varying degrees of successDES reasonably resistant to it,cf LuciferDifferential Cryptanalysis Compares Pairs of Encryptions with a known difference in the input searching for a known difference in outputwhen

28、 same subkeys are usedDifferential Cryptanalysishave some input difference giving some output difference with probability pif find instances of some higher probability input/output difference pairs occurringcan infer subkey that was used in roundthen must iterate process over many rounds(with decrea

29、sing probabilities)Differential CryptanalysisDifferential Cryptanalysisperform attack by repeatedly encrypting plaintext pairs perform attack by repeatedly encrypting plaintext pairs with known input XOR until obtain desired output XOR with known input XOR until obtain desired output XOR when foundw

30、hen foundl lif intermediate rounds match required XOR have a if intermediate rounds match required XOR have a right pairright pairl lif not then have a if not then have a wrong pairwrong pair,relative ratio is S/N for attack,relative ratio is S/N for attack can then deduce keys values for the rounds

31、can then deduce keys values for the roundsl lright pairs suggest same key bitsright pairs suggest same key bitsl lwrong pairs give random values wrong pairs give random values for large numbers of rounds,probability is so low that for large numbers of rounds,probability is so low that more pairs are

32、 required than exist with 64-bit inputs more pairs are required than exist with 64-bit inputs Biham and Shamir have shown how a 13-round iterated Biham and Shamir have shown how a 13-round iterated characteristic can break the full 16-round DES characteristic can break the full 16-round DES Linear C

33、ryptanalysisanother recent development also a statistical method must be iterated over rounds,with decreasing probabilitiesdeveloped by Matsui et al in early 90sbased on finding linear approximationscan attack DES with 243 known plaintexts,easier but still in practise infeasibleLinear Cryptanalysisf

34、ind linear approximations with prob p!=PiPi1 1,i,i2 2,.,i,.,ia a CjCj1 1,j,j2 2,.,j,.,jb b=KkKk1 1,k,k2 2,.,k,.,kc c where iwhere ia a,j,jb b,k,kc c are bit locations in P,C,K are bit locations in P,C,K gives linear equation for key bitsget one key bit using max likelihood algusing a large number of

35、 trial encryptions effectiveness given by:|p1/2 2|DES Design Criteriaas reported by Coppersmith in COPP947 criteria for S-boxes provide for l lnon-linearitynon-linearityl lresistance to differential cryptanalysisresistance to differential cryptanalysisl lgood confusiongood confusion3 criteria for pe

36、rmutation P provide for l lincreased diffusionincreased diffusionBlock Cipher Designbasic principles still like Feistels in 1970snumber of roundsl lmore is better,exhaustive search best attackmore is better,exhaustive search best attackfunction f:l lprovides“confusion”,is nonlinear,avalancheprovides

37、“confusion”,is nonlinear,avalanchel lhave issues of how S-boxes are selectedhave issues of how S-boxes are selectedkey schedulel lcomplex subkey creation,key avalanchecomplex subkey creation,key avalancheSummaryhave considered:l lblock vs stream ciphersblock vs stream ciphersl lFeistel cipher design&structureFeistel cipher design&structurel lDESDES detailsdetails strengthstrengthl lDifferential&Linear CryptanalysisDifferential&Linear Cryptanalysisl lblock cipher design principlesblock cipher design principles