DES - Data Encryption Standard

A little bit of theory

The Data Encryption Standard (DES) algorithm, adopted by the U.S. government in  July 1977. It was reaffirmed in 1983, 1988, and 1993. DES is a block cipher that transforms 64-bit data blocks under a 56-bit secret key, by means of permutation and substitution. It is officially described in FIPS PUB 46.

DES is a "symmetrical" encryption algorithm: same key that is used for encryption is used to decrypt the message.

The DES algorithm is still widely used and is considered reasonably secure. There is no feasible way to break DES as is using a 64-bit (8 characters) block cipher.  There are 70,000,000,000,000,000 (seventy quadrillion) possible keys of 56 bits. However, due to the advance in the computational power of super-computers, an exhaustive search of 2^55 steps on average, can retrieve the key used in the encryption (if the key is changed frequently, the risk of this event is greatly diminished).  Because of this it is common practice to protect data using Triple-DES. See FIPS PUB 74 for more details regarding the strength of this algorithm against various threats.

Triple-DES is a secure variation of the Data Encryption Standard first developed by IBM, and later in 1977 adopted by the U.S. government. 
Triple-DES is a 192 bit (24 characters) cipher that uses three separate 64 bit keys and encrypts data using the DES algorithm three times.
 

Theoretical procedure (based on an article by Matthew Fischer November published in 1995):

(practical example)

1 Process the key.

1.1 Get a 64-bit key from the user. (Every 8th bit (the least significant bit of each byte) is considered a parity bit. For a key to have correct parity, each byte should contain an odd number of "1" bits.) This key can be entered directly, or it can be the result of hashing something else. There is no standard hashing algorithm for this purpose.

1.2 Calculate the key schedule.

1.2.1 Perform the following permutation on the 64-bit key. (The parity bits are discarded, reducing the key to 56 bits. Bit 1 (the most significant bit) of the permuted block is bit 57 of the original key, bit 2 is bit 49, and so on with bit 56 being bit 4 of the original key.)

1.2.2 Split the permuted key into two halves. The first 28 bits are called C[0] and the last 28 bits are called D[0].

1.2.3 Calculate the 16 sub keys. Start with i = 1.

1.2.3.1 Perform one or two circular left shifts on both C[i-1] and D[i-1] to get C[i] and D[i], respectively. The number of shifts per iteration are given in the table below.

Iteration # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Left Shifts 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

1.2.3.2 Permute the concatenation C[i]D[i] as indicated below. This will yield K[i], which is 48 bits long.

1.2.3.3 Loop back to 1.2.3.1 until K[16] has been calculated.

2 Process a 64-bit data block.

2.1 Get a 64-bit data block. If the block is shorter than 64 bits, it should be padded as appropriate for the application.

2.2 Perform the following permutation on the data block.

2.3 Split the block into two halves. The first 32 bits are called L[0], and the last 32 bits are called R[0].

2.4 Apply the 16 sub keys to the data block. Start with i = 1.

2.4.1 Expand the 32-bit R[i-1] into 48 bits according to the bit-selection function below.

2.4.2 Exclusive-or E(R[i-1]) with K[i].

2.4.3 Break E(R[i-1]) xor K[i] into eight 6-bit blocks. Bits 1-6 are B[1], bits 7-12 are B[2], and so on with bits 43-48 being B[8].

2.4.4 Substitute the values found in the S-boxes for all B[j]. Start with j = 1. All values in the S-boxes should be considered 4 bits wide.

2.4.4.1 Take the 1st and 6th bits of B[j] together as a 2-bit value (call it m) indicating the row in S[j] to look in for the substitution.

2.4.4.2 Take the 2nd through 5th bits of B[j] together as a 4-bit value (call it n) indicating the column in S[j] to find the substitution.

2.4.4.3 Replace B[j] with S[j][m][n].

2.4.4.4 Loop back to 2.4.4.1 until all 8 blocks have been replaced.

2.4.5 Permute the concatenation of B[1] through B[8] as indicated below.

2.4.6 Exclusive-or the resulting value with L[i-1]. Thus, all together, your R[i] = L[i-1] xor P(S[1](B[1])...S[8](B[8])), where B[j] is a 6-bit block of E(R[i-1]) xor K[i]. (The function for R[i] is more concisely written as, R[i] = L[i-1] xor f(R[i-1], K[i]).)

2.4.7 L[i] = R[i-1].

2.4.8 Loop back to 2.4.1 until K[16] has been applied.

2.5 Perform the following permutation on the block R[16]L[16]. (Note that block R precedes block L this time.)

This has been a description of how to use the DES algorithm to encrypt one 64-bit block. To decrypt, use the same process, but just use the keys K[i] in reverse order. That is, instead of applying K[1] for the first iteration, apply K[16], and then K[15] for the second, on down to K[1].

