Subject: Cryptography & Network Security

Topic: Module 2

Difficulty: Medium/High

${\underline{\textbf{Block Cipher & Public Key Cryptography}}}$

Difference between stream & block cipher

1. Stream Ciphers

• In Stream Cipher, encryption & decryption are done on one symbol (such as a character or a bit) at a time.

$P=P_1,P_2,P_3, …..$ $C=C_1C_2C_3…$ $K=(K_1, K_2, K_3 …)$

$\phantom{P=}\downarrow$ $\phantom{_1,P_2,P_3, ….. ;...;}\downarrow$ $\phantom{_1,P_2,P_3fgfdghfd}\downarrow$

$C_1=E_{K_1}(P_1)$ $\phantom{asdsa}$$C_2=E_{K_2}(P_2)$ $\phantom{asdsa}$ $C_3=E_{K_3}(P_3)$

The figure below gives the idea behind a stream cipher. Character are fed into the encryption algorithm, one at a time, the ciphertext are also created one at a time

The key stream can be created in many ways, it may be a stream of predetermined values, it may be created one value at a time using an algorithm. The values may depend on the previous key values. - Here the fig. shows the third character in the plaintext stream is being encrypted using 3rd value in the key stream & results in 3rd character cipher.

2. Block Cipher

• In a block cipher, a group of plaintext symbols of size m, (m>1) are encrypted together creating a group of ciphertext of the same size
• A single key is used to encrypt the whole block even if the key is made of multiple values.

Fiestel Cipher

• It is a design model from which many different block ciphers are divided.
• DES is an example.
• Cryptographic system based on Fiestel Cipherstructure uses the same algorithm for both encryption and decryption.
• Consists of multiple rounds of processing of the plaintext, each round consisting of a substitution step followed by a permutation step.

Encryption steps using a Fiestal Cipher

1. Split the 64 bits of plaintext into left 32 bits $L_0$ and right 32 bits $R_0$
2. Apply carefully designed mathematical function of that takes as i/p the key K & $R_0$ and computes o/p f($R_0$,K)
3. XOR the o/p of the mathematical function with $L_0$, to compute a new 32 bit sequence X=$L_0\oplus f(R_0,K)$
4. Let the new right 32 bits be X
5. let the new left 32 bits $L_1$ be the previous right 32 bits $R_0$
6. Repeat the process from step 2 to step 5 except using $R_1$ instead of $R_0$ & $L_1$ instead of $L_0$. This sequence of steps (steps 2 to 5) is known as a round of the block cipher. The function used is often referred to as the round function.
7. Repeat step 6 for as many rounds as specified by the design algorithm. Once the last round (round m) is completed then the last left 32 bits $L_m$ are joined with the last right 32 bits $R_m$ to form the 64 bits of the Ciphertext, which is formed by concatenating $R_m$ & $L_m$ (in that order).

Key management: (Diffie Hellman key exchange)

• It is a way of generating a shared secret between two people in such a way that the secret cant be seen by observing the communication.

Steps-

1. A & B agree to use Modulus p=23 & base g=5

2. A chooses a secret unit a=4 & sends it to B, i.e A=$g^a\ mod\ p=5^4\ mod\ 23=4 $

3. B chooses a secret unit b=3 & sends it to A, i.e $B=g^b\ mod\ p=5^3\ mod\ 23=10$

4. A computes S (secret key) = $B^a\ mod\ p=10^4\ mod\ 23=18$

5. B computes S (secret key) = $A^b\ mod\ p=4^3\ mod\ 23=18$ Now they share a secret no. 18 $A^b\ mod\ p=B^a\ mod\ p=g^{ab}\ mod\ p$

Data Encryption Standard

• DES is a symmetric key block cipher published by NIST (National institute of Standards & Technologies)
• DES is an implementation of a Fiestal cipher.
• It has a 64-bit block size, a 64-bit key length & uses 16 rounds.
• DES has an effective key length of 56 bits, since 8 of the 64 bots are not used by the encryption algorithm (they are check bits)
• Since fiestal cipher blueprint is used for DES, all that is required is to fully specify DES is –
  • The round function: which is based on taking groups of input bits & replacing (substituting) them according to some rules based on tables known as S-boxes.
  • The key structure: which identifies which bits of the key are used to form the subkeys for any given round.
  • Any additional processing steps: for eg. DES conducts an initial permutation of all i/p bits before the first encryption round begins & then performs the inverse of this permutation to all the output bits immediately after the last encryption round has been completed.

1. Round Function: The DES function applies a 48-bit key to the rightmost 32 bits to produce a 32-bit output.

Initial and Final permutation: are straight permutation boxes (p-boxes) that are inverse of each other. They have no cryptography significance in DES. The initial & final permutation as shown below.

Round function (continued...)

