Multiple
Encryption
and Triple
DES
Multiple Encryption
DES uses 56 bit key
DES is vulnerable to brute-force
attack
Multiple encryption uses multiple
stages of DES
Existing investment in software
and equipment for DES are utilized
Double DES
56 bits 56 bits
64 bits 64 bits
K1 K2
64 bits X C
E E C = E(K2,E(K1,P))
P
K2 K1
X P
D D
C
C = E(K2,E(K1,P)), P = D((K1,D(K2,C))
Key length 56 x 2 = 112 bits
Double DES
56 bits 56 bits
K1 K2
64 bits X C 64 bits
E E C = E(K2,E(K1,P))
P
K2 K1
X P
D D P = D((K1,D(K2,C))
C
C = E(K2,E(K1,P)), P = D((K1,D(K2,C))
Key length 56 x 2 = 112 bits
Double DES
56 bits 56 bits
K1 K2 64 bits
64 bits X C
E E C = E(K2,E(K1,P))
P
K2 K1
X
P
C D D P = D((K1,D(K2,C))
Key length 56 x 2 = 112 bits
Therefore 2-DES is better than DES
However, 2-DES is not secure
Meet-in-the-middle attack for 2-DES
56 bits 56 bits
K1 K2
64 bits X 64 bits
C
E E
P
Given known pair(P,C)
Using P, try 256 possible keys for K1 to
generate 256 values X
Probable values for man-in-
the-middle-attack
X=E(P, K1) X=D(C, K2)
K1 (56 bits) X (64 bits) K2 (56 bits) X (64 bits)
000 111011..01 000 100001..01
001 100101.00 001 111101.00
: : : :
11.0 111101.00 11.0 100000.11
11.1 010111.10 11.1 111111.00
Meet-in-the-middle attack for 2-DES
56 bits 56 bits
K1 K2
X 64 bits
64 bits C
E E
P
Given known pair(P,C)
Using P, try 256 possible keys to generate 256
values X
Using C, try 256 possible keys to generate 256
values of X
Probable values for man-in-
the-middle-attack
X=E(P, K1) X=D(C, K2)
K1 (56 bits) X (64 bits) K2 (56 bits) X (64 bits)
000 111011..01 000 100001..01
001 100101.00 001 111101.00
: : : :
11.0 111101.00 11.0 100000.11
11.1 010111.10 11.1 111111.00
Probable values for meet-
in-the-middle-attack
X=E(P, K1) X=D(C, K2)
K1 (56 bits) X (64 bits) K2 (56 bits) X (64 bits)
000 111011..01 000 100001..01
001 100101.00 001 111101.00
: : : :
11.0 111101.00 11.0 100000.11
11.1 010111.10 11.1 111111.00
Using candidate keys and another P,C pair to verify
candidate keys
repeat the above
Meet-in-the-middle attack for 2 DES
56 bits 56 bits
K1 K2
X 64 bits
64 bits C
E E
P
K2 K1
X P
D D
C
There are 264 possibilities of ciphertext-
plaintext pairs
2112 possibilities of key
2112 /264=248 false combinations of keys
Triple-DES with Two-Keys
K1 K2 K1
64 bits A B C 64 bits
E D E
P
K1 K2 K1
B P
A
D E D
C
Uses 3 stages of encryptions
Can use 2 keys with E-D-E sequence
C = E(K1, (D(K2 ,(E(K1,P)))))
P = D(K1, (E(K2 ,(D(K1,C)))))
Triple-DES with Two-Keys
K1 K2 K1
64 bits A C 64 bits
B
E D E
P
K1 K2 K1
B P
A
D E D
C
Uses 3 stages of encryptions
Can use 2 keys with E-D-E sequence
C = E(K1, (D(K2 ,(E(K1,P)))))
P = D(K1, (E(K2 ,(D(K1,C)))))
Triple-DES with Two-Keys
K1 K2 K1 64 bits
64 bits A C
B
E D E
P
K1 K2 K1
B P
A
D E D
C
Uses 3 stages of encryptions
Can use 2 keys with E-D-E sequence
C = E(K1, (D(K2 ,(E(K1,P)))))
P = D(K1, (E(K2 ,(D(K1,C)))))
Triple-DES with Two-Keys
K1 K2 K1
64 bits A B C 64 bits
E D E
P
K1 K2 K1
B P
A
D E D
C
Triple-DES with two keys is a popular alternative
to single-DES
3 times slower to run
The use of encryption & decryption stages are
equivalent
Adopted for use in the key management
standards ANS X9.17 and ISO 8732.
Triple-DES with Two-Keys
K1 K2 K1
64 bits C 64 bits
A B
E D E
P
K1 K2 K1
B P
A
D E D
C
Currently,there are no practical cryptanalytic
attacks on 3DES.
Cost of a brute-force key search on 3DES is on
the order of 2^112 (=5*10^33)
Security attack for 3 DES
i j i
a Bj C
E D E
P
Pi=D(i,a), Bj=D(j,a) B=D(i,C)
Security attack for 3 DES (known plaintext)
i j i
a Bj C
E D E
P
Pi=D(i,a), Bj=D(j,a) B=D(i,C)
Known n pairs of P-C
Pi (64 bits) Ci (64 bits) Known n pairs of P-C
000 11..01 Assume a value for a
For each of the 256 possible keys, i
001 01.00
Pi=D(i,a)
: :
11.0 01.00
11.1 11.10
Security attack for 3 DES (known plaintext)
i j i
a Bj C
E D E
P
Pi=D(i,a), Bj=D(j,a) B=D(i,C)
Known n pairs of P-C
Pi (64 bits) Ci (64 bits) Bj (64 bits) Key,i (56 bits)
000 11..01 000 11..01
001 01.00 001 01.00
: : : :
11.0 01.00 11.0 01.00
11.1 11.10 11.1 11.10
For each of the 256 possible keys, j calculate
Bj=D(j,a)
For each Pi, determine i and B to match Ci
Security attack for 3 DES (known plaintext)
i j i
a Bj C
E D E
P
Pi=D(i,a), Bj=D(j,a) B=D(i,C)
Known n pairs of P-C
Pi (64 bits) Ci (64 bits) Bj (64 bits) Key,i (56 bits)
000 11..01 000 11..01
001 01.00 001 01.00
: : : :
11.0 01.00 11.0 01.00
11.1 11.10 11.1 11.10
IfBj matches with B then candidate keys are i and j
Test each i and j for other P,C pairs.
If it does not work then try a new value of a
Triple-DES with Two-Keys
Standardized in ANSI X9.17 & ISO 8732
No current known practical attacks
Triple-DES with Three Keys
K1 K2 K3
X Y C
E E E
P
K3 K2 K1
Y P
X
D D D
C
Better than 3-DES with 2 keys
Internet based applications like PGP and
S/MIME have adopted 3DES
Block vs Stream Ciphers
Block vs Stream Ciphers
Modes of Operation
To encrypt a stream of plaintext
characters five modes are available
1. Electronic code book
2. Cipher block chaining
3. Cipher feedback
4. Output feedback
5. counter
Modes of Operation
To encrypt a stream of plaintext
characters five modes are available
1. Electronic code book
2. Cipher block chaining
3. Cipher feedback
4. Output feedback
5. counter
Electronic Code Book(ECB)
(ECB)
Electronic Code Book(ECB)
(ECB)
Electronic Code Book(ECB)
Message is broken into fixed length
blocks of b bits
Generally b=64 bits
If last block has less than b bits then it is
appended with fillers
Each block uses the same key
Electronic Code Book(ECB)
For a given key, there is a unique
ciphertext for each b-bit block of plaintext
There are 2b ciphertexts for each of 2k keys
Codebook contains 2bk entries
For DES, size of codebook = 2b x 2k = 264+56
ECB is used for secure transmission of single
values
Advantages and Limitations of ECB
Ifmessage has repeated blocks then
ciphertext shows the repetition because
key is same for each message
Encryption is independent for each block
Therefore Ideal for a few blocks of data
Useful for secure transmission of encryption
key
Modes of Operation
To encrypt a stream of plaintext
characters five modes are available
1. Electronic code book
2. Cipher block chaining
3. Cipher feedback
4. Output feedback
5. counter
Cipher Block Chaining (CBC)
Overcomes security deficiencies of ECB
Generates different ciphertext for same plaintext
Each previous cipher blocks is chained with current
plaintext block
CBC
Use Initial Vector (IV) to start process
C-1 = IV, C1 = E(K, P1 XOR IV)
Initial Vector
o Known to sender and receiver
o Must be unpredictable and random
o Must be protected from unauthorized user
o Use secure transmission like ECB to send IV to
receiver
CBC
C2 = E(K, P2 XOR C1)
CBC
CN = E(K, PN XOR CN-1)
CBC
Used for bulk
data encryption
and
authentication
Advantages and Limitations of CBC
Repetition of ciphertext is avoided
A ciphertext block depends on all cipher blocks
before it
Need Initialization Vector (IV)
which must be known to sender & receiver
if not secured then attacker can change bits of first
block, and change IV to compensate
Must be sent encrypted in ECB mode before rest of
message
Message Padding for ECB
and CBC
Sometimes last block of message less than b bits
append either with known non-data value (eg
nulls)
or append last block with number of bytes
required to append
eg. [ b1 b2 b3 0 0 0 0 5] has 3 data bytes and
additional bytes for [0 0 0 0 5]
Modes of Operation
To encrypt a stream of plaintext
characters five modes are available
1. Electronic code book
2. Cipher block chaining
3. Cipher feedback
4. Output feedback
5. counter
Stream Modes of Operation
block modes encrypt entire block
may need to operate on smaller units for real time
data
Stream cipher encrypts each character and
transmits cipher character immediately
Types of stream cipher
cipher feedback (CFB) mode
output feedback (OFB) mode
counter (CTR) mode
Modes of Operation
To encrypt a stream of plaintext
characters five modes are available
1. Electronic code book
2. Cipher block chaining
3. Cipher feedback
4. Output feedback
5. counter
Cipher Feedback (CFB)
C1 = P1 XOR E(K, IV)
Message is divided into segment of s bits
CFB
C1 = P1 XOR E(K, IV) C2 = P2 XOR E(K, C1)
Message is divided into segment of s bits
Like CBC, blocks of plaintext are chained together
Feed back is used for the next stage (hence name)
CFB
C1 = P1 XOR E(K, IV) C2 = P2 XOR E(K, C1) CN = PN XOR E(K, CN-1)
CFB
CFB
CFB
Allows any number of bits (1, 8, 64 or 128 ) for the
feed back
Denoted by CFB-1, CFB-8, CFB-64, CFB-128
uses: stream data encryption, authentication
Advantages and Limitations of
CFB
Appropriate when data arrives in bits/bytes
errors propagate for several blocks after the
erroneous block
Modes of Operation
To encrypt a stream of plaintext
characters five modes are available
1. Electronic code book
2. Cipher block chaining
3. Cipher feedback
4. Output feedback
5. counter
Output Feedback (OFB)
Like
CFB, message is treated as a stream of bits
Output is then feed back (hence name)
OFB
Nonce is a
data block
which is
unique to
each
execution
of
encryption
Eg.
Counter,
message
number,
time,
random
number
OFB
O-1 = nonce
Oi = E(K, Oi-1)
Ci = Pi XOR Oi
Uses: stream encryption on noisy channels
OFB
C1 = P1 XOR E(K, N)
C1 XOR E(K, N) = P1 XOR E(K, N) XOR E(K,N) = P1
OFB
Advantages and Limitations of OFB
Needs nonce which is unique for each use
Encryption is done on nonce not plaintext
Bit errors do not propagate
Modes of Operation
To encrypt a stream of plaintext
characters five modes are available
1. Electronic code book
2. Cipher block chaining
3. Cipher feedback
4. Output feedback
5. counter
Counter (CTR)
Similarto OFB
Encrypts counter value rather than any
feedback value
Must have a different key & counter value
for every plaintext block
Chaining is not used
uses: high-speed network encryptions
CTR
CTR
CTR
Advantages and Limitations of CTR
can do parallel encryptions in h/w or s/w
good for bursty high speed links
random access to encrypted data blocks
security is equivalent to other modes
key/counter values should not repeat
Does not require decryption
stream ciphers process messages a bit or byte at a
time for en/decryption
E.g. Vigenere and vernam ciphers
One-time-key pad is commonly used to make it
unbreakable
block ciphers en/decrypts one block at a time
Plaintext is divided into blocks
Block size 64 or 128 bits
Block vs Stream Ciphers