CNS - Unit - 2 - Stream Ciphers and Block Ciphers

Stream ciphers and block ciphers, Block Cipher structure, Data Encryption standard (DES) with example, strength of DES, Design principles of block cipher, AES with structure, its transformation functions, key expansion, example and implementation

1. Cryptography and Network Security
UNIT - 2

Stream Ciphers and Block Ciphers

2. Outline...

* Stream ciphers and Block ciphers

* Block Cipher Structure

* Data Encryption standard (DES)

* Strength of DES

* Design principles of Block cipher

* AES with structure

* AES Transformation functions

* Key expansion and Implementation

3. Types of Algorithm Base on Key

*There are two different types of algorithm are available in
cryptograph.
1. Symmetric Key Algorithm.
2. Asymmetric Key Algorithm.

+ Symmetric Key Algorithm:- Key remains same for encryption and
decryption.

* Asymmetric Key Algorithm:- Algorithms which requires two separate
keys, one of which is secret (or private) and one of which is public.

4. Stream Cipher

* A stream cipher is one that encrypts a digital data stream one bit or
one byte at a time.

Bit-stream e Bit-stream
generation 4 generation
algorithm algorithm

Plaintext
(pp

5. « Example:

Key

Stream Cipher

Plain Text

10111001
(a)

10101011
(b)

00010010

Cipher Text

6. Block Cipher

° A block cipher is one in which a block of plaintext is treated as a
whole and used to produce a ciphertext block of equal length. a block
size of 64 or 128 bits is used.

b bits b bits

7. Block Cipher

* Blocks of bytes Encrypted at a time.

* Length of Cipher text block is remain same as length of Plain text
block.

* 64 bit or 128 bits block is used for processing.
* Provide reversible or nonsingular transformation.

* Problem of block cipher is repeating text and to overcome this
problem different Chaining Modes are used for processing.

8. Block Size

* Avoid very small block size - Say a block size is m bits. Then the
possible plaintext bits combinations are then 2m. If the attacker
discovers the plain text blocks corresponding to some previously sent
ciphertext blocks, then the attacker can launch a type of ‘dictionary
attack’ by building up a dictionary of plaintext/ciphertext pairs sent
using that encryption key. A larger block size makes attack harder as
the dictionary needs to be larger.

+ Do not have very large block size - With very large block size, the
cipher becomes inefficient to operate. Such plaintexts will need to be
padded before being encrypted.

* Multiples of 8 bit - A preferred block size is a multiple of 8 as it is easy

for implementation as most computer processor handle data in
multiple of 8 bits.

9. Padding in Block Cipher

* Block ciphers process blocks of fixed sizes (say 64 bits). The length of
plaintexts is mostly not a multiple of the block size. For example, a
150-bit plaintext provides two blocks of 64 bits each with third block
of balance 22 bits. The last block of bits needs to be padded up with
redundant information so that the length of the final block equal to
block size of the scheme. In our example, the remaining 22 bits need
to have additional 42 redundant bits added to provide a complete
block. The process of adding bits to the last block is referred to as
padding.

* Too much padding makes the system inefficient. Also, padding may
render the system insecure at times, if the padding is done with same
bits always.

10. Block Cipher Example
+ Digital Encryption Standard (DES)
* Triple DES
* Advanced Encryption Standard (AES)
+ IDEA
* Twofish

* Serpent

11. CONFUSION & DIFFUSION

* Claude Shannon introduced this two terms

* Confusion
+ It is a technique of ensuring that a cipher text gives no clue about plain text
+ Achieved by Substitution technique.

+ Diffusion

* Increases the redundancy of the plain text by spreading it across rows and
columns.

+ Achieved by permutation known as Transposition technique

12. FEISTEL CIPHER
* Feistel proposed a scheme to produced a block cipher using
permutation and substitution alternatively.

* It is the approach to develop a block cipher with a key length of k-bits
and a block length of n-bits allowing a total 2k possible
transformation

13. Encryption:
Plaintext

KE

‘Ciphertext (2w bits)

Ky

14. Dutpur (plaintext

Decryption:

Ciphertext

Plaintext
Input (ciphertext)

15. FEISTEL NETWORK PARAMETERS

* Block Size
* Large block size provide high security achieved by diffusion
* 64 bit block is universal block cipher design
* Less encryption/decryption speed of algo
» Key Size
+ Large key size provide high security achieved by confusion
* 128 bit is common key size
* Number of Rounds
* Single round offers less security
+ Multiple round provide greater security
* 16 rounds are common

16. FEISTEL NETWORK PARAMETERS

* Sub key generation Algo.
* Complex algo provide high security
* Round Function
+ Complex rounding operation provide high security

17. ROUND FUNCTION

I
EXPANSION
PERMUATATION (
it)
CE

A

Le

48-Bit

Substitution

32-Bit

PERMUATATION
(32-Bit)

18. History of Data Encryption Standard (DES)

* Known as DEA(Data Encryption Algorithm) by ANSI and DEA-1 by ISO.

* DES is landmark in cryptographic algorithms.

* Generally Used in ECB(Electronic Code Book), CBC(Cipher Block
Chaining) and CFB(Cipher Feedback Block) mode

« NBS(National Bureau of Standards), now knows as the National
Institute Standard and Technology (NIST) worked with DES in 1972

* IBM’s Lucifer was considered as Standard of Encryption in 1975 by
NBS

+ 1976 US-Federal Govt. announced DES as a standard algorithm for
encryption

19. 6:
Pain Text

pe n]

64-bit
Cipher Text

BLOCK-1

How DES Works

64-bit
Pain Text

64-bit
Cipher Text

BLOCK-2

64-bit
Cipher Text

BLOCK-n

20. Key Discarding Process

+ We have mentioned that DES uses a 56-bit key. Actually, the initial key
consists of 64 bits. However, before the DES process even starts,
every eighth bit of the key is discarded to produce a 56-bit key.

64-bit
fo} I Key
Every 8% Bit of Original Key Discarding
Key is Discarded Process
Resulting Key