Summaries:

Key schedule:
C[0]D[0] = PC1(key)
for 1 <= i <= 16
C[i] = LS[i](C[i-1])
D[i] = LS[i](D[i-1])
K[i] = PC2(C[i]D[i])

Encipherment:
L[0]R[0] = IP(plain block)
for 1 <= i <= 16
L[i] = R[i-1]
R[i] = L[i-1] xor f(R[i-1], K[i])
cipher block = FP(R[16]L[16])

Decipherment:
R[16]L[16] = IP(cipher block)
for 1 <= i <= 16
R[i-1] = L[i]
L[i-1] = R[i] xor f(L[i], K[i])
plain block = FP(L[0]R[0])

To encrypt or decrypt more than 64 bits there are four official modes (defined in FIPS PUB 81). One is to go through the above-described process for each block in succession. This is called Electronic Codebook (ECB) mode. A stronger method is to exclusive-or each plaintext block with the preceding ciphertext block prior to encryption. (The first block is exclusive-or'ed with a secret 64-bit initialization vector (IV). This IV is generally a random value that is kept with the key.) This is called Cipher Block Chaining (CBC) mode. The other two modes are Output Feedback (OFB) and Cipher Feedback (CFB).

When it comes to padding the data block, there are several options. One is to simply append zeros. Two suggested by FIPS PUB 81 are, if the data is binary data, fill up the block with bits that are the opposite of the last bit of data, or, if the data is ASCII data, fill up the block with random characters and put the ASCII character for the number of pad characters in the last byte of the block.

The DES algorithm can also be used to calculate cryptographic checksums up to 64 bits long (see FIPS PUB 113). If the number of data bits to be checksummed is not a multiple of 64, the last data block should be padded with zeros. If the data is ASCII data, the most significant bit of each byte should be set to 0. The data is then encrypted in CBC mode with IV = 0. The most significant n bits (where 16 <= n <= 64, and n is a multiple of 8) of the final ciphertext block are an n-bit checksum.


*************************************************************************************************

A practical example of the DES algorithm encryption, by Adrian Grigorof - adrian.grigorof@altairtech.ca.

This is an attempt to show how it actually works in practice - how are bits moved around to perform the theoretical encryption presented above. While there are many applications to perform the DES encryption, I couldn't find an actual example, as simple as it may have been. So, armed with the theory, I went ahead of doing it myself. Please note, this may contain mistakes -  the point of this exercise is to give firewall and VPN administrators an idea of what lies behind the DES acronyms that they use every day.

The sample 64-bit key:
ddd,bbbbbbbb
222,11011110
16,00010000
156,10011100
88,01011000
232,11101000
164,10100100
166,10100110
48,00110000

The 64-bit key is (hex): DE,10,9C,58,E8,A4,A6,30

The original 64-bit key with parity bits

1 1 0 1 1 1 1 0 bits 1-8
0 0 0 1 0 0 0 0 bits 9-16
1 0 0 1 1 1 0 0 bits 17-24
0 1 0 1 1 0 0 0 bits 25-32
1 1 1 0 1 0 0 0 bits 33-40
1 0 1 0 0 1 0 0 bits 41-48
1 0 1 0 0 1 1 0 bits 49-56
0 0 1 1 0 0 0 0 bits 57-64

The original bit positions:

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

The 56-bit key (parity bits stripped)

1 1 0 1 1 1 1
0 0 0 1 0 0 0
1 0 0 1 1 1 0
0 1 0 1 1 0 0
1 1 1 0 1 0 0
1 0 1 0 0 1 0
1 0 1 0 0 1 1 
0 0 1 1 0 0 0

The original positions of the bits after the parity is stripped:

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

The positions of the remained 56 bits after Permuted Choice 1 (PC-1)

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

The permuted 56-bit key:

0 1 1 1 0 1 0
1 0 0 0 1 1 0
0 1 1 0 0 0 1
0 0 0 1 0 0 0
0 1 0 0 0 0 0
1 0 1 1 0 0 1
0 1 0 0 0 1 1
1 0 1 1 1 1 1

Split the permuted key into two halves. The first 28 bits are called C[0] and the last 28 bits are called D[0]. 

C[0]

0 1 1 1 0 1 0
1 0 0 0 1 1 0
0 1 1 0 0 0 1
0 0 0 1 0 0 0

D[0]

0 1 0 0 0 0 0 
1 0 1 1 0 0 1
0 1 0 0 0 1 1
1 0 1 1 1 1 1

Calculate the 16 sub keys. Start with i = 1
Perform one or two circular left shifts on both C[i-1] and D[i-1] to get C[i] and D[i], 
respectively. The number of shifts per iteration are given in the table below. 

Iteration # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Left Shifts 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1


C[0]
0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0

D[0]
0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1

C[1]
1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0

D[1]
1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0

C[2]
1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1

D[2]
0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 

C[3]
0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 

D[3]
0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 

C[4]
0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 

D[4]
0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 

C[5]
0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 

D[5]
0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 

C[6]
0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 

D[6]
1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 1 

C[7]
1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 

D[7]
0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 1 1 0 

C[8]
0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 

D[8]
0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 

C[9]
1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 

D[9]
1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 

C[10]
0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 

D[10]
0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 

C[11]
0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 

D[11]
1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 

C[12]
0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 

D[12]
1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 

C[13]
0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 

D[13]
1 1 1 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 

C[14]
0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 

D[14]
1 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 

C[15]
0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 

D[15]
1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 

C[16]
0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 

D[16]
0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 

Permute the concatenation C[i]D[i] as indicated below. This will yield K[i], which is 48 bits long. 

Permuted Choice 2 (PC-2)

14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32

C[0]D[0]
0 1 1 1 0 1 0 bits 1-7
1 0 0 0 1 1 0 bits 8-14
0 1 1 0 0 0 1 bits 15-21
0 0 0 1 0 0 0 bits 22-28
0 1 0 0 0 0 0 bits 29-35
1 0 1 1 0 0 1 bits 36-42
0 1 0 0 0 1 1 bits 43-49
1 0 1 1 1 1 1 bits 50-56

K[0]
0 1 0 0 0 0
1 0 0 1 1 0
0 0 1 1 0 1
1 0 0 0 1 1
0 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 0 1
0 1 1 1 0 0

Loop back until K[16] has been calculated (for this example, the calculation of the rest of the K[x] is skipped)

Process a 64-bit data block. 

Get a 64-bit data block. If the block is shorter than 64 bits, it should be padded as appropriate for the application. 

Sample 64 bit data: 
86,01010110 
233,11101001 
158,10011110 
172,10101100 
222,11011110 
95,01011111 
244,11110100 
177,10110001 

The original bit positions:

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

Perform the following permutation on the data block. 

Initial Permutation (IP) 

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

Original data:
0 1 0 1 0 1 1 0 bits 1-8
1 1 1 0 1 0 0 1 bits 9-16
1 0 0 1 1 1 1 0 bits 17-24
1 0 1 0 1 1 0 0 bits 25-32
1 1 0 1 1 1 1 0 bits 33-40
0 1 0 1 1 1 1 1 bits 41-48
1 1 1 1 0 1 0 0 bits 49-56
1 0 1 1 0 0 0 1 bits 57-64

Permuted data:
0 1 1 1 0 0 1 1
1 1 1 1 0 1 0 1
0 1 1 1 1 1 0 1
1 0 1 0 0 0 1 0
1 1 0 1 1 1 1 0
1 1 0 0 1 0 1 0
0 0 1 1 1 1 1 0
0 0 1 1 0 1 0 1

Split the block into two halves. The first 32 bits are called L[0], and the last 32 bits are called R[0]. 

L[0]
0 1 1 1 0 0 1 1
1 1 1 1 0 1 0 1
0 1 1 1 1 1 0 1
1 0 1 0 0 0 1 0

R[0]
1 1 0 1 1 1 1 0
1 1 0 0 1 0 1 0
0 0 1 1 1 1 1 0
0 0 1 1 0 1 0 1

Apply the 16 sub keys to the data block. Start with i = 1. Expand the 32-bit R[i-1] into 48 bits according to the bit-selection function below. 

Expansion (E) 

32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1

R[0]
1 1 0 1 1 1 1 0 bites 1-8
1 1 0 0 1 0 1 0 bites 9-16
0 0 1 1 1 1 1 0 bites 17-24
0 0 1 1 0 1 0 1 bites 25-32

1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32

Expanded R[0] or E(R[0])
1 1 0 1 1 1
1 1 1 1 0 1
0 1 1 0 0 1
0 1 0 1 0 0
0 0 0 1 1 1
1 1 1 1 0 0
0 0 0 1 1 0
1 0 1 0 1 1

Exclusive-or E(R[i-1]) with K[i]. 

E(R[0])
1 1 0 1 1 1
1 1 1 1 0 1
0 1 1 0 0 1
0 1 0 1 0 0
0 0 0 1 1 1
1 1 1 1 0 0
0 0 0 1 1 0
1 0 1 0 1 1

K[0]
0 1 0 0 0 0 1 1 0 1 1 1
1 0 0 1 1 0 1 1 1 1 0 1
0 0 1 1 0 1 0 1 1 0 0 1
1 0 0 0 1 1 0 1 0 1 0 0
0 1 0 0 0 1 0 0 0 1 1 1
1 0 0 0 0 1 1 1 1 1 0 0
1 1 1 1 0 1 0 0 0 1 1 0
0 1 1 1 0 0 1 0 1 0 1 1

XOR: If one, and only one, of the expressions evaluates to True, result is True

Perform Exclusive-or E(R[i-1]) with K[i]. 

E(R[i-1]) xor K[i] 

1 0 0 1 1 1
0 1 1 0 1 1
0 1 1 1 0 0
1 1 1 0 0 1
0 1 1 1 1 0
0 1 1 1 0 1
1 1 1 0 1 1
1 1 0 1 1 1

Break E(R[i-1]) xor K[i] into eight 6-bit blocks. 
Bits 1-6 are B[1], bits 7-12 are B[2], and so on with bits 43-48 being B[8]. 

B[1]
1 0 0 1 1 1

B[2] 
0 1 1 0 1 1

B[3]
0 1 1 1 0 0

B[4]
1 1 1 0 0 1

B[5]
0 1 1 1 1 0

B[6]
0 1 1 1 0 1

B[7]
1 1 1 0 1 1

B[8]
1 1 0 1 1 1

Substitute the values found in the S-boxes for all B[j]. Start with j = 1. 
All values in the S-boxes should be considered 4 bits wide. 

Take the 1st and 6th bits of B[j] together as a 2-bit value (call it m) 
indicating the row in S[j] to look in for the substitution. 
Take the 2nd through 5th bits of B[j] together as a 4-bit value (call it n) 
indicating the column in S[j] to find the substitution. 


B[1]
1 0 0 1 1 1
1 2 3 4 5 6 bit order

m = 11 = 3
n = 0011 = 3

Replace B[j] with S[j][m][n]. 


Substitution Box 1 (S[1]) 

14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

S[1][3][3] = 2

B[2] 
0 1 1 0 1 1

m = 01 = 1
n = 1101 = 13

S[2] 

15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 

S[2][1][13] = 9

B[3]
0 1 1 1 0 0

m = 00 = 0
n = 1110 = 14

S[3] 

10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12

S[3][0][14] = 2

B[4]
1 1 1 0 0 1

m = 11 = 3
n = 1100 = 12

S[4] 

7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14

S[4][3][12]=12

B[5]
0 1 1 1 1 0

m = 00 = 0
n = 1111 = 15

S[5] 

2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3

S[5][0][15] = 9

B[6]
0 1 1 1 0 1

m = 01 = 1
n = 1110 = 14

S[6] 

12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13

S[6][1][14]=3

B[7]
1 1 1 0 1 1

m = 11 = 3
n = 1101 = 13

S[7] 

4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12

S[7][3][13] = 2

B[8]
1 1 0 1 1 1

m = 11 = 3
n = 1011 = 11

S[8] 

13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11

S[8][3][11] = 0

Permute the concatenation of B[1] through B[8] as indicated below. 

B[1] = S[1][3][3] = 2 = 0010
B[2] = S[2][1][13] = 9 = 1001
B[3] = S[3][0][14] = 2 = 0010
B[4] = S[4][3][12] = 12 = 1100
B[5] = S[5][0][15] = 9 = 1001
B[6] = S[6][1][14] = 3 = 0011
B[7] = S[7][3][13] = 2 = 0010
B[8] = S[8][3][11] = 0 = 0000

B[1-8]

0 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32


Permutation P 

16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25


P(S[1](B[1])...S[8](B[8]))
0 0 1 0
0 0 0 1
0 0 1 0
1 0 0 0
0 1 1 1
0 1 1 0
0 1 0 0
0 1 0 0

Exclusive-or the resulting value with L[i-1]. 
Thus, all together, your R[i] = L[i-1] xor P(S[1](B[1])...S[8](B[8])), 
where B[j] is a 6-bit block of E(R[i-1]) xor K[i]. 
(The function for R[i] is more concisely written as, R[i] = L[i-1] xor f(R[i-1], K[i]).) 

L[0] xor P(S[1](B[1])...S[8](B[8]))

L[0] (see above)
0 1 1 1 0 0 1 1
1 1 1 1 0 1 0 1
0 1 1 1 1 1 0 1
1 0 1 0 0 0 1 0

L[0]

0 1 1 1
0 0 1 1
1 1 1 1
0 1 0 1
0 1 1 1
1 1 0 1
1 0 1 0
0 0 1 0

xor with

P(S[1](B[1])...S[8](B[8]))
0 0 1 0
0 0 0 1
0 0 1 0
1 0 0 0
0 1 1 1
0 1 1 0
0 1 0 0
0 1 0 0

R[1]
0 1 0 1
0 0 1 0
1 1 0 1
1 1 0 1
0 0 0 0
1 0 1 1
1 1 1 0
0 1 0 0