시간과 공간 그리고 진실의 방

Block ciphers are built in the Feistel cipher structure. Block cipher has a specific number of rounds and keys for generating ciphertext.Block cipher is a type of encryption algorithm that processes fixed-size blocks of data, usually 64 or 128 bits, to produce ciphertext. The design of a block cipher involves several important principles to ensure the security and efficiency of the algorithm. Some of these principles are:

1. Number of Rounds – The number of Rounds is regularly considered in design criteria, it just reflects the number of rounds to be suitable for an algorithm to make it more complex, in DES we have 16 rounds ensuring it to be more secure while in AES we have 10 rounds which makes it more secure.
2. Design of function F – The core part of the Feistel Block cipher structure is the Round Function. The complexity of cryptanalysis can be derived from the Round function i.e. the increasing level of complexity for the round function would be greatly contributing to an increase in complexity. To increase the complexity of the round function, the avalanche effect is also included in the round function, as the change of a single bit in plain text would produce a mischievous output due to the presence of avalanche effect.
3. Confusion and Diffusion: The cipher should provide confusion and diffusion to make it difficult for an attacker to determine the relationship between the plaintext and ciphertext. Confusion means that the ciphertext should be a complex function of the key and plaintext, making it difficult to guess the key. Diffusion means that a small change in the plaintext should cause a significant change in the ciphertext, which makes it difficult to analyze the encryption pattern.
4. Key Size: The key size should be large enough to prevent brute-force attacks. A larger key size means that there are more possible keys, making it harder for an attacker to guess the correct one. A key size of 128 bits is considered to be secure for most applications.
5. Key Schedule: The key schedule should be designed carefully to ensure that the keys used for encryption are independent and unpredictable. The key schedule should also resist attacks that exploit weak keys or key-dependent properties of the cipher.
6. Block Size: The block size should be large enough to prevent attacks that exploit statistical patterns in the plaintext. A block size of 128 bits is generally considered to be secure for most applications.
7. Non-linearity: The S-box used in the cipher should be non-linear to provide confusion. A linear S-box is vulnerable to attacks that exploit the linear properties of the cipher.
8. Avalanche Effect: The cipher should exhibit the avalanche effect, which means that a small change in the plaintext or key should cause a significant change in the ciphertext. This ensures that any change in the input results in a complete change in the output.
9. Security Analysis: The cipher should be analyzed for its security against various attacks such as differential cryptanalysis, linear cryptanalysis, and brute-force attacks. The cipher should also be tested for its resistance to implementation attacks, such as side-channel attacks. 

Overall, a good block cipher design should be resistant to various attacks, efficient, and easy to implement.

This article talks about the Data Encryption Standard (DES), a historic encryption algorithm known for its 56-bit key length. We explore its operation, key transformation, and encryption process, shedding light on its role in data security and its vulnerabilities in today’s context.

What is DES?

Data Encryption Standard (DES) is a block cipher with a 56-bit key length that has played a significant role in data security. Data encryption standard (DES) has been found vulnerable to very powerful attacks therefore, the popularity of DES has been found slightly on the decline. DES is a block cipher and encrypts data in blocks of size of 64 bits each, which means 64 bits of plain text go as the input to DES, which produces 64 bits of ciphertext. The same algorithm and key are used for encryption and decryption, with minor differences. The key length is 56 bits. 

The basic idea is shown below:

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 8th bit of the key is discarded to produce a 56-bit key. That is bit positions 8, 16, 24, 32, 40, 48, 56, and 64 are discarded. 

Thus, the discarding of every 8th bit of the key produces a 56-bit key from the original 64-bit key.
DES is based on the two fundamental attributes of cryptography: substitution (also called confusion) and transposition (also called diffusion). DES consists of 16 steps, each of which is called a round. Each round performs the steps of substitution and transposition. Let us now discuss the broad-level steps in DES. 

• In the first step, the 64-bit plain text block is handed over to an initial Permutation (IP) function.
• The initial permutation is performed on plain text.
• Next, the initial permutation (IP) produces two halves of the permuted block; saying Left Plain Text (LPT) and Right Plain Text (RPT).
• Now each LPT and RPT go through 16 rounds of the encryption process.
• In the end, LPT and RPT are rejoined and a Final Permutation (FP) is performed on the combined block
• The result of this process produces 64-bit ciphertext.

Initial Permutation (IP)