21. Key Discarding Process

10 11 12 13 14

17 18 19 20 21 22 26 27 28 29 30

33 34 35 36 37 38 42 43 44 45 46

49 50 51 s2 33 54 58 ae 60 61 62

Thus, the discarding of every 8" bit of the key produces a 56-bit key
from the original 64-bit key, as shown in table.

22. Working of DES

« Based on two fundamentals of cryptography
* Substitution
* Transposition

» 16 Steps are known as Round

23. Steps of DES

. 64-bit plain text block is given to Initial Permutation (IP)
function

2. IP performed on 64-bit plain text block
3. IP produced tow half of the permuted block known as Left

Plain Text (LPT) and Right Plain Text (RPT)

4. Each LPT and RPT performed 16-rounds of encryption process

. LPT and RPT rejoined and Final Permutation (FP) is performed
on combined block

. 64-bit Cipher text block is generated

24. SiLEPSORBES

Plain Text (64-bit)

Initial
Permutation(IP)

LPT RPT

16 Rounds of
Encryption
Final Permutation
(FP)

64-bit Cipher Text

25. INITIAL PERMUTATION

* Initial Permutation performed only once
* Bit sequence have changed as per IP table
+ Example:

+ 1% bit take 40" Position
+ 58! bit take 1* position

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

* Out put of IP is divided into two equal halves known as LPT, RPT

26. 16 ROUNDS OF ENCRYPTION

Expansion
Permutation
S-box (substitution)
P-box
(Permutation)

