Application Center - Maplesoft

# The Advanced Encryption Standard and its modes of operation

You can switch back to the summary page by clicking here.

The Advanced Encryption Standard and its modes of operation

José Luis Gómez Pardo

Departamento de Álxebra, Universidade de Santiago

15782 Santiago de Compostela, Spain

e-mail: gomez.pardo@usc.es

Carlos Gómez-Rodríguez

Departamento de Computación, Universidade da Coruña

15071 A Coruña, Spain
e-mail: cgomezr@udc.es

 Version, requirements and copyright Version: 1.1   Requirements: Maple v11 or higher   Copyright Notice: © (2008-2010) José Luis Gómez Pardo, Carlos Gómez-Rodríguez   Legal Notice: The copyright for this application is owned by the authors. Neither Maplesoft nor the authors are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the authors for permission if you wish to use this application in for-profit activities.

Initialization

 >

GF(2 )

AES, like other symmetric block ciphers, is byte-oriented in the sense that the basic processing unit is a byte, i.e., a sequence of 8 bits which can also be thought as an 8-bit string or list, whichever is more convenient (often, in the literature, the perhaps more precise term octet is used instead of byte). Each byte in turn can be identified with the integer it represents in binary and, for this, we shall generally adopt the big-endian convention, meaning that the most significant bit is the leftmost one (here, it is convenient to point out that Maple's function convert/base uses the little-endian convention). Thus we shall often identify the bytes with the (decimal) integers in the 0..255 range. Several of AES operations are based on the arithmetic of the 256-element field GF(2) defined by the irreducible polynomial x + x+ x + x +1 (a good reference for finite fields and their applications is [Lidl-Niederreiter]). The elements of this field are binary polynomials of degree less than or equal to 7, and the field operations are just polynomial addition (in Z2[X], where Z2 = GF(2) = {0,1} is the prime field of characteristic 2) and polynomial multiplication modulo the polynomial specified above (this just means that multiplication in Z2[X] is followed by taking the remainder of division by the irreducible polynomial). The elements of the field can be identified with the binary strings defined by their coefficients and hence with the bytes. In order to make the implementation able to encrypt files of moderate size, the field arithmetic is going to be implemented by means of lookup tables (in the form of Maple's tables or Arrays). These tables are constructed here during the initialization process by using the basics of finite field arithmetic and, in particular, Maple's package GF . The field GF(2) is defined as follows:

 >

We will need some conversion functions to convert the field elements to the different formats. In particular, we want to be able to convert integers in the 0..255 range (i.e., bytes) to lists of 8 bits and vice versa. The next function is used to pass from bytes to lists of bits and, as mentioned, we will use the big-endian convention in which the most significant bit comes first.

 >

The following tables will be helpful to speed up the process of converting between integers in the 0..255 range and 8-bit lists.

 >

Using these tables we define a very efficient conversion between bit lists and bytes regarded as decimal numbers in the 0..255 range (thus, for efficiency, we will use bytetobits instead of byte2bits in the sequel; these functions will be used mainly to apply then to a list by means of map, in other cases we will use the preceding tables directly).

 >

For example, we have:

 >

Another usual and more compact form to represent the bytes and hence also the elements of GF(2) is by means of hex digits, each two-digit hex string corresponding to one byte. More generally, we can represent any list of bytes (as integers in the 0..255 range) by the even-length hex string obtained by concatenating the hex representations of the bytes in the list. We are going to give conversions between bytes or lists of bytes and hex strings that will be used in the encryption/decryption/authentication functions. In particular, these functions can be used to convert between keys given as lists of bytes and keys given as hex strings. To make these conversions faster, we will use tables. Note that Maple's convert/hex function outputs the alphabetic hex digits as upper case letters but we will use lower case letters instead as it is more usual in cryptographic texts and code. We start by building a table (in Array format) with the correspondences between bytes and hex digits.

 >

Based on the above table, the following is a function to convert a list of bytes to a hex string.

 >

Next, we "invert" the preceding table, this time to convert strings formed by two hex digits to the corresponding bytes in integer form and use this table to give the associated function that converts hex strings to lists of bytes:

 >

A quick check that these functions behave as intended is the following:

 >

We will use AES to encrypt and decrypt files. For this purpose, the natural way to proceed is to view a file as a list of bytes, i.e., a list of elements of GF(2).  The FileTools[Binary]  package has functions to read and write binary files by using a hardware integer type and the closest to what we want, which is a list of bytes as integers in the 0..255 range, is obtained by using the integer[1] type. However, these integers range from -128 to 127 and so we must make the conversion after reading the file and before writing it to disk. To read a file to a list of bytes, we use the integer[1] type and convert to bytes by reducing modulo 256:

 >

For the inverse process we want to check, before writing a list of bytes to a file, if a file of the same name already exists and, if this is the case, if it can be overwritten. The following function checks this and prompts the user about the action to take if the file already exists. In this case the user can choose between overwriting the existing file, abort the process or choosing a new file name. The output of the function is either an error message if the operation is aborted or a file name:

 >

Now, to write a list of bytes to a file we have to convert bytes (integers in the 0..255 range) to integers of type integer[1]. One would like to use the function mods(-, 256) but this function does not convert the 0..255 range to the -128..127 range but to the -127..128 range instead. This problem is easily solved as, if one applies mods(-,256) one only needs to take care of converting the 128 byte to -128 instead of keeping its original value. We will do it by using a slight modification of this function, namely the function x -> mods(x+1,256)-1. In order to speed this process up, we build a table to convert bytes to integers in the integer[1] range:

 >

Then the function that writes the byte list to a file is the following one. The input is the list of bytes to be written to the file, the file name (given as a string), a boolean-valued parameter called filecheck and a parameter called logoutput. If the value true is passed to filecheck, the function calls checkfile to check whether a file of the same name exists in the current directory and eventually prompts the user about which action to take. On the other hand, the value of logoutput can be none, file or terminal, and it specifies whether log information (indicating the number of bytes written and the name of the file) is provided and, in this case, whether it is written to a file or to the terminal (i.e., printed on the screen).

 >

To test these functions, let's generate a random list of size slightly less than 16 Kibibytes. We use Mersenne Twister (called from RandomTools:-Generate) instead of Blum-Blum-Shub; the latter is much less efficient and there is no point in using it here:

 >

Let's now write this list of bytes to a file named "testfile" in the current directory:

 >

To check the correct behavior of the file writing and reading functions, we read the file to a list and compare it to the original list:

 >

Next, using the previous conversion functions and bearing in mind that, later on, we will give encryption/authentication functions that accept as input several types of messages, we give functions to convert messages which can be either ordinary text strings or hex strings or files, to lists of bytes or, in other words, to lists of elements of GF(2) (note that a hex string is different from ordinary text in that it translates to the list of bytes given by hexstringtobytes instead of the ASCII codes given by convert/bytes which are used in the ordinary text case). As mentioned above, we use lower case for the alphabetic hex digits appearing in hex strings but we want that the functions that take hex strings as input also accept the equivalent version that uses upper case letters. For this reason, in the next function, StringTools:-LowerCase is called before applying hexstringtobytes.

 >

To go in the opposite direction, we also give a function to convert a list of bytes to a message in the specified format. Note that, when using this function, one must be careful if the 0 byte belongs to the list to be converted because in that case the conversion will be truncated at this point (this aspect will be discussed in more detail below, in the section dealing with text encryption and decryption).

 >

Finally, by combining the file/bytes and bytes/string conversions, we give functions to write a (hex or text) string to a (binary) file or to read a file as a string.

 >
 >

To check these functions we start with a string containing a quote from Octavio Paz with a lot of punctuation and diacritical marks:

 >

We write this string to a file named "paz.txt", then we read the file to a string which is compared to the original string:

 >

Next, we consider a hex string:

 >

The next function will play an auxiliary role in several functions where a key or a seed that can be either given as a hexadecimal string or an integer is used. It checks whether the input is a string and, if so, whether it is a hexadecimal string and, in that case, it converts it to an integer.

 >

The BitXor operation

When the elements of GF(2) are regarded as integers in the 0..255 range, the sum in GF(2) is just the bitwise Xor or BitXor. This operation is frequently used in the AES algorithm and hence it is convenient to have it efficiently implemented. As Maple v11 does not have BitXor natively implemented for integers, the easier solution is just to use the package GF and define the sum in the field F = GF(2) as:

However, to make the operation faster, we will implement it by means of a lookup table. This table can be constructed with the help of the preceding function but, to speed the process up, we will use the previously constructed tables that convert between bytes and bit lists, to define the BitXor operation for integers in the 0..255 range. First, we give a procedure to carry out the BitXor operation between lists of bits of the same length:

 >

Then, the lookup table for the BitXor operation can be constructed as a symmetric array (since the operation is commutative) as follows.

