6-Modern Symmetric Ciphers

Strength Of a Cipher

A strong cipher is one that completely obscures the statistical properties of the original message
In 1945, Shannon suggested that a cipher must have two properties

• Diffusion
• Confusion

Confusion means that each character of the ciphertext should depend on several parts of the key, obscuring the connection between the two
This property makes it difficult to find key from ciphertext. If a single bit in key is changed, values of most or all bits in ciphertext will be affected.

Diffusion means the influence of one plaintext character is spread over many ciphertext symbols, so that the statistical properties of plaintext remain hidden. Diffusion implies that each symbol (character) in the ciphertext is dependent on some or all symbols in the plaintext

Block and Stream Ciphers

Block Ciphers operate only on messages of predetermined sizes e.g 64 bits or 128 bits.
Cipher encrypts one block of plaintext and creates a ciphertext block of the same size.
To encrypt data that is smaller than block size, data is padded to make it’s size equal to block size.
If data is larger than block size it will be split into blocks of smaller size.
Each character in the block contributes to encryption of other characters in the block.
Block cipher uses both confusion and diffusion
Product cipher is one that uses multiple rounds of subsitution and permuation operations.

Stream Ciphers encrypts data one bit or one byte at a time rather than in fized-size blocks as in block cipher.
It generates a keystream that is combined with the plaintext to produce ciphertext
Stream ciphers are made for scenarios where data needs to be encrypted in the continuous streams making them suitable for real-time applications.
To create encrytion keys, the stream ciphers use a pseudorandom keystream generator
Stream cipher uses only confusion.

XOR Operation in Cryptography

The XOR operation has a reversible nature that makes it ideal for encryption and decryption
It is different from AND and OR operations

0 AND 0 : 0
0 AND 1 : 0
1 AND 0 : 0
1 AND 1 : 1

0 OR 0 : 0
0 OR 1 : 1
1 OR 0 : 1
1 OR 1 : 1

0 XOR 0 : 0
0 XOR 1 : 1
1 XOR 0 : 1
1 XOR 1 : 0

Assume we use AND for encryption and a ciphertext is generated by performing AND operation on all bits of plaintext with all bits of key.
When we need to decrypt the ciphertext back to plaintext, if we get the bit 0 in ciphertext and corresponding bit of key is 0, we do not know for certain whether the plaintext bit was 0 or 1.
Similary in the case of OR, if we get the bit 1 in ciphertext and corresponding key bit is 1, we do not know for certain whether the plaintext bit was 1 or 0.
This uncertainty makes these two operations unsuitable for encryption and decryption.
Note that we can encrypt and decrypt with XOR operation without any issues.

There is another issue of information leakage in AND and OR operations.
Consider we get the bit 1 in ciphertext that was encrypted using AND operation, now even without the key, we know for certain that the corresponding plaintext bit is 1.
Similarly, for OR operation, the ciphertext bit 0 can be mapped to plaintext bit 0.

Data Encryption Standard - DES

DES is a symmetric-key block cipher developed by IBM in the 1970s and later adopted by the U.S National Insitute of Standards and Technology (NIST) in 1977 as a federal encryption standard.
It was widely used in securing data, but today it is considered insecure because of its short key length.

Key Properties

• Type Symmetric (same key for encryption and decryption)
• Block Size 64 bits
• Key Size 56 bits effective (though the original key is 64 bits, 8 bits are used for parity)
• Rounds 16 rounds of processing

How DES Works

The DES algorithm is based on the Feistel Cipher structure:

1. Initial Permuation: The 64-bit plaintext is permuted. The order of bits is changed using a predefined table: IP table.
2. 16 Rounds:
   • Each round takes the 64 bit block and divides it into left and right halves.
   • A round function f(R, K) is applied, where K is the round subkey (48 bits).
   • Left and right halves are swapped after each round.
   • This gives confusion and diffusion (Shannon’s principle).
3. Final Permutation: This is inverse of initial permutation, producing the ciphertext.

Initial Permutation Table

This IP table describes how initial permutation is done
The numbers in boxes tell where the elements were in original matrix before initial permutation.
For example, the first bit of the permuted block is taken from the 58th bit of the original plaintext.
The last (64th) bit comes from the 7th bit of the original plaintext.

The Initial Permutation is done only once and after it, the first round begins