XOR a [oR and swar_| SWAP

27. KEY TRANSFORMATION

*Combination of two process
* Key Bit Shifted per round
*Compression Permutation

28. KEY BIT SHIFTED PER ROUND

« 56-bit key is divided into two halves each of 28-bits
* Circular left shift is performed on each halves

+ Shifting of Bit position is depending on round
* For round number 1,2,9 and 16 shift is done by one position
+ For remaining rounds shift is done by 2 position

Round 3 |4 5 6 7 8 10 11 12 13 14

Key bit i J1 |2 |2 E 2 æ & x ® 2 Zz z 2
shifted

29. COMPRESSION PERMUTATION

+ 56-bit input with bit shifting position
* Generates 48-bit key (Compression of Key bit)
* Drop 9, 18, 22, 25, 35, 38, 43 and 54 bits.

14 17 11 24 1 5 3 28 15 6 21 10

a 19 12 4 26 8 16 € 27 20 43, Ed

41 52 31 37 47 LE 30 40 Si 45 33 48

44 49 39 56 34 53 46 42 50 36 29 32

30. EXPANSION PERMUTATION

+ 32-bit RPT of IP is expanded to 48-bits

+ Expansion permutation steps:
* 32-bit RPT is divided into 8-blocks each of 4-bits

32-bit RPT

% y

(4-bits) (4-bits) (4-bits)

31. EXPANSION PERMUTATION

* Each 4-bit block is expanded to 6-bit and produce 48-bit output

i 5 8. 4 5 6 7 8 2 30, 31 32

SI

2 3 4 5 6 789 10 11 12 43 44 45 46 47 48

32. EXPANSION PERMUTATION

* 48-bit RPT is X-Ored with 48-bit Key and output is given to S-Box

48-bit RPT

48-bit Output

33. S-BOX Substitution

48-bit Input (48-bit RPT Xored 48-bit Key)

6-bit Sub block

6-bit Sub block 6-bit Sub block

32-bit Output

35. S Box-2

1 8 4 6 11 3 4 9
B 47152 8 U RD

W 7 1110 4 B 15
§ 0 1.31 4 21

36. S-BOX WORKING

4-bit column Number

2-bit Row Number

37. P-BOX Permutation

* Output of s-box is given to p-box
* 32-bit is permuted with 16 x 2 permutation table

16 |7 20 |21 |29 [12 |28 |17 |1 15 |23 |26

31 |10

2 8 24 |14 |32 [27 |3 9 19 |13 [30 |6

22 |11

38. XOR AND SWAP

+ 32-bit LPT is X-Ored with 32-bit p-box

64-bit Plain Text

32-bit LPT 32-bit RPT

. Key Transformation

. Expansion Permutation
» S-box

. P-box

39. Final Permutation

* At the end of rounds 16, The left and right halves of the output are
swapped to produce the pre-output. Finally, the pre-output is passes
through a Final Permutation is performed (only once), This is a simple
transposition, based on below Table, the 40** bit take the position of
the 1% output bit so on.

40 8 48 16 56 24 64 32 39 Y 47 15 55 23 63 31

38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29

36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27

32 2 42 10 50 22 58 26 33 1 41 9 49 17 57 25

40. Strength of DES

» Key Length (Use of 56-bit Key)
« 2456 Possible Keys (7.2 x 10116 Keys)
+ Brute force attack take more than thousand Years

+ Use of S-boxes

* Complex Structure of S-box
* Scope of attack is very less

+ DES is Reversible algorithm

41. Weakness of DES

* Trying all 256 possible keys are not much harder these days.

* If you spend at least $25 K you can build DES password crackers that
will successes in few hours.

* The purpose of initial and final permutation is not clear.

42. AVALANCHE EFFECT

* The small change in Plain text of Key produce a significant change
in the Cipher text.

* One bit change in plain text or key should produce a change in
many bits of the cipher text.

* DES Provide a strong Avalanche effect due to complexity of
algorithm.

43. AES (Advanced Encryption Standards)

* AES is symmetric key cryptographic algorithm published by NIST.

* The algorithm was proposed by Rijndael the reason also called Rijndael
encryption algorithm.

» AES is replacement of DES.

* AES works on block cipher technique. Input block of data and output block
of data which is the same size.

+ An input key is also required input to the AES algorithm.

* It allows the data length (plain text size) of 128, 192 and 256 bits, and
supporting three different key lengths, 128, 192 and 256 bits.

* AES consists of multiple rounds of processing different key bits like 10

rounds for processing 128-bit keys, 12 round for processing 192-bit keys,
and 14 rounds for processing 256-bit keys.

44. AES Operation

Do the following one-time initialization processes:
a) Expand the 16-byte key to get the actual Key block to be used.
b) Do onetime initialization of the 16-byte plain text block(called as State).
c) XOR the state with key block.
For each round, do the following:
a) Apply S-box to each of the plain text bytes.
b) Rotate row k of the plain text block(state) by k bytes.
c) Perform a mix columns operation.
d) XOR the state with the key block

