DATA ENCRYPTION STANDARD

• It is previously predominant algorithm for the encryption of a electronic data.It was highly influential in the advacement of modern cryptography in the academic world.Developed in the early 1970s at IBM and based on an earlier design by Horst Feistel

Data Encryption Standard

-DES is a feistel cipher

-Block Length is 64 bit

-Key Length is 56 bit

-No of rounds are 16

-Each round is applied on one Block Cipher

-Security depends primarly on "s-boxes"

-Each S-boxes maps 6 bits to 4-bits

Objectives

• Block cipher
• Full Size cipher and Partial key cipher
• Components of a Modern Block Cipher
-P Box (Permutation Box)
-S Box (Substitution Box)
-Swap
-Exclusive OR operation
• Diffusion and Confusion
• Feistel cipher

Two classes of product ciphers

• Feistel ciphers, Example DES(data encryption standard)
• Non-feistel Ciphers, Example AES(Advanced Encryptin system)

Feistel Cipher

Feistel cipher

• A Feistel cipher is a symmentric structure used in the construction of block ciphers,named after the German-born physicist and cryptographyer Horst Feistel who did pioneering research while working for IBM (USA);it is also commonly known as a Feistel network.

• A large portion of block ciphers use the sheme,including the Data Encryption Standard
• Feistel structure has the advantage that encryption and decryption operations are very similar,even identical in some cases
• A Feistel network is an iterated cipher with an internal function called round function

Encryption

• Feistel cipher refers to a type of block cipher design,not a specific cipher
• split plaintext block into left and right halves:Plaintext = (L₀,R₀)
• For each round i=1,2,......,n compute
    L_i = R_i-1
    R_i = L_i-1 ⊕ f(R_i-1,K_i)
    where f is round function and K_i is a subkey
• Ciphertext = (L_n,R_n)

-if you do encrypt the message in this way it is easy to break for the attacker and further the security is very less

-so what should we do now?

• -Now they came with this structure .The round function is a combination of both R_i-1 and Key
• -So we need R_i-1 at the decrypting side so they directly the results of the R_i-1 to the next step

• -Again they found other problem?
• Here comes the swap operation we have discussed earlier

Decryption in fiestal cipher

Decryption:cipher text = (L_n,R_n)

For each round i=n,n-1,........,1 compute

    R_i-1 = L_i

    L_i-1 = R_i ⊕ f(R_i-1,K_i)

    where f is round function and K_i is subkey

Plain text = (L₀,R₀)

---

Block cipher

• As the name suggests here the block of data is encrypted
• Typically block of data which is encrypted is 64-bit
• If the data has fewer no of bits than 'n'?
• If the data is not in the multiples of 'n' ?

Padding

• If the data has fewer than 'n' bits,padding must be done to make it 'n' bits
• If the message Size is not a multiple of 'n' bits,then it should be divided with into 'n' bit blocks and the last block should be padded

---

Full Size Cipher

• Transposition Cipher
• Substitution Cipher

Transposition cipher

-It involves rearrangement of bits,without changing value

-Consider an n-bit cipher

-How many key bits are necessary? n!

-How many key bits are necessary ?

    ceil[log₂(n!)]

Substitution cipher

-It does not transpose bits,but substitutes values

-can we model this as as permutation?

-Yes.The n bits inputs and outputs can be represented as 2ⁿ bit sequences,with one 1 and rest 0's.this can be thus modeled as a transposition.

-Thus it is a permutation of 2ⁿ values,thus needs

  ceil[log₂(2^n!)]bits

-Example:

-No of possible r-arrangements = 8!

-SIze of the key = [log₂ 8!]

-In the case of a 3-bit transposition cipher,size of the key = log₂ 3!

Examples

• Cnsider a 3-bit block ciphers.How many bits are needed for the full-size Key?

-Transposition cipher:ceil(log₂6)=3 bits

-Substitution cipher:

• There are 8!=40,320 possible substitutions
• Thus there are ceil(log₂(40,320))=16 bits
• Thus it is a permutation of 2ⁿ values,thus needs
    ceil[log₂(2¹⁶)]=65,536 bits
  -We can observe there is a lot unused keys.

So what should we do now?

---

Partial-Size key ciphers

• Actual ciphers cannot use full size keys,as the size is large
• Block ciphers are substitution ciphers(and not transpositions).why?

-if we use transposition cipher then it will very easy for Attacker to break the code by usng Hamming weight
-Hamming weight is nothing but no of 1's in a given code
 Example=(101011) Hamming weight is 4
• Consider DES,with 64 bit block cipher.
-Size of full key=ceil(log₂(64!))≈ 2⁷⁰
-Much large compared to 56 bits which is actually used
-so we are using partial key cipher
-here we are considering the 56 bit key for DES

---

Components of Modern Block cipher

