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
email: gomez.pardo@usc.es
Carlos GómezRodríguez
Departamento de Computación, Universidade da Coruña
15071 A Coruña, Spain email: cgomezr@udc.es

Introduction


This worksheet contains an implementation (and also a brief explanation) of the Advanced Encryption Standard (AES) block cipher and its modes of operation (which are not exclusive of AES and apply to other block ciphers as well). AES was selected as successor of DES in an open competition to this effect staged by the United States National Institute of Standards and Technology (NIST). The winner of this competition was the Rijndael algorithm, designed by Joan Daemen and Vincent Rijmen, which was specified as a Federal Information Processing Standard (FIPS) under the AES name by NIST in 2001 [FIPS197]. AES is a symmetric block cipher with a 128bit block size and three possible keylengths, namely, 128, 192, and 256 bits. The encryption and decryption functions act in a number of rounds which depends on the size of the key: there are 10 rounds for a 128bit key, 12 rounds for a 192bit key and 14 rounds for a 256bit key. Apart from the already mentioned FIPS publication, AES is described in detail in many books and web pages. Among the books we can mention [Stinson], [Oppliger] and [DaemenRijmen2], where the latter gives a first hand account of the design choices that led to the final form of the algorithm. Among the web pages, apart from the already cited NIST page, we mention Wikipedia's page, the MSDN magazine Encrypt It page, the AES Lounge which contains a lot of additional information, and also H.W. Lenstra's page, where a onepage description of Rijndael is given for people with sufficient algebraic background.
AES can be used to build up encryption or authentication schemes (or schemes that combine both aspects) and for that the so called "modes of operation" are required. The modes of operation allow the encryption of messages of arbitrary length and are a necessary ingredient of AESbased encryption schemes but AES itself is not such a scheme. The security properties of these encryption schemes depend heavily on the mode of operation used. Even if AES behaves like an ideal block cipher, i.e., as a pseudorandom permutation on the 128bit blocks on which the AES encryption function (also called the forward cipher function) acts which would imply that AES is highly secure, ECB mode, for example, is considered insecure. In this mode, if a message or block is repeatedly encrypted with the same key, this fact can be easily detected by an attacker. This is a significant leakage of information that could even allow an active attacker to change the order of the blocks in a message or to replace new messages by old ones without the manipulation being noticed by the legitimate receiver of the information. We refer to the [BellareRogaway] notes and to [KatzLindell] for rigorous and detailed discussion of the issues related to the use of the modes of operation for AES and other block ciphers (for more elementary introductions, the reader may also check [Buchmann] and [TrappeWashington]).
In view of the preceding remarks, one design goal for this project was to cover most of the modes of operation currently in use. In fact, all the modes of operation specified by NIST so far are implemented here: the encryption modes ECB, CBC, CFB (the CFB128 version only), OFB and CTR, the CMAC authentication mode, and the CCM and GCM/GMAC modes for authenticated encryption (another mode, called XTS, is currently proposed for NIST approval and yet more modes will probably be approved in the future). A second design goal was to build up an implementation able to handle plaintexts and ciphertexts in a variety of formats and having the capability of encrypting/decrypting/authenticating real messages and not just short text strings. We feel that, even if the primary purpose of an implementation like this one is to let users to experiment and learn, these goals are best achieved if it can handle these messages. Thus the implementation uses, whenever possible, lookup tables for efficiency and is able to encrypt both text strings and binary files of moderate size, up to several megabytes.
Another aspect worthy of mention is the fact that the implementation contains detailed explanations of the procedures used, including the lower level ones and discussing both the programming and the cryptographic aspects involved in the design choices made. However, with a few exceptions, we have not included linebyline comments in the code itself. Since the code for each function is not too long (with the possible exception of some of the test functions at the end, which are essentially variants of other previously defined functions), we feel that the required explanations are better presented in the text comments surrounding the code, where they are not limited to technical implementation issues but deal with broader aspects related to design choices, to the algorithms, and so on. On the other hand, we have not tried to give a very detailed description of the AES algorithm itself because we feel that there are many excellent presentations in the literature and, in particular, in the references below (several of these presentations can be easily accessed from here just by clicking on the appropriate hyperlink). Nevertheless, the attentive reader can also extract a complete description of the algorithm from our comments and from the code. In the case of the more recent modes such as CCM or GCM/GMAC, we have tried to include some more detail in the comments although, of course, the reader is encouraged to look at the original sources and, in particular, to the NIST publications where these modes are specified.
Apart from the above mentioned features, we have also included a collection of tests. Among them there are tests that check compliance with NIST's specifications and other tests devoted to analyze some basic properties that are cryptographically relevant, such as diffusion, which is studied by collecting, displaying (in both text and graphic format) and analyzing statistical data.
Before starting to describe the contents of the worksheet, a remark on terminology is in order. In Maple, an expression of type "function" is what might be better called a "function call", i.e., citing Maple's help, "an application of a function or procedure to arguments" . Here we will use the term "function", apart from some specific cases in which it refers to the mathematical concept, in the sense it is used in the text of the previous hyperlink, i.e., more or less as a synonym of "procedure".
The broad structure of the worksheet may be sketched as follows. The Initialization section builds most of the lower level functions that will be used through the worksheet. These include, in addition to conversion functions between different kinds of data and functions to generate pseudorandom data such as keys, an implementation of the arithmetic of the 256element field GF(2 ) which, in turn, is used to construct the round constants required by the Key Schedule process the process that generates the round subkeys from an AES key and the SBox, a permutation of GF(2 ) that underlies one of the AES operations. These operations, as well as the Key Schedule are defined in the next section (AES operations). Then there is a section, Lowlevel AES functions, devoted to functions that do lowlevel AES encryption and decryption by processing either one state (an AES block formatted as a 4x4 Array of bytes) or a list of bytes. These functions may operate in any of the five confidentiality modes and, in this section, functions are also provided for generating initialization vectors and for padding. The next section (AES encryption and decryption functions) builds up the higher level functions that are used for encrypting/decrypting data in the usual formats. Among them there are keygenerating functions, functions to encrypt and decrypt binary files, functions to encrypt and decrypt text strings, and functions to encrypt and decrypt text files (line by line). These functions can encrypt or decrypt data in any of the five confidentiality modes. The next section, Authentication, is devoted to CMAC authentication mode and has functions for generation and verification of the MAC associated to a message. In the Authenticated Encryption section, the two modes for authenticated encryption approved by NIST (CCM and GCM/GMAC) are implemented. Then there are two sections devoted to provide tests for the implementation. First, Validation tests, where tests that check compliance with the algorithms approved by NIST are given. These include functions to display on screen several constant and tables used by AES, some random tests and Known Answer Tests that check whether the implementation of AES encryption (or authentication) in the different modes behaves as expected by comparing the results with the "example vectors" provided in NIST publications. The output of these functions is formatted as in NIST publications to facilitate the comparison. Then there is a section on Diffusion tests, in which functions are given to collect and display statistical data and to perform some simple statistical tests related to the diffusion properties of AES. The final section contains the references, with hyperlinks to the appropriate web pages in case they are online (in fact, all of them are except the books).
Finally, a few remarks about function naming and type checking. In general, we have tried to use meaningful names for the functions we define. These names tend to be long but they are easier to remember and to identify than shorter names. In the case of lower level procedures that are intended to be called from other functions and not directly by the user, we often use lower case letters only. For functions that are to be called by the user or that have a definite cryptographic meaning we frequently use a concatenation of the words that describe the function with the initial letter of each word in upper case. Also, to allow for more compact code when calling functions from Maple packages, one could use the with command in the Initialization section to make the short names of these functions available. However, there are some cases in which two of the packages we use export the same name (for example, LengthSplit, Reverse and Rotate are common to both ListTools and StringTools, Generate is common to StringTools and RandomTools, Random is common to StringTools and LinearAlgebra:Modular ...). We could still use the short form of these names in many situations but this would require keeping track of the order in which the names of the different packages were exported, creating a potential source of confusion. To prevent this and also to make the code usable in different contexts without further modification, we have decided to use the long function names even in case these names are not repeated in different packages. Regarding type checking, it is minimal or even nonexistent in low level functions but we have tried to make extensive use of it in the higher level ones. Also, for many of high level functions and for the convenience of the user, we have provided default values for some of the parameters, whenever it makes sense.