45. |. One-time Initialization Process

a) Expand the 16-byte key to get the Actual Key Block to be Used

* This step expands this 16 bytes key into 11 arrays, each array
contain 4 rows and 4 columns.

+ In other words the original 16 bytes key array is expand into a key
contain 11 * 4 * 4 =176 bytes.

« In AES a word means 4 bytes therefore in the current context, our
16-byte initial key will be expanded into 176-byte key(44 words).

46. Expand Key Process

1. Firstly, the original 16-byte key is copied into the first 4 words of the
expand key array.

2. After filling the first array of the expanded key block as explained
above, the remaining 10 arrays are filled one-by-one. Every time
4*4 array gets filled. That is every added word w[i] depends on
wli-1] and wli-4]. We have said that this fill four word at a time.

a) If the word in the W array is multiple of four, some complex logic is used,
explained later. This is, for words w[4],w[8],w[12].etc.

b) For other, a simple XOR is used.

47. Logic is describe in an algorithm

ExpandKey (byte K[16], word W[44])

{

word tmp;
// First copy all the 16 input key blocks into first four words of output key
for(i=0; | < 4; i++)

{
wii] = k[4*i], k[4*i+1] , k[4*i+2] , k[4*i+3];
}
for(i=4; i<44; i++)
{
tmp=w[i-1];
if(i mod 4==0)
tmp = Substitute (Rotate(tmp)) XOR Constant [i/4];
wii] = wli-4] XOR tmp;

48. Process for key block is a multiple of 4

+ Let us now understand the three function Substitute, Rotate and

Constant.

I. Function Rotate perform a circular left shift on the contents of the

word by one byte. E.g.[B1,B2,B3,B4]; then [B2,B3,B4,B1].

Il. Function Substitute perform a byte substitution on each byte of the

input word. For this purpose it use an S-box.

lll. In this function Constant, the output of the above step is XORed
with constant. This is constant is a word consisting 4 bytes. The
value of the constant depends on Round number. The last three
byte of constant word always contain 0.

Round number

1

2

3

4

10

Value of constant to be used in Hex

01

02

04

08

10

20

80

18

36

49. 0 1| 2] 3 4
0|63| 7c| 77 | Tb| £2
1|ca| 82] c9 | 74| fa
2| b7 | fa| 93 | 26 | 36
3/04| c7| 23| c3]| 18
4| 09 | 83 | 2c | 1a | 1b
5| 53 | d1| 00 | ed | 20
6| d0 | ef | aa | fb| 43
7| 51 | a3] 40 | 8£ | 92
8| cd| Oc} 13 | ec | 5f
9| 60] 81| 4f | de | 22
a|e0| 32] 3a|0a| 49
b|e7|c8| 37 | 6d| 8d
c|ba| 78| 25 | 2e | le
d| 70 | 3e| b5 | 66 | 48
e| el | f8| 98 | 11 | 69
f| 8c|al| 89 | Od| b£

50. b) Do onetime Initialization of the 16-byte plain Text Block (Called as State)

* This step is relatively simple.

+ Here the 16-byte plain text block is copied into a two-dimensional 4*4 array

called a state.

* The order of copying is in the column order.

+ That is, the first four bytes of the plain text block get copied into the first column
of the state array, the next four byte of the plain text block get copied into the
second column of the state array and so on.

