Data encryption standard

Unit 2_Chapter 6

1. Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Chapter 6
Data Encryption Standard
(DES)

2. 6-1 INTRODUCTION
TheDataEncryptionStandard(DES)isasymmetric-
keyblockcipherpublishedbytheNationalInstituteof
StandardsandTechnology(NIST).
6.1.1History
6.1.2Overview
Topics discussed in this section:

3. In1973,NISTpublishedarequestforproposalsfora
nationalsymmetric-keycryptosystem.Aproposalfrom
IBM,amodificationofaprojectcalledLucifer,was
acceptedasDES.DESwaspublishedintheFederal
RegisterinMarch1975asadraftoftheFederal
InformationProcessingStandard(FIPS).
6.1.1 History

4. DESisablockcipher,asshowninFigure6.1.
6.1.2 Overview
Figure 6.1 Encryption and decryption with DES

5. 6-2 DES STRUCTURE
Theencryptionprocessismadeoftwopermutations
(P-boxes),whichwecallinitialandfinal
permutations,andsixteenFeistelrounds.
6.2.1Initial and Final Permutations
6.2.2Rounds
6.2.3Cipher and Reverse Cipher
6.2.4Examples
Topics discussed in this section:

6. 6-2 Continue
Figure 6.2 General structure of DES

7. 6.2.1 Initial and Final Permutations
Figure 6.3 Initial and final permutation steps in DES

8. 6.2.1Continue
Table 6.1 Initial and final permutation tables

9. Example 6.1
6.2.1Continued
Findtheoutputofthefinalpermutationboxwhentheinput
isgiveninhexadecimalas:
Onlybit25andbit63are1s;theotherbitsare0s.Inthefinal
permutation,bit25becomesbit64andbit63becomesbit15.
Theresultis
Solution

10. Example 6.2
6.2.1Continued
Provethattheinitialandfinalpermutationsaretheinverse
ofeachotherbyfindingtheoutputoftheinitialpermutation
iftheinputis
Theinputhasonlytwo1s;theoutputmustalsohaveonlytwo
1s.UsingTable6.1,wecanfindtheoutputrelatedtothese
twobits.Bit15intheinputbecomesbit63intheoutput.Bit
64intheinputbecomesbit25intheoutput.Sotheoutput
hasonlytwo1s,bit25andbit63.Theresultinhexadecimalis
Solution

11. 6.2.1Continued
The initial and final permutations are
straight P-boxes that are inverses
of each other.
They have no cryptography significance in
DES.
Note

12. DESuses16rounds.EachroundofDESisaFeistel
cipher.
6.2.2 Rounds
Figure 6.4
A round in DES
(encryption site)

13. TheheartofDESistheDESfunction.TheDESfunction
appliesa48-bitkeytotherightmost32bitstoproducea
32-bitoutput.
6.2.2Continued
DES Function
Figure 6.5
DES function

14. ExpansionP-box
SinceR
I−1isa32-bitinputandK
Iisa48-bitkey,wefirst
needtoexpandR
I−1to48bits.
6.2.2Continue
Figure 6.6 Expansion permutation

15. Althoughtherelationshipbetweentheinputandoutput
canbedefinedmathematically,DESusesTable6.2to
definethisP-box.
6.2.2Continue
Table 6.6 Expansion P-box table

16. Whitener(XOR)
Aftertheexpansionpermutation,DESusestheXOR
operationontheexpandedrightsectionandtheround
key.Notethatboththerightsectionandthekeyare48-
bitsinlength.Alsonotethattheroundkeyisusedonlyin
thisoperation.
6.2.2Continue

17. S-Boxes
TheS-boxesdotherealmixing(confusion).DESuses8
S-boxes,eachwitha6-bitinputanda4-bitoutput.See
Figure6.7.
6.2.2Continue
Figure 6.7 S-boxes

18. 6.2.2Continue
Figure 6.8 S-box rule

19. Table6.3showsthepermutationforS-box1.Fortherest
oftheboxesseethetextbook.
6.2.2Continue
Table 6.3 S-box 1

20. Example 6.3
6.2.2Continued
TheinputtoS-box1is100011.Whatistheoutput?
Ifwewritethefirstandthesixthbitstogether,weget11in
binary,whichis3indecimal.Theremainingbitsare0001in
binary,whichis1indecimal.Welookforthevalueinrow3,
column1,inTable6.3(S-box1).Theresultis12indecimal,
whichinbinaryis1100.Sotheinput100011yieldstheoutput
1100.
Solution

21. Example 6.4
6.2.2Continued
TheinputtoS-box8is000000.Whatistheoutput?
Ifwewritethefirstandthesixthbitstogether,weget00in
binary,whichis0indecimal.Theremainingbitsare0000in
binary,whichis0indecimal.Welookforthevalueinrow0,
column0,inTable6.10(S-box8).Theresultis13indecimal,
whichis1101inbinary.Sotheinput000000yieldstheoutput
1101.
Solution

22. StraightPermutation
6.2.2Continue
Table 6.11 Straight permutation table

23. Usingmixersandswappers,wecancreatethecipherand
reversecipher,eachhaving16rounds.
6.2.3 Cipher and Reverse Cipher
FirstApproach
Toachievethisgoal,oneapproachistomakethelast
round(round16)differentfromtheothers;ithasonlya
mixerandnoswapper.
In the first approach, there is no swapper in
the last round.
Note

24. 6.2.3Continued
Figure 6.9 DES cipher and reverse cipher for the first approach