Version, requirements and copyright


Version: 1.1
Requirements: Maple v11 or higher
Copyright Notice: © (20082010) José Luis Gómez Pardo, Carlos GómezRodrí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 noncommercial, nonprofit use only. Contact the authors for permission if you wish to use this application in forprofit activities.


Initialization


> 


GF(2 )


AES, like other symmetric block ciphers, is byteoriented 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 8bit 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 bigendian 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 littleendian 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 256element field GF(2) defined by the irreducible polynomial x + x+ x + x +1 (a good reference for finite fields and their applications is [LidlNiederreiter]). 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 Z_{2}[X], where Z_{2} = 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 Z_{2}[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 bigendian 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 8bit 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 twodigit hex string corresponding to one byte. More generally, we can represent any list of bytes (as integers in the 0..255 range) by the evenlength 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 booleanvalued 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 BlumBlumShub; 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 BitXoring 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 2dimensional Array as a 1dimensional 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 8bit 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 4byte words (herein represented as 4byte 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 8bit 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 pseudorandom generator


An important role is played in this worksheet (and, more generally, in cryptography) by the pseudorandom 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 [MatsumotoNishimura], 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 BlumBlumShub (BBS) generator (see, for example, [Stinson] or [GeislerKroigardDanielsen] for a security proof, and also [MonaganFee] 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 pseudorandom 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 [SP80090]). 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 pseudorandom 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 1024bit primes and, similarly, n512 and n768 evaluate, respectively, to a 308digit product of two 512bit primes and a 462digit product of two 768bit 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 pseudorandom 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 pseudorandom 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 [MonaganFee]. 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 BlumBlumShub 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 [MonaganFee] 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 128bit 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 2dimensional 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..30..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 4byte word, which is done here by means of the previously defined function SB.
> 

For example, let's look at the expanded key for a 128bit 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.
> 



AddRoundKey


The AddRoundKey operation is simply the result of BitXoring 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.
> 




Lowlevel 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 0bytes. 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 16byte 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 16byte 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 1dimensional 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 errorchecking 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 80038A]. 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 socalled 32bit incrementing function which consists in adding 1 to the counter modulo 2, when the counter is viewed as a 16digit number in base 256, in bigendian order, i.e., with the most significant byte first. Therefore, the 32bit 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 32bit version provides for 2 different counter values. Since each of these values is used to encrypt one 2byte 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 24 bytes, which is close to 64 MB. It is possible to modify the implementation to allow for larger plaintexts but, given other realistic spacetime 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 (AES128) 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 BlumBlumShub through the BBSByteGen function to generate a pseudorandom 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 pseudorandom 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 pseudorandom 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 24hour clock format), the minute and the second. This sequence of 6 bytes is then completed with n6 pseudorandomly 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 nonregular 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 pseudorandomly 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 [SP80038A]. 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 16byte 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 221 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 16digit base256 number. Assuming that the pseudorandom 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 8byte number that may correspond to the pseudorandom part of the nonce/counter and 0, namely 21, so that an increase of 221 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 pseudorandom part of the nonce, one should encrypt, at least, (221)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 0bytes:
> 

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 lowlevel 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.
> 