BO B1 B2 B3 B4 B5 B6 B7 B8 B9 | B10 | B11 | B12 | B13 | B14 | B15
BO B4 B8 B12
B1 BS B9 B13
+—— State array
B2 B6 B10 B14
B3 B7 B11 B15

51. C) XOR the state with the Key block

« Now the first 16-byte of the expanded key are XOR
into the 16-byte state array. Thus, every byte in the
state array is replaced by the XOR of itself and the
corresponding byte in the expanded key.

*At this stage, the initialization is complete and we are
ready for rounds.

52. AES Operation

Do the following one-time initialization processes:
a) Expand the 16-byte key to get the actual Key block to be used.
b) Do onetime initialization of the 16-byte plain text block(called as State).
c) XOR the state with key block.
For each round, do the following:
a) Apply S-box to each of the plain text bytes.
b) Rotate row k of the plain text block(state) by k bytes.
c) Perform a mix columns operation.
d) XOR the state with the key block

53. ll. Foreach round Process

a) Apply S-box to each of the plain text bytes.
* This step is very straightforward. The contents of the state array are

looked up into S-box.

* Byte by substitution is done to replace the contents of the state array

with the respective entries in the S-box.

* Note that only one S-box is used, unlike DES, which has multiple S-

boxes.

54. 0 1| 2] 3 4
0|63| 7c| 77 | Tb| £2
1|ca| 82] c9 | 74| fa
2| b7 | fa| 93 | 26 | 36
3/04| c7| 23| c3]| 18
4| 09 | 83 | 2c | 1a | 1b
5| 53 | d1| 00 | ed | 20
6| d0 | ef | aa | fb| 43
7| 51 | a3] 40 | 8£ | 92
8| cd| Oc} 13 | ec | 5f
9| 60] 81| 4f | de | 22
a|e0| 32] 3a|0a| 49
b|e7|c8| 37 | 6d| 8d
c|ba| 78| 25 | 2e | le
d| 70 | 3e| b5 | 66 | 48
e| el | f8| 98 | 11 | 69
f| 8c|al| 89 | Od| b£

55. b) Rotate row k of the plain text block(state) by k bytes

+ Here, each of the four rows of the state array are rotated to the left.

* Row 0 is rotated O byte, row 1 is rotated by 1 byte, row 2 is rotated 2 byte and
row 2 is rotated 3 bytes.

* This helps in diffusion of data.

¢ Thus,

the values as

if

the original
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 then the rotate operation would change

ollows:

16 bytes of

the

state

array contain values

Original array Modified array
1 5 9 13 1 5 9 13
2 6 10 14 6 10 14 2
3 7 11 15 11 15 3 F
4 8 12 16 16 4 8 12

56. C) Performa mix columns operation

*Now each column is mixed independent of the other. Matrix
multiplication is used. The output of this step is the matrix
multiplication of the old values and a constant matrix.

* This is perhaps the most complex step to understand and also to
explain.

* There are two aspects of this step. The first explains witch parts of the
state are multiplied against witch parts of the matrix. The second
explains how this multiplication is implemented over what’s called
as a Galois Field.

57. c.1) Matrix Multiplication

+ Multiplication is performed one column at a time. Each value in the
column is eventually multiplied against every value of the matrix.

* The results of these multiplication are XOR together to produce only 4
resulting bytes for the next state.

* We together have 4 bytes input, 16 multiplication, 12 XOR and 4
bytes output.

+ The multiplication is performed one matrix row at a time against each
value of a state column.

+ Constant Matrix

wlnlnln
menu
n|noluls
plwlnle

58. c.1) Matrix Multiplication

+ The second result byte is calculated by multiplying four values of the
state column with the four values of the first row of the matrix. The
result of each multiplication is then XOR to produce one byte.

