Appendix E: Block Ciphers

A block cipher is a cryptographic primitive that can be used for implementing symmetric encryption mechanisms. It can be also used in the construction of other security mechanisms, including the MAC schemes.

The cryptographic literature provides many examples of block ciphers; the most used are the Data Encryption Standard (DES) [1], IDEA, RC-5, and Blowfish.

E.1 Definition and parameters

A block cipher is an encryption algorithm E described by a one-to-one invertible function parameterized by a secret key K of k bits, which maps plaintext blocks P _i of n bits to ciphertext blocks C _i of the same bit-length, C _i = E ( K )[ P _i ]. The decryption algorithm D is the inverse mapping of the function E , D = E ^{ˆ’ 1} , which computes the plaintext block P _i from the ciphertext block C _i using the same secret key K as a parameter, P _i = E ^{ˆ’ 1} ( K )[ D _i ].

When encrypting a message M of arbitrary bit-length l using a block cipher, a padding operation could be applied to the message M before splitting it into blocks of appropriate bit-length.

• When the length l of the message M is a multiple of n , the message can be directly split into a number of t blocks, such that l = t * n . There are padding schemes, like that proposed in EMV ¢ [2], that can add one single block with a predefined structure at the end of the given message, such that the bit-length l ² of the padded message M ² becomes l ² = ( t + 1)* n .

• When the length of the message M is not divisible by n , the message M is first padded with a number of bits such that the length l ² of the padded message M ² is divisible by n . Depending on the padding scheme, the number of resulting blocks is t = ˆ l / n ‰ or t = ˆ l / n ‰ + 1, where ˆ l / n ‰ denotes the smallest positive integer greater than the result of the division l / n . In this case the length of the padded message is l ² = t * n .

After appropriately padding, the plaintext message M is divided into a number of i plaintext blocks of the fixed bit-length n , P ₁ , , P _t . For plaintext messages exceeding one block in length, various modes of operations for block ciphers can be used, as described in Section E.2.

The block size ( n ) impacts on the security of a block cipher. The larger the block size, the better its security (see the CBC operation mode in Section E.2). The block size also influences the complexity of the block cipher, for which a larger block size reflects in a more complex algorithm and in a more costly implementation. The block size can also affect performance, when padding is required.

The key size ( k ) defines an upper bound on the security of a block cipher by considering the brute force attack, which consists of the exhaustive search of the secret key K : the attacker tries all possible keys. The attacker only needs a single matching pair plaintext block, ciphertext block produced with that key. Longer keys increase the efforts of the attackers performing exhaustive key search. Longer keys, however, involve additional operational costs determined by the generation, transmission, and storage of these keys.

The values of the block size and key size parameters are given for several well-known block ciphers. The block cipher DES operates on blocks of n = 64 bits with a key of k = 56 bits. The block cipher IDEA uses a key of k = 128 bits to encrypt blocks of n = 64 bits. Rijndael, which has recently been chosen as the block cipher of the Advanced Encryption Standard (AES) [3], is designed with the goal of accepting various key sizes of k = 128, 192, 256 bits, while the block size is n = 128. The Rijndael, designed by Daemen and Rijmen was chosen in October 2000 by the NIST in United States as the DES replacement.