AES1.html

The Advanced Encryption Standard and its modes of operation

José Luis Gómez Pardo

Departamento de Álxebra, Universidade de Santiago

15782 Santiago de Compostela, Spain

e-mail: gomez.pardo@usc.es

Carlos Gómez-Rodríguez

Departamento de Computación, Universidade da Coruña

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

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 128-bit 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 128-bit key, 12 rounds for a 192-bit key and 14 rounds for a 256-bit 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 [Daemen-Rijmen2], 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 one-page 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 AES-based 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 pseudo-random permutation on the 128-bit 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 [Bellare-Rogaway] notes and to [Katz-Lindell] 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 [Trappe-Washington]).

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 line-by-line 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 pseudo-random data such as keys, an implementation of the arithmetic of the 256-element 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, Low-level AES functions, devoted to functions that do low-level 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 key-generating 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 on-line (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 non-existent 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

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

Initialization

GF(2⁸)

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

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

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

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

For example, we have:

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

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

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

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

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

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

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

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

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

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

16381 bytes saved to testfile

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:

1100 bytes saved to paz.txt

Next, we consider a hex string:

64 bytes saved to hex64

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

The BitXor operation

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

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

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

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

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

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

The multiplication in GF(2⁸)

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

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

The round constants

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

The list of round constants, Rcon, is then:

The SBox

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

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

Matrix(%id = 162620856), Vector[column](%id = 153839764)

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

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

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

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

The pseudo-random generator

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

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

> $`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$
$`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$
$`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$
$`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$
$`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$
$`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$
$`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$
$`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$
$`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$
$`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$
$`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$
$`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$
$`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$
$`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$
$`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$
$`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$
$`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$
$`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$
$`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$
$`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$
$`:=`(BBSByteGen, proc (`::`(length, posint), `::`(seed, {posint, string}), { `:=`(`::`(format, name), list), `:=`(`::`(primeslength, {512, 768, 1024}), 1024) }) local s, B, l; if _params['seed'] = NUL...$

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

AES operations

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

SubBytes and its inverse

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

ShiftRows and its inverse

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

MixColumns and its inverse

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

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

The Key Schedule

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

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

[Matrix(%id = 162689560), Matrix(%id = 162689608), Matrix(%id = 162689664), Matrix(%id = 162689720), Matrix(%id = 162689776), Matrix(%id = 162689832), Matrix(%id = 162689888), Matrix(%id = 152722956),...

AddRoundKey

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

Low-level AES functions

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

The Rijndael rounds and the cipher and inverse cipher functions

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

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

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

Finally, the inverse cipher function:

Encrypting and decrypting lists of bytes

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

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

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

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

The encryption function for lists of bytes is then:

> `(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">
`(mode, "ecb") t..." align="center" border="0">

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

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

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

Initialization vectors

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

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

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

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

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

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

> $`:=`(checkiv, proc (`::`(iv, {string, list(integer[0 .. 255])})) if _params['iv'] = NULL then return NULL elif type(iv, list) then if `<>`(nops(iv), 16) then error$
$`:=`(checkiv, proc (`::`(iv, {string, list(integer[0 .. 255])})) if _params['iv'] = NULL then return NULL elif type(iv, list) then if `<>`(nops(iv), 16) then error$
$`:=`(checkiv, proc (`::`(iv, {string, list(integer[0 .. 255])})) if _params['iv'] = NULL then return NULL elif type(iv, list) then if `<>`(nops(iv), 16) then error$
$`:=`(checkiv, proc (`::`(iv, {string, list(integer[0 .. 255])})) if _params['iv'] = NULL then return NULL elif type(iv, list) then if `<>`(nops(iv), 16) then error$
$`:=`(checkiv, proc (`::`(iv, {string, list(integer[0 .. 255])})) if _params['iv'] = NULL then return NULL elif type(iv, list) then if `<>`(nops(iv), 16) then error$
$`:=`(checkiv, proc (`::`(iv, {string, list(integer[0 .. 255])})) if _params['iv'] = NULL then return NULL elif type(iv, list) then if `<>`(nops(iv), 16) then error$
$`:=`(checkiv, proc (`::`(iv, {string, list(integer[0 .. 255])})) if _params['iv'] = NULL then return NULL elif type(iv, list) then if `<>`(nops(iv), 16) then error$
$`:=`(checkiv, proc (`::`(iv, {string, list(integer[0 .. 255])})) if _params['iv'] = NULL then return NULL elif type(iv, list) then if `<>`(nops(iv), 16) then error$
$`:=`(checkiv, proc (`::`(iv, {string, list(integer[0 .. 255])})) if _params['iv'] = NULL then return NULL elif type(iv, list) then if `<>`(nops(iv), 16) then error$
$`:=`(checkiv, proc (`::`(iv, {string, list(integer[0 .. 255])})) if _params['iv'] = NULL then return NULL elif type(iv, list) then if `<>`(nops(iv), 16) then error$
$`:=`(checkiv, proc (`::`(iv, {string, list(integer[0 .. 255])})) if _params['iv'] = NULL then return NULL elif type(iv, list) then if `<>`(nops(iv), 16) then error$
$`:=`(checkiv, proc (`::`(iv, {string, list(integer[0 .. 255])})) if _params['iv'] = NULL then return NULL elif type(iv, list) then if `<>`(nops(iv), 16) then error$
$`:=`(checkiv, proc (`::`(iv, {string, list(integer[0 .. 255])})) if _params['iv'] = NULL then return NULL elif type(iv, list) then if `<>`(nops(iv), 16) then error$

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 128-bit block is added if the plaintext bit length is already a multiple of 128). Using 10ⁱ padding means that, since we work at the byte level and the binary expansion of 128 is 1 followed by seven zeros, we will use a byte 128 to mark the beginning of the padding and then all bytes 0 until completing the desired length (until the byte length is a multiple of 16).

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

AES encryption and decryption functions

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

Key generation

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

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

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

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

A 256-bit key generated with automatic seeding is:

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

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

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

16400 bytes saved to ctestfile

16381 bytes saved to dtestfile

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

16397 bytes saved to ctestfile

16381 bytes saved to dtestfile

Text encryption and decryption

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

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

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

Encrypting and decrypting text files

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

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

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

Authentication

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

CMAC

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

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

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

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

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

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

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

The resulting MAC's are the following:

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

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

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

Authenticated Encryption

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

CCM mode

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

The payload P and the associated data A may be empty. In the first case, CCM reduces to CBC authentication of A while in the second it reduces to CTR encryption of P. The byte length of A is denoted by a and, if a ", mathvariant = "normal", fence = "false", separator = "false", stretchy = "false", symmetric = "false", largeop = "false", movablelimits = "false", accent = "false", lspace = "0.27..." align="center" border="0"> 0, then a is encoded as follows (note that the third case is not really necessary for this implementation because of the size limit on plaintexts but we include it anyway):

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

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

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

A small encodings sample is the following:

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

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

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

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

We are now going to build the CCM formatting function. With the above parameter values in mind, we describe the leading byte of the first block B₀, 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 ", mathvariant = "normal", fence = "false", separator = "false", stretchy = "false", symmetric = "false", largeop = "false", movablelimits = "false", accent = "false", lspace = "0.27..." align="center" border="0"> 0 (A is nonempty). Then two 3-bit strings follow, the first encoding t as the binary representation of (t - 2)/2 (with the most significant bit on the left) and the second encoding q as the binary representation of q - 1. The rest of B₀ consists, in order, of the n bytes of the nonce and, finally, q bytes devoted to the encoding of Q (the byte length of the payload P). The next 16-byte blocks B₁, ..., B_u (where u may be 0) correspond (if a ", mathvariant = "normal", fence = "false", separator = "false", stretchy = "false", symmetric = "false", largeop = "false", movablelimits = "false", accent = "false", lspace = "0.27..." align="center" border="0"> 0) to the concatenation of the encoded value of a obtained from the aencoding function with the associated data A adding, if necessary, some 0 bytes at the end to complete an entire number of 16-byte blocks. The input arguments of the formatting function are the nonce, the associated data, the payload, and the tag length. The output is a one-dimensional Array whose entries are two-dimensional 0..3,0..3 Arrays containing the data blocks.

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

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

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

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

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

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

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

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

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

16402 bytes saved to testfile2.ccm

16381 bytes saved to testfile2

GCM/GMAC mode

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

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

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

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

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

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

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

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

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

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

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

A quick test of these functions is the following:

16409 bytes saved to testfile3.gcm

16381 bytes saved to testfile3

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

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

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

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

Validation tests

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

Displaying AES constants and tables

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

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

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

Matrix(%id = 173647776)

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:

80000000000000000000000000000000|6cd02513e8d4dc986b4afe087a60bd0c

c0000000000000000000000000000000|2ce1f8b7e30627c1c4519eada44bc436
e0000000000000000000000000000000|9946b5f87af446f5796c1fee63a2da24
f0000000000000000000000000000000|2a560364ce529efc21788779568d5555
f8000000000000000000000000000000|35c1471837af446153bce55d5ba72a0a
fc000000000000000000000000000000|ce60bc52386234f158f84341e534cd9e
fe000000000000000000000000000000|8c7c27ff32bcf8dc2dc57c90c2903961
ff000000000000000000000000000000|32bb6a7ec84499e166f936003d55a5bb
ff800000000000000000000000000000|a5c772e5c62631ef660ee1d5877f6d1b
ffc00000000000000000000000000000|030d7e5b64f380a7e4ea5387b5cd7f49
ffe00000000000000000000000000000|0dc9a2610037009b698f11bb7e86c83e
fff00000000000000000000000000000|0046612c766d1840c226364f1fa7ed72
fff80000000000000000000000000000|4880c7e08f27befe78590743c05e698b
fffc0000000000000000000000000000|2520ce829a26577f0f4822c4ecc87401
fffe0000000000000000000000000000|8765e8acc169758319cb46dc7bcf3dca
ffff0000000000000000000000000000|e98f4ba4f073df4baa116d011dc24a28
ffff8000000000000000000000000000|f378f68c5dbf59e211b3a659a7317d94
ffffc000000000000000000000000000|283d3b069d8eb9fb432d74b96ca762b4
ffffe000000000000000000000000000|a7e1842e8a87861c221a500883245c51
fffff000000000000000000000000000|77aa270471881be070fb52c7067ce732
fffff800000000000000000000000000|01b0f476d484f43f1aeb6efa9361a8ac
fffffc00000000000000000000000000|1c3a94f1c052c55c2d8359aff2163b4f
fffffe00000000000000000000000000|e8a067b604d5373d8b0f2e05a03b341b
ffffff00000000000000000000000000|a7876ec87f5a09bfea42c77da30fd50e
ffffff80000000000000000000000000|0cf3e9d3a42be5b854ca65b13f35f48d
ffffffc0000000000000000000000000|6c62f6bbcab7c3e821c9290f08892dda
ffffffe0000000000000000000000000|7f5e05bd2068738196fee79ace7e3aec
fffffff0000000000000000000000000|440e0d733255cda92fb46e842fe58054
fffffff8000000000000000000000000|aa5d5b1c4ea1b7a22e5583ac2e9ed8a7
fffffffc000000000000000000000000|77e537e89e8491e8662aae3bc809421d
fffffffe000000000000000000000000|997dd3e9f1598bfa73f75973f7e93b76
ffffffff000000000000000000000000|1b38d4f7452afefcb7fc721244e4b72e
ffffffff800000000000000000000000|0be2b18252e774dda30cdda02c6906e3
ffffffffc00000000000000000000000|d2695e59c20361d82652d7d58b6f11b2
ffffffffe00000000000000000000000|902d88d13eae52089abd6143cfe394e9
fffffffff00000000000000000000000|d49bceb3b823fedd602c305345734bd2
fffffffff80000000000000000000000|707b1dbb0ffa40ef7d95def421233fae
fffffffffc0000000000000000000000|7ca0c1d93356d9eb8aa952084d75f913
fffffffffe0000000000000000000000|f2cbf9cb186e270dd7bdb0c28febc57d
ffffffffff0000000000000000000000|c94337c37c4e790ab45780bd9c3674a0
ffffffffff8000000000000000000000|8e3558c135252fb9c9f367ed609467a1
ffffffffffc000000000000000000000|1b72eeaee4899b443914e5b3a57fba92
ffffffffffe000000000000000000000|011865f91bc56868d051e52c9efd59b7
fffffffffff000000000000000000000|e4771318ad7a63dd680f6e583b7747ea
fffffffffff800000000000000000000|61e3d194088dc8d97e9e6db37457eac5
fffffffffffc00000000000000000000|36ff1ec9ccfbc349e5d356d063693ad6
fffffffffffe00000000000000000000|3cc9e9a9be8cc3f6fb2ea24088e9bb19
ffffffffffff00000000000000000000|1ee5ab003dc8722e74905d9a8fe3d350
ffffffffffff80000000000000000000|245339319584b0a412412869d6c2eada
ffffffffffffc0000000000000000000|7bd496918115d14ed5380852716c8814
ffffffffffffe0000000000000000000|273ab2f2b4a366a57d582a339313c8b1
fffffffffffff0000000000000000000|113365a9ffbe3b0ca61e98507554168b
fffffffffffff8000000000000000000|afa99c997ac478a0dea4119c9e45f8b1
fffffffffffffc000000000000000000|9216309a7842430b83ffb98638011512
fffffffffffffe000000000000000000|62abc792288258492a7cb45145f4b759
ffffffffffffff000000000000000000|534923c169d504d7519c15d30e756c50
ffffffffffffff800000000000000000|fa75e05bcdc7e00c273fa33f6ee441d2
ffffffffffffffc00000000000000000|7d350fa6057080f1086a56b17ec240db
ffffffffffffffe00000000000000000|f34e4a6324ea4a5c39a661c8fe5ada8f
fffffffffffffff00000000000000000|0882a16f44088d42447a29ac090ec17e
fffffffffffffff80000000000000000|3a3c15bfc11a9537c130687004e136ee
fffffffffffffffc0000000000000000|22c0a7678dc6d8cf5c8a6d5a9960767c
fffffffffffffffe0000000000000000|b46b09809d68b9a456432a79bdc2e38c
ffffffffffffffff0000000000000000|93baaffb35fbe739c17c6ac22eecf18f
ffffffffffffffff8000000000000000|c8aa80a7850675bc007c46df06b49868
ffffffffffffffffc000000000000000|12c6f3877af421a918a84b775858021d
ffffffffffffffffe000000000000000|33f123282c5d633924f7d5ba3f3cab11
fffffffffffffffff000000000000000|a8f161002733e93ca4527d22c1a0c5bb
fffffffffffffffff800000000000000|b72f70ebf3e3fda23f508eec76b42c02

fffffffffffffffffc00000000000000|6a9d965e6274143f25afdcfc88ffd77c
fffffffffffffffffe00000000000000|a0c74fd0b9361764ce91c5200b095357
ffffffffffffffffff00000000000000|091d1fdc2bd2c346cd5046a8c6209146
ffffffffffffffffff80000000000000|e2a37580116cfb71856254496ab0aca8
ffffffffffffffffffc0000000000000|e0b3a00785917c7efc9adba322813571
ffffffffffffffffffe0000000000000|733d41f4727b5ef0df4af4cf3cffa0cb
fffffffffffffffffff0000000000000|a99ebb030260826f981ad3e64490aa4f
fffffffffffffffffff8000000000000|73f34c7d3eae5e80082c1647524308ee
fffffffffffffffffffc000000000000|40ebd5ad082345b7a2097ccd3464da02
fffffffffffffffffffe000000000000|7cc4ae9a424b2cec90c97153c2457ec5
ffffffffffffffffffff000000000000|54d632d03aba0bd0f91877ebdd4d09cb
ffffffffffffffffffff800000000000|d3427be7e4d27cd54f5fe37b03cf0897
ffffffffffffffffffffc00000000000|b2099795e88cc158fd75ea133d7e7fbe
ffffffffffffffffffffe00000000000|a6cae46fb6fadfe7a2c302a34242817b
fffffffffffffffffffff00000000000|026a7024d6a902e0b3ffccbaa910cc3f
fffffffffffffffffffff80000000000|156f07767a85a4312321f63968338a01
fffffffffffffffffffffc0000000000|15eec9ebf42b9ca76897d2cd6c5a12e2
fffffffffffffffffffffe0000000000|db0d3a6fdcc13f915e2b302ceeb70fd8
ffffffffffffffffffffff0000000000|71dbf37e87a2e34d15b20e8f10e48924
ffffffffffffffffffffff8000000000|c745c451e96ff3c045e4367c833e3b54
ffffffffffffffffffffffc000000000|340da09c2dd11c3b679d08ccd27dd595
ffffffffffffffffffffffe000000000|8279f7c0c2a03ee660c6d392db025d18
fffffffffffffffffffffff000000000|a4b2c7d8eba531ff47c5041a55fbd1ec
fffffffffffffffffffffff800000000|74569a2ca5a7bd5131ce8dc7cbfbf72f
fffffffffffffffffffffffc00000000|3713da0c0219b63454035613b5a403dd
fffffffffffffffffffffffe00000000|8827551ddcc9df23fa72a3de4e9f0b07
ffffffffffffffffffffffff00000000|2e3febfd625bfcd0a2c06eb460da1732
ffffffffffffffffffffffff80000000|ee82e6ba488156f76496311da6941deb
ffffffffffffffffffffffffc0000000|4770446f01d1f391256e85a1b30d89d3
ffffffffffffffffffffffffe0000000|af04b68f104f21ef2afb4767cf74143c
fffffffffffffffffffffffff0000000|cf3579a9ba38c8e43653173e14f3a4c6
fffffffffffffffffffffffff8000000|b3bba904f4953e09b54800af2f62e7d4
fffffffffffffffffffffffffc000000|fc4249656e14b29eb9c44829b4c59a46
fffffffffffffffffffffffffe000000|9b31568febe81cfc2e65af1c86d1a308
ffffffffffffffffffffffffff000000|9ca09c25f273a766db98a480ce8dfedc
ffffffffffffffffffffffffff800000|b909925786f34c3c92d971883c9fbedf
ffffffffffffffffffffffffffc00000|82647f1332fe570a9d4d92b2ee771d3b
ffffffffffffffffffffffffffe00000|3604a7e80832b3a99954bca6f5b9f501
fffffffffffffffffffffffffff00000|884607b128c5de3ab39a529a1ef51bef
fffffffffffffffffffffffffff80000|670cfa093d1dbdb2317041404102435e
fffffffffffffffffffffffffffc0000|7a867195f3ce8769cbd336502fbb5130
fffffffffffffffffffffffffffe0000|52efcf64c72b2f7ca5b3c836b1078c15
ffffffffffffffffffffffffffff0000|4019250f6eefb2ac5ccbcae044e75c7e
ffffffffffffffffffffffffffff8000|022c4f6f5a017d292785627667ddef24
ffffffffffffffffffffffffffffc000|e9c21078a2eb7e03250f71000fa9e3ed
ffffffffffffffffffffffffffffe000|a13eaeeb9cd391da4e2b09490b3e7fad
fffffffffffffffffffffffffffff000|c958a171dca1d4ed53e1af1d380803a9
fffffffffffffffffffffffffffff800|21442e07a110667f2583eaeeee44dc8c
fffffffffffffffffffffffffffffc00|59bbb353cf1dd867a6e33737af655e99
fffffffffffffffffffffffffffffe00|43cd3b25375d0ce41087ff9fe2829639
ffffffffffffffffffffffffffffff00|6b98b17e80d1118e3516bd768b285a84
ffffffffffffffffffffffffffffff80|ae47ed3676ca0c08deea02d95b81db58
ffffffffffffffffffffffffffffffc0|34ec40dc20413795ed53628ea748720b
ffffffffffffffffffffffffffffffe0|4dc68163f8e9835473253542c8a65d46
fffffffffffffffffffffffffffffff0|2aabb999f43693175af65c6c612c46fb
fffffffffffffffffffffffffffffff8|e01f94499dac3547515c5b1d756f0f58
fffffffffffffffffffffffffffffffc|9d12435a46480ce00ea349f71799df9a
fffffffffffffffffffffffffffffffe|cef41d16d266bdfe46938ad7884cc0cf
ffffffffffffffffffffffffffffffff|b13db4da1f718bc6904797c82bcf2d32

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

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

80000000000000000000000000000000|0edd33d3c621e546455bd8ba1418bec8

c0000000000000000000000000000000|4bc3f883450c113c64ca42e1112a9e87
e0000000000000000000000000000000|72a1da770f5d7ac4c9ef94d822affd97
f0000000000000000000000000000000|970014d634e2b7650777e8e84d03ccd8
f8000000000000000000000000000000|f17e79aed0db7e279e955b5f493875a7
fc000000000000000000000000000000|9ed5a75136a940d0963da379db4af26a
fe000000000000000000000000000000|c4295f83465c7755e8fa364bac6a7ea5
ff000000000000000000000000000000|b1d758256b28fd850ad4944208cf1155
ff800000000000000000000000000000|42ffb34c743de4d88ca38011c990890b
ffc00000000000000000000000000000|9958f0ecea8b2172c0c1995f9182c0f3
ffe00000000000000000000000000000|956d7798fac20f82a8823f984d06f7f5
fff00000000000000000000000000000|a01bf44f2d16be928ca44aaf7b9b106b
fff80000000000000000000000000000|b5f1a33e50d40d103764c76bd4c6b6f8
fffc0000000000000000000000000000|2637050c9fc0d4817e2d69de878aee8d
fffe0000000000000000000000000000|113ecbe4a453269a0dd26069467fb5b5
ffff0000000000000000000000000000|97d0754fe68f11b9e375d070a608c884
ffff8000000000000000000000000000|c6a0b3e998d05068a5399778405200b4
ffffc000000000000000000000000000|df556a33438db87bc41b1752c55e5e49
ffffe000000000000000000000000000|90fb128d3a1af6e548521bb962bf1f05
fffff000000000000000000000000000|26298e9c1db517c215fadfb7d2a8d691
fffff800000000000000000000000000|a6cb761d61f8292d0df393a279ad0380
fffffc00000000000000000000000000|12acd89b13cd5f8726e34d44fd486108
fffffe00000000000000000000000000|95b1703fc57ba09fe0c3580febdd7ed4
ffffff00000000000000000000000000|de11722d893e9f9121c381becc1da59a
ffffff80000000000000000000000000|6d114ccb27bf391012e8974c546d9bf2
ffffffc0000000000000000000000000|5ce37e17eb4646ecfac29b9cc38d9340
ffffffe0000000000000000000000000|18c1b6e2157122056d0243d8a165cddb
fffffff0000000000000000000000000|99693e6a59d1366c74d823562d7e1431
fffffff8000000000000000000000000|6c7c64dc84a8bba758ed17eb025a57e3
fffffffc000000000000000000000000|e17bc79f30eaab2fac2cbbe3458d687a
fffffffe000000000000000000000000|1114bc2028009b923f0b01915ce5e7c4
ffffffff000000000000000000000000|9c28524a16a1e1c1452971caa8d13476
ffffffff800000000000000000000000|ed62e16363638360fdd6ad62112794f0
ffffffffc00000000000000000000000|5a8688f0b2a2c16224c161658ffd4044
ffffffffe00000000000000000000000|23f710842b9bb9c32f26648c786807ca
fffffffff00000000000000000000000|44a98bf11e163f632c47ec6a49683a89
fffffffff80000000000000000000000|0f18aff94274696d9b61848bd50ac5e5
fffffffffc0000000000000000000000|82408571c3e2424540207f833b6dda69
fffffffffe0000000000000000000000|303ff996947f0c7d1f43c8f3027b9b75
ffffffffff0000000000000000000000|7df4daf4ad29a3615a9b6ece5c99518a
ffffffffff8000000000000000000000|c72954a48d0774db0b4971c526260415
ffffffffffc000000000000000000000|1df9b76112dc6531e07d2cfda04411f0
ffffffffffe000000000000000000000|8e4d8e699119e1fc87545a647fb1d34f
fffffffffff000000000000000000000|e6c4807ae11f36f091c57d9fb68548d1
fffffffffff800000000000000000000|8ebf73aad49c82007f77a5c1ccec6ab4
fffffffffffc00000000000000000000|4fb288cc2040049001d2c7585ad123fc
fffffffffffe00000000000000000000|04497110efb9dceb13e2b13fb4465564
ffffffffffff00000000000000000000|75550e6cb5a88e49634c9ab69eda0430
ffffffffffff80000000000000000000|b6768473ce9843ea66a81405dd50b345
ffffffffffffc0000000000000000000|cb2f430383f9084e03a653571e065de6
ffffffffffffe0000000000000000000|ff4e66c07bae3e79fb7d210847a3b0ba
fffffffffffff0000000000000000000|7b90785125505fad59b13c186dd66ce3
fffffffffffff8000000000000000000|8b527a6aebdaec9eaef8eda2cb7783e5
fffffffffffffc000000000000000000|43fdaf53ebbc9880c228617d6a9b548b
fffffffffffffe000000000000000000|53786104b9744b98f052c46f1c850d0b
ffffffffffffff000000000000000000|b5ab3013dd1e61df06cbaf34ca2aee78
ffffffffffffff800000000000000000|7470469be9723030fdcc73a8cd4fbb10
ffffffffffffffc00000000000000000|a35a63f5343ebe9ef8167bcb48ad122e
ffffffffffffffe00000000000000000|fd8687f0757a210e9fdf181204c30863
fffffffffffffff00000000000000000|7a181e84bd5457d26a88fbae96018fb0
fffffffffffffff80000000000000000|653317b9362b6f9b9e1a580e68d494b5
fffffffffffffffc0000000000000000|995c9dc0b689f03c45867b5faa5c18d1
fffffffffffffffe0000000000000000|77a4d96d56dda398b9aabecfc75729fd
ffffffffffffffff0000000000000000|84be19e053635f09f2665e7bae85b42d
ffffffffffffffff8000000000000000|32cd652842926aea4aa6137bb2be2b5e
ffffffffffffffffc000000000000000|493d4a4f38ebb337d10aa84e9171a554
ffffffffffffffffe000000000000000|d9bff7ff454b0ec5a4a2a69566e2cb84
fffffffffffffffff000000000000000|3535d565ace3f31eb249ba2cc6765d7a
fffffffffffffffff800000000000000|f60e91fc3269eecf3231c6e9945697c6
fffffffffffffffffc00000000000000|ab69cfadf51f8e604d9cc37182f6635a
fffffffffffffffffe00000000000000|7866373f24a0b6ed56e0d96fcdafb877
ffffffffffffffffff00000000000000|1ea448c2aac954f5d812e9d78494446a
ffffffffffffffffff80000000000000|acc5599dd8ac02239a0fef4a36dd1668
ffffffffffffffffffc0000000000000|d8764468bb103828cf7e1473ce895073
ffffffffffffffffffe0000000000000|1b0d02893683b9f180458e4aa6b73982

fffffffffffffffffff0000000000000|96d9b017d302df410a937dcdb8bb6e43
fffffffffffffffffff8000000000000|ef1623cc44313cff440b1594a7e21cc6
fffffffffffffffffffc000000000000|284ca2fa35807b8b0ae4d19e11d7dbd7
fffffffffffffffffffe000000000000|f2e976875755f9401d54f36e2a23a594
ffffffffffffffffffff000000000000|ec198a18e10e532403b7e20887c8dd80
ffffffffffffffffffff800000000000|545d50ebd919e4a6949d96ad47e46a80
ffffffffffffffffffffc00000000000|dbdfb527060e0a71009c7bb0c68f1d44
ffffffffffffffffffffe00000000000|9cfa1322ea33da2173a024f2ff0d896d
fffffffffffffffffffff00000000000|8785b1a75b0f3bd958dcd0e29318c521
fffffffffffffffffffff80000000000|38f67b9e98e4a97b6df030a9fcdd0104
fffffffffffffffffffffc0000000000|192afffb2c880e82b05926d0fc6c448b
fffffffffffffffffffffe0000000000|6a7980ce7b105cf530952d74daaf798c
ffffffffffffffffffffff0000000000|ea3695e1351b9d6858bd958cf513ef6c
ffffffffffffffffffffff8000000000|6da0490ba0ba0343b935681d2cce5ba1
ffffffffffffffffffffffc000000000|f0ea23af08534011c60009ab29ada2f1
ffffffffffffffffffffffe000000000|ff13806cf19cc38721554d7c0fcdcd4b
fffffffffffffffffffffff000000000|6838af1f4f69bae9d85dd188dcdf0688
fffffffffffffffffffffff800000000|36cf44c92d550bfb1ed28ef583ddf5d7
fffffffffffffffffffffffc00000000|d06e3195b5376f109d5c4ec6c5d62ced
fffffffffffffffffffffffe00000000|c440de014d3d610707279b13242a5c36
ffffffffffffffffffffffff00000000|f0c5c6ffa5e0bd3a94c88f6b6f7c16b9
ffffffffffffffffffffffff80000000|3e40c3901cd7effc22bffc35dee0b4d9
ffffffffffffffffffffffffc0000000|b63305c72bedfab97382c406d0c49bc6
ffffffffffffffffffffffffe0000000|36bbaab22a6bd4925a99a2b408d2dbae
fffffffffffffffffffffffff0000000|307c5b8fcd0533ab98bc51e27a6ce461
fffffffffffffffffffffffff8000000|829c04ff4c07513c0b3ef05c03e337b5
fffffffffffffffffffffffffc000000|f17af0e895dda5eb98efc68066e84c54
fffffffffffffffffffffffffe000000|277167f3812afff1ffacb4a934379fc3
ffffffffffffffffffffffffff000000|2cb1dc3a9c72972e425ae2ef3eb597cd
ffffffffffffffffffffffffff800000|36aeaa3a213e968d4b5b679d3a2c97fe
ffffffffffffffffffffffffffc00000|9241daca4fdd034a82372db50e1a0f3f
ffffffffffffffffffffffffffe00000|c14574d9cd00cf2b5a7f77e53cd57885
fffffffffffffffffffffffffff00000|793de39236570aba83ab9b737cb521c9
fffffffffffffffffffffffffff80000|16591c0f27d60e29b85a96c33861a7ef
fffffffffffffffffffffffffffc0000|44fb5c4d4f5cb79be5c174a3b1c97348
fffffffffffffffffffffffffffe0000|674d2b61633d162be59dde04222f4740
ffffffffffffffffffffffffffff0000|b4750ff263a65e1f9e924ccfd98f3e37
ffffffffffffffffffffffffffff8000|62d0662d6eaeddedebae7f7ea3a4f6b6
ffffffffffffffffffffffffffffc000|70c46bb30692be657f7eaa93ebad9897
ffffffffffffffffffffffffffffe000|323994cfb9da285a5d9642e1759b224a
fffffffffffffffffffffffffffff000|1dbf57877b7b17385c85d0b54851e371
fffffffffffffffffffffffffffff800|dfa5c097cdc1532ac071d57b1d28d1bd
fffffffffffffffffffffffffffffc00|3a0c53fa37311fc10bd2a9981f513174
fffffffffffffffffffffffffffffe00|ba4f970c0a25c41814bdae2e506be3b4
ffffffffffffffffffffffffffffff00|2dce3acb727cd13ccd76d425ea56e4f6
ffffffffffffffffffffffffffffff80|5160474d504b9b3eefb68d35f245f4b3
ffffffffffffffffffffffffffffffc0|41a8a947766635dec37553d9a6c0cbb7
ffffffffffffffffffffffffffffffe0|25d6cfe6881f2bf497dd14cd4ddf445b
fffffffffffffffffffffffffffffff0|41c78c135ed9e98c096640647265da1e
fffffffffffffffffffffffffffffff8|5a4d404d8917e353e92a21072c3b2305
fffffffffffffffffffffffffffffffc|02bc96846b3fdc71643f384cd3cc3eaf
fffffffffffffffffffffffffffffffe|9ba4a9143f4e5d4048521c4f8877d88e
ffffffffffffffffffffffffffffffff|a1f6258c877d5fcd8964484538bfc92c

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

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

Ciphertext blocks:
7649abac8119b246cee98e9b12e9197d
5086cb9b507219ee95db113a917678b2
73bed6b8e3c1743b7116e69e22229516
3ff1caa1681fac09120eca307586e1a7

Ciphertext blocks:

874d6191b620e3261bef6864990db6ce
9806f66b7970fdff8617187bb9fffdff
5ae4df3edbd5d35e5b4f09020db03eab
1e031dda2fbe03d1792170a0f3009cee

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

Ciphertext blocks:

601ec313775789a5b7a7f504bbf3d228
f443e3ca4d62b59aca84e990cacaf5c5
2b0930daa23de94ce87017ba2d84988d
dfc9c58db67aada613c2dd08457941a6

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:

Plaintext blocks:

6bc1bee22e409f96e93d7e117393172a
ae2d8a571e03ac9c9eb76fac45af8e51
30c81c46a35ce411e5fbc1191a0a52ef
f69f2445df4f9b17ad2b417be66c3710

AES (Pseudo-)Random Tests

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

100 tests ...

200 tests ...

256 tests successfully passed

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:

Test Nr.: 1, Mode: OFB, Key: 1eaae16c4dd7f5517c5749620d86d49e5f8f1a7d83146df2

Test Nr.: 2, Mode: ECB, Key: 2d2d2eea80e38f54a54b1db29e13d3afb3b6bf55ef4ac31e

Test Nr.: 3, Mode: OFB, Key: bc62b372f2f1e21b5ada060c857e8f58

3 encryption/decryption tests successfully passed

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

CMAC Test

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

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

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

K: 603deb10 15ca71be 2b73aef0 857d7781
1f352c07 3b6108d7 2d9810a3 0914dff4

K1        cad1ed03 299eedac 2e9a9980 8621502f
K2        95a3da06 533ddb58 5d353301 0c42a0d9
M         6bc1bee2 2e409f96 e93d7e11 7393172a
         ae2d8a57 1e03ac9c 9eb76fac 45af8e51
         30c81c46 a35ce411 e5fbc119 1a0a52ef
         f69f2445 df4f9b17 ad2b417b e66c3710
T         e1992190 549f6ed5 696a2c05 6c315410

CCM Test

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

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

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

K:        40414243 44454647 48494a4b 4c4d4e4f
N:        10111213 141516
A:        00010203 04050607
P:        20212223

B:        4f101112 13141516 00000000 00000004
         00080001 02030405 06070000 00000000
         20212223 00000000 00000000 00000000

T:        6084341b

Ctr0:     07101112 13141516 00000000 00000000
S0:       2d281146 10676c26 32bad748 559a679a

Ctr1:     07101112 13141516 00000000 00000001
S1:       51432378 e474b339 71318484 103cddfb

C:        7162015b 4dac255d

K:        40414243 44454647 48494a4b 4c4d4e4f
N:        10111213 14151617 18191a1b
A:        00010203 04050607 08090a0b 0c0d0e0f
         10111213
P:        20212223 24252627 28292a2b 2c2d2e2f
         30313233 34353637

B:        5a101112 13141516 1718191a 1b000018
         00140001 02030405 06070809 0a0b0c0d
         0e0f1011 12130000 00000000 00000000
         20212223 24252627 28292a2b 2c2d2e2f
         30313233 34353637 00000000 00000000

T:        67c99240 c7d51048

Ctr0:     02101112 13141516 1718191a 1b000000
S0:       2f8a00bb 06658919 c3a040a6 eaed1a7f

Ctr1:     02101112 13141516 1718191a 1b000001
S1:       c393238a d1923c5d b335c0c7 e1bac924

Ctr2:     02101112 13141516 1718191a 1b000002
S2:       514798ea 9077bc92 6c22ebef 2ac732dc

C:        e3b201a9 f5b71a7a 9b1ceaec cd97e70b
         6176aad9 a4428aa5 484392fb c1b09951

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

K:        40414243 44454647 48494a4b 4c4d4e4f
N:        10111213 14151617 18191a1b 1c
A:        00010203 04050607 08090a0b 0c0d0e0f
         10111213 14151617 18191a1b 1c1d1e1f
         20212223 24252627 28292a2b 2c2d2e2f
         30313233 34353637 38393a3b 3c3d3e3f
         40414243 44454647 48494a4b 4c4d4e4f
         50515253 54555657 58595a5b 5c5d5e5f
         60616263 64656667 68696a6b 6c6d6e6f
         70717273 74757677 78797a7b 7c7d7e7f
         80818283 84858687 88898a8b 8c8d8e8f
         90919293 94959697 98999a9b 9c9d9e9f
         a0a1a2a3 a4a5a6a7 a8a9aaab acadaeaf
         b0b1b2b3 b4b5b6b7 b8b9babb bcbdbebf
         c0c1c2c3 c4c5c6c7 c8c9cacb cccdcecf
         d0d1d2d3 d4d5d6d7 d8d9dadb dcdddedf
         e0e1e2e3 e4e5e6e7 e8e9eaeb ecedeeef
         f0f1f2f3 f4f5f6f7 f8f9fafb fcfdfeff
         ...
P:        20212223 24252627 28292a2b 2c2d2e2f
         30313233 34353637 38393a3b 3c3d3e3f

B:        71101112 13141516 1718191a 1b1c0020
         fffe0001 00000001 02030405 06070809
         0a0b0c0d 0e0f1011 12131415 16171819
         1a1b1c1d 1e1f2021 22232425 26272829
         2a2b2c2d 2e2f3031 32333435 36373839
         ...
         dadbdcdd dedfe0e1 e2e3e4e5 e6e7e8e9
         eaebeced eeeff0f1 f2f3f4f5 f6f7f8f9
         fafbfcfd feff0000 00000000 00000000
         20212223 24252627 28292a2b 2c2d2e2f
         30313233 34353637 38393a3b 3c3d3e3f

T:        f4dd5d0e e4046172 25ffe34f ce91

Ctr0:     01101112 13141516 1718191a 1b1c0000
S0:       407136e2 77ec38fc 5af24ef3 24ca1178

Ctr1:     01101112 13141516 1718191a 1b1c0001
S1:       49b07f8e 3aa1e010 4241e8bd 5260854e

Ctr2:     01101112 13141516 1718191a 1b1c0002
S2:       6ad1cf2c 9af17af3 bcbbbf12 7a01f14d

C:        69915dad 1e84c637 6a68c296 7e4dab61
         5ae0fd1f aec44cc4 84828529 463ccf72
         b4ac6bec 93e8598e 7f0dadbc ea5b

GCM Test

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

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

           Variable|Value
                 K:|00000000000000000000000000000000
                 P:|
                 A:|
                IV:|000000000000000000000000

                 H:|66e94bd4ef8a2c3b884cfa59ca342b2e
      GHASH(H,A,C):|00000000000000000000000000000000
                 C:|
                 T:|58e2fccefa7e3061367f1d57a4e7455a

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

Diffusion tests

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

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

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

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

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

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

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

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

Plot_2d

Data summary:

Testing whether sample follows the Binomial(128,0.5) distribution:

Chi-Square Test for Suitable Probability Model
----------------------------------------------
Null Hypothesis:
Sample was drawn from specified probability distribution
Alt. Hypothesis:
Sample was not drawn from specified probability distribution

Bins:                    43
Distribution:            ChiSquare(42)
Computed statistic:      57.2675
Computed pvalue:         0.0583102
Critical value:          58.12403751

Result: [Accepted]
There is no statistical evidence against the null hypothesis

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.

Plot_2d

Data summary:

Testing whether sample follows the Binomial(16,255./256) distribution:
Chi-Square Test for Suitable Probability Model
----------------------------------------------
Null Hypothesis:
Sample was drawn from specified probability distribution
Alt. Hypothesis:
Sample was not drawn from specified probability distribution

Bins:                    3
Distribution:            ChiSquare(2)
Computed statistic:      0.107699
Computed pvalue:         0.947575
Critical value:          5.991464547

Result: [Accepted]
There is no statistical evidence against the null hypothesis

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

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

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

Plot_2d

Data summary:

Testing whether sample follows the Binomial(1000,0.5) distribution:
Chi-Square Test for Suitable Probability Model
----------------------------------------------
Null Hypothesis:
Sample was drawn from specified probability distribution
Alt. Hypothesis:
Sample was not drawn from specified probability distribution

Bins:                    101
Distribution:            ChiSquare(100)
Computed statistic:      100.809
Computed pvalue:         0.458523
Critical value:          124.3421137

Result: [Accepted]
There is no statistical evidence against the null hypothesis

Next we do the diffusion test at the byte level:

Plot_2d

Data summary:

Testing whether sample follows the Binomial(1000, 255./256) distribution:
Chi-Square Test for Suitable Probability Model
----------------------------------------------
Null Hypothesis:
Sample was drawn from specified probability distribution
Alt. Hypothesis:
Sample was not drawn from specified probability distribution

Bins:                    12
Distribution:            ChiSquare(11)
Computed statistic:      6.41321
Computed pvalue:         0.844422
Critical value:          19.67513758

Result: [Accepted]
There is no statistical evidence against the null hypothesis

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

Conclusions

We have used Maple's capabilities in several domains including pseudo-random number generation, file and text handling, statistical analysis and, more generally, as a programming environment, to implement and explore the encryption and authentication schemes that use AES as underlying block cipher and are based on the eight modes of operation for block ciphers so far approved by NIST. The implementation uses, whenever possible, lookup tables for efficiency and is able to encrypt/decrypt/authenticate files of moderate size. We have also included tests to analyze either compliance with the standards or some basic properties such as diffusion, which is studied by collecting, displaying (in both text and graphic format) and analyzing statistical data.

References

[SP800-90] E. Barker, J. Kelsey, Recommendation for Random Number Generation using Deterministic Random Bit Generators (Revised), NIST Special Publication 800-90 (2007), available via http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf
[AESAVS] L.E. Bassham III, The Advanced Encryption Standard Algorithm Validation Suite, NIST publication (2002) available via http://csrc.nist.gov/groups/STM/cavp/documents/aes/AESAVS.pdf
[Bellare-Rogaway] M. Bellare, P. Rogaway, Introduction to Modern Cryptography, available via http://www-cse.ucsd.edu/~mihir/cse207/classnotes.html
[Buchmann] J.A. Buchmann, Introduction to Cryptography, Second Edition, Springer-Verlag (2004).
[Daemen-Rijmen1] J. Daemen, V. Rijmen, AES Proposal: Rijndael, available via http://csrc.nist.gov/archive/aes/rijndael/Rijndael-ammended.pdf
[Daemen-Rijmen2] J. Daemen, V. Rijmen, The design of Rijndael, Springer-Verlag, Berlin (2002).
[SP800-38A] M. Dworkin, Recommendation for Block Cipher Modes of Operation: Methods and Techniques, NIST Special Publication 800-38A (2001), available via http://csrc.nist.gov/publications/nistpubs/800-38a/sp800-38a.pdf
[SP800-38B] M. Dworkin, Recommendation for Block Cipher Modes of Operation: The CMAC mode for authentication, NIST Special Publication 800-38B (2005), available via http://csrc.nist.gov/publications/nistpubs/800-38B/SP_800-38B.pdf
[SP800-38C] M. Dworkin, Recommendation for Block Cipher Modes of Operation: The CCM mode for Authentication and Confidentiality, NIST Special Publication 800-38C (2004), available via http://csrc.nist.gov/publications/nistpubs/800-38C/SP800-38C_updated-July20_2007.pdf
[SP800-38D] M. Dworkin, Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC, NIST Special Publication 800-38D (2007), available via http://csrc.nist.gov/publications/nistpubs/800-38D/SP-800-38D.pdf
[FIPS197] Federal Information Processing Standards Publication 197, Specification for the Advanced Encryption Standard (AES) (2001), available via http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
[Geisler-Kroigard-Danielsen] M. Geisler, M. Kroigard, A. Danielsen, About random bits, available via http://www.daimi.au.dk/~mg/mamian/random-bits.pdf
[Hellekalek-Wegenkittl] P. Hellekalek, S. Wegenkittl, Empirical evidence concerning AES, ACM Transactions on Modeling and Computer Simulation (TOMACS), 13 (2003), 322-333, available via http://random.mat.sbg.ac.at/ftp/pub/publications/peter/aes_sub.ps

[Katz-Lindell] J. Katz, Y. Lindell, Introduction to Modern Cryptography, Chapman & Hall/CRC (2008).

[Lenstra] H.W. Lenstra, Jr., Rijndael for algebraists, available via http://math.berkeley.edu/~hwl/papers/rijndael0.pdf
[Lidl-Niederreiter] R. Lidl, H. Niederreiter, Introduction to Finite Fields and their Applications, Cambridge University Press (1994).
[Matsumoto-Nishimura] M. Matsumoto, T. Nishimura, Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Transactions on Modeling and Computer Simulation (TOMACS), 8 (1998), 3-30, available via http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf
[McGrew-Viega] D.A. McGrew, J.Viega, The Galois/Counter Mode of Operation (GCM), Submission to NIST Modes of Operation Process, available via http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-revised-spec.pdf
[Monagan-Fee] M. Monagan, G. Fee, A Cryptographically Secure Random Bit Generator for Maple, available via http://www.cecm.sfu.ca/CAG/papers/monfeeMSWS04.pdf
[Oppliger] R. Oppliger, Contemporary Cryptography, Artech House (2005).
[Stinson] D.R. Stinson, Cryptography Theory and Practice, 3rd Edition, Chapman & Hall/CRC (2005).
[Trappe-Washington] W. Trappe, L.C. Washington, Introduction to Cryptography with Coding Theory, Prentice Hall (2002).
[Viega] J. Viega, Practical Random Number Generation in Software, Proc 19th Annual Computer Security Applications Conference (2003), 129-140, available via http://www.acsac.org/2003/papers/79.pdf

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