Block ciphers

Specifically, a block cipher \(F\) is a deterministic algorithm that works as follows:

Input: \( K, M \) \(K\): A fixed-length encryption key \(M\): A fixed-length plaintext block. Output: \(C\) \(C\): A fixed-length ciphertext block. Requirement The length of M is fixed, and it's the same as the length of C. We call the length of M (= the length of C) as the block size. For a block cipher \(F\), we will use the following notation: \[ C \leftarrow F(K, M) \]

Sometimes we will also use the following short-handed notation when discussing the key is less important: \[ C \leftarrow F_K(M) \] Block cipher = Pseudorandom permutation A block cipher is also called a pseudorandom permutation. For every key \(K\), it hold that \( F_K: \{0,1\}^\ell \rightarrow \{0,1\}^\ell \) is a permutation. The permutation is pseudorandom, which means that it looks random even to the computers although it is not truly random in the strict mathematical sense. Therefore, unless you have a key, given a ciphertext block, which looks random, you cannot know what the corresponding the plaintext block is.

Decryption

AES (Advanced Encryption Standard)

AES became effective as a federal government standard on May 26, 2002 after approval by the Secretary of Commerce. AES is included in the ISO/IEC 18033-3 standard. AES is available in many different encryption packages, and is the first publicly accessible and open cipher approved by the National Security Agency (NSA) for top secret information when used in an NSA approved cryptographic module . See the following for the key length, and the block size.

Mode of Operations: Encrypting a long message

OpenSSL

sudo apt install openssl

Documenation

Electronic Code Book (ECB) Mode

Fig 1. Electronic Code Book (ECB) mode

This is the simplest mode of operation: directly apply the block cipher to each plaintext block. \( {\sf Gen} \): Choose a random key \( K \) uniformly at random from \( \{ 0, 1 \}^n \) . \( {\sf Enc}_K(M_1, M_2, \ldots, M_m) \): Output \( ( F_K(M_1), F_K(M_2), \ldots, F_K(M_m) ) \). \( {\sf Dec}_K(C_1, C_2, \ldots, C_m) \): Output \( (F_K^{-1}(C_1), F_K^{-1}(C_2), \ldots, F_K^{-1}(C_m)) \). Insecurity of ECB Mode If you encrypt messages using the ECB mode, the ciphertext will leak information of the underlying plaintext. In the ECB mode, if \( M_i = M_j \), then \( C_i = C_j \) The above statement is true, since we apply the same permutation \( F_K \) to each message. Since \( F_K \) is a deterministic function, if the inputs are the same, the outputs will always be the same.

Example

1. Download pic_original.bmp. It's a picture:

   

2. Execute the following command in the terminal to encrypt the file with the ECB mode:

   openssl enc -aes-128-ecb -in pic_original.bmp -out output_ecb.bin -K 00112233445566778899aabbccddeeff 

   In the above,
   • -aes-128-ecb means encryption with AES-ECB mode, where the length of the key is 128 bits.
   • -in option specifies the input file.
   • -out option specifies the output file.
   • -K option specifies the encryption key. The values should be used the hex string form. That is, the toy key we used here is 0x00112233...ff (16 bytes = 128 bits).
3. Check the first 128 bytes of the first two files:

   $ hexdump -v -n 128 pic_original.bmp 0000000 4d42 d28e 0002 0000 0000 0036 0000 0028 0000010 0000 01cc 0000 0086 0000 0001 0018 0000 0000020 0000 d258 0002 0000 0000 0000 0000 0000 0000030 0000 0000 0000 ffff ffff ffff ffff ffff 0000040 ffff ffff ffff ffff ffff ffff ffff ffff 0000050 ffff ffff ffff ffff ffff ffff ffff ffff 0000060 ffff ffff ffff ffff ffff ffff ffff ffff 0000070 ffff ffff ffff ffff ffff ffff ffff ffff 0000080

   $ hexdump -v -n 128 output_ecb.bin 0000000 84f5 37a4 1698 d97a c529 7360 7038 6a86 0000010 af54 a084 3127 1d87 adae b5c5 c3f2 e1b0 0000020 5906 6599 c30d 0ed9 3a1c bafc 2477 d7e5 0000030 368d 9ff9 86e2 bd31 3388 2321 17f8 515d 0000040 b164 1493 1ac3 5af4 dfcc 3c7e b74d 0d9f 0000050 b164 1493 1ac3 5af4 dfcc 3c7e b74d 0d9f 0000060 b164 1493 1ac3 5af4 dfcc 3c7e b74d 0d9f 0000070 b164 1493 1ac3 5af4 dfcc 3c7e b74d 0d9f 0000080

   Note each line of hexdump is 16 bytes = 128 bits, which is the size of one block of AES. The above actually verifies the following:
   In the ECB mode, if \( M_i = M_j \), then \( C_i = C_j \)

   Q: Why so many ffff ffff ... ffff in the bmp file?

   Answer: R=0xff=255, G=0xff=255, B=0xff=255. White pixel. Check out the picture.
   