b1= (b1*2) XOR (b2*3) XOR (b3*1) XOR (b4*1
b2= (b1*1) XOR (b2*2) XOR (b3*3) XOR (b4*1)

b3= (b1*1) XOR (b2*1) XOR (b3*2) XOR (b4*3)

b4= (b1*3) XOR (b2*1) XOR (b3*1) XOR (b4*2

59. c.2) Galois Field Multiplication

* The result of the multiplication is actually the output of a lookup of
the L table, followed by the addition of the results, followed by a
lookup of the E table.

* Note that the term addition means a traditional mathematical
addition and not a bit-wise AND operation.

+ All number being multiplied using the Mix Column function converted
to Hex will form a maximum of 2 digit Hex number.

* We use the first digit in the number on the vertical index and the
second number on the horizontal index.

* If the value begin multiplied is composed of only one digit we use 0
on the vertical index.

60. c.2) Galois Field Multiplication

* For example if the two Hex values begin multiplied are AF * 8 we first
lookup L (AF) index which return B7 and then lookup L (08) which
return 4B.

* Once the L table lookup is complete we can then simply add the
numbers together. The only trick begin that if the addition result is
greater than FF, we subtract FF from the addition result.

* For example B7 + 4B = 102. Because 102 > FF, we perform: 102 — FF
which gives us 03.

* The last step is look up the addition result on the E table. Again we
take the first digit to look up the vertical index and the second digit to
look up the horizontal index.

+ For example E(03) = OF. Therefore, the result of multiplying AF*8 over
Galois Field is OF.

61. un) alm BIS 2|2|Y$|R|8|2 85/8
81 21813 2 ei8|3 15/18
Ö
alu o |alelwi=lo <lolniolmio|w
wi2 8 a[R|[R | B|S|s[S3|8 3 2
3
2

Ô
olqlalwlælmiwlolulu alalala
a(2[Aa[<[6 Afajojajoaja|o 5

2
n

[a]

w
slwlolmlæololæaln|l<«|lu|ælm|olwlrin
EE als 8)

<
{=}

a

[6]
als 5 R/2 80181213 ô 21313
sıs [2/23 88 e 2 ¡2/2 15 PIE:

a

a
alv alo nimir|imle K nio

x ,
<IR 8 als BR|aln| | m |

IS

5
a|8S|ia az a|=|R|5 5 a S| 8
a a 21812 8/8/2818 &

a à
a
© nm alale alalalalala u
n
313 S1S/3 81 181819 2 E
<

a
siu|z[olo|pnlulolola[ojw[|uzla|=|olao
S|c|<[S[oJ[Oo[R | Ejujojo Ind

©
a

3

<

x -
Sır)a w sIGin|«|als|s <

©
88
8/2/38 28|2|12 313/85

©
nimlnlalu|alaloln|aln|iulmiæs|miaolnr
8lniRlnlnimialm|alo|ol|u Ra

E

Ë

a
316 15 3 8 [¡3S|S|a 3 |< 213

&

<

i
aa eal all a
2/5/2318 2/18 2|/Rl8|8|88 HR

a

S

a
alelelols|/nijalnjmla}alel}alalalaia
sıo/ma|ın/S o[a|[n|[A|[mju|o + a

5

A

o
alo ln is=([v [ws [ojolu|<[olu[le lolo
8|5/1519/25/[85/73)315|15 a +

mn
[a]

a
elsaluln|im|oulminlwlæo|lml|ulo nlala
s/s) EEE 2/3/38

ha

a

5
slalss 5 < u

w
a
alu
©
S
Ss
fr}
3
SiS
Ss
318

9/81 - 3

62. 03
cl
78

7b | b7

$1

70 | 07

ee | df
le

© | 09

76

1f | 2d | a4

fo

12

24

ei

15 | 9b
fa

Cra | eb [as | ob [is [ss [eo | Sf [bo | se | 29

05 | 21

8a

79 | Oa
58 | a8
d7 | 75

2f

65

3
z
8

2b
af
[9 | 2c |

Ca [ar [oe | 16 [er | 17 la | 49 | ec | 08 | 43

age -7

63. d) XOR the state with the key block

*This step XOR the key for this round into the state
array.