Padding


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 128bit 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 256bit 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 [BellareRogaway, KatzLindell]. 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 indepth 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 pseudorandom 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 bruteforce attacks; for example, if randomly chosen 32bit 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 32bit seeds produced by these functions are not large enough to prevent bruteforce 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 256bit keys we would have to generate fewer random bits by using the PRNG.
> 

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

A 256bit 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.
> 

Let's check a hexadecimal key;
> 



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 24. 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 192bit 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 8bit 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 8bit ASCII character set is not a good alphabet for our purposes as it contains many nonprintable characters. Thus, while we will deal with 8bit 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 CBCMAC). 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, AESbased CBCMAC is insecure and, in particular, is vulnerable to forgeries when used to authenticate variable length messages [BellareRogaway, KatzLindell]. Because of this, the basic CBCMAC 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 [SP80038B] and its references).

CMAC


The core of the CMAC algorithm is a variation of CBCMAC 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 k_{1}, k_{2} are used. If no padding was added, the algorithm is the same as CBCMAC except for the fact that, before encrypting the last block with k, this block is Xored with k_{1}. If, on the other hand, padding was added, then a similar operation is performed, Xoring the last block with k_{2} before encryption. CMAC proceeds in a similar way, except for the fact that keys k_{1} and k_{2} 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 Z_{2}[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..21 range and hence by the 128bit (or 16byte) vectors (where the most significant bit or byte is the leftmost one). Let then L = E_{k}(0) be the result of encrypting the 0block with AES using k as key. L is an element of GF(2) and the CMAC subkeys k_{1} and k_{2} are obtained by taking k_{1} = 2L (where " denotes multiplication in GF(2)) and k_{2} = 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 16byte 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 [SP80038B]:
> 

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 [SP80038B]. 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 [SP80038C]. 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: generationencryption and decryptionverification. 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 generationencryption, 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 decryptionverification, 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 generationencryption 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 B_{0}, ..., B_{r}. The formatting function is only required to satisfy three conditions which are specified in [SP80038C], 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 [SP80038C] 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 [80038C], 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 [SP80038C] 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 [SP80038C] 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 16byte 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 B_{0}, 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 3bit 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 B_{0} 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 16byte blocks B_{1}, ..., B_{u} (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 16byte blocks. The input arguments of the formatting function are the nonce, the associated data, the payload, and the tag length. The output is a onedimensional Array whose entries are twodimensional 0..3,0..3 Arrays containing the data blocks.
> 

Next we give the generationencryption and decryptionverification 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 generationencryption 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 decryptionverification 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 encryptiongeneration function (the one that accepts as input either files or strings to be encryptedverified).
> 

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

Next, Example 4 in [SP80038C]. This example should produce as output the 368bit (48 bytes) ciphertext hex string given in [SP80038C], 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 sizepayload 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 generationencryption 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 decryptionverification 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 decryptionverification function. Note that in [SP80038C] 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 verificationdecryption 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 encryptionverification function to this file producing a file named "testfile2.ccm". Then we apply the decryptionverification 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 [SP80038D]. 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, nonconfidential 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 CBCMACbased 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 128bit (16byte) 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 littleendian convention, i.e., the block [a_{0}, ..., a_{127}] corresponds here to the polynomial a_{0} + a_{1}x + ... + a_{127}x. We will not change the representation of bytes as bit strings, keeping the bigendian 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 128bit blocks to elements of this field:
> 

> 

The inputs of GHASH are a the hash subkey H given as a 128bit block in list format (in [SP80038D] 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 128bit 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 [SP80038D] and in the original submission to NIST [McGrewViega], 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 [SP80038D]) 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 64bit binary form. It is entirely similar to the bytetobits function but this one is not tablebased and hence slower, though it does not matter much as it is only applied twice in each authenticationencryption.
> 

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 [SP80038D] 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 bytelength of the IV and, because of this, the initial counter is just J = IV0^311 (in [SP80038D] 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 IV0^3010 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 [McGrewViega]. For example, Test Case 7:
> 

Next, let's try Test Case 16, which uses a 256bit 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 [SP80038D] 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 PRNGbased construction described in [SP80038D, 8.2.2], with empty free field (in the terminology used therein). Thus the IV will be pseudorandomly 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 [McGrewViega] 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 [McGrewViega] and also in [SP80038D], 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 128bit key are:
> 

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

> 

The following hex plaintext and 128bit hex key are used in [SP80038A]. 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 256bit 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 pseudorandom strings of variable length between 1 and the maximum specified length. For each of these strings, the procedure generates a pseudorandom key of any of the three possible lengths (where the keylength is also pseudorandomly chosen) and picks (again pseudorandomly) 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 [SP80038B]. 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 [SP80038B]:
> 



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 [SP80038C]
> 

The following key is used in the [SP80038C] examples:
> 

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

> 

Finally, Example 4 in [Sp80038C]:
> 



GCM Test


Next, a function to test GCM mode by displaying test vectors as in [McGrewViega], 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 [McGrewViega]:
> 

> 




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) pseudorandom permutation ([KatzLindell]), 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 (128bit 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 [KatzLindell] for detailed definitions). Of course, having good diffusion properties is a necessary but not sufficient condition to be a pseudorandom 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 pseudorandomness, 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 pseudorandom 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 16byte 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 pseudorandomly flip one bit in a 16byte block:
> 

The Hamming distance between two blocks may be measured by doing the BitXor of both blocks and counting the number of 1bits (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 1bits 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 16byte block given as a list, the key also as a list of bytes (both of these parameters evaluate to pseudorandomly generated 16byte 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 onedimensional 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 onedimensional 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 "0th 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 pseudorandom properties of AES in relation with Hamming distance; for a full suite of statistical tests to evaluate (pseudo) randomness see [SP80022] and for a discussion of statistical analyses of AES see [HellekalekWegenkittl]. 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 goodnessoffit 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 pseudorandomness 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 pseudorandomness 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 pseudorandom 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 pseudorandom 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 goodnessoffit 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).


References


[SP80090] E. Barker, J. Kelsey, Recommendation for Random Number Generation using Deterministic Random Bit Generators (Revised), NIST Special Publication 80090 (2007), available via http://csrc.nist.gov/publications/nistpubs/80090/SP80090revised_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 [BellareRogaway] M. Bellare, P. Rogaway, Introduction to Modern Cryptography, available via http://wwwcse.ucsd.edu/~mihir/cse207/classnotes.html [Buchmann] J.A. Buchmann, Introduction to Cryptography, Second Edition, SpringerVerlag (2004). [DaemenRijmen1] J. Daemen, V. Rijmen, AES Proposal: Rijndael, available via http://csrc.nist.gov/archive/aes/rijndael/Rijndaelammended.pdf [DaemenRijmen2] J. Daemen, V. Rijmen, The design of Rijndael, SpringerVerlag, Berlin (2002). [SP80038A] M. Dworkin, Recommendation for Block Cipher Modes of Operation: Methods and Techniques, NIST Special Publication 80038A (2001), available via http://csrc.nist.gov/publications/nistpubs/80038a/sp80038a.pdf [SP80038B] M. Dworkin, Recommendation for Block Cipher Modes of Operation: The CMAC mode for authentication, NIST Special Publication 80038B (2005), available via http://csrc.nist.gov/publications/nistpubs/80038B/SP_80038B.pdf [SP80038C] M. Dworkin, Recommendation for Block Cipher Modes of Operation: The CCM mode for Authentication and Confidentiality, NIST Special Publication 80038C (2004), available via http://csrc.nist.gov/publications/nistpubs/80038C/SP80038C_updatedJuly20_2007.pdf [SP80038D] M. Dworkin, Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC, NIST Special Publication 80038D (2007), available via http://csrc.nist.gov/publications/nistpubs/80038D/SP80038D.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/fips197.pdf [GeislerKroigardDanielsen] M. Geisler, M. Kroigard, A. Danielsen, About random bits, available via http://www.daimi.au.dk/~mg/mamian/randombits.pdf [HellekalekWegenkittl] P. Hellekalek, S. Wegenkittl, Empirical evidence concerning AES, ACM Transactions on Modeling and Computer Simulation (TOMACS), 13 (2003), 322333, available via http://random.mat.sbg.ac.at/ftp/pub/publications/peter/aes_sub.ps
[KatzLindell] 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 [LidlNiederreiter] R. Lidl, H. Niederreiter, Introduction to Finite Fields and their Applications, Cambridge University Press (1994). [MatsumotoNishimura] M. Matsumoto, T. Nishimura, Mersenne twister: a 623dimensionally equidistributed uniform pseudorandom number generator, ACM Transactions on Modeling and Computer Simulation (TOMACS), 8 (1998), 330, available via http://www.math.sci.hiroshimau.ac.jp/~mmat/MT/ARTICLES/mt.pdf [McGrewViega] 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/gcmrevisedspec.pdf [MonaganFee] 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). [TrappeWashington] 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), 129140, 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 noncommercial, nonprofit use only. Contact the authors for permission if you wish to use this application in forprofit activities.
