Conventional(symmetric) Encryption Principles

• An encryption scheme has five ingredients:

– Plaintext
– Encryption algorithm
– Secret Key
– Cipher text
– Decryption algorithm
• Security depends on the secrecy of the key,
not the secrecy of the algorithm.
Conventional(symmetric) Encryption Principles
 The 3 CRYPTs
• Cryptology= Cryptography + Cryptanalysis

• Cryptography= Deals with design of algorithms for encryption

and decryption, intended to ensure the secrecy and/or
authenticity of messages.

• Cryptanalysis= Deals with breaking of a cipher (algorithm) to

recover information, or forging encrypted information that
will be accepted as authentic.
 Cryptography
• Classified along three independent
dimensions:
1. The type of operations used for transforming
plaintext to cipher text
2. The number of keys used
a) symmetric (single key, secret key ,or conventional
encryption)
b) asymmetric (two-keys, or public-key encryption)
3. The way in which the plaintext is processed. A
block cipher processes the input one block of
elements at a time, producing an o/p block for
each i/p block. A stream cipher processes the i/p
elements continuously, producing o/p one element
at a time ,as it goes along.
German Lorenz cipher machine,

used in World War II to encrypt

very-high-level general staff

messages
 Cryptanalysis
• The process of attempting to discover the
plaintext or key is known as cryptanalysis.
• The strategy used by the cryptanalyst depends
on nature of the encryption scheme and the
information available to the cryptanalyst.
Average time required for exhaustive
key search

Key Size Number of Time required at

(bits) Alternative Keys 106 Decryption/µs
32 232 = 4.3 x 109 2.15 milliseconds
56 256 = 7.2 x 1016 10 hours
128 2128 = 3.4 x 1038 5.4 x 1018 years
168 2168 = 3.7 x 1050 5.9 x 1030 years
 Feistel Cipher Structure
• Virtually all conventional block
encryption algorithms, including DES
have a structure first described by
Horst Feistel of IBM in 1973
• The realization of a Fesitel Network
depends on the choice of the following
parameters and design features (see
next slide):
 Feistel Cipher Structure

• Block size: larger block sizes mean greater

security
• Key Size: larger key size means greater
security
• Number of rounds: multiple rounds offer
increasing security
• Subkey generation algorithm: greater
complexity will lead to greater difficulty of
cryptanalysis.
• Fast software encryption/decryption: the
speed of execution of the algorithm
becomes a concern
Simplified DES(S-DES)
Conventional Encryption Algorithms

• Data Encryption Standard (DES)

– The most widely used encryption scheme
– The algorithm is reffered to the Data
Encryption Algorithm (DEA)
– DES is a block cipher
– The plaintext is processed in 64-bit
blocks
– The key is 56-bits in length
DES Encryption Overview
 DES Round Structure
• 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)
• F takes 32-bit R half and 48-bit subkey:
– expands R to 48-bits using perm E
– adds to subkey using XOR
– passes through 8 S-boxes to get 32-bit result
– finally permutes using 32-bit perm P
 Encryption (IP, IP-1)
• IP ■ IP-1

Bit 0 1 2 3 4 5 6 7 Bit 0 1 2 3 4 5 6 7
1 58 50 42 34 26 18 10 2 1 40 8 48 16 56 24 64 32
9 60 52 44 36 28 20 12 4 9 39 7 47 15 55 23 63 31
17 62 54 46 38 30 22 14 6 17 38 6 46 14 54 22 62 30
25 64 56 48 40 32 24 16 8 25 37 5 45 13 53 21 61 29
33 57 49 41 33 25 17 9 1 33 36 4 44 12 52 20 60 28
41 59 51 43 35 27 19 11 3 41 35 3 43 11 51 19 59 27
49 61 53 45 37 29 21 13 5 49 34 2 42 10 50 18 58 26
57 63 55 47 39 31 23 15 7 57 33 1 41 9 49 17 57 25

■ Note: IP(IP-1) = IP-1(IP) = I

 Expansion /Permutation box

Since right input is 32-bit and round key is a 48-bit, we first need to
expand right input to 48 bits.
Permutation logic is graphically depicted in the following illustration −
The graphically depicted permutation logic is generally described as table in DES specification illustrated as shown −
 Encryption (Round) (cont.)
■ E ■ P

32 1 2 3 4 5 16 7 20 21 29 12 28 17
4 5 6 7 8 9
1 15 23 26 5 18 31 10
8 9 10 11 12 13
2 8 24 14 32 27 3 9
12 13 14 45 16 17
16 17 18 19 20 21 9 13 30 6 22 11 4 25
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1