As we have noted, the initial permutation (IP) happens only once and it happens before the first round. It suggests how the transposition in IP should proceed, as shown in the figure. For example, it says that the IP replaces the first bit of the original plain text block with the 58th bit of the original plain text, the second bit with the 50th bit of the original plain text block, and so on.

This is nothing but  jugglery of bit positions of the original plain text block. the same rule applies to all the other bit positions shown in the figure.

As we have noted after IP is done, the resulting 64-bit permuted text block is divided into two half blocks. Each half-block consists of 32 bits, and each of the 16 rounds, in turn, consists of the broad-level steps outlined in the figure. 

Step 1: Key transformation

We have noted initial 64-bit key is transformed into a 56-bit key by discarding every 8th bit of the initial key. Thus, for each a 56-bit key is available. From this 56-bit key, a different 48-bit Sub Key is generated during each round using a process called key transformation. For this, the 56-bit key is divided into two halves, each of 28 bits. These halves are circularly shifted left by one or two positions, depending on the round.

For example: if the round numbers 1, 2, 9, or 16 the shift is done by only one position for other rounds, the circular shift is done by two positions. The number of key bits shifted per round is shown in the figure.

After an appropriate shift, 48 of the 56 bits are selected. From the 48 we might obtain 64 or 56 bits based on requirement which helps us to recognize that this model is very versatile and can handle any range of requirements needed or provided. for selecting 48 of the 56 bits the table is shown in the figure given below. For instance, after the shift, bit number 14 moves to the first position, bit number 17 moves to the second position, and so on. If we observe the table , we will realize that it contains only 48-bit positions. Bit number 18 is discarded (we will not find it in the table), like 7 others, to reduce a 56-bit key to a 48-bit key. Since the key transformation process involves permutation as well as a selection of a 48-bit subset of the original 56-bit key it is called Compression Permutation.

Because of this compression permutation technique, a different subset of key bits is used in each round. That makes DES not easy to crack.

Step 2: Expansion Permutation

Recall that after the initial permutation, we had two 32-bit plain text areas called Left Plain Text(LPT) and Right Plain Text(RPT). During the expansion permutation, the RPT is expanded from 32 bits to 48 bits. Bits are permuted as well hence called expansion permutation. This happens as the 32-bit RPT is divided into 8 blocks, with each block consisting of 4 bits. Then, each 4-bit block of the previous step is then expanded to a corresponding 6-bit block, i.e., per 4-bit block, 2 more bits are added. 

This process results in expansion as well as a permutation of the input bit while creating output. The key transformation process compresses the 56-bit key to 48 bits. Then the expansion permutation process expands the 32-bit RPT to 48-bits. Now the 48-bit key is XOR with 48-bit RPT and the resulting output is given to the next step, which is the S-Box substitution.

Key Generation

The round-key generator creates sixteen 48-bit keys out of a 56-bit cipher key. The process of key generation is depicted in the following illustration −

The logic for Parity drop, shifting, and Compression P-box is given in the DES description.

Prerequisite –

Simplified Data Encryption Standard is a simple version of Data Encryption Standard having a 10-bit key and 8-bit plain text. It is much smaller than the DES algorithm as it takes only 8-bit plain text whereas DES takes 64-bit plain text. It was developed for educational purpose so that understanding DES can become easy. It is a block cipher algorithm and uses a symmetric key for its algorithm i.e. they use the same key for both encryption and decryption. It has 2 rounds for encryption which use two different keys.

First, we need to generate 2 keys before encryption. After generating keys we pass them to each individual round for s-des encryption. The below diagram shows the steps involved in the s-des algorithm.

Components :

S-DES encryption involves four functions –

1. Initial permutation(IP) –

2. Complex function (fk) –

It is the combination of permutation and substitution functions. The below image represents a round of encryption and decryption. This round is repeated twice in each encryption and decryption.

Components in fk are –

a. Expanded Permutation (EP) –

It takes a 4-bit input and converts it into an 8-bit output.

b. S-boxes (S0 and S1) –

It is a basic component of a symmetric key algorithm that performs substitution.

c. Permutation P4 –

3. Switch (SW) –

4. Inverse of Initial Permutation (IP-1) –

First, we need to generate 2 keys before encryption.

Consider, the entered 10-bit key is - 1 0 1 0 0 0 0 0 1 0

Therefore,

Key-1 is - 1 0 1 0 0 1 0 0
Key-2 is - 0 1 0 0 0 0 1 1

Encryption –

Entered 8-bit plaintext is - 1 0 0 1 0 1 1 1

Step-1:

We perform initial permutation on our 8-bit plain text using the IP table. The initial permutation is defined as –

IP(k1, k2, k3, k4, k5, k6, k7, k8) = (k2, k6, k3, k1, k4, k8, k5, k7)
After ip = 0 1 0 1 1 1 0 1

Step-2:

After the initial permutation, we get an 8-bit block of text which we divide into 2 halves of 4 bit each.

l = 0 1 0 1  and r = 1 1 0 1

On the right half, we perform expanded permutation using EP table which converts 4 bits into 8 bits. Expand permutation is defined as –

EP(k1, k2, k3, k4) = (k4, k1, k2, k3, k2, k3, k4, k1)

After ep = 1 1 1 0 1 0 1 1

We perform XOR operation using the first key K1 with the output of expanded permutation.

Key-1 is - 1 0 1 0 0 1 0 0
(1 0 1 0 0 1 0 0) XOR (1 1 1 0 1 0 1 1) =  0 1 0 0 1 1 1 1
After XOR operation with 1st Key = 0 1 0 0 1 1 1 1

Again we divide the output of XOR into 2 halves of 4 bit each.

l = 0 1 0 0  and r = 1 1 1 1

We take the first and fourth bit as row and the second and third bit as a column for our S boxes.

S0 = [1,0,3,2
      3,2,1,0
      0,2,1,3
      3,1,3,2]

S1=  [0,1,2,3
      2,0,1,3
      3,0,1,0
      2,1,0,3]

For l = 0 1 0 0
row = 00 = 0, column = 10 = 2
S0 = 3 = 11

For r = 1 1 1 1
row = 11 = 3, column = 11 = 3
S1 = 3 = 11

After first S-Boxes combining S0 and S1 = 1 1 1 1

S boxes gives a 2-bit output which we combine to get 4 bits and then perform permutation using the P4 table. P4 is defined as –

P4(k1, k2, k3, k4) = (k2, k4, k3, k1)
After P4 = 1 1 1 1

We XOR the output of the P4 table with the left half of the initial permutation table i.e. IP table.

(0 1 0 1) XOR (1 1 1 1) = 1 0 1 0
After XOR operation with left nibble of after ip = 1 0 1 0

We combine both halves i.e. right half of initial permutation and output of ip.

Combine 1 1 0 1 and 1 0 1 0
After combine = 1 0 1 0 1 1 0 1

Step-3:

Now, divide the output into two halves of 4 bit each. Combine them again, but now the left part should become right and the right part should become left.

After step 3 = 1 1 0 1 1 0 1 0

Step-4:

Again perform step 2, but this time while doing XOR operation after expanded permutation use key 2 instead of key 1.

* 4 1 2 3 2 3 4 1 pointed EP Sequence

Expand permutation is defined as - 4 1 2 3 2 3 4 1
After second ep = 0 1 0 1 0 1 0 1
After XOR operation with 2nd Key = 0 0 0 1 0 1 1 0
After second S-Boxes = 1 1 1 1

P4 is defined as - 2 4 3 1
After P4 = 1 1 1 1

After XOR operation with left nibble of after first part = 0 0 1 0
After second part = 0 0 1 0 1 0 1 0

l = 1 1 0 1  and r = 1 0 1 0

On the right half, we perform expanded permutation using EP table which converts 4 bits into 8 bits. Expand permutation is defined as –

EP(k1, k2, k3, k4) = (k4, k1, k2, k3, k2, k3, k4, k1)
After second ep = 0 1 0 1 0 1 0 1

We perform XOR operation using second key K2 with the output of expanded permutation.

Key-2 is - 0 1 0 0 0 0 1 1
(0 1 0 0 0 0 1 1) XOR (0 1 0 1 0 1 0 1) =  0 0 0 1 0 1 1 0
After XOR operation with 2nd Key = 0 0 0 1 0 1 1 0

Again we divide the output of XOR into 2 halves of 4 bit each.

l = 0 0 0 1  and r = 0 1 1 0

We take the first and fourth bit as row and the second and third bit as a column for our S boxes.

S0 = [1,0,3,2
      3,2,1,0
      0,2,1,3
      3,1,3,2]

S1 = [0,1,2,3
      2,0,1,3
      3,0,1,0
      2,1,0,3]

For l = 0 0 0 1
row = 01 = 1 , column = 00 = 0
S0 = 3 = 11

For r = 0 1 1 0
row = 00 = 0 , column = 11 = 3
S1 = 3 = 11