Using a symmetric Array cuts in half both the time to build the table and the storage required in comparison with the full table. However, it also has some drawbacks derived from the fact that, for the array to be symmetric, the indexing must start at 1 instead of at 0. This forces us to carry out a few extra operations when computing a BitXor by looking up the table and, since this operation will be applied a lot of times, it produces a non negligible loss of speed. Moreover, accessing a symmetric array is slower than accessing an array with rectangular storage. Thus we will use an array with rectangular storage containing the full table (with 256 = 65536 entries, which is not too much for today's computers).

 >

Then the BitXor operation with two integers in the 0..255 range as arguments is the following:

 >

We will also use the following version of BitXor, which computes the BitXor of a 0..3,0..3 Array a with a list l of no more than 16 terms, where the array is passed as the first argument and the list as the second. If n is the the length of l, then the output is the list of length n obtained by BitXor-ing the elements of l with the first n elements of a with respect to Fortran_order . The function ArrayTools:-Alias is used here to view the 2-dimensional Array as a 1-dimensional Array with this order.

 >

The multiplication in GF(2)

In the MixColumns operation of AES we will have to make use of the multiplication in the field GF(2). The multiplication, for elements as integers in the 0..255 range is given by:

 >

However, we will not use this function directly in MixColumns because we will have to multiply 4x4 matrices over GF(2) and this means a lot of multiplications of field elements. To optimize speed, we will instead use a lookup table constructed by means of this function. In fact, we will build two tables. The reason is that only a handful of the field elements (specifically, 1, 2, 3, 9, 11, 13, 14) are required for MixColumns and its inverse and so we only need to know the result of multiplying each of these bytes by any other byte. If one uses tables, then the indices need not be consecutive and so one can build up a table whose rows correspond to all the elements of the field (bytes in the 0..255 range) and whose columns correspond to the elements of the field mentioned above (excepting 1, as multiplication by 1 is trivial), namely, 2,3 (required by MixColumns) and 9,11,13,14 (for the inverse). This would give a table that is much smaller than the full multiplication table -which would require much more time to build and much more space to store- and, since the indices of a table need not be integers, it would also permit to deal with the elements in the form of 8-bit lists instead of bytes.  But this approach will not be pursued here as it has other drawbacks. We will use arrays, which must be indexed by integer ranges and so, to economize both space and time, we will build up two Arrays for the multiplication table, one for the multiplication by 2 and 3 and the other for the multiplication by the elements in the 9..14 range:

 >

The round constants

Here, we define the "round constants" which are used during the key schedule that builds the round subkeys. These constants are 14 4-byte words (herein represented as 4-byte lists) which are obtained by successive multiplication by 2 in GF(2) starting with the word [1,0,0,0].

 >

The list of round constants, Rcon, is then:

 >

The SBox

The SubBytes operation is based on a permutation of GF(2) that associates to each nonzero byte the result of computing the inverse byte in GF(2) —the 0 byte is mapped to itself— and then applies an affine map to the corresponding bit vector. To obtain an efficient implementation of SubBytes we will construct a table called the SBox. To build the table we start with the following function that gives the inverse of a byte in GF(2):

 >

The affine map used by SubBytes is given by an 8x8 matrix of bits and a bit vector of dimension 8. These are the following:

 >

Now, the affine map itself, with input and output an 8-bit list:

 >

With these ingredients, we give a function (ByteSub) that implements the permutation of GF(2) underlying SubBytes (which will be defined in the next section).

 >

We now construct the SBox table and its inverse (InvSBox). Since in this case all the required indices are integers, we will use Array as data structure instead of table:

 >

Based on these tables, we can define more efficient versions of ByteSub and its inverse permutation. The SB function will also be used during the Key Schedule process.

 >

The pseudo-random generator

An important role is played in this worksheet (and, more generally, in cryptography) by the pseudo-random number generators (PRNG's) used to generate keys, initialization vectors, etc. An important feature of PRNG's is that they must be seeded by an entropy source. In this worksheet we are going to use Maple's PRNG's often and, since they are deterministic algorithms, if directly called without previous seeding they would produce the same output sequence each time. For some specific purposes this could be acceptable but it is clear that keys, for example, should not be generated this way. From version 10 onwards, the default PRNG in Maple (the one that is called by the function rand()) is the Mersenne Twister  PRNG (described in detail in [Matsumoto-Nishimura], where it was introduced). Although this is not the PRNG that we will use to generate keys -for reasons that will be explained later on- it will still play a role for some purposes such as testing, so that we will now set the initial state of this PRNG or, rather, let Maple do so by seeding it with values taken from the system (this initialization should always be carried out before using the PRNG). The next function sets the initial state of Mersenne Twister:

 >

The Mersenne Twister PRNG is very fast and passes many statistical randomness tests (so it is often the PRNG of choice for statistical simulations) but is considered unsuitable for cryptographic use due to the fact that knowledge of only 624 consecutive outputs is sufficient to predict further outputs. For cryptographic applications a "cryptographically secure" PRNG is required, meaning that it should pass the "next bit" test, in the sense that knowing the first s bits of a sequence output one should not be able to predict the value of the (s+1)-bit with probability significantly greater than 1/2. A PRNG that has been proven to be cryptographically secure under certain assumptions -the most important being the assumed difficulty of the integer factorization problem- is the Blum-Blum-Shub (BBS) generator (see, for example, [Stinson] or [Geisler-Kroigard-Danielsen] for a security proof, and also [Monagan-Fee] which, in addition, gives a description of the BBS Maple implementation). The BBS generator is implemented in Maple in RandomTools:-BlumBlumShub  and we will use this PRNG to generate pseudo-random keys and other objects. A problem inherent to the way PRNG's work is that they must be seeded by an entropy source which, in order to provide the true random bits required to obtain sufficient security, should involve some kind of physical process (see [SP800-90]). In our case we shall either use externally generated random seeds -this is the preferred method and the only one that, if correctly used, produces secure results- or seeds taken from the system, which are not random but may be used for demonstration purposes. As we shall see in the following sections, we will deal with keys and initialization vectors that are lists of integers in the 0..255 range, which we will refer to as bytes. The PRNG that we will use to generate pseudo-random bytes is BBS and, in particular, its implementation in Maple's function RandomTools:-BlumBlumShub:-NewBitGenerator . This function has a required input parameter for the seed and the BBS PRNG works by taking squares modulo and integer which is a product of two large primes congruent to 3 (mod 4). For the security of BBS it is crucial that an adversary be unable to factor this integer and recover the prime factors. In the case of Maple's implementation, there is a choice among three integers which are stored in three variables local to the module  called n512, n768 and n1024. The latter evaluates to an integer of 616 decimal digits that is a product of two 1024-bit primes and, similarly, n512 and n768 evaluate, respectively, to a 308-digit product of two 512-bit primes and a 462-digit product of two 768-bit primes and RandomTools:-BlumBlumShub:-NewBitGenerator  lets us choose which of these integers to use through the input parameter called primes, in which any of the three values 512, 768 and 1024 may be specified. The next function BBSByteGen relies on NewBitGenerator to generate a list of pseudo-random bytes of specified length. The required input parameters are length for the length of the list of string or bytes to be generated and seed for the seed  (which, as mentioned above, should be randomly generated). Actually, the function will also work if no argument is passed to the parameter seed, in which case the seed will be generated by means of Maple's function RandomTools:-MersenneTwister:-GenerateInteger() (see the comments about this usage in the discussion of the function PseudoRandomKeyGen below). There are two optional keyword parameters, format, used to specify whether the output will be a list of bytes or a hexadecimal string (with list as default)  and primeslength, which specifies the length of the primes to be used by BBS among the three possible values 512, 768, 1024, with the latter being the default.

 >

This function does not have type checking nor default values for the parameters because it is not intended to be called directly by the user but rather by other functions that will build lists of pseudo-random bytes. The seed can be any positive integer which is increased by 1 inside the function because Maple's NewBitGenerator procedure enters an infinite loop when seed = 1 which, anyway, will only happen with negligible probability if the seed is randomly chosen. The integer values of n512, n768, and n1024 can be obtained from Maple's source code and are also given by the authors of Maple's BBS implementation in [Monagan-Fee]. According to the publicly available knowledge, it seems that factoring these numbers is not currently feasible, although it is foreseeable that n512 could be factored within a few years. Of course, these numbers were constructed by finding the prime factors first and then multiplying them, and this means that if one uses Maple's Blum-Blum-Shub implementation, one has to trust Maple's assertion (in NewBitGenerator's help ) that it does not have these factorizations. If Alice does not want to trust Maple, then she can modify Maple's code by replacing the values of n512, n768 and n1024 (or, at least, of some of them) by different integers of similar size which are known only to her and satisfy the requirements of the BBS generator. This is easy to do following the method indicated in [Monagan-Fee] but it requires a certain amount of computation because the primes are chosen so as to make easy the computation of a seed which will produce a BBS output sequence with long period. However, the fact that these primes will be known only to Alice can be used to reduce the computational cost of computing them as this makes easier to find an appropriate seed. But, on the other hand, Alice might as well have to reveal these primes to Bob if she wants to convince him that the key she is offering to share cannot be easily guessed by Eve ...

AES operations

In this section, the four AES operations are defined. These operations are, following standard terminology: SubBytes, ShiftRows, MixColumns, and AddRoundKey. Furthermore, we also set up the Key Schedule which is the process that generates the round subkeys through a function called KeyExpansion. Observe that all AES operations operate on 128-bit plaintext or ciphertext blocks each of which is organized as a 4x4 matrix of bytes called the state. In our implementation, the state will be a 2-dimensional Array with 0..3, 0..3 indexing. This is slightly more efficient than the 1..4,1..4 matrix indexing as it simplifies the operations done when manipulating its entries. A perhaps simpler alternative would be to use a list for the state. However, working with lists is generally less efficient than using Arrays and, moreover, Arrays can be modified "in place", which often makes it unnecessary to build a different copy and gives additional efficiency gains.

SubBytes and its inverse

For the SubBytes operation and its inverse we could just use LinearAlgebra:-Map to map the SB function defined above to the state Array. However, to increase speed, we will use the following functions that replace the state entries by looking directly at the SBox and InvSBox tables:

 >
 >

ShiftRows and its inverse

The ShiftRows operation consists in shifting the rows of the state Array by 0, 1, 2, 3 positions to the left, i.e., each row is shifted by the same amount as its index. The inverse operation just shifts rows right by the same offsets. These operations are not implemented "in place" as we need to use a copy of the state Array inside the corresponding function.

 >
 >

MixColumns and its inverse

The MixColumns operation acts on the state matrix by multiplying it by a 4x4 matrix with entries in GF(2). It replaces state by the matrix M state, where M =   (so that the multiplication of these matrices uses the addition and the multiplication in GF(2)). This operation may also be regarded as replacing each column of the state matrix by the result of multiplying M by it, hence the name. To improve speed, the function calls directly bitxortable and multtable1 to do multiplications by 2 and 3 in GF(2). This is important because MixColumns requires, for each plaintext block, 64 multiplications of bytes per round, which translates into a minimum of 576 multiplications per block during encryption.

 >

The inverse operation consists in multiplying by the inverse matrix of M which is . To implement it we use the second multiplication table, multtable2:

 >

The Key Schedule

The only AES operation remaining to be defined is AddRoundKey. For this operation it is necessary to generate the "round subkeys" using the so called "Key Schedule" process. This is done by the next function which takes as input the AES key, given as a list of 16, 24 or 32 bytes (we will give functions to generate keys later on). The output is a list of 0..3-0..3 Arrays whose entries are bytes; each one of these Arrays is a round subkey.  The first 4, 6 or 8 columns of the first two Arrays contain the key, which has been mapped to them columnwise, starting on the top of the leftmost column. The functions RotWord and SubWord mentioned in [FIPS197] are not defined here because the first is simply a version of Rotate from the ListTools package and the second consists in applying SubBytes to a 4-byte word, which is done here by means of the previously defined function SB.

 >

For example, let's look at the expanded key for a 128-bit key consisting entirely of zero bytes. The results may be compared to those in the web page Key Schedule bearing in mind that here each round key is a 4x4 matrix and that the string form of the subkey defined by each of these matrices is obtained by going through the matrix entries columnwise.

 >

The AddRoundKey operation is simply the result of BitXor-ing the bytes in the state matrix with those in the corresponding round subkey of the expanded key (in other words, the new state matrix is obtained by adding over GF(2) the round subkey matrix to the old state matrix). The state Array is changed "in place" by modifying it and this can be done without returning anything. However, for convenience, our function returns the new value of the state. Note that in this case we do not define the inverse operation as AddRoundKey is its own inverse.

 >

Low-level AES functions

In this section we define two levels of AES encryption/decryption functions and also some auxiliary functions to provide them with the input in the required format. The lower level consists of the "forward cipher function" and its inverse (herein called Encrypt and Decrypt, respectively). These functions accept as input a state matrix (i.e., a plaintext or ciphertext block) and the expanded key and give as output the corresponding plaintext/ciphertext state matrix. The higher level functions deal with lists of bytes of arbitrary length (assumed to be a multiple of the block length for some modes) and they incorporate the five confidentiality modes of operation specified by NIST. We start with the lower of the two levels just mentioned.

The Rijndael rounds and the cipher and inverse cipher functions

First we define an AES round. The input is a state Array and a round subkey (also a 0..3,0..3 Array) and the output is a modified state.

 >

The next function is the forward cipher function which, given a state matrix and a expanded key, produces the ciphertext corresponding to this state.

 >

Similar to the Round function, the inverse round is now:

 >

Finally, the inverse cipher function:

 >

Encrypting and decrypting lists of bytes

Now, we give higher level encryption and decryption functions, EncryptBytes and DecryptBytes. In this case, the input is a list of bytes (like the one obtained by reading a file from disk), a key (given also as a list of 16, 24 or 32 bytes), a mode of operation (one of the following strings: "ecb", "cbc", "cfb", "ofb", "ctr", which we use to represent ECB, CBC, CFB, OFB and CTR modes, respectively) and an "initialization vector" (IV) except in the case of ECB mode which does not require it. We take as default mode "cbc" and, for the IV, we use a keyword parameter iv with default value the list of 16 0-bytes. The output is a list of bytes containing the corresponding ciphertext (with the IV added in case the used mode requires it) or the plaintext (in the case of the decryption function). For ECB, CBC and CFB modes, the length of the input list of bytes is supposed to be a multiple of the block length (i.e., the byte length of this list should be a multiple of 16). We will see later how every plaintext can be converted to such a list by using padding. The list of bytes -together with the IV- is partitioned into 16-byte sublists (the blocks) and each of these blocks is converted to a state 0..3,0..3 Array. In the case of OFB and CTR modes, which do not require padding, the list of bytes has arbitrary length and is partitioned again into 16-byte sublists, except the last one which may have less than 16 bytes and is regarded as a partial block. Because of this we do not make the states into Arrays in these cases and we keep them as lists instead (in this case, the length of the ciphertext -minus the IV- must be exactly equal to the length of the plaintext because otherwise you would not know after decryption where the plaintext ends). In these cases we will use the function BitXorAL  defined above which allows us to compute the BitXor of a 0..3,0..3 Array of bytes and a list of bytes of no more than 16 elements. In all cases, the list of all the states is converted to a 1-dimensional Array -this is necessary because we want to modify the states and this cannot be made by direct assignment if they are the members of a list of more than 100 entries.
These functions are still pretty low level and they are not supposed to be directly called by the user, except perhaps for testing or learning purposes. Instead, they will be called from other functions that are the ones that actually encrypt files or text strings. Because of this we do not include any error-checking here, as the higher level functions are supposed to pass correctly formatted arguments to these ones. Note also that the output of the EncryptBytes function for the modes that require an IV is not just the ciphertext but the IV concatenated to the ciphertext. This has the advantage that the decryption function does not require the IV as a separate input and is perfectly OK since the IV need not be secret and, moreover, its length is fixed and publicly known. Observe that in these functions, in contrast with the previous ones, the key (as a list of bytes) is used instead of the expanded key. There is the possibility of gaining some speed by using the expanded key instead of the key in all the encryption/decryption functions (here and in the higher level ones). This way, the key expansion function would be invoked only once for each key, just after generating it, and the expanded key thus obtained would be the one used by all the functions. Since the time taken by KeyExpansion is not too long and, moreover, one should change keys often, we will not implement this.

The implementation of the modes of operation consists in running a loop over the Array containing the states replacing each state with the corresponding encrypted or decrypted one. These loops just use the functions Encrypt/Decrypt, BitXor (where BitXor applied to two state matrices is just the AddRoundKey operation) and BitXorAL in the way described in the specification for the modes of operation [NIST 800-38A]. The only thing worthy of mention here is that, in CTR mode, a series of different blocks called counters (one for each plaintext block) must be generated. To generate the counters we need two ingredients. One of them is an algorithm to choose the initial counter block corresponding to each encryption; this initial counter will be the IV and we will later give functions to generate it. The other ingredient is a method to generate the subsequent counters in such a way that their values are never repeated across all the encryptions done with the same key. To achieve this we use an "incrementing function" which is called after encrypting each block in order to obtain the counter for the next block from the preceding counter. We will use the so-called 32-bit incrementing function which consists in adding 1 to the counter modulo 2, when the counter is viewed as a 16-digit number in base 256, in big-endian order, i.e., with the most significant byte first. Therefore, the 32-bit incrementing function only modifies the last four bytes of the counter -that initially are all zero- and cycles among all the possible values of these 4 bytes. The function could also have been defined modulo 2 -for example-, so that the counter values would cycle among 2 possible ones but this is not really necessary. The 32-bit version provides for 2 different counter values. Since each of these values is used to encrypt one 2-byte block, this means that the plaintext can have up to 2 bytes without any counter value being repeated during encryption. This is more than enough (as 2 bytes = 64 gigabytes) and, in fact, the implementation cannot handle plaintexts so large because Maple's list size limit imposes here a maximum plaintext size of 2-4 bytes, which is close to 64 MB. It is possible to modify the implementation to allow for larger plaintexts but, given other realistic space-time constraints, there would be little point in doing so.

During encryption, the counter blocks will take the form of 0..3,0..3 Arrays and the increasing function that acts on them is the following (note that the function just increases the counter value without returning the new value; it just returns the last modified byte and can be easily modified to return NULL).

 >

In the EncryptBytes and DecryptBytes functions we shall need to compute the BitXor of two states. The AddRoundKey function does just this. To distinguish the use of BitXor in CBC and CFB modes from the AddRoundKey operation, we define an alias of the latter and call it BitXor:

 >

The encryption function for lists of bytes is then:

 >

The decryption function that acts on lists of bytes is very similar to the preceding one. Here the IV is not required because it consists of the first 16 bytes of the (ciphertext) list.

 >

Later, we will give tests to check the behavior of these functions against known values. For now we give, as a very simple example, the result of encrypting and decrypting the example vectors in Example C1 (AES-128) of [FIPS197]:

 >
 >

When calling the preceding functions from higher level encryption/decryption functions, we will use the following procedure to check if the supplied mode name is correct. Valid modes are

 >

Initialization vectors

For all modes except ECB, an initialization vector (IV) must be generated. The IV need not be secret but, for CBC and CFB modes, it must be unpredictable so that, for any given plaintext, it must not be possible to predict the IV that will be associated to it. One of the best ways to generate such an IV is by using a PRNG and so we will use Blum-Blum-Shub through the BBSByteGen function to generate a pseudo-random IV of specified length. For the confidentiality modes already mentioned we will only use IV's of byte length 16 but IV's of different length will also be used in some of the authentication modes to be implemented later on in this worksheet.

For OFB mode, the IV need not be unpredictable and hence it need not be random but it must be a nonce (in the cryptographic sense) that is unique to each execution of the encryption operation (with the same key). The usual techniques to obtain a nonce are based on using a timestamp or a PRNG of sufficient quality to ensure a probabilistically negligible chance of repeating a previously generated value. In this case, we are going to use a combination of both techniques. The reason for not using the timestamp alone is that Maple will only retrieve the current date/time up to the seconds and so, to prevent a repetition if several quick encryptions are done within the same second, we will add the pseudo-random values. Moreover, since unpredictability is not a concern here, we shall use the Mersenne Twister PRNG because of its high efficiency. On the other hand, we will not use a purely pseudo-random nonce to prevent the very small chance of getting a repeated value. Thus, a nonce of length n (a list of n bytes) will be generated as follows. Using StringTools:-FormatTime with the appropriate format string and then using sscanf, we get a list of 6 bytes which correspond to the last two digits of the year, the month of the year, the day of the month, the hour (in 24-hour clock format), the minute and the second. This sequence of 6 bytes is then completed with n-6 pseudo-randomly generated bytes. Note that it would be a mistake to initialize the PRNG each time that nonce() is invoked because, as the seed is taken from the system clock, this would allow the possibility of obtaining two consecutive equal values when calling this function, although it would be an unlikely event if an actual encryption is being carried out. On the other hand, there is no need to initialize the PRNG here, for this has already been done at the beginning of the session. Note that, in fact, for the purpose of this function it would even be unnecessary to seed the PRNG since the purpose here is not so much obtaining random values as the fact that these values are not repeated (an alternative approach would consist in taking some of the bytes from the CPU time spent).

One rather trivial difficulty that might, in theory, arise is that using the date/time stamp to generate the nonce as we do here might lead to a repetition if the system time is changed in a non-regular way, for example at the winter daylight saving time or because of a malfunction of the system clock. This could allow the value to reach a repetition. However, since half of the bytes are pseudo-randomly generated, such a repetition is very unlikely and it can also be prevented with some precautionary measures, so that we shall not worry about this either.

 >

One of the uses of the previous function will be to set the initial value of the counter in CTR mode. The procedure we are going to follow for this is similar to one suggested in [SP800-38A]. At the start of each CTR encryption, the initial counter will be obtained by calling nonce(12) and completing it with four zeros on the right to make a 16-byte block. We have already mentioned the use of the incrementing function to generate the subsequent counter values but, on the other hand, since the counter is initialized by using the nonce each time the CTR encryption function is called, one has to ensure not only that the value returned by the nonce function never repeats -as already discussed- and that the counter value never repeats during one encryption but also that no repeated counter values arise during different encryptions with the same key. Assuming that the nonce behaves as expected, since the counter works by successively increasing the initial nonce during each encryption, the only thing that must be satisfied to ensure that the counter values never repeat is that the value returned by calling the nonce function increases at greater speed than the counter itself. Of course, the speed with which the counter increases depends on the speed of the encryption operation, given that the counter increases by 1 for each 16 bytes that are encrypted. On the other hand, the nonce advances (assuming than at least one second has passed) more than 2-2-1 units per second. This is because the byte corresponding to the seconds is the sixth from the left and an increase of a unit in this byte corresponds to an increase of 2 in the value of the block if we view it as a 16-digit base-256 number. Assuming that the pseudo-random part is at its maximum value before increasing the sixth byte and at its minimum value after increasing it, the difference between both values is the one between the largest 8-byte number -that may correspond to the pseudo-random part of the nonce/counter- and 0, namely 2-1, so that an increase of 2-2-1 is obtained. Each unit corresponds to 16 bytes and hence for the counter to reach the new nonce value (or a larger one) after an encryption -discounting the case in which two encryptions are started within the same second which, apart from being rare, is dealt with by the pseudo-random part of the nonce-, one should encrypt, at least, (2-2-1)2 bytes per second. This is more than 2 bytes/second or more than 8 yobibytes/second, were 1 yobibyte (YiB) = 2 bytes is currently the largest information storage unit, so we do not have to worry about it.
We are now ready to give the function that selects the nonce, or the initial counter or, more generally, the IV appropriate for each mode (except for ECB mode where it is not used). The encryption functions below accept the IV as an input, so that the IV may be externally generated if desired but, in case no IV value is passed to the functions, then it will be generated by the following function.

 >

As an example, we select an IV (i.e., an initial counter in this case) for use in CTR mode. In this case, the last four bytes are 0-bytes:

 >

The next function will be used by the encryption functions to check that the IV passed to the function is valid (i.e., a list of bytes or a hexadecimal string of valid length). The function returns an error in case the IV is not valid, otherwise it returns the IV as a list of bytes, which is the format used by the low-level encryption and decryption functions. Note also that, if the key is given as a hex string, both lower case and upper case letters will be accepted as hex digits. If, on the other hand, no argument is passed to the function, then the output is the NULL sequence, which is useful for ECB mode, where no IV is used.

 >

The encryption function that acts on lists of bytes requires, for ECB, CBC and CFB modes, that the bit length of the plaintext be a multiple of 128 (the block size). If this is not the case then it is necessary to pad the plaintext (in order to complete a certain number of blocks) and to unpad it (once decrypted, to recover the original plaintext). The usual padding method (10 padding) consists in adding a "1" bit to mark the beginning of the padding and then completing it with as many "0" bits as needed to make its length a multiple of 128 (and, in order to avoid ambiguity, a full 128-bit block is added if the plaintext bit length is already a multiple of 128). Using 10 padding means that, since we work at the byte level and the binary expansion of 128 is 1 followed by seven zeros, we will use a byte 128 to mark the beginning of the padding and then all bytes 0 until completing the desired length (until the byte length is a multiple of 16).

 >

The function that removes the padding of a decrypted plaintext is the following:

 >

AES encryption and decryption functions

In this section we set up the encryption and decryption functions that will be used to encrypt/decrypt files, text, etc., as well as some auxiliary functions. We start with the functions devoted to generating keys.

Key generation

We will give a couple of functions to generate AES keys in different formats. Before defining these functions we want to mention an alternative possibility that produces highly insecure keys. This method converts a text string (which can be input through the keyboard) to a key given as a list of bytes and we mention it only to illustrate why it should never be used. The required keylength (in bits) is supplied through the second argument of the function, which will only accept one of the three allowed keylengths. If the byte keylength is n and the number of characters of the input text string is greater than or equal to n, then the bytes corresponding to the first n characters are taken, otherwise the string appended to itself as many times as necessary.

 >

For example, we can generate a 256-bit key as follows:

 >

This method allows the generation of keys that are easy to remember but, because of this very fact,  it is not very recommendable and, as already mentioned, it should not be used. If the text string is passed to the function by typing it at the keyboard then the number of different bytes that may appear in the key is severely restricted (there are many bytes that will never appear in a string produced this way). On the other hand, if the text string is a meaningful sentence in a natural language, then the effective size of the key space is severely reduced and even more so if a string of less characters than the required byte keylength is used. This would violate a basic cryptographic principle which postulates that all keys should be equally likely and hence they should be chosen uniformly at random [Bellare-Rogaway, Katz-Lindell]. If we observe the key obtained in the previous example, we see that all its bytes (with the exception of 32 that corresponds to the space) are in the 84..116 range and, moreover, the last 12 bytes are the same as the first 12. Thus not only the key is not random but it hardly looks random!
The requirement that AES keys be selected uniformly at random is very difficult to meet (see, e.g., [Viega] for an in-depth analysis of the many difficulties that arise in practice when trying to generate secure keys by means of PRNG's). As an alternative, we will use the BBS PRNG (just by calling BBSByteGen) to generate a sequence of pseudo-random bytes of the required length. This is done by the function PseudoRandomKeyGen below, whose required input parameters are keylength (which admits only the three possible values 128, 192 and 256, corresponding to the possible bit sizes of an AES key) and seed, for the seed given either as a positive integer or a hexadecimal string.  There are also two optional keyword parameters, format and primeslength, which play the same role and have the same default values as in the function BBSByteGen.  As already mentioned, for security the seed should be randomly chosen among all possible seeds of sufficient length. The seed length should be large enough to prevent brute-force attacks; for example, if randomly chosen 32-bit seeds are used, an adversary could mount a successful attack by carrying out an exhaustive search over all the 2 possible seeds, which is feasible. Therefore, in order to prevent such an attack, it is advisable to choose the seed at random among all the strings of length at least 128 bits. This cannot be done with Maple but operating systems have reasonably good methods to generate random seeds or even, with patience, one can always resort to the slow method of coin tossing and use Von Neumann's trick just in case the coin is biased.  Maple also has methods to generate seeds, such as those given by the functions randomize() and RandomTools:-MersenneTwister:-SetState(), but seeds taken from the system clock are hardly random and, moreover, the 32-bit seeds produced by these functions are not large enough to prevent brute-force attacks. However, we include the possibility of using Maple's automatic seed in the function PseudoRandomKeyGen, which will also work if no value is passed to the parameter seed, in which case the seed will be generated  by BBSByteGen by calling RandomTools:-MersenneTwister:-SetState(). This is done only for convenience and for demonstration purposes but we insist that this method is not secure and that, for security, true random seeds (or true random AES keys) should be used. If one is going to use true random seeds, then one might as well generate a true random AES key by the same method because, anyway, the seed should have at least 128 bits as remarked above, so only in the case of 192- and 256-bit keys we would have to generate fewer random bits by using the PRNG.

 >

For example, a 256-bit hex key is the following:

 >

A 256-bit key generated with automatic seeding is:

 >

The next procedure will be used by the encryption/decryption functions to check that the key passed to the function is valid (i.e., a list of bytes or a hexadecimal string of valid length). The function, which is similar to checkiv, takes as input at an AES key given either as a list of bytes or as a hexadecimal string, checks whether the key is correctly formatted and, if this is the case, it returns the key as a hexadecimal hex string.

 >

 >

File encryption and decryption

Next, we are going to give higher level functions to encrypt and decrypt files. For this we will use the previously defined functions filetobytes and bytestofile, to read a file to a list of bytes and to write a list of bytes to a file, respectively. Observe that the size of the files that can be handled by these functions is limited by the maximum list size which is 2-4. This limitation will also affect other kinds of plaintexts (like strings) and, in the case of files means that, since 2 bytes equals 1 MB, the maximum size that can be read by filetobytes is just below 64 MB. On the other hand, files close to 64 MB in size would take quite a long time to encrypt or decrypt but the implementation can easily deal, within reasonable time, with the typical files produced by word processors. The input for these functions is the name of the file to be encrypted or decrypted (as a string delimited by double quotes), the name of the file where the result of the encryption/decryption operation is to be written, the key (as a hex string or a list of bytes),  the mode of operation (as a lower case string with default value "cbc"),  and some keyword parameters. The keyword parameter iv (used only by the EncryptFile function) is for the IV given as a list of 16 bytes and, if no argument is passed to this parameter, then the default value makes the function to generate the IV by means of the previous function selectiv. This way, the IV may be, for example, an externally generated random IV but it can also be generated inside the function, although the automatic seeding used makes this second method insecure. The keyword parameter filecheck is used for file checking and logoutput specifies (with the same format as in bytestofile and with default value terminal) where the output log is to be written. The functions check if the file exists by default but in the subsequent tests we override this check by specifying filecheck = false in order to facilitate procedure timing.

 >
 >

To test these functions we use the file "testfile" that was previously generated, and the corresponding list of bytes called testlist. We encrypt "testfile" in CBC mode (the default) by using as key the list of bytes in the 0..15 range and we write the ciphertext to a file named "ctestfile". Afterwards, we decrypt this file to a file named "dtestfile". Finally, we read "dtestfile" to a list and compare this list to the original testlist. The comparison should reveal that both lists are the same and hence that the encryption/decryption process worked correctly.

 >

Next, we do a similar test for CTR mode. In this case we generate a 192-bit random key and we use it to successively encrypt and decrypt "testfile". Finally, we compare the result of reading the decrypted file to a list of bytes with the original list.

 >

Text encryption and decryption

We are now going to provide encryption and decryption functions for text strings.  The obvious way of encrypting text strings by using the extended ASCII character set (ISO Latin 1) as alphabet is not a good idea here. The reason is that Maple's 8-bit extended ASCII character set contains only 255 characters instead of the required 256 (the null character, corresponding to the 0 byte is missing). This poses no problem with plaintext because in ordinary text a null character never appears. However, after encryption, the 0 byte may appear in the ciphertext (with equal chance as any other byte). Since this byte has no corresponding character, we are in trouble. This difficulty is mirrored in the natural way to convert between bytes and characters by means of Maple's convert/bytes function. This function does not really convert between bytes and characters but between bytes or lists of bytes and strings of characters instead. This way, the 0 byte is converted to the empty string but this string is not a good replacement for the null character. Thus, for example, gives as output the empty list while returns [\$1..255]. This stems from the fact that convert/bytes truncates the string when converting a list to a string and finding the 0 byte. This is not a big problem anyway, because the 8-bit ASCII character set is not a good alphabet for our purposes as it contains many non-printable characters. Thus, while we will deal with 8-bit ASCII plaintexts, ciphertexts will only use as alphabet the set of hex digits. In the encryption function, the keyword parameter  is used to specify an IV (which is selected by by default). In both functions, to select between the two formats that the plaintext may have, we use a keyword parameter (messagetype) which can take as values either text (for ordinary text) or hex (to be used mainly for testing purposes). The encryption and decryption functions are the following:

 >
 >

Let's use the above defined strings paztext and hex64 to check these functions:

 >

Observe that a plaintext consisting of a hex string can be encrypted either as messagetype = text or messagetype = hex. In the first case the ciphertext will be longer and, after decryption, the plaintext letters will be in the same case as in the original plaintext. In the second case, the ciphertext is shorter (approximately, half as long) and the decrypted plaintext will have the hex digits as lower case letters.

Encrypting and decrypting text files

The procedures given to encrypt and decrypt binary files do not have any restriction (except the one regarding maximum file size) and are sufficient for most situations. However, there may be cases in which one would like to encrypt a text file and that the resulting ciphertext were also contained in a text file. If we use the binary encryption given above, the ciphertext file will not be a text file in general. Thus we give encryption and decryption functions that work with text files and produce only text files.The next function will be used during encryption or decryption of text files to check whether a file is already open. If the file is not open then this function will open it and if the file is already open, then it will go to the "0 position" (start of the file) instead (because trying to open it would give an error).

 >

Next, the encryption and decryption functions for text files. The text in the file is read line by line and the string obtained from each line is then encrypted/decrypted and written to the destination file.

 >
 >

To test these functions we create a text file called "textfile" in the current directory:

 >
 >

Authentication

One important goal of modern cryptography is to provide authentication. We are going to see that AES can provide message authentication between parties that share a secret AES key. A basic idea for this purpose is to use CBC mode by exploiting the fact that a change in a plaintext block submitted to CBC encryption induces a change in all the subsequent ciphertext blocks. Then authentication is achieved by using a MAC (Message Authentication Code) which adopts the form of a tag which, attached to a message, serves to guarantee its authenticity. When CBC mode is used this way, the MAC attached to a message is the last ciphertext block obtained by encrypting it in CBC mode with a public IV (usually, the block 0 with all 128 bits equal to 0) and a shared secret key (this version receives the name of CBC-MAC). The authenticity of the message can then be checked by computing the MAC through CBC encryption with the secret key and comparing it with the one received. However, AES-based CBC-MAC is insecure and, in particular, is vulnerable to forgeries when used to authenticate variable length messages [Bellare-Rogaway, Katz-Lindell]. Because of this, the basic CBC-MAC algorithm has been modified in several ways, and one of these modifications is CMAC, which has been proven to be secure under reasonable hypotheses (see the NIST specification in [SP800-38B] and its references).

CMAC

The core of the CMAC algorithm is a variation of CBC-MAC that Black and Rogaway proposed under the name XCBC and that was later improved under the name OMAC by Iwata and Kurosawa. CMAC is the NIST specification of OMAC1, one of the variants of OMAC. In XCBC, the padding algorithm (the 10 padding we are using) is modified by not adding an extra block whenever the bit length of the message is already a multiple of 128. In addition to the AES key k, two additional whitening keys k1, k2 are used. If no padding was added, the algorithm is the same as CBC-MAC except for the fact that, before encrypting the last block with k, this block is Xor-ed with k1. If, on the other hand, padding was added, then a similar operation is performed, Xor-ing the last block with k2 before encryption. CMAC proceeds in a similar way, except for the fact that keys k1 and k2 are not independent from k but are derived from it. This is done as follows. Consider the field GF(2) defined by the irreducible polynomial x + x + x + x + 1 of Z2[X]. The elements of this field can be represented, in a way similar to the one used for GF(2), by the integers in the 0..2-1 range and hence by the 128-bit (or 16-byte) vectors (where the most significant bit -or byte- is the leftmost one). Let then L = Ek(0) be the result of encrypting the 0-block with AES using k as key. L is an element of GF(2) and the CMAC subkeys k1 and k2 are obtained by taking k1 = 2L (where " denotes multiplication in GF(2)) and k2 = 4L. Then the algorithm proceeds in the same way as XCBC explained above. We start by giving an auxiliary function to make a cyclic left shift on the list of bits corresponding to a 16-byte list:

 >

The next function implements multiplication by 2 in GF(2) (note that 2 is the element that corresponds to the polynomial x). Of course, this multiplication can also be implemented by using the GF package but since we will not make use of multiplication by other elements of the field and, moreover, multiplication by 2 is very simple as it essentially reduces to a left shift, we shall implement it directly by means of the next function. Note that the 134 that appears in the body of the function comes from the fact that this is the value that the polynomial x + x + x, obtained by discarding the highest and lowest degree monomials in the polynomial defining GF(2), takes for x = 2.

 >

The next function generates the subkeys used by CMAC from an AES key.

 >

As a quick check we look at Example D.1 in the "Updated CMAC Examples" correction to Appendix D in [SP800-38B]:

 >

The next function implements CMAC for lists of bytes. The input is the message and the AES key, both given as lists of bytes. The output is the MAC given as a hex string.

 >

Next we give the function that implements CMAC for a message that can be either a file or a (hex or text) string. The input is the message, given as a string which contains either the name of the file or the message itself, the key given as a hex string (in either lower or upper case) or a list of bytes, and the message type as a keyword parameter that must take one of the following values: text, hex or file (the latter being the default).

 >

Later, we will give a function to test Cmac against the examples in [SP800-38B]. For now, we check the tags corresponding to a few of these examples. We define several hex strings that will be used as messages (together with the above defined string called hex64) and also several keys:

 >

The resulting MAC's are the following:

 >

Let's now check the CMAC tag of a file. The file named "hex64" in the current directory contains a copy of the hex string hex64. Thus the MAC for this file should be the same as the last output:

 >

We are now going to implement a function for the MAC verification process of CMAC. The required inputs are the (received) message, the key, and the received MAC and the output will be VALID (if indeed the MAC corresponds to the message) or INVALID otherwise.

 >

A quick check of one of the previously computed tags is then:

 >

Authenticated Encryption

The modes of operation we have used so far are aimed at guaranteeing either confidentiality or authenticity of data but there are also modes that provide assurance of both. In this section we implement the two modes for authenticated encryption that have been specified by NIST: CCM and GCM/GMAC.

CCM mode

CCM mode ("Counter with Cipher Block Chaining"-Message Authentication Code) is specified in [SP800-38C]. CCM is essentially a combination of CTR mode (which is used for encryption/decryption) and CBC mode (used for authentication). CCM consists of two related processes: generation-encryption and decryption-verification. The input to the first includes three elements: 1) data that will be both authenticated and encrypted, called the payload; 2) associated data that will be authenticated but not encrypted; and 3) a nonce that is assigned to the payload and the associated data. In generation-encryption, CBC is applied to these three elements to generate a MAC and then CTR encryption is applied to the MAC and the payload to produce a ciphertext, so that the output consists of both the ciphertext and the MAC (and we will also include the nonce which, as it is not secret, will be sent together with them). In decryption-verification, CTR decryption is applied to the ciphertext to recover the MAC and the payload, then CBC is applied to the payload, the received associated data, and the received nonce to verify the correctness of the MAC. Successful verification provides assurance that the payload and the associated data originated from a source with access to the key.