Expansion Expansion
 Encryption (Round) (cont.)

■ S-box

[1

]
 DES Key Schedule
• forms subkeys used in each round
– initial permutation of the key (PC1) which selects
56-bits in two 28-bit halves
– 16 stages consisting of:
• rotating each half separately either 1 or 2 places
depending on the key rotation schedule K
• selecting 24-bits from each half & permuting them by
PC2 for use in round function F
• Concerns about:
– The algorithm and the key length (56-bits)
 DES Analysis

The DES satisfies both the desired properties of block cipher. These two properties
make cipher very strong.
• Avalanche effect − A small change in plaintext results in the very grate change in
the ciphertext.
• Completeness − Each bit of ciphertext depends on many bits of plaintext.

During the last few years, cryptanalysis have found some weaknesses in DES when key
selected are weak keys. These keys shall be avoided.
DES has proved to be a very well designed block cipher. There have been no significant
cryptanalytic attacks on DES other than exhaustive key search.
Time to break a code (106
decryptions/µs)
 Double DES and Triple DES

Double DES

(or)

Double DEA

Triple DES

(or)

Triple DEA

With two
 Triple DEA
with 3 keys

• Use three keys and three executions of

the DES algorithm (encrypt-decrypt-
encrypt)

• C = ciphertext
C = EK3[DK2[EK1[P]]]
• P = Plaintext
• EK[X] = encryption of X using key K
• DK[Y] = decryption of Y using key K

• Effective key length of 168 bits

Triple DEA
 Advanced Encryption Standard (AES) Origins

⮚ clear a replacement for DES was needed

● have theoretical attacks that can break it

● have demonstrated exhaustive key search attacks

⮚ can use Triple-DES – but slow, has small blocks

⮚ US NIST issued call for ciphers in 1997

⮚ 15 candidates accepted in Jun 98
⮚ 5 were shortlisted in Aug-99
⮚ Rijndael was selected as the AES in Oct-2000
⮚ issued as FIPS PUB 197 standard in Nov-2001
 The AES Cipher - Rijndael

⮚ designed by Rijmen-Daemen in Belgium

⮚ Key: 128/192/256 bit keys,
⮚ Plaintext: 128 bit data

⮚ an iterative rather than Feistel cipher

● processes data as block of 4 columns of 4 bytes
● operates on entire data block in every round

⮚ designed to have:
● resistance against known attacks
● speed and code compactness on many CPUs
 AES Structure

⮚ data block of 4 columns of 4 bytes is state

⮚ key is expanded to array of words

⮚ has 9/11/13 rounds in which state undergoes:

1. byte substitution (1 S-box used on every byte)
2. shift rows (permute bytes between groups/columns)
3. mix columns (subs using matrix multiply of groups)
4. add round key (XOR state with key material)
• view as alternating XOR key & scramble data bytes
AES Encryption

Process
 AES

Structure
 Some Comments on AES

1. an iterative rather than Feistel cipher

2. key expanded into array of 32-bit words
1. four words form round key in each round
3. 4 different stages are used as shown
4. has a simple structure
5. only AddRoundKey uses key
6. AddRoundKey a form of Vernam cipher
7. each stage is easily reversible
8. decryption uses keys in reverse order
9. decryption does recover plaintext
10. final round has only 3 stages
 Substitute Bytes

⮚ a simple substitution of each byte

⮚ uses one table of 16x16 bytes containing a permutation of all 256 8-bit values

⮚ each byte of state is replaced by byte indexed by row (left 4-bits) & column (right 4-
bits)

● eg. byte {95} is replaced by byte in row 9 column 5

● which has value {2A}

⮚ S-box constructed using defined transformation of values

⮚ designed to be resistant to all known attacks

 Substitute Bytes

Substitute Bytes

Example
 Shift Rows

⮚ a circular byte shift in each each

● 1st row is unchanged
● 2nd row does 1 byte circular shift to left
● 3rd row does 2 byte circular shift to left
● 4th row does 3 byte circular shift to left
⮚ decrypt inverts using shifts to right
⮚ since state is processed by columns, this step permutes bytes between
the columns
Shift Rows
 Mix Columns
⮚ each column is processed separately
⮚ each byte is replaced by a value dependent on all 4 bytes in the column
Mix Columns Example
 Add Round Key
⮚ XOR state with 128-bits of the round key
⮚ again processed by column (though effectively a series of byte operations)
⮚ inverse for decryption identical
● since XOR own inverse, with reversed keys

⮚ designed to be as simple as possible

