Data Encryption Standard (DES)

• Most widely used block cipher in world

• Adopted in 1977 by NBS (now NIST)
– as FIPS PUB 46
• Encrypts 64-bit data using 56-bit key
• It has widespread use
• It has been considerable controversy over its
security

1
 DES History
• IBM developed Lucifer cipher
– by team led by Feistel
– used 64-bit data blocks with 128-bit key
• Then redeveloped as a commercial cipher
with input from NSA and others
• In 1973 NBS issued request for proposals for a
national cipher standard
• IBM submitted their revised Lucifer which was
eventually accepted as the DES
2
 DES Design Controversy
• However, DES standard is public
• Considerable controversy over design
– in choice of 56-bit key (vs Lucifer 128-bit)
– and because design criteria were classified
• Subsequent events and public analysis show in
fact design was appropriate
• DES has become widely used, especially in
financial applications
3
DES Encryption

4
Initial Permutation (IP) and Inverse
Initial Permutation
• The initial permutation and its inverse are defined
by Tables.
• The tables are to be interpreted as follows:
– The input to a table consists of 64 bits numbered left to
right from 1 to 64
– The 64 entries in the permutation table contain a
permutation of the numbers from 1 to 64
• Each entry in the permutation table indicates the position
of a numbered input bit in the output
– which also consists of 64 bits

5
 64-bit input

Initial Permutation

Inverse Initial Permutation

6
 Single Round of DES Algorithm
• Internal structure of a single round is as

7
 Uses two 32-bit L & R halves. As for any Feistel cipher can describe as:
Li = Ri–1
Ri = Li–1  F(Ri–1, Ki)

Takes 32-
bit R half
Expands R
to 48-bits
using
permutation
E

XOR R and
Subkey Ki

Result
Passes Finally Permute
through 8 this using 32-bit
permutation P
S-boxes to
Produce
32 bit
output
Single Round of DES Algorithm

9
 Substitution Boxes (S-Boxes)
• Substitution consists of a
set of eight S-boxes
which accepts 6 bit input
and produces 4 bits
output.
• The transformations are
interpreted as:
– outer bits 1 & 6 (row bits)
select one rows
– inner bits 2-5 (column
bits) are substituted
– result is 8 lots of 4 bits, or
32 bits
• row selection depends on
both data & key

10
Definition of DES S Boxes

11
 DES Key Schedule
• Forms subkeys used in each round.
– 64-bit key is used as input to the algorithm,
though every eighth bit is ignored
– It is first processed by Permuted Choice 1
– The resulting 56-bit key is then treated as two 28-
bit quantities C & D

12
• In each round, these are separately
processed through a circular left shift
(rotation ) of 1 or 2 bits
• These shifted values serve as input to the
next round of the key schedule and
Permuted Choice 2, which produces a 48-
bit output that serves as input to the
round function F.

13
 DES Decryption
• As with any Feistel cipher, DES decryption uses the
same algorithm as encryption

• Except that the subkeys are used in reverse order SK16

.. SK1.
• If you trace through the DES overview diagram, you
can see how each decryption step top to bottom with
reversed subkeys.
• Undoes the equivalent encryption step moving from
bottom to top
14
 Avalanche Effect
• Key desirable property of encryption algorithm,
that is a small change in either the plaintext or
the key should produce a significant change in
the ciphertext.
• In particular, a change in one bit of the plaintext
or one bit of the key should produce a change in
many bits of the ciphertext. This is referred to as
the avalanche effect.
• DES exhibits strong avalanche.
15
 Strength of DES
• The concerns about the level of security
provided by DES falls into two areas:
– Key Size
– Nature of algorithm

16
Strength of DES: The Use of 56- bit
Keys
– 56-bit keys have 256 = 7.2 x 1016 keys
– So, brute force search looks hard: takes long time
– Recent advances have shown it is possible
• in 1997 on Internet in a few months
• in 1998 on dedicated machine DES cracker built by EFF in
a less than three days
• in 1999 above combined in 22hrs!
– still must be able to recognize plaintext if the text has
been compressed before then recognition is more
difficult.
– Now considering alternatives to DES such as AES.
17
Strength of DES: The Nature of DES
Algorithm
– More concern is that cryptanalysis is possible by
exploiting the characteristics of DES
– The focus of concern is the eight S-boxes used in
each iteration.
– As design criteria for S- boxes were not made
published there is a suspicion cryptanalysis is
possible for an opponent who knows weaknesses
of S-boxes.
– No one succeeded in discovering fatal weaknesses
in S- boxes.
18
 Strength of DES – Timing Attacks