After first S-Boxes combining S0 and S1 = 1 1 1 1

S boxes gives a 2-bit output which we combine to get 4 bits and then perform permutation using the P4 table. P4 is defined as –

P4(k1, k2, k3, k4) = (k2, k4, k3, k1)
After P4 = 1 1 1 1

We XOR the output of the P4 table with the left half of the initial permutation table i.e. IP table.

(1 1 0 1) XOR (1 1 1 1) = 0 0 1 0
After XOR operation with left nibble of after first part = 0 0 1 0

We combine both halves i.e. right half of initial permutation and output of ip.

Combine 1 0 1 0 and 0 0 1 0
After combine = 0 0 1 0 1 0 1 0
After second part = 0 0 1 0 1 0 1 0

Step-5:

Perform inverse initial permutation. The output of this table is the cipher text of 8 bit.

Output of step 4 : 0 0 1 0 1 0 1 0

Inverse Initial permutation is defined as –

IP-1(k1, k2, k3, k4, k5, k6, k7, k8) = (k4, k1, k3, k5, k7, k2, k8, k6)

8-bit Cipher Text will be = 0 0 1 1 1 0 0 0

Simplified Data Encryption Standard (S-DES) is a simple version of the DES Algorithm. It is similar to the DES algorithm but is a smaller algorithm and has fewer parameters than DES. It was made for educational purposes so that understanding DES would become simpler.  It is a block cipher that takes a block of plain text and converts it into ciphertext.  It takes a block of 8 bit.

It is a symmetric key cipher i.e. they use the same key for both encryption and decryption. In this article, we are going to demonstrate key generation for s-des encryption and decryption algorithm. We take a random 10-bit key and produce two 8-bit keys which will be used for encryption and decryption.

Key Generation Concept: In the key generation algorithm, we accept the 10-bit key and convert it into two 8 bit keys. This key is shared between both sender and receiver. 

In the key generation, we use three functions:

1. Permutation P10

2. Permutation P8

3. Left Shift

Step 1: We accepted a 10-bit key and permuted the bits by putting them in the P10 table.

Key = 1 0 1 0 0 0 0 0 1 0
(k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) = (1, 0, 1, 0, 0, 0, 0, 0, 1, 0)

P10 Permutation is: P10(k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) = (k3, k5, k2, k7, k4, k10, k1, k9, k8, k6) 
After P10, we get 1 0 0 0 0 0 1 1 0 0

Step 2: We divide the key into 2 halves of 5-bit each.

l=1 0 0 0 0, r=0 1 1 0 0

Step 3: Now we apply one bit left-shift on each key.

l = 0 0 0 0 1, r = 1 1 0 0 0

Step 4: Combine both keys after step 3 and permute the bits by putting them in the P8 table. The output of the given table is the first key K1.

After LS-1 combined, we get 0 0 0 0 1 1 1 0 0 0
P8 permutation is: P8(k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) = (k6, k3, k7, k4, k8, k5, k10, k9)
After P8, we get Key-1 : 1 0 1 0 0 1 0 0

Step 5: The output obtained from step 3 i.e. 2 halves after one bit left shift should again undergo the process of two-bit left shift.

Step 3 output - l = 0 0 0 0 1, r = 1 1 0 0 0 
After two bit shift - l = 0 0 1 0 0, r = 0 0 0 1 1

Step 6: Combine the 2 halves obtained from step 5 and permute them by putting them in the P8 table. The output of the given table is the second key K2.

After LS-2 combined = 0 0 1 0 0 0 0 0 1 1
P8 permutation is: P8(k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) = (k6, k3, k7, k4, k8, k5, k10, k9)
After P8, we get Key-2 : 0 1 0 0 0 0 1 1

Final Output:

Key-1 is: 1 0 1 0 0 1 0 0
Key-2 is: 0 1 0 0 0 0 1 1

회사에서 Cryptography 관련된 자료를 다시 공부하라고 넘겨주셧는데 자료가 굉장히 불친절하게 되어 있었다. 정확하게는 왜때문에 어떤 과정이 나오는지에 대한 부분이 잘 안나와 있기 때문이었다.

Simple DES 라서 사실상 쓰이는 일은 없겠지만 (물론 있을 수도 있고), 오랜만에 봐서 빡쳐가지고 찾아보고 가져왔다.

이건 Key Generation 을 하는 딱 1부 파트이기 때문에, 실제 Cipher Suite 인 Cipher 는 다음 글에