● a form of Vernam cipher on expanded key

● requires other stages for complexity / security

 AES Round

(state formed by column-

wise placing of elements )
 AES Key Expansion
⮚ takes 128-bit (16-byte) key and
expands into array of 44/52/60 32-
bit words
1. start by copying key into first 4
words
2. then loop creating words that
depend on values in previous & 4
places back
✔ in 3 of 4 cases just XOR these together

✔ 1st word in 4 has rotate + S-box + XOR

round constant on previous, before XOR

4th back

wi=wi-1 xor wi-4 | if i≠ multiple of 4

g = S-Box (LCS(w3)) xor RoundConstanti

 Key Expansion Rationale

⮚ designed to resist known attacks

⮚ design criteria included
● knowing part key insufficient to find many more
● invertible transformation
● fast on wide range of CPU’s
● use round constants to break symmetry
● diffuse key bits into round keys
● enough non-linearity to hinder analysis
● simplicity of description
Other Symmetric Block Ciphers
• International Data Encryption
Algorithm (IDEA)
– 128-bit key
– Used in PGP
• Blowfish (A variant of DES with S-Box having values
that are both random and key dependant)
– Easy to implement
– High execution speed
– Run in less than 5K of memory
 Other Symmetric Block Ciphers
• RC5
– Variable number of rounds
– Data-dependent rotations
– Variable-length key
– Suitable for hardware and software
– Fast, simple
– Adaptable to processors of different word lengths
– Low memory requirement
– High security
• Cast-128
– Key size from 40 to 128 bits
– The round function differs from round to round
Cipher Block Modes of Operation
 Encrypting a Large Massage
1. Electronic Code Book (ECB)
2. Cipher Block Chaining (CBC)
3. Output Feedback Mode (OFB)
4. Cipher Feedback Mode (CFB)
5. Counter Mode
 Electronic Code Book (ECB)
Break the message into 64-bit blocks (padding the last one)
and encrypt each block with the secret key.

Two problems:
1. two identical plain text block produce two identical
cipher blocks
2. blocks can be rearranged or modified.

Example: An eavesdropper:
1. can see which sets of employees have identical or
similar salaries and
2. he can alter his own salary to match another
employee with higher salary.
ECB Scheme
 Remarks on ECB

• Typical application:
– secure transmission of short pieces of information (e.g. a
temporary encryption key)
 Cipher Block Chaining (CBC)
• Solve security deficiencies in ECB
– Repeated same plaintext block result different ciphertext block

• Each previous cipher blocks is chained to be input

with current plaintext block, hence name

• Use Initialization (or Initial) Vector (IV) to start

process
Ci = EK (Pi XOR Ci-1)
C0 = IV
• Uses: bulk data encryption, authentication
 Remarks on CBC

• Initialization Vector (IV)

– May sent encrypted in ECB mode before the rest of
ciphertext
 Cipher FeedBack (CFB)
• Use Initial Vector to start process

• Encrypt previous ciphertext , then combined with the plaintext

block using X-OR to produce the current ciphertext
• Cipher is fed back (hence name) to concatenate with the rest of IV

• Plaintext is treated as a stream of bits

– Any number of bit (1, 8 or 64 or whatever) to be feed back (denoted CFB-
1, CFB-8, CFB-64)

• Relation between plaintext and ciphertext

Ci = Pi XOR SelectLeft(EK (ShiftLeft(Ci-1)))
C0 = IV

• Uses: stream data encryption, authentication

Remarks on Feedback Mode
 Location of Encryption Devices
• Link encryption:
– A lot of encryption devices
– High level of security
– Decrypt each packet at every switch
• End-to-end encryption
– The source encrypt and the receiver decrypts
– Payload encrypted
– Header in the clear
• High Security: Both link and end-to-end
encryption are needed (see Figure 2.9)
 Key Distribution
1. A key could be selected by A and physically
delivered to B.
2. A third party could select the key and
physically deliver it to A and B.
3. If A and B have previously used a key, one
party could transmit the new key to the
other, encrypted using the old key.
4. If A and B each have an encrypted
connection to a third party C, C could deliver
a key on the encrypted links to A and B.
 Key Distribution (See Figure 2.10)
• Session key:
– Data encrypted with a one-time session
key.At the conclusion of the session the
key is destroyed
• Permanent key:
– Used between entities for the purpose of
distributing session keys
 Authentication

• Requirements - must be able to verify

that:
1. Message came from apparent source
or author,
2. Contents have not been altered,
3. Sometimes, it was sent at a certain
time or sequence.

• Protection against active attack