– Attacks actual implementation of cipher
– Use knowledge of consequences of implementation
to derive knowledge of some/all subkey bits
– Specifically use fact that calculations can take
varying times depending on the value of the inputs
to it
– Particularly problematic on smartcards
– Though DES appears to be fairly resistant to a
successful timing attack.

19
 Block Cipher Design Principles
• basic principles still like Feistel in 1970’s
• number of rounds
– more is better, exhaustive search best attack
• function f:
– provides “confusion”, is nonlinear, avalanche
• key schedule
– complex subkey creation, key avalanche

20
 Modes of Operation
• block ciphers encrypt fixed size blocks
• e.g. DES encrypts 64-bit blocks, with 56-bit key
• need way to use in practice, given usually have
arbitrary amount of information to encrypt
• four were defined for DES in ANSI standard ANSI
X3.106-1983 Modes of Use
• subsequently now have 5 for DES and AES
• have block and stream modes

21
 Electronic Codebook Book (ECB)
• message is broken into independent blocks
which are encrypted
• each block is a value which is substituted, like
a codebook, hence name
• each block is encoded independently of the
other blocks
Ci = DESK1 (Pi)
• uses: secure transmission of single values

22
Electronic Codebook Book (ECB)

23
 Advantages and Limitations of ECB
• repetitions in message may show in ciphertext
– if aligned with message block
– particularly with data such as graphics
– or with messages that change very little, which
become a code-book analysis problem
• weakness due to encrypted message blocks
being independent
• main use is sending a few blocks of data

24
 Cipher Block Chaining (CBC)
• message is broken into blocks
• but these are linked together in the encryption
operation
• each previous cipher blocks is chained with
current plaintext block, hence name
• use Initial Vector (IV) to start process
Ci = DESK1(Pi XOR Ci-1)
C-1 = IV
• uses: bulk data encryption, authentication

25
Cipher Block Chaining (CBC)

26
 Advantages and Limitations of CBC
• each ciphertext block depends on all message blocks
• thus a change in the message affects all ciphertext blocks
after the change as well as the original block
• need Initial Value (IV) known to sender & receiver
– however if IV is sent in the clear, an attacker can change bits of the
first block, and change IV to compensate
– hence either IV must be a fixed value or it must be sent encrypted in
ECB mode before rest of message
• at end of message, handle possible last short block
– by padding either with known non-data value (eg nulls)
– or pad last block with count of pad size
• eg. [ b1 b2 b3 0 0 0 0 5] <- 3 data bytes, then 5 bytes pad+count

27
 Cipher FeedBack (CFB)
• message is treated as a stream of bits
• added to the output of the block cipher
• result is feed back for next stage (hence name)
• standard allows any number of bit (1,8 or 64 or
whatever) to be feed back
– denoted CFB-1, CFB-8, CFB-64 etc
• is most efficient to use all 64 bits (CFB-64)
Ci = Pi XOR DESK1(Ci-1)
C-1 = IV
• uses: stream data encryption, authentication
28
Cipher FeedBack (CFB)

29
 Advantages and Limitations of CFB
• appropriate when data arrives in bits/bytes
• most common stream mode
• limitation is need to stall while do block
encryption after every n-bits
• note that the block cipher is used in
encryption mode at both ends
• errors propagate for several blocks after the
error
30
 Output FeedBack (OFB)
• message is treated as a stream of bits
• output of cipher is added to message
• output is then feed back (hence name)
• feedback is independent of message
• can be computed in advance
Ci = Pi XOR Oi
Oi = DESK1(Oi-1)
O-1 = IV
• uses: stream encryption over noisy channels
31
Output FeedBack (OFB)

32
 Advantages and Limitations of OFB
• used when error feedback a problem or where need to
encryptions before message is available
• superficially similar to CFB
• but feedback is from the output of cipher and is independent
of message
• a variation of a Vernam cipher
– hence must never reuse the same sequence (key+IV)
• sender and receiver must remain in sync, and some recovery
method is needed to ensure this occurs
• originally specified with m-bit feedback in the standards
• subsequent research has shown that only OFB-64 should ever
be used
33
 Counter (CTR)
• a “new” mode, though proposed early on
• similar to OFB but encrypts counter value
rather than any feedback value
• must have a different key & counter value for
every plaintext block (never reused)
Ci = Pi XOR Oi
Oi = DESK1(i)
• uses: high-speed network encryptions
34
Counter (CTR)

35
 Advantages and Limitations of CTR
• efficiency
– can do parallel encryptions
– in advance of need
– good for bursty high speed links
• random access to encrypted data blocks
• provable security (good as other modes)
• but must ensure never reuse key/counter
values, otherwise could break (cf OFB)
36
 Summary
• have considered:
– block cipher design principles
– DES
• details
• strength
– Modes of Operation
• ECB, CBC, CFB, OFB, CTR

37