Block Ciphers PDF

Here is the transcription of the image to a structured markdown format. ### Feistel ciphers and DES An interesting property of a Feistel cipher is that the round function is invertible regardless of the choice of the function in the box marked F. Encryption: $L_i = R_{i-1}$ $R_i = L_{i-1} \oplus ...

Here is the transcription of the image to a structured markdown format. ### Feistel ciphers and DES An interesting property of a Feistel cipher is that the round function is invertible regardless of the choice of the function in the box marked F. Encryption: $L_i = R_{i-1}$ $R_i = L_{i-1} \oplus F(k_i, R_{i-1})$ Hence, the decryption can be performed via: $R_i = L_{i-1}$ $L_{i-1} = R_i \oplus F(k_i, L_i)$ The image shows the encryption and decryption process of a Feistel cipher using round keys to generate the cyphertext block from the plaintext block. * Round key $k_i$, a key generated every round. * We can choose any function F and we still obtain an encryption function which can be inverted using the secret key. * Same code is used for both encryption and decryption. * In order to obtain a secure cipher we still need to take care with: * How the round keys are generated. * How many rounds to use. * The round function F. ### Properties of DES The basic properties of the DES cipher are that it is a variant of the Feistel design in which: * The number of rounds $r$ is 16 * The block length $n$ is 64 bits * The key length is 56 bits * Round keys $k_i$'s are each 48 bits Note that a key length of 56 bits is insufficient for many modern applications, hence often one uses triple DES or 3 DES. The image shows a 3DES encryption scheme with encryption using $K_1, K_2, K_3$ and decryption using $K_3, K_2, K_1$ 3 DES has a key length of 56+56+56 = 168 bits. There exists another way of using DES 3 times, but using 2 keys, instead of 3, giving rise to a key length of 112 bits. In this 2 key version of 3DES, one uses the 3 DES basic structure but with $K_1, K_3$. 2 key 3DES is not as secure as 3 key DES. One can break with $2^{56}$ effort. In summary the DES cipher operates on 64 bits of plaintext in the following manner: * Perform an initial permutation. * Split the blocks into the left and right half. * Perform 16 rounds of identical operations. * Join the half blocks back together. * Perform a final inverse operation. * Key schedule provides 16 round keys of 48 bits in length by selecting 48 bits from the 56-bit main key. ### Function F The round consists of the following six stages: * Expansion permutation: 32 bits is expanded and permuted to 48 bits. * Removing dependence: small change in the plaintext generates a completely different ciphertext. * Round key Addition: The 48-bit output from the expansion permutation is exclusive or'd with the round key (48bit). This is the only place where the key is used in the algorithm (different key = different ciphertext). * Splitting: The resulting 48 bit value is split into 8 lots of 6-bit values. * S-boxes: Each 6-bit value is passed into one of 8 different S-boxes (Substitution Box) to produce a 4-bit result. The S-boxes represent the non-linear component of the DES algorithm, and their design is a major contributor to the algorithm's security. Each S-box is a look-up table of 4 rows and 16 columns. Bits 1 and 6 generate the row number, whilst bits 2,3,4 and 5 specify the column number. The output of each S-box is the value held in that element in the table. * P-Box: We now have 8 lots of 4 bit-outputs which are then combined into a 32-bitvalue and permuted to form the output of the function F. The image shows the encryption process of a block of plaintext LoRo, and how it iterates though 16 identical rounds to produce ciphertext $L_rR_r$. DES Key Schedule: The DES key schedule takes the 56-bit key, which is actually input as a bitstring of 64 bits, comprising the key and 8 parity bits, for error detection.The parity bits are in bit positions 8, 16, 24, 32, 40, 48, 56, 64 and ensure that each byte of the key contains an odd number of bits set to one. ### AES AES is a block cipher which does not rely on the basic design of the Feistel cipher; instead it is designed as a substitution- permutation function. AES does have a number of similarities with DES. Block ciphers based on the SP-network design consist of a series of rounds, each of which consists of a key addition phase, a substitution phase and a permutation phase. The idea is that phase aims to diffuse differences in the input to differences in the output as much as possible performing diffusion. The substitution phase aims to introduce as much non-linearity or confusion into other parts of the state as quickly as possible. The avalanche effect aims to produce an avalanche effect by spreading the bits. Rijndael was a parameterized algorithm, in that it could operate on block sizes of 128, 192 or 256 bits, but in the final AES standard the block size was fixed at 128 bits. However, AES does support keys of size 128, 192 or 256 bits. For each size a different number of rounds is specified. * 128 bit - 10 rounds * 192 bit- 12 rounds * 256 bit- 14 rounds US Federal standard released 4 recommended ways of using DES for data encryption. The 4 modes are: * ECB mode: This is the simple to use, but suffers from possibly deletion and insertion attacks. * CBC mode: This is probably the best of the original modes of operation. * OFB mode: This mode turns a block cipher into a stream cipher. It has because of the bit flip. * CFB mode: This mode again turns a block cipher into a stream cipher. Let ECB[F], CBC[F], OFB[F], CFB[F] denote a mode of operation when instantiated with the function F, which could be a blockcipher, a pseudo - random permutation or a pseudo-random function. ### ECB mode The simplest way to use a blockcipher. The data to be encrypted m is divided into blocks of n bits $m_1, m_2, m_3...$ with the last block padded if needed. The ciphertext blocks $C_1, C_2, C_3...$ are then defined as follows: $C_i = E_k(m_i)$ * If $m_i = m_j$ then $C_i = C_j$ (same input are mapped to the same output) * Stereotyped beginnings and endings of messages are common. * We could simply delete blocks from the message. * The encrypted blocks can be used in a replay attack. * ECB mode is deterministic. ### CBC mode (Cipher Block Chaining Mode) One way of countering the problem with ECB mode is to chain the cipher, and in this way to add context of each ciphertext block. Again the plainteset must be divided into a series of blocks: $m_1,m_2,...m_g$, padding may be added to the last block to make the plaintext length a multiple of the block length. * Encryption: * $C_1 = E_k(IV \oplus m_1)$ * $C_i = E_k(m_i\oplus C_{i-1}), for i>1 $ * Output ciphertext $IV||C_1||C_2...$ * Decryption * $m_1= D_k (C_1)\oplus IV$ * $m_i = D_k(C_i)\oplus C_{i-1} ,\text{for } i >= 1$ With ECB mode, a single bit error in transmission of the ciphertext will result in a whole block being decrypted wrongly, whilst in CBC mode we see that not only will we decrypt a whole block incorrectly, but the error will also affect a single bit of the next block. * We require an IV * We think the IV should be a nonce. ### OFB Mode (Output Feedback Mode) It enables a block cipher to be used as a steam cipher. We use the black cipher to create the heystream, n bits at a time, where n is the block size. Again we divide the plaintext into a series of blocks, each block beng m-bits long $Y_0 = IV$ $c_i = Y_i \oplus m_i$ $Y_{i+1} = E(Y_i)$ The output ciphertext is $IV||C_1||C_2$ Decryption is performed similarly ### CFB mode (cipher Feedback Mode) $Y_0 = IV$ $Y_i = m_i \oplus C_{i-1}$ Recall that in OFB mode, the heystream was generated by encypting IV and then iteratively encrypting the output from the, previous encryption. In CFB mode the key stream output is produced by the encryption of the ciphertext ### CTR mode(Counter Mode) This combines many of the advantages of ECB mode, but without most of the disadvantages. We first select a public IV, or counter, which is chosen differently for each message encrypted under the fixed key k Encryption is done in the following way: $C_i = m_i \oplus E_k (IV + i)$ $C = IV || C_1 || C_2 || C_3$ ### Difference Between Stream Cipher and Block Cipher 1. Definition * Stream Cipher: Encrypts data one bit or byte at a time in a continuous stream. * Block Cipher: Encrypts data in fixed-size blocks (64-bit, 128-bit) at a time. 2. Working mechanism * Stream Cipher: Converts plaintext into ciphertext bit by bit (or byte) using a keystream * Block Cipher: Divides plaintext into fixed-size blocks and encrypts each block separately, often using the one key * Example algorithms * Stream Cipher : RC4 (used in GSM encryption) * Block ciphers : AES, DES, 3DES *Streamcipher: More vulnerable to attacks if the same key stream is used multiple times.