(falsification of data and transactions)
 Approaches to Message
Authentication
1. Authentication Using Conventional Encryption
Only the sender and receiver should share a
key.
Message with an error-detection code and a
sequence no, timestamp.

2. Message Authentication without Message

Encryption
• -Message Authentication Code
• -One-Way hash function

75
2. Message Authentication without Message Encryption -
Message Authentication Code

MACM=F(KAB,M)
 If received code matches the calculated code, then:

•The receiver is assured that the message has not altered.

•The receiver is assured that the message is from the

alleged sender.

•If the message includes a sequence number, then the

receiver can be assured of the proper sequence, because an
attacker cannot successfully alter the sequence number.
2. Message Authentication without
Message Encryption
• -One-Way hash function
 Secure HASH Functions
Purpose of the HASH function is to produce a
”fingerprint.

Properties of a HASH function H :

1. H can be applied to a block of data of any size
2. H produces a fixed length output
3. H(x) is easy to compute for any given x.
4. For any given code h, it is computationally
infeasible to find x such that H(x) = h
5. For any given block x, it is computationally
infeasible to find with H(y) = H(x).
6. It is computationally infeasible to find any pair
(x, y) such that H(x) = H(y)
79
 Simple Hash Function

b11 xor b12 xor …..xor b1m

 • SHA-1
✔ The algorithm takes as input a message with a maximum length of less

than 2^64 bits and produces as output a 160-bit message digest.

✔ The input is processed in 512-bit blocks.

Steps
1. pad message so its length is 448 mod 512

2. append a 64-bit length value to message

3. initialise 5-word (160-bit) buffer (A,B,C,D,E) to

(67452301,efcdab89,98badcfe,10325476,c3d2e1f0)

4. process message in 16-word (512-bit) blocks:

expand 16 words into 80 words by mixing & shifting

81
use 4 rounds of 20 bit operations on message block & buffer
 Message Digest Generation Using
Secure Hash Algorithm – 1 (SHA-1)

82
SHA-1 Processing of single 512-Bit Block
SHA-1 Compression Function

85
 SHA-1 Compression Function

• each round has 20 steps which replaces the 5 buffer words

thus:

(A,B,C,D,E) <-(E+f(t,B,C,D)+S5(A)+W +K ),A,S30(B),C,D

t t

• a,b,c,d refer to the 4 words of the buffer

• t is the step number

86
Other Secure HASH functions
 HMAC
• Use a MAC derived from a cryptographic
hash code, such as SHA-1.
• Motivations:
– Cryptographic hash functions executes faster
in software than encryptoin algorithms such as
DES
– Library code for cryptographic hash functions
is widely available
– No export restrictions from the US
A cryptographic hash function: hash function which takes an input (or 'message') and returns a

fixed-size alphanumeric string, which is called the hash value (sometimes called a message digest, a

digital fingerprint, a digest or a checksum). 88

 HMAC Design Objectives
•To use without modifications, available hash functions-in particular,
hash functions that perform well in software, and for which code is freely
and widely available.

•To allow for easy replaceability of the embedded hash functions in case
faster or more secure hash functions are found or required.

•To preserve the original performance of the hash functions without

incurring a significant degradation.

•To use and handle keys in a simple way.

•To have a well understood cryptographic analysis of the strength of the

authentication mechanism based on reasonable assumptions about
embedded hash function.
HMAC Structure
H = embedded hash function (e.g., SHA-1)
IV= initial value input to hash function
M = message input to HMAC (including the padding specified in the
embedded hash function)
Yi = i th block of M, 0 ≤ i ≤ (L-1)
L = number of blocks in M
b = number of bits in a block
n = length of hash code produced by embedded hash function
K = secret key; if key>b;the key is input to hash fun to produce an n-bit
key:recommended length is >=n.
K+ = K padded with zeros on the left so that the result is b bits in length
ipad = 00110110 (36 in hexadecimal) repeated b/8 times
opad = 01011100 (5C in hexadecimal) repeated b/8 times
Then HMAC can be expressed as follows:
• HMACk = H[(K+ opad) || H[(K+ ipad) || M]]
• HMAC Algorithm
1.Append zeros to the left end of K to create a b-
bit string K+ (e.g., if K is of length 160 bits and
b=512, then K will be appended with 44 zero
bytes 0x00).
2.XOR K+ with ipad to produce the b-bit block si
3.Append M to si
4.Apply H to the stream generated in step3
5.XOR K+ with opad to produce the b-bit block s0
6.Append the hash result from step4 to s0
7.Apply H to the stream generated in step6 and
output the result.