Expansion permutation box: Since i/p is 32 bit & round key is 48 bit, we need to expand the right input to 48 bits. XOR (whitner) – After expansion permutation, DES does XOR operation on the expanded right section & the round key. The round key is used only in this operation.

Substitution boxes: The S-boxes carry out the real mixing DES uses S-boxes, each with a 6-bit input and a 4-bit input.

There are total 8 S-box tables. The o/p of all eight S-boxes is then combined in to a 32-bit section. Straight permutation: the 32-bit o/p of the S-boxes then subjected to the straight permutation.

2. Key Generation: the round key generation creates 48-bit keys out of 56-bit cipher. Process of key generation is as follows-

Shifting | Rounds | Shift | |:-------:|:-------:| | 1,2,9,6 | one bit | | other | two bit |

$\underline{\text{Block Cipher Modes of Operation}}$

These are operational rule for generic block cipher that each result in different properties being achieved when they are applied to plaintext consisting of more than one block.

1. Electronics Code Book: Most straight forward way of processing a series of sequentially listed message blocks. Operations: - The user takes the first block of plaintext & encrypts it with the key to produce the first block of ciphertext. - Then take the second block of plaintext & encrypt it with the key to produce the second block of ciphertext. - This mode is determined i.e if plaintext block $P_1,P_2,P_3……P_m$ areencrypted twice under the same key,the o/p ciphertext blocks will be the same. - for a given key, we can create a codeblock of ciphertext for all possible plaintext blocks. - Encryption would then only look up for required plaintext & select the corresponding ciphertext.

e.g plaintext plaintext

Good$\phantom{sds}$‘Morning GOOD’

$\phantom{s}\downarrow$ $\phantom{aaaa}\downarrow$

\$/@$\phantom{sds}$\$/@

*suitable only when repetition of plaintext is less.

Analysis of ECB mode:

• If any application data usually have partial information which can be guessed for eg range of salary can be guessed, a ciphertext from ECB can allow an attacker to guess the plaintext by trial & error if the plaintext message is within predictable.
• for eg if a ciphertext from the ECB mode is known to encrypt a salary figure, then a small number of trials will allow an attacker to recover the figure, hence we do not prefer to use a deterministic cipher i.e ECB mode.

2. Cipher block Chaining Mode (CBC Mode): provides message dependency for generating ciphertext & makes the system non-determiniastic.

Operations:

• Load the ‘n’ bit initialization vector (IV) in the top register.
• XOR the ‘n’ bit plaintext block with data value in top register.
• Encrypt the result of XOR operation with underlying block cipher with key ‘k’.
• feed ciphertext block into top register & continue the operation till all plaintext blocks are processed.
• for decryption, IV data is XORed with 1st ciphertext block decrypted, the first ciphertext block is also fed into the register replacing IV for decrypting next ciphertext block.

Analysis of CBC mode:

• In CBC mode, the current plaintext block is added to the previous ciphertext block & then the result is encrypted with key. Decryption is thus the reverse process, which involves decrypting the current ciphertext & then adding the previous ciphertext block to the result. Advantage over ECB:
• Changing IV results in different ciphertext for ‘identical message’ Disadvantage
• The error in the transmission gets propagated to few further block during decryption due to chaining effect.
• CBC mode forms the basis for a well-known data origin authentication mechanism. Thus it is advantage for those applications that require both symmetric encryption & data origin authentication.

e.g Plaintext$\phantom{sds}$GOOD$\phantom{sds}$MORNING GOOD

$\phantom{jhgjhghjhgsds}$ $\downarrow$ $\phantom{sds}$ $\phantom{asfasd}\downarrow$

$\phantom{sd}$Ciphertext$\phantom{sds}$\$/@$\phantom{sds}$123@/# xz@\$

3. Cipher feedback (CFB) Mode: In this mode each ciphertext block gets fed back into the encryption process in order to encrypt the next plaintext block.

Operation:

• The operation of CFB mode is depicted in the following illustration. For example, in the present system a message block has a size s bit where 1$\lt$s$<$n. The CFB mode requires an initialization vector (IV) as the initial random n-bit input block. The IV need not the secret. Steps of operation are: - Load the IV in the top register. - Encrypt the data value in top register with underlying block cipher with key k. - Take only s number of most significant bits (left bits) of o/p of encryption process & XOR them with s bit plaintext message block to generate ciphertext block. - feed ciphertext block into top register by shifting already present data to the left and continue the operation till all the plaintext blocks are processed. - Essentially, the previous ciphertext block is encrypted with the key & then the result is XORed to the current plaintext block. - Similar steps are followed for decryption. Pre-decided IV is initially loaded at the start of decryption. ![\[m2-13\]][13] Analysis of CFB mode: - Unlike ECB mode , the ciphertext corresponding to a given plaintext block depends not just on that plaintext block & the key, but also on the previous ciphertext block, i.e the ciphertext block is dependent of message. - CFB has a feature in which user decrypts the ciphertext using only the encryption process of the block cipher. The decryption algorithm of the underlying block cipher is never used. - Apparently CFB mode is converting a block cipher into a type of stream cipher. The encryption algorithm is used as a key-stream generator to produce key-stream that is placed in the bottom register. This key stream is then XORed with the plaintext as in case of Stream Cipher. - By converting a block cipher into a stream cipher, CFB mode provides some of the the advantageous properties of a stream cipher while retaining the advantageous properties of block cipher & on the other side, the error of transmission gets propagated due to chaining of blocks. **4. Output Feedback (OFB) mode:** - It involves feeding the successive output blocks from the underlying block cipher back to it. These feedback blocks provide string of bits to feed the encryption algorithm which act as the key-stream generates as in case of OFB mode. - The key-stream generated is XORed with the plaintext blocks. The OFB mode requires an IV as the initial random n-bit input block. The IV need not be secret. - The operation is depicted in the following illustration. ![\[m2-14\]][14] **AES ( Advanced Encryption Standard)** - The need for coming up with AES algorithm was because of the weakness in DES. The 56 bit key of DES were no longer considered safe against attacks based on exhaustive key section and the 64 bit blocks were also considered weak. - AES is based on 128 lit blocks with 128 bits keys ie the plaintext size is 128 bits and key size is also 128 bits. - No of rounds in AES are 10 or 14 - It works on byte and not on a single bit - Since it works on bites we say that 128 bit key size = 16 byte and 128 bit plain text = 16 byte - It works in two phases $\hspace{2.5cm}$a. One time initialization on key and plaintext $\hspace{2.5cm}$b. Actual rounds **1. One time initialization(OTI):** - As AES requires 10 rounds it while need 10 keys and 1 more key for OTI - In all eleven keys are required - So the 16 byte key is expanded to get the actual block ie the 16 byte key is expanded into a key containing 4*4 entries - Out of the 11 keys 1 key is used for OTI and the remaining 10 keys are used for 10 rounds ![enter image description here][15] - The next step is to take the palin text block called as state and represented into a 4*4 matrix. - While copying the elements in the matrix the order should e coumn wise Plaintext ![enter image description here][16] - Now the 4*4 initialization key is XORed with the 4*$ plaintext block (state Array)

• After XORing we get an initial input of size 4*4 which is carried forward to the list of round.

2. Processes in each Round:

a. Apply S box to each of the plaintext bytes: The ontents of the state array are locked up into the S box. Byte by byte substitution is done to replace the contents of the state array with the respective entries in the S-box. (only one S box is used)

b. Rotate row ‘K’ of the plaintext (ie state) block by k byte: Each of the four rows of the state array are rotated to the left.

$\hspace{2.5cm}$Row ‘o’ is rotated 0 bytes (i.e. not rotated at all)

$\hspace{2.5cm}$Row ‘1’ is rotated 1 bytes

$\hspace{2.5cm}$Row ‘2’ is rotated 2 bytes

$\hspace{2.5cm}$Row ‘3’ is rotated 3 bytes

This helps us in diffusion of data.

3. Perform a mix Columns Operation:

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

• Multiplication is performed one column at a time (i.e. 4 bytes at a time), each value in the column is eventually multiplied against every value of the matrix (i.e. 16 total multiplications are performed)

• The results of these multiplications are XORed together to produce only 4 resulting bytes for next state.

• Finally we have 4 bytes of i/p, 16 multiplication, 12 XORs and 4 bytes of output. e.g., Multiplication Matrix

  

• The first result byte is calculated by multiplying the same four values of the state column with four values of first row of the matrix ,the result of each multiplication is then XORed to produce one byte. e.g. $\hspace{2.5cm} b_1=(b_1\times2)XOR (b_2\times3)XOR (b_3\times1) XOR(b_4\times1)$

• The second result byte is calculated by multiplying the same four values of the state column with four values of second row of the matrix ,the result of each multiplication is then XORed to produce one byte. e.g. $\hspace{2.5cm} b_2=(b_1\times1)XOR (b_2\times2)XOR (b_3\times3) XOR(b_4\times1)$

• The third result byte is calculated by multiplying the same four values of the state column with four values of third row of the matrix ,the result of each multiplication is then XORed to produce one byte. e.g. $\hspace{2.5cm} b_3=(b_1\times2)XOR (b_2\times1)XOR (b_3\times1) XOR(b_4\times2)$

• Similarly fourth result is calculated as
  $\hspace{2.5cm}b_y=(b_1\times3)XOR (b_2\times1)XOR (b_3\times1) XOR(b_y\times2)$

• This procedure is repeated again with next column of the state until there are no more state columns

• Then XOR the state with the key block to produce ciphertext. This is the ciphertext round 1 the Entire process is repeated for all the 10 rounds.