Key Transformation

The 64-bit initial key is converted into 56-bit effective key. This 56-bit key further generates 48-bit subkeys for each of the 16 Feistel rounds.

Conversion of 64-bit key to 56-bit key

Initial key first goes through Permuted Choice 1 (PC-1) which reduces the key length from 65 to 56 bits.
In PC-1 every eighth bit of the key is discarded. That is bit positions 8,16,24,32,40,48,56 and 64 are discarded.
These discarded bits are called parity bits which are used for error checking.
Remaining 56 bits are split into two 28-bit halves.

• Left Half (Ci): First 28 bits
• Right Half (Di): Last 28 bits

i represents the number of Feistel round.

Generating 48-bit Round Subkeys

For each of the 16 rounds, right half (first 28 bits) and left half (last 28 bits) undergo circular left shift rotation. For Feistel rounds 1,2,9 and 16 both left and right halves undergo 1-bit left shift rotation
For other rounds: 3,4,5,6,7,8,10,11,12,13,14,15, the halves undergo 2-bit left shift rotation.
After circular shift, both halves are combined again to form a 56-bit block. This block then goes through Permutation Choice 2 (PC-2).
The PC-2 selects and arrange 48 bits out of the 56 to form the round subkey (Ki). These 48 bits are selected on the basis of a predefined table

Permuation Choice 2 Table

According to this table, 14th bit is placed in first position, 1th bit in second position and so on.
The output 48-bit subkey of this table is used to cipher the plaintext in the Feistel round.

For the next round, we will use the already left shifted Ci and Di as left and right half. We again perform the cirular left shift operation on both halves. We again combine them to form a 56-bit block and user permutation choice 2 to generate new 48-bit subkey for the next round.

This process of Circular Left Shift and Permutation Choice 2 is followed for 16 rounds and different round subkey Ki is generated for each round.

Feistel Round

There are 16 Feistel rounds which involve a number of different operations to induce confusion and diffusion into the cyphertext.
Every round receives 64-bit plaintext and 48-bit transformed subkey.
The 64-bit plaintext is divided into two halves, Left Plaintext and Right Plaintext. Both 32-bit in size.
The Right half goes through a Mangler function. Mangler function involves Expansion, Key Mixing, Substitution (S-boxes), and Permutation (P=box).

The Right Plaintext first goes through Expansion Permutation. In this operation, the 32-bit plaintext half is expanded into 48-bit using predefined E-box table.

The resulting 48-bits from this E-box is then XORed with the 48-bit round subkey.
After XOR is done, the resulting 48-bit is divided into 8 blocks, each having 6-bits.
Each of the block is fed into a different S-box (S1 to S8)
S-Boxes are predefined lookup tables which reduce each of the 6-bit to 4-bit. The result after feeding 6-bit block into S-box is a 4-bit output.
From all the S-boxes (8), we get 8 blocks, each having 4-bits.
All these 8 blocks are combined to get 32-bit block as output.
The 32-bit block again gets permuted using a P-box table.

This permutation is called Transposition. The mangler function is finished here. The block output from mangler function is XORed with the 32-bit Left Plaintext that was produced after Initial Permutation. The output after XOR serves as the Right Plaintext for next round and the initial Right Half will serve as Left Half for next round.\

Li = Ri-1 Ri = Li-1 XOR F(Ri-1, Ki)

Where

• Li-1 = The Left Half or Left Plaintext (LPT) of current round.
• Li = The Left Half or Left Plaintext (LPT) for next round.
• Ri-1 = The Right Half or Right Plaintext (LPT) of current round.
• Ri = The Right Half or Right Plaintext (LPT) for next round.

The Feistel round is repeated 16 times. After the last round we get two 32-bit blocks. These 32-bit left and right halves are again swapped. This step is called 32-bit Swap.
Finally after swap, the block undergoes Inverse Initial Permutation or Final Permutation, this is the inverse of Initial Permutation.

The final output from this Final Permutation is our 64-bit cyphertext.\

Decryption in DES

For decryption, every step remains the same as in Encryption, the only difference is in subkeys. During decryption the subkeys are used in reverse order. For instance, if subkey 1 was used in first round during encryption, it will be used in last round during decryption. The Feistel round, Initial Permutation, Final Permutation and every other step or table remains the same.\