4. The first 54 bytes of this bitmap file should contain the legitimate header information. If you're interested in the bitmap format, see wikipedia. Since encryption messes up the header information, we recover the header information by simply overwrite the first 54 bytes of output_ecb.bin with that of pic_original.bmp.

   
   >>> header = open("pic_original.bmp", "rb").read(54)    # read the bmp header from the bmp file  
   >>> data = open("output_ecb.bin", "rb").read()[54:]     # read the ciphertext data part
   >>> open("output_ecb.bmp", "wb").write( header + data ) # write header+data into output_ecb.bmp
   

5. Open output_ecb.bmp file from the file browser. It will look as follows:

   

Cipher Block Chaining (CBC) Mode

Fig 2. Cipher Block Chaining (CBC) mode

To encrypt in this mode, a random initialization vector (IV) is chosen, which is set as the first cipher block \(C_0\). Then, ciphertext blocks are generated by applying the block cipher to the XOR of the current plaintext block and previous ciphertext block. \( {\sf Gen} \): Choose a random key \( K \) uniformly at random from \( \{ 0, 1 \}^n \) . \( {\sf Enc}_K(M_1, M_2, \ldots, M_m) \): Output \( (C_0, C_1, \ldots, C_m) \), where \( C_0 = IV \), where \( IV \) is chosen uniformly at random from \( \{ 0, 1 \}^\ell \) and for \( i = 1, \ldots, m:\) \[C_i = F_K(C_{i-1} \oplus M_i ). \] \( {\sf Dec}_K(C_0, C_1, C_2, \ldots, C_m) \): Output \( (M_1, \ldots, M_m) \), where for \( i = 1, \ldots, m:\) \[M_i = F^{-1}_K(C_i) \oplus C_{i-1}. \]

Security of CBC Mode

If IV is chosen uniformly random, the encryption scheme with CBC mode is
indistinguishable under the chosen plaintext attack.

Example

1. Execute the following command to encrypt the file with the CBC mode:

   openssl enc -aes-128-cbc -in pic_original.bmp -out output_cbc.bin -K 00112233445566778899aabbccddeeff -iv 000102030405060708090a0b0c0d0e0f

2. As we did for the ECB mode, copy the header of the bmp file into the output_cbc.bmp.
3. The file output_cbc.bmp look as follows:

   

Parallelization

Counter (CTR) Mode

Fig 3. Counter (CTR) mode

To encrypt in this mode, a uniform value (ctr) of length \( \ell \) (i.e., the block length) is first chosen. Then, a pseudorandom stream is generated from ctr. \( {\sf Gen} \): Choose a random key \( K \) uniformly at random from \( \{ 0, 1 \}^n \) . \( {\sf Enc}_K(M_1, M_2, \ldots, M_m) \): Choose \( ctr \) uniformly random from \( \{ 0, 1 \}^\ell \). Output \( (C_0, \ldots, C_m) \), where \( C_0 = ctr \) and for \( i = 1, \ldots, m:\) \[ C_i = F_K(ctr+i) \oplus M_i.\] \( {\sf Dec}_K(C_0, C_1, C_2, \ldots, C_m) \): Set \( ctr = C_0 \). Output \( (M_1, \ldots, M_m) \), where for \( i = 1, \ldots, m:\) \[M_i = F_K(ctr+i) \oplus C_i.\]

Parallelization

Security of CTR Mode

If ctr is chosen uniformly random, the encryption scheme with CTR mode is
indistinguishable under the chosen plaintext attack. 

It is important to choose ctr randomly. If the same ctr is ever used again, the same pseudorandom stream will be generated!

Example

1. Execute the following command to encrypt the file with the CTR mode:

   openssl enc -aes-128-ctr -in pic_original.bmp -out output_ctr.bin -K 00112233445566778899aabbccddeeff -iv 000102030405060708090a0b0c0d0e0f

2. As with the other modes, modify the header.
3. The output_ctr.bmp file will look as follows:

   

Padding

$ ls -alF *.bin *.bmp
-rw------- 1 choi choi 184976 Jun 20 03:16 output_cbc.bin
-rw------- 1 choi choi 184974 Jun 20 03:17 output_ctr.bin
-rw------- 1 choi choi 184976 Jun 20 02:10 output_ecb.bin
-rwxrwxrwx 1 choi choi 184974 Jan  5  2016 pic_original.bmp

• ECB and CBC needs padding. Since the size of pic_original.bmp is 184974 = 11560*16 + 14. You need pad two bytes to make the remaining 14 bytes to 16 bytes. So, the output ciphertext will have 184976 bytes.

  The reason that padding is necessary is because \(F\) is a block cipher; the input always has to be a block. (See the picture and understand what this means).

• CTR mode don't need padding. This is because the input to \(F\) is ctr+i, which has nothing to do with the ciphertext or the plaintext.

  The output \(F\) can be easily trimmed to fit into the plaintext/ciphertext length. (See the picture and understand what this means).

Comparison