The payload P and the associated data A may be empty. In the first case, CCM reduces to CBC authentication of A while in the second it reduces to CTR encryption of P. The byte length of A is denoted by a and, if a  0, then a is encoded as follows (note that the third case is not really necessary for this implementation because of the size limit on plaintexts but we include it anyway):

1) If 0  a  2- 2 then a is encoded as two bytes (a in base 256).
2) If 2- 2  a  2 then a is encoded as [255, 254, 4 bytes] where the last 4 bytes correspond to a in base 256.

3) If 2 a  2 then a is encoded as [255, 255, 8 bytes], where the last 8 bytes are the ones of a in base 256 (the specification imposes 2- 1 as an upper bound to the size of A).

Note that by looking at the first two bytes we know in which of the three cases we are for in the first the leading byte cannot be 255, in the second the second byte is different from 255 and in the third the two leading bytes are 255. The function that encodes a is:

 >

A small encodings sample is the following:

 >

The input for the generation-encryption algorithm is formatted by means of a formatting function that builds, from the nonce N, P, and A, a series of 128 bit data blocks B0, ..., Br. The formatting function is only required to satisfy three conditions which are specified in [SP800-38C], p. 8 (one of these conditions involves also the counter generation function and specifies that the first block of the output of the formatting function is always distinct from any counters used under the given key). We shall adopt the formatting function and the counter generation function described in the Example given in Appendix A of [SP800-38C] which were suggested by the authors of CCM mode and are also adopted in the IEEE Standard 802.11 for wireless local area networks; these functions comply with the mentioned requirements.