25. AlternativeApproach
6.2.3Continued
Wecanmakeall16roundsthesamebyincludingone
swappertothe16throundandaddanextraswapperafter
that(twoswapperscanceltheeffectofeachother).
KeyGeneration
Theround-keygeneratorcreatessixteen48-bitkeysout
ofa56-bitcipherkey.

26. 6.2.3Continued
Figure 6.10
Key generation

27. 6.2.3Continued
Table 6.12 Parity-bit drop table
Table 6.13 Number of bits shifts

28. 6.2.3Continued
Table 6.14 Key-compression table

29. Example 6.5
6.2.4 Examples
Wechoosearandomplaintextblockandarandomkey,and
determinewhattheciphertextblockwouldbe(allin
hexadecimal):
Table 6.15 Trace of data for Example 6.5

30. Example 6.5
Table 6.15 Trace of data for Example 6.5 (Conintued
6.2.4Continued
Continued

31. Example 6.6
6.2.4Continued
LetusseehowBob,atthedestination,candecipherthe
ciphertextreceivedfromAliceusingthesamekey.Table6.16
showssomeinterestingpoints.

32. 6-3 DES ANALYSIS
CriticshaveusedastrongmagnifiertoanalyzeDES.
Testshavebeendonetomeasurethestrengthofsome
desiredpropertiesinablockcipher.
6.3.1Properties
6.3.2Design Criteria
6.3.3DES Weaknesses
Topics discussed in this section:

33. Twodesiredpropertiesofablockcipherarethe
avalancheeffectandthecompleteness.
6.3.1 Properties
Example 6.7
TochecktheavalancheeffectinDES,letusencrypttwo
plaintextblocks(withthesamekey)thatdifferonlyinonebit
andobservethedifferencesinthenumberofbitsineach
round.

34. Example 6.7
6.3.1Continued
Althoughthetwoplaintextblocksdifferonlyintherightmost
bit,theciphertextblocksdifferin29bits.Thismeansthat
changingapproximately1.5percentoftheplaintextcreatesa
changeofapproximately45percentintheciphertext.
Table 6.17 Number of bit differences for Example 6.7
Continued

35. 6.3.1Continued
Completenesseffect
Completenesseffectmeansthateachbitoftheciphertext
needstodependonmanybitsontheplaintext.

36. 6.3.2 Design Criteria
S-Boxe
Thedesignprovidesconfusionanddiffusionofbitsfrom
eachroundtothenext.
P-Boxes
Theyprovidediffusionofbits.
NumberofRounds
DESusessixteenroundsofFeistelciphers.theciphertext
isthoroughlyarandomfunctionofplaintextand
ciphertext.

37. Duringthelastfewyearscriticshavefoundsome
weaknessesinDES.
6.3.3 DES Weaknesses
WeaknessesinCipherDesign
1.WeaknessesinS-boxes
2.WeaknessesinP-boxes
3.WeaknessesinKey

38. Example 6.8
6.3.3Continued
LetustrythefirstweakkeyinTable6.18toencryptablock
twotimes.Aftertwoencryptions
withthesamekeytheoriginalplaintextblockiscreated.Note
thatwehaveusedtheencryptionalgorithmtwotimes,not
oneencryptionfollowedbyanotherdecryption.

39. 6.3.3Continued
Figure 6.11 Double encryption and decryption with a weak key

40. 6.3.3Continued

41. 6.3.3Continued

42. 6.3.3Continued
Figure 6.12 A pair of semi-weak keys in encryption and decryption

43. Example 6.9
6.3.3Continued
Whatistheprobabilityofrandomlyselectingaweak,asemi-
weak,orapossibleweakkey?
Solution
DEShasakeydomainof2
56
.Thetotalnumberoftheabove
keysare64(4+12+48).Theprobabilityofchoosingoneof
thesekeysis8.8×10
−16
,almostimpossible.

44. 6.3.3Continued

45. Example 6.10
6.3.3Continued
Letustesttheclaimaboutthecomplementkeys.Wehave
usedanarbitrarykeyandplaintexttofindthecorresponding
ciphertext.Ifwehavethekeycomplementandtheplaintext,
wecanobtainthecomplementofthepreviousciphertext
(Table6.20).

46. 6-4 Security of DES
DES,asthefirstimportantblockcipher,hasgone
throughmuchscrutiny.Amongtheattemptedattacks,
threeareofinterest:brute-force,differential
cryptanalysis,andlinearcryptanalysis.
6.4.1Brute-Force Attack
6.4.2Differential Cryptanalysis
6.4.3Linear Cryptanalysis
Topics discussed in this section:

47. Wehavediscussedtheweaknessofshortcipherkeyin
DES.Combiningthisweaknesswiththekeycomplement
weakness,itisclearthatDEScanbebrokenusing2
55
encryptions.
6.4.1 Brute-Force Attack

48. IthasbeenrevealedthatthedesignersofDESalready
knewaboutthistypeofattackanddesignedS-boxesand
chose16asthenumberofroundstomakeDES
specificallyresistanttothistypeofattack.
6.4.2 Differential Cryptanalysis

49. Linearcryptanalysisisnewerthandifferential
cryptanalysis.DESismorevulnerabletolinear
cryptanalysisthantodifferentialcryptanalysis.S-boxes
arenotveryresistanttolinearcryptanalysis.Ithasbeen
shownthatDEScanbebrokenusing2
43
pairsofknown
plaintexts.However,fromthepracticalpointofview,
findingsomanypairsisveryunlikely.
6.4.3 Linear Cryptanalysis