• Most important components are
-PBOX:It is a key-less fixed transposition cipher
-SBOX: It is a key-less fixed substitution cipher
• They are used to provide:
-DIFFUSION:It hides the relationship between the ciphertext and the plaintext
-CONFUSION:It hides the relationship between the ciphertext and the key

Principle of Confusion and Diffusion

• The design principles of Block Cipher depends on these properties
• The S-BOX is used to provide Confusion,as iti is dependent on the unkonwn Key
• The P-BOX is fixed,and there is no confusion due to it
• But it provides diffusion
• Properly combining these is necessary.
• Diffusion boxes are generally of three types

• How to read this?
-First bit of the output 01 is derived from the first bit of input
-It is bijective mapping because there are 24 inputs and 24 outputs
-In the case of Expansion boxes we have 12*24 means input size is 12 and the output size is 24 so we can see repetition.
-In the case of Compression boxes we have 24*12 means input size is 24 and output size is 12 so we can see the loss of information

S-BOX

• An S-Box(SUbstitution box) is an M*N susbtitution box where m and n are not necessarily same.
• each output bit is a boolean function function of the inputs.
    y1=f1(x₁,x₂,.........,x_n)
    y2=f2(x₁,x₂,.........,x_n)
    y3=f3(x₁,x₂,.........,x_n)
    .........................
    ym=fm(x₁,x₂,..........,x_n)

-All the S-boxes should be non-linear
-Suppose if you consider a bad S-box like Linear.what will happen?
    S_i(X₁,X₂,........,X₆)=(X₂⊕X₃, X₁⊕X₄⊕X₅, X₁⊕X₆, X₂⊕X₃⊕X₆)
    y1=a₁₁x₁ ⊕ a₁₂x₂ ⊕ ............ a_1nx_n
    y2=a₂₁x₁ ⊕ a₂₂x₂ ⊕ ............ a_2nx_n
    ...........................
    ym=a_m1x₁ ⊕ a_m2x₂ ⊕ ............ a_mnx_n
• written equivalently: S_i=A_iX (mod 2)
• -That means we can represent them as form of matrix

• if you do in the same as above the S-BOX just perform XOR operation between various things, permutes and shuffle bits around so it is just XOR's and bit permutations
• As a result all the DES operations would be linear which does not provide security
• From this we can observe only S-BOX operations are non-linear to provide security
Eg:     y₁=X₁X₃ ⊕ X₂,Y₂=X₁X₂ ⊕ X₃

Permutation Box(P-BOX)

• permutation box (or P-box) is a method of bit-shuffling used to permute or transpose bits across S-boxes inputs

Other Components

• Circular shift
-It shifts each bit in an n-bit word K positions to the left.the leftmost k bits become the original rightmost bits.
-Invertile Transformation
-For example,repeatedly applying circular shifts to the four-tuple(a,b,c,d) successively gives
    (d,a,b,c),(c,d,a,b),(b,c,d,a),(a,b,c,d)

• Swap
-A specail type of shift operation where k=n/2
• Other operations involve split and combine
• An important component is exclusive - or operation

Properties of EX-OR

• EX-or is a binary operator,which results in 1 when both the inputs have a different logic.Otherwise,it computes 0
• -Symbol ⊕
• Closure:Result of exoring two n bit numbers is also n bits
• Associativity:Allows to use more than one's ⊕ in any order
-    X ⊕ (Y ⊕ Z) = (X ⊕ Y) ⊕ Z
• Comutatavity:X ⊕ Y=Y ⊕ X
• Identity:The identity element is the n bit 0,represented by
    (0,0,0,......0) = 0ⁿ
    Thus X ⊕ 0ⁿ = X
• Inverse:Each word is the additive inverse of itself
    X ⊕ X = 0ⁿ

Application of EX-OR

• The key is known to both the encryptor and decryptor and helps to recoer the plaintext.
    C=P ⊕ K
    C ⊕ K = (P ⊕ K) ⊕ K
        = P ⊕ (K ⊕ K)
        = P ⊕ 0ⁿ(identity)
        = P

A product cipher made of 2 rounds

-Here 8th bit of the plain text is XOR ed with the 8 th bit of the Key

-From Xor we got 2 bits of output and passed to different positions in the middle text

-And from there it is XOR ed with the 2nd and 4th bit of the Key and produces four output bits

-An this four bit are passsed to 1,3,6,7 positions of the cipher text

-Now you can see if you change or disturb one bit in the plain text then 4 bits are affected in the cipher text

-Here we can feel Diffusion(the single bit is converted into 4 bits )so hiding from the plain text is provided

-Here we can feel Confusion(the 1,3,6,7 bit are depend upon the 8th of k₁,2nd and 4th bit of the k₂)so hiding of cipher text from the Key is obtained

Practical ciphers

• Large data blocks
• More S-boxes
• More rounds
• These help to improve the diffusion and confusion in the cipher