Following the notational conventions of [800-38C], we shall denote by t the byte length of the MAC -this is a parameter of the mode which is fixed for all the invocations of CCM with the same key; the minimum recommended value is 8 and we shall adopt 16 as default value-, by q the byte length of the byte length Q of P (i.e., the number of digits in base 256 of the number of bytes of P) and by n the byte length of the nonce N. In [SP800-38C] all data are represented as bit strings but here, for convenience in the Maple implementation, we will represent them as byte lists instead. The byte length is just the bit length divided by 8, the conversion being trivial because all bit strings considered in the standard have a length which is a multiple of 8. The parameters n and q are related by the equation n + q = 15, a condition which amounts to a tradeoff between the maximum number of invocations of CCM under a given key and the maximum payload length for these invocations. Indeed, q determines the maximum length of the payload as, by definition, P consists of fewer than 2 bytes, while the value of n determines the maximum number of different nonces. As defaults, we shall take q = 4 and n = 11, which allow payloads up to 2 bytes in size and give also a sufficient number of possible values for the nonce. The functions below will allow all the permitted values of q and n specified in [SP800-38C] but note that, as already mentioned, Maple's list limit size of 2 - 4, together with the way plaintexts are handled here, impose this number in practice as a bound on the byte size of both P and A.

The CCM counters are 16-byte blocks formatted as follows. The first byte is called the "flags field" and its 5 leading bits are set to 0 (the first two are Reserved and their value might change in future expansions). The last three bits encode q = 15 - n as q - 1 = 15 - n - 1, so that, in our byte representation, the leading byte is 15 - n - 1, where n is the byte length of the nonce. The n bytes following the first byte are the nonce bytes, and the last 15 - n bytes give the base 256 representation of the index i of the counter (starting at i = 0). Thus the counter function, which generates the initial counter taking as input a nonce N is the following:

 >

For example, we generate a nonce of length 11 (which is one of the allowed lengths) and the corresponding initial counter:

 >

We are now going to build the CCM formatting function. With the above parameter values in mind, we describe the leading byte of the first block B0, which is constructed as follows. The leading bit of this byte is 0 (it is Reserved for possible future use). The second bit is either 0 if the byte length a of A is 0 (i.e., the associated data is the empty string) or 1 if a  0 (A is nonempty). Then two 3-bit strings follow, the first encoding t as the binary representation of (t - 2)/2 (with the most significant bit on the left) and the second encoding q as the binary representation of q - 1. The rest of B0 consists, in order, of the n bytes of the nonce and, finally, q bytes devoted to the encoding of Q (the byte length of the payload P). The next 16-byte blocks B1, ..., Bu (where u may be 0) correspond (if a  0) to the concatenation of the encoded value of a obtained from the aencoding function with the associated data A adding, if necessary, some 0 bytes at the end to complete an entire number of 16-byte blocks. The input arguments of the formatting function are the nonce, the associated data, the payload, and the tag length. The output is a one-dimensional Array whose entries are two-dimensional 0..3,0..3 Arrays containing the data blocks.

 >

Next we give the generation-encryption and decryption-verification functions. As in previous modes we will build the final functions in two stages. The lower level functions take as arguments lists of bytes and the higher level functions will be the ones that act on plaintexts/ciphertexts given as files or text strings. We start with the lower level generation-encryption function. The function parameters are the nonce, the associated data, the payload, the key (all of them given as lists of bytes), and the tag length. The output is a list of bytes obtained by joining the list corresponding to the ciphertext with the one corresponding to the tag.

 >

The next function implements the decryption-verification process with input data given as lists. The inputs are the nonce, the associated data, the ciphertext, the key and the tag length. The nonce should be built up for each invocation of the higher level encryption-generation function (the one that accepts as input either files or strings to be encrypted-verified).

 >

Later on we will provide a function to test CCM mode. For now, we do a few of the tests in [SP800-38C]. For instance, Examples 1 and 2 in Appendix C are:

 >

Next, Example 4 in [SP800-38C]. This example should produce as output the 368-bit (48 bytes) ciphertext hex string given in [SP800-38C], p. 20:

 >

Next we provide the high level CCM Encryption/Decryption functions. Here one has to control the various bounds and limits imposed by the standard. For example, the MAC size and the nonce size can only take a few possible values. These values can be passed to the functions by means of keyword parameters: t specifies the MAC size in bytes, while n specifies the byte length of the nonce. As default values we have adopted 16 for the MAC size (this gives the greatest security; sizes below 8 are not recommended) and 11 for the nonce size. The latter allows a large number of nonces while, at the same time, allowing payloads of up to 2 bytes, which are significantly larger than what one can handle with this implementation (the nonce size-payload size tradeoff inherent to the standard means that the byte length of the payload is below 2). The standard also specifies a limit on the size of the associated data, which should be less than 2 bytes long. This limit is enforced in the generation-encryption function below following NIST's recommendation but in practice a lower limit (also for the associated data string) is imposed by Maple's maximum list size. Other optional parameters in the next function are the one that specifies the message type, which can be either file, hex or text. The first tells the encryption function that the string passed to it as the payload argument is the name of a file, hex means that the payload is a hex string and text means that the payload is ordinary text (a different conversion to a list of bytes is applied in these two cases). The default message type is file. The remaining optional parameters, given also as keyword parameters, are the file name (which is only needed when the message type is file) to which the resulting ciphertext is going to be written and the filecheck parameter which specifies if a check for a file with the given name should be done before writing to disk (to avoid inadvertently overwriting an existing file with the same name). filename has a default which consists in appending the string ".ccm" to the name of the file being processed and the filecheck parameter has true as default value. The false value for this parameter is useful mainly for testing purposes.

 >

In the decryption-verification function we will use the following procedure to establish the default name were the result of decrypting an encrypted file will be written  (this procedure will also be used later on for GCM mode). In the case of CCM mode, if the string "ccm" is passed as first argument and the name of a file ending in ".ccm" is passed as second argument, then the procedure returns the name of the file with the suffix ".ccm" dropped. Thus if this procedure is applied to the name of an encrypted file produced by the preceding function, then the name of the original unencrypted file will be recovered. If the name of the file does not end in ".ccm", then the returned name is the result of appending to the name of the file the suffix ".decrypted".

 >

Now, the decryption-verification function. Note that in [SP800-38C] it is required that if INVALID is returned, an unauthorized party cannot distinguish whether the error message results from the step just before calling CCMDV or from the last step (using, for example, timing of the error messages). This could be more or less attained by calling CCMDV with some valid values of N, A, C, k, t before returning the error message but in this implementation this does not make much sense as Maple is not going to send error messages to an attacker, so that this would only make the verification-decryption process less efficient. Therefore, we shall not bother about timing here.
Similar remarks as those made regarding the parameters and the size limits for the encryption function apply here but note that in the decryption function, if the size limits of the data are exceeded or the parameters do not take allowed values, then only INVALID is returned, with no explicit error message being printed. This is because the decryption function should not return informative messages to a hypothetic attacker although this possibility seems very unlikely here (unless the attacker is looking over the shoulders of the message receiver).

 >

Let's do a quick test of these functions. First, the payload and the associated data are empty, in the second test we use text strings for both:

 >

Another quick test of these functions, using the file "testfile" is the following one. First we copy this file to a file named "testfile2". Then we apply the encryption-verification function to this file producing a file named "testfile2.ccm". Then we apply the decryption-verification function to this file and the output should be a new version of "testfile2" that should be equal to the original one, which can be checked by comparing it with "testfile".

 >

GCM/GMAC mode

The next mode we are going to implement is the Galois/Counter Mode (GCM) specified in [SP800-38D]. GCM may be regarded as a mode of operation of AES and, like CCM, is an "authenticated encryption" mode that provides confidentiality by means of a variation of CTR mode and authenticity by means of a "universal hash function" defined over the Galois field GF(2) (hence the mode's name). The authentication assurance, like in the CCM case, can be provided for both the confidential (encrypted) data and for additional data that is not encrypted. If the GCM input is restricted to data that is not to be encrypted, the resulting specialization of GCM is an authentication mode called GMAC. The two GCM functions are called authenticated encryption and authenticated decryption. The first of these functions encrypts the confidential data and computes an authentication tag (a MAC) on both the confidential data and the additional, non-confidential data. The authenticated decryption function decrypts the confidential data contingent on the verification of the tag. We are going to see that, in this implementation, GCM is significantly more efficient than CCM. This is because the authentication part of GCM, i.e., GMAC, is based on a hash function called GHASH which is much faster than CBC-MAC-based authentication like the one in CMAC and CCM. Thus, GMAC is here at least 5 times faster than CMAC and this also means that, compared with CTR, GCM additionally provides authentication for a time increase of less than 20%.
The GHASH function is given by multiplication in the GF(2) field by a fixed parameter H called the hash subkey, which is generated by applying the block cipher to the "zero" block. A 128-bit (16-byte) block may be identified with an element of GF(2) as we have seen in the CMAC implementation and the irreducible polynomial defining the GF(2) arithmetic is the same as in CMAC, namely, x + x + x + x + 1. One difference with CMAC, however, is that in GCM the field elements are represented with the little-endian convention, i.e., the block [a0, ..., a127] corresponds here to the polynomial a0 + a1x + ... + a127x. We will not change the representation of bytes as bit strings, keeping the big-endian approach used so far (as this has nothing to do with the representation of the elements of GF(2) as bit strings). We start by initializing the GF(2) field and giving a function called blocktopoly for fast conversion of 128-bit blocks to elements of this field:

 >
 >

The inputs of GHASH are a the hash subkey H given as a 128-bit block in list format (in [SP800-38D] this is called a prerequisite since it can be precomputed) and a bit list X whose length is a multiple of 128. The output is a 128-bit block. This function does not use AES but just the multiplication in GF(2); therefore, it is not necessary to format the blocks as states and, for convenience, they are treated here as bit lists rather than byte lists. The only place where the multiplication of GF(2) is used is in GHASH and, to make the implementation more efficient, we will not build a separate function for the multiplication which will be performed by calling the GF package. When doing this we will avoid almost all the conversions, resulting in an efficient multiplication which seems preferable in this case to the method described in [SP800-38D] and in the original submission to NIST [McGrew-Viega], as that method requires a lot of Xors and Shifts which are not that quick in Maple. Now, the GHASH function is the following:

 >

Another primitive of GCM is the function GCTR, a variation of CTR mode used for encryption; its initial counter block for encryption is generated by incrementing a block obtained from the IV. Note that we will use inc32 (as specified in [SP800-38D]) as incrementing function. We model the GCTR function on the CTR mode of EncryptBytes, so that the plaintext and the ciphertext are going to be lists of bytes, as are also the key and the initial counter block ICB. The output is a list of bytes.

 >

The preceding functions give us the primitives we need to build the authenticated encryption and authenticated decryption functions of GCM. As usual, we will first define these functions for lists of bytes and then we will build on top of them the higher level functions that deal with files and strings. We need a function to convert an integer to its 64-bit binary form. It is entirely similar to the bytetobits function but this one is not table-based and hence slower, though it does not matter much as it is only applied twice in each authentication-encryption.

 >

The authenticated encryption function for lists of bytes, GCMAE,  is given next and requires three input lists: an IV (which is essentially a nonce), the plaintext, denoted P, and the additional authenticated data (AAD) herein denoted A. Moreover, another input will be the byte length t of the tag to be produced by the function. The expanded key is required several times here and this is why the key expansion is invoked in this function and not in the lower level ones such as GCTR. There is an initial counter which depends on the IV. In [SP800-38D] it is recommended that implementations restrict support to the length of 96 bits (12 bytes) for IV's, in order to promote interoperability, efficiency and simplicity of design. Following this recommendation we will adopt 12 as the byte-length of the IV and, because of this, the initial counter is just J = IV||0^31||1 (in [SP800-38D] notation, where || denotes concatenation of bit strings). This initial counter is used twice, the first time, increased by 1 (so that, in this case, it is IV||0^30||1||0 in bit string format), to encrypt the plaintext P by means of GCTR, and the other to compute the tag using again GCTR and the output of the GHASH function previously computed. The output of GCMAE is a list consisting of two lists of bytes, the first corresponding to the ciphertext and the second to the tag.

 >

Let's do a few tests taken from [McGrew-Viega]. For example, Test Case 7:

 >

Next, let's try Test Case 16, which uses a 256-bit key:

 >

We are now going to give the authenticated decryption function, which is very similar to the AE one. The input is similar to the one of the AE function with the ciphertext instead of the plaintext and with an additional list of bytes T corresponding to the tag. The output is either the plaintext if authentication was successful or FAIL in other case.

 >

Next we use the authenticated decryption function to validate the result of Test Case 16 above:

 >

We now build the higher level authenticated encryption and authenticated decryption functions. These can be modeled after the ones of CCM, although here the situation is slightly different. The generation of the IV will be done according to one of the two frameworks provided in [SP800-38D] where it is stated that for any supported IV length that is 96 bits or greater (and 96 bits is our only supported IV length), exactly one of these two constructions shall be used for a given key. We will always use the PRNG-based construction described in [SP800-38D, 8.2.2], with empty free field (in the terminology used therein). Thus the IV will be pseudo-randomly generated and we will use BBSByteGen(12) to generate it. The parameters of the encryption function are the plaintext, the AAD, the key (all of them strings), the messagetype (which can be file, text or hex, with the first taken as default), and three keyword parameters (we have not included the seed and primeslength parameters accepted by BBSByteGen in order to keep down the number of them but, if required, the function can be easily modified to accept these parameters). The first keyword parameter, t, is the tag byte length and has 16 as default value. The second is filename, a string with the name of the file where the ciphertext output is to be written (this parameter is only required if messagetype takes file as value), with default obtained by concatenating ".gcm" to the plaintext string (which, in this case, is the name of the file containing the plaintext). Finally, the last parameter filecheck is of type truefalse and takes true as default value, in which case the function checks if a file named filename exists before writing the ciphertext to this file. The output of this function is the ciphertext given as a hex string (when the plaintext is either a text or a hex string) or a file (when the plaintext is a file). The limits on the sizes of the plaintext and the associated data are enforced by this function that returns an error message if some of them is not respected. The output data of the authenticated encryption function is a string obtained by concatenating the IV, the ciphertext C and the authentication tag T. As mentioned, we use 16 as default for the byte length t of T but any of the values in the recommended 12..16 range can be used; the user should bear in mind that a single, fixed value of t among all the supported choices shall be associated with each key (i.e., no different values of t shall be used with the same key).

 >

The GCM decryption function is similar to the encryption one. As input, the same parameters are used with the ciphertext replacing the plaintext. In this case, filename takes as default the result of calling defaultfilename("gcm", ciphertext)  (recall that in case the filename parameter is actually used the argument passed to  ciphertext is just the name of the file containing the ciphertext). Thus if the ciphertext file was produced by GCMEncrypt, then the original name of the file containing the plaintext will be recovered, otherwise the name of the decrypted file will be obtained by appending to the name of the encrypted file the suffix ".decrypted".

 >

A quick test of these functions is the following:

 >

Next we give the GMAC function, which is the specialization of GCM to an empty plaintext, providing authentication only. Since in this case the message is not encrypted, the IV will not be concatenated to the message but it will be passed as an argument to the function. The input parameters are the message, the key, the IV (all of them strings), the message type (text, hex or file, with the latter the default) and a keyword parameter t containing the tag length (16 by default). The output is the MAC given as a hex string.

 >

The verification function GmacVer is given next. The input parameters are the same as those of Gmac with the addition of the MAC (as a hex string) and without the tag length which can be deduced from it. The output is either VALID if the MAC corresponds to the message under the given key or INVALID otherwise.

 >

Let's do a test corresponding to Test Case 1 in [McGrew-Viega] by computing the MAC with Gmac and then checking that the previously generated tag corresponds to the empty string with the 0 IV and key:

 >

A final remark on GCM is the following. In [McGrew-Viega] and also in [SP800-38D], it is explicitly stated that the tag length must be fixed for each key. A possible way to enforce this restriction is to associate the tag length with the key. The PseudoRandomKeyGen generating function (for this mode at least and perhaps for other authentication modes) could have an (optional) parameter to specify the tag length. If this parameter were present then the key would consist of two components, the key itself and the associated tag length, so that the latter would be derived from the key in the preceding functions and the last parameter t of these functions would be dropped. However, we will not implement this and leave to the user the care of using a fixed tag length for each key.

Validation tests

In this section we include some tools to test the code in the worksheet.

Displaying AES constants and tables

We start by setting up an explicit display of some of the constants and tables used in AES, namely, the S Box, the inverse S Box, the matrices used in MixColumns and its inverse, and the round constants Rcon. The S Box and its inverse will be displayed as 16x16 matrices whose entries will be bytes in hex format. If we index the rows and columns of these matrices by the hex digits from 0 to f, the result of applying SubBytes to the byte whose hex form is "ij" (where i and j are hex digits) is the matrix entry in row i and column j. Similarly for the inverse S Box and InvSubBytes. The other objects mentioned are also displayed as matrices and in all cases the entries are given in hexadecimal format. The next auxiliary function is similar to the previously given function to convert lists of bytes to hex strings but it acts on single bytes instead and, for readability, it does not convert them to strings but to hex symbols:

 >

The next function is the one that displays the objects mentioned above. The input may be one of the following strings: "SBox", "InvSBox", "MC", "IMC" or "Rcon". Note that, to allow the S Box and the inverse S Box to be displayed on screen, the rtablesize variable of the interface command is set to 16 and, after printing the required object, it is returned to the original value, which may or may not be the default.

 >

As an example of the use of the displaying function, we have:

 >

Known Answer Tests (KAT) and other AES Tests

We start with some of the Known Answer Tests in [AESAVS] and we first give the variable text test. The output are the plaintexts printed alongside the corresponding ciphertexts, both given as lower case hex strings as in [AESAVS].

 >

For example, the test values corresponding to a keylength of 192 (where the key is 0) are:

 >

Now, the variable key text is very similar to the preceding one. In this case, the roles of the key and the plaintext are interchanged so that the plaintext is fixed and the key varies.

 >

The test values corresponding to a variable 128-bit key are:

 >

We now give encryption/decryption tests for the confidentiality modes of operation, based on the example vectors in [SP800-38A]. The output of these functions prints only the successive plaintext/ciphertext blocks produced.

 >
 >

The following hex plaintext and 128-bit hex key are used in [SP800-38A]. We next carry out the tests for several modes with this plaintext and key:

 >
 >
 >

Let's now make the encryption test in CTR mode with 256-bit key:

 >

Note that, in order to apply DecryptTest, we first have to strip the IV (in the case of modes other than ECB) and also the padding (in all modes) out from the ciphertext if it was obtained from EncryptText or, simply, we can take as plaintext the output of the corresponding EncryptTest which was already checked. For example, for CBC mode we can use the following ciphertext which was obtained in the encryption test above (it consists of the four strings concatenated into one), and we recover the plaintext:

 >

AES (Pseudo-)Random Tests

We are now going to provide a couple of functions that do not test compliance with the standards but rather the fact that encryption followed by decryption recovers the original plaintext. First we give the test for the text encryption/decryption functions. The input of the following function is the number of iterations to be performed and the maximum length of the text strings to be tested. The procedure generates pseudo-random strings of variable length between 1 and the maximum specified length. For each of these strings, the procedure generates a pseudo-random key of any of the three possible lengths (where the keylength is also pseudo-randomly chosen) and picks (again pseudo-randomly) one of the five confidentiality modes. Then the string is encrypted and the corresponding ciphertext is decrypted with the key and mode just generated. The decrypted string is then compared to the original one and the iteration of the test is passed if both strings are equal. The test is successfully passed when all these comparisons match, in which case a message is printed at the end informing the user that the test was successful. If the test fails at some iteration, then a message is printed indicating the string, key and mode that produced the failure. Furthermore, in this case the test gives as output a sequence with the string, key and mode involved, so that one could make further tests with these data (hopefully, this will not be needed ....).

 >
 >

Now we will give the function to test encryption and decryption of binary files. The input has two parameters, a file name and a positive integer which corresponds to the number of encryption/decryption processes to be performed. The first argument must be either the name of a file in the current directory or the full path to the file that is to be encrypted/decrypted. Needless to say, this test should only applied to easily replaceable files or to files that can be discarded (as the file will be overwritten twice for each iteration, the first time with the encrypted version and the second with the decrypted one). After each iteration, i.e., after each encryption/decryption process, the file contents are read and compared to those of the original file and, if all these comparisons match, the test ends by printing a message informing that it was successfully passed. If the test fails at some iteration, an informative message is printed and the key and mode for which the test failed is returned by the procedure. Moreover, the test writes either to the terminal (if logoutput = terminal) or to a file (if logoutput = file), a log of the operations performed where also the keys and modes used are recorded. In the latter case, the name of the log file is the same as the one of the file being tested with the suffix ".log" appended. When performing this test one should also bear in mind that, depending on the size of the file, the running time could be long, so the number of iterations should not be chosen too high.

 >

For example, we can use the previously generated file "testfile" to carry out the test:

 >

If, instead of choosing logoutput = terminal we set logoutput = file, then a similar message is written to the file "testfile.log" and only the last line of the message is printed on the screen.

CMAC Test

We give a function that tests CMAC by producing output in the format used in the Examples of Appendix D in [SP800-38B]. The formatted output will be printed by the next function that will also be used when testing CCM:

 >

Now, the function that does the CMAC test is the following:

 >

We now do Example D3 in [SP800-38B]:

 >

CCM Test

Next we present a function to test CCM mode. It is modeled after the previous function CCMGE and the output has the same format as the Example Vectors in [SP800-38C]

 >

The following key is used in the [SP800-38C] examples:

 >

Let's do the first example and the third example:

 >
 >

Finally, Example 4 in [Sp800-38C]:

 >

GCM Test

Next, a function to test GCM mode by displaying test vectors as in [McGrew-Viega], which we take as model, though we omit some intermediate outputs:

 >

To carry out the tests, let's define some keys, IV's, plaintexts ...

 >
 >

Next, we define a few more inputs and do Test Case 4 in [McGrew-Viega]:

 >
 >

Diffusion tests

In his paper "Communication theory of secrecy systems", published in 1949, C. Shannon introduced, in the context of information theory, the concept of diffusion as a desirable property of a cryptosystem in order to make it resistant to statistical cryptanalytic attacks. Informally, the diffusion of a cryptosystem is high when the change of one plaintext character (or bit) produces the change of many ciphertext characters (or bits). For a block cipher such as AES, this means that diffusion propagates small changes in a plaintext block to a large part of the corresponding ciphertext block. In modern cryptography, a block cipher such as AES is usually assumed to be a (strong) pseudo-random permutation ([Katz-Lindell]), which allows the construction of encryption schemes that are resistant to chosen plaintext attacks and, informally, means that the forward cipher function corresponding to a randomly chosen key is indistinguishable (to a "polynomially bounded" adversary) from a permutation chosen uniformly at random from the set of all the permutations of the set of (128-bit in the case of AES) blocks. The "strong" version of the concept means that the function should be indistinguishable even if the adversary has oracle access to the inverse cipher function (i.e., can query an oracle -a black box- about the value of the inverse function at any given block) (see [Katz-Lindell] for detailed definitions). Of course, having good diffusion properties is a necessary but not sufficient condition to be a pseudo-random permutation and we will check for "good diffusion" by looking at two properties. The first is that there should not be correlation between the Hamming distance (i.e., the number of different bits) between plaintext blocks and the Hamming distance between the corresponding ciphertext blocks and, more specifically that plaintext blocks within low Hamming distance -and, in particular, adjacent blocks, i.e., blocks within Hamming distance equal to 1- may produce ciphertext blocks separated by large Hamming distances (note that, when working at the byte level as we will also do, bits should be replaced by bytes in the preceding discussion and, of course, in that case Hamming distance between blocks refers to the number of different bytes). The second is that, in addition, the positions of flipped bits obtained when comparing the ciphertexts corresponding to adjacent blocks should be uniformly distributed within each block. Of course, all of these properties are implied by pseudo-randomness, for then one should not be able, for example, to distinguish the Hamming distances between pairs of ciphertext blocks arising from pairs of plaintext blocks within short distance from the ones between pairs of ciphertext blocks arising from randomly chosen pairs of plaintext blocks.

To analyze the diffusion properties of AES we will construct tests that give a graphic representation of these properties as well as perform certain statistical tests. We will only test the AES forward cipher function which is equivalent to working with ECB mode; other modes could be tested as well but all of them rely on the use of this function, so this test is relevant for them too. We will work under the hypothesis that AES is a pseudo-random permutation and we will measure the distances and the distribution of bit flips between ciphertext blocks arising from plaintext blocks that are within short distance to check that they behave as expected. The test will work either at the byte level or the bit level. We will start with a 16-byte AES block and encrypt it under a given key. Then we will modify the block by (pseudo-) randomly changing the value of just one byte (or one bit), encrypt it, and compare the resulting ciphertext with the one corresponding to the preceding block, measuring how many bytes (or bits) have changed and/or recording the positions of these changes. We will iterate the process by changing another byte/bit, encrypting the new block and comparing the ciphertext again with the previous one and so on. First we give a function to (pseudo-) randomly change one byte in a given block (note that here we use the Mersenne Twister PRNG, which is perfectly adequate for this purpose).

 >

As we want to test also the bit diffusion properties,  we also give a procedure to pseudo-randomly flip one bit in a 16-byte block:

 >

The Hamming distance between two blocks may be measured by doing the BitXor of both blocks and counting the number of 1-bits (i.e., the Hamming weight) of the resulting block. To speed up the process, we make a table that contains the Hamming weight of each byte:

 >

Now, the procedure that counts the number of 1-bits in a block  (i.e., computes the Hamming weight of the block) given as a state Array is the following:

 >

The next function collects the sample data to carry out the tests. The input arguments of the test function are a 16-byte block given as a list, the key also as a list of bytes (both of these parameters evaluate to pseudo-randomly generated 16-byte lists by default), and five keyword parameters. The first two keyword parameters are rounds, to specify the number of rounds that one wants to test (the default is the number of rounds Nr corresponding to the size of the key being tested) and samplesize, the number of iterations (equivalently, the number of "adjacent" blocks tested which is 1000 by default). The next parameter, testlevel, can take as values either bit or byte and specifies whether the function will test bit diffusion (when testlevel = bit, the default) or byte diffusion (when testlevel = byte). Another keyword parameter, missingop, specifies if any of AES operations is going to be omitted (in order to test the influence of the operations in the diffusion properties). The valid arguments for missingop are MC if the MixColumns operation is going to be omitted from the AES rounds, SR if the ShiftRows operation is omitted or none (the default) if no operation is omitted, i.e., the full AES algorithm is tested. Finally, the last parameter, output, specifies the type of data that is going to be collected. If output = distance (the default), then the output of the procedure is a one-dimensional Array containing the Hamming distances (either in bit or bytes according to the value of testlevel) between the ciphertexts corresponding to the pairs of adjacent blocks generated. For this, the initial block is modified samplesize times by the preceding function and the result of encrypting each block is compared with the result of encrypting the next (adjacent) block. In case output = diffusion, the output is a one-dimensional Array (with 128 entries if testlevel = bit and 16 entries if testlevel = byte) which records, in each position, how many times the corresponding bit (or byte) changed value when passing from one ciphertext to the one corresponding to the next (adjacent) block.

 >

Note that calling the above function with a value of rounds less than the number of rounds Nr that corresponds to the supplied key will perform that number of full rounds in addition to the initial "0-th round" which only performs an AddRoundKey operation. If, on the other hand, rounds = Nr (the maximum value it can take), then the last round is the "reduced last round" of AES, in which the MixColumns operation is missing (of course, if missingop = SR is selected, then ShiftRows will be also missing from all the rounds including the last).
We are now ready for the Hamming distance test, which is implemented in the next function. It is a simple test that gives a visual image -and also a goodness of fit test- of the good pseudo-random properties of AES in relation with Hamming distance; for a full suite of statistical tests to evaluate (pseudo-) randomness see [SP800-22] and for a discussion of statistical analyses of AES see [Hellekalek-Wegenkittl]. The arguments of the function are the same as those in the previous function except output, which is missing, and an additional argument, display, which is used to select the type of graphical representation that the test will produce. The arguments that can be passed to this parameter are freqplot, linechart, histogram or normalplot (with names that correspond to the ones used in the Statistics  package). The output of the function is a graphical representation of the Hamming distances between ciphertext blocks corresponding to pairs of adjacent blocks together with a summary of the statistics of the sample and -in most cases- a Chi Square goodness-of-fit test to determine whether the obtained sample follows the expected binomial distribution (one should bear in mind that this is less likely in the case of tests with a lower number of rounds or missing operations).

 >

Let's do a Hamming distance test with default values. Under the pseudo-randomness hypothesis, the Hamming distance corresponding to ciphertext pairs coming from adjacent blocks should be distributed like the Hamming distance for random pairs of blocks and hence it should behave as a random variable which follows a binomial distribution B(128, 0.5). Maple's function Statistics:-ChiSquareSuitableModelTest tests whether this is indeed the case.

 >

Next we carry out the same test at the byte level. Now, the Hamming distances are expected to follow the binomial distribution B(n, p), with n = 16 and p = 255/256.

 >

Different results are obtained if, for example, the number of tested rounds is low, when one expects less diffusion to occur. The most extreme case is when rounds = 1 and then (assuming also that missingop = none, i.e., all operations are used) the byte Hamming distance between the ciphertext blocks corresponding to an adjacent pair is exactly 4. The reason is that, after applying SubBytes and ShiftRows, only one byte has changed and then MixColumns changes all the bytes in the column of the state matrix to which this changed byte belongs. At the bit level, one would expect the average Hamming distance to be 2/255 but one should not expect a lot of pseudo-randomness in just one round. If we move on to the case when rounds = 2 then, as is well known, AES already has complete diffusion in the sense that all the bits of a ciphertext block may change as a consequence of changing only one bit in the plaintext block. If we look at Hamming distances at the byte level, we see that they take constant value 16 for pair of ciphertext blocks coming from adjacent blocks. This is because, after one round the state has 4 changed bytes all in the same column and then, in the second round, all these bytes are moved each one to a different column by the ShiftRows operation. At this moment, each of the columns of the state matrix has exactly one byte different from the corresponding one in the state coming from the adjacent block. Then the MixColumns operation in the second round makes the resulting state to have all 16 bytes different from the ones in the state coming from the adjacent block. At the bit level, the Hamming distance is not constant and it has an expected mean value equal to 128/255.
Let's now analyze the influence of some of the AES operations in the diffusion process. It is clear that AddRoundKey preserves Hamming distances (both at the bit and the byte level) and also SubBytes preserves Hamming distances at the byte level, though not at the bit level. Thus we will analyze the effect of ShiftRows and MixColumns on diffusion by carrying out the test with one of these operations omitted. It is clear that the most important source of diffusion is MixColumns and, if we set missingop = MC, we see that at the byte level, with independence of the value of rounds,the ciphertext blocks corresponding to two adjacent plaintext blocks are also adjacent, i.e., only differ in exactly one byte (so that diffusion is nonexistent). At the bit level, the one different byte in the ciphertexts corresponding to adjacent blocks gives some diffusion as potentially all the bits in the changed byte may change, so the average number of flipped bits should be close to 1024/255. On the other hand, if ShiftRows is omitted, then diffusion is restricted to one column of the state matrix (only the column with the changed byte changes).

The preceding test provides a certain evaluation of AES diffusion but, even if the distribution of Hamming distances is the one expected in case the forward cipher function is a pseudo-random permutation, this does not guarantee that the bit/byte changes are uniformly distributed along the block. Thus, to complete the analysis of AES diffusion, we include the following test which is, in a certain sense, "orthogonal" to the preceding one and hence is a good complement to it. The input data are the same and the test calls the DiffusionSample function to record the number of bit/byte changes in each block position. Under the pseudo-random assumption and with rounds > 2 and missingop = none, one expects that these numbers are distributed according to the binomial distribution B(n,p), where n = samplesize and either p = 0.5 (at the bit level) or p = 255/256 (at the byte level). The output of the function is similar to that of the preceding one, providing a graphical representation of the gathered data, a summary of the statistics of the data and, whenever appropriate, a Chi Square goodness-of-fit test to check the adequacy of the model.

 >

The diffusion test, with default inputs except display = histogram, is the following:

 >

Next we do the diffusion test at the byte level:

 >

In case the number of rounds in test is reduced or some operation is missing, then similar remarks as above apply. For example, with rounds = 2 and missingop = none, one expects that the sample follows the Binomial(samplesize, 128/255) distribution and with the default value of rounds and missingop = MC, the Binomial(samplesize,8/255) distribution (with testlevel = bit in both cases).

 Conclusions We have used Maple's capabilities in several domains including pseudo-random number generation, file and text handling, statistical analysis and, more generally, as a programming environment, to implement and explore the encryption and authentication schemes that use AES as underlying block cipher and are based on the eight modes of operation for block ciphers so far approved by NIST. The implementation uses, whenever possible, lookup tables for efficiency and is able to encrypt/decrypt/authenticate files of moderate size. We have also included tests to analyze either compliance with the standards or some basic properties such as diffusion, which is studied by collecting, displaying (in both text and graphic format) and analyzing statistical data.
 References [SP800-90] E. Barker, J. Kelsey, Recommendation for Random Number Generation using Deterministic Random Bit Generators (Revised), NIST Special Publication 800-90 (2007), available via http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf[AESAVS] L.E. Bassham III, The Advanced Encryption Standard Algorithm Validation Suite, NIST publication (2002) available via http://csrc.nist.gov/groups/STM/cavp/documents/aes/AESAVS.pdf[Bellare-Rogaway] M. Bellare, P. Rogaway, Introduction to Modern Cryptography, available via http://www-cse.ucsd.edu/~mihir/cse207/classnotes.html[Buchmann] J.A. Buchmann, Introduction to Cryptography, Second Edition, Springer-Verlag (2004).[Daemen-Rijmen1] J. Daemen, V. Rijmen, AES Proposal: Rijndael, available via http://csrc.nist.gov/archive/aes/rijndael/Rijndael-ammended.pdf[Daemen-Rijmen2] J. Daemen, V. Rijmen, The design of Rijndael, Springer-Verlag, Berlin (2002).[SP800-38A] M. Dworkin, Recommendation for Block Cipher Modes of Operation: Methods and Techniques, NIST Special Publication 800-38A (2001), available via http://csrc.nist.gov/publications/nistpubs/800-38a/sp800-38a.pdf[SP800-38B] M. Dworkin, Recommendation for Block Cipher Modes of Operation: The CMAC mode for authentication, NIST Special Publication 800-38B (2005), available via http://csrc.nist.gov/publications/nistpubs/800-38B/SP_800-38B.pdf[SP800-38C] M. Dworkin, Recommendation for Block Cipher Modes of Operation: The CCM mode for Authentication and Confidentiality, NIST Special Publication 800-38C (2004), available via http://csrc.nist.gov/publications/nistpubs/800-38C/SP800-38C_updated-July20_2007.pdf[SP800-38D] M. Dworkin, Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC, NIST Special Publication 800-38D (2007), available via http://csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf[FIPS197] Federal Information Processing Standards Publication 197, Specification for the Advanced Encryption Standard (AES) (2001), available via http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf[Geisler-Kroigard-Danielsen] M. Geisler, M. Kroigard, A. Danielsen, About random bits, available via http://www.daimi.au.dk/~mg/mamian/random-bits.pdf[Hellekalek-Wegenkittl] P. Hellekalek, S. Wegenkittl, Empirical evidence concerning AES, ACM Transactions on Modeling and Computer Simulation (TOMACS), 13 (2003), 322-333, available via http://random.mat.sbg.ac.at/ftp/pub/publications/peter/aes_sub.ps [Katz-Lindell] J. Katz, Y. Lindell, Introduction to Modern Cryptography, Chapman & Hall/CRC (2008). [Lenstra] H.W. Lenstra, Jr., Rijndael for algebraists, available via http://math.berkeley.edu/~hwl/papers/rijndael0.pdf[Lidl-Niederreiter] R. Lidl, H. Niederreiter, Introduction to Finite Fields and their Applications, Cambridge University Press (1994).[Matsumoto-Nishimura] M. Matsumoto, T. Nishimura, Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Transactions on Modeling and Computer Simulation (TOMACS), 8 (1998), 3-30, available via http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf[McGrew-Viega] D.A. McGrew, J.Viega, The Galois/Counter Mode of Operation (GCM), Submission to NIST Modes of Operation Process, available via http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-revised-spec.pdf[Monagan-Fee] M. Monagan, G. Fee, A Cryptographically Secure Random Bit Generator for Maple, available via http://www.cecm.sfu.ca/CAG/papers/monfeeMSWS04.pdf[Oppliger] R. Oppliger, Contemporary Cryptography, Artech House (2005).[Stinson] D.R. Stinson, Cryptography Theory and Practice, 3rd Edition, Chapman & Hall/CRC (2005).[Trappe-Washington] W. Trappe, L.C. Washington, Introduction to Cryptography with Coding Theory, Prentice Hall (2002).[Viega] J. Viega, Practical Random Number Generation in Software, Proc 19th Annual Computer Security Applications Conference (2003), 129-140, available via http://www.acsac.org/2003/papers/79.pdf

Legal Notice: The copyright for this application is owned by the authors. Neither Maplesoft nor the authors are responsible for any errors contained within and are not liable for any damages resulting from the use of this material.. This application is intended for non-commercial, non-profit use only. Contact the authors for permission if you wish to use this application in for-profit activities.