If you would like to read the next part in this article series please go to The Layman’s Unconventional Guide to the Advanced Encryption Standard (Part 2).
Since its inception, the acronym “AES” has found its way into most everyone’s tech-tionary; it reeks of strength, with the adjective, “Advanced,” standing firmly in front of the words “Encryption,” which incites some sense of mathematical intensity that would give any Einstein a run for his mental money, and “Standard,” which suggests that it’s strong enough to have gained a governmental approval as the “Dom P” of this era’s block ciphers, so to speak. Given its academic and societal popularity, a score of pieces have been written; among these are general articles often written by non-cryptographers, who cover superficial aspects, such as who designed it, the type of primitive it is, the key and block lengths it supports, and so on and so forth. I’m not one for the usual, so here’s my attempt at bridging the gap between the academic terminology that rarely escapes from between the binding of scientific journals, and the cursory glance that the general media provides.
Permutations – they’re what’s for dinner
The Advanced Encryption Standard is merely a specification of an underlying primitive – Rijndael. Most folks “in the [basic] know” are aware of this; in fact, the only differentiating factor between the AES specification and Rijndael lies in the fact that the AES supports a smaller range of Rijndael’s possible lengths for blocks and keys. Most folks deduce Rijndael to the household term, “block cipher,” but that’s usually the extent of it. In all actuality, there’s much more to the generalization that a “block cipher” is; it’s probably best that I lay out some terminology, before we dive into the pool of AESpecifics. To be fair to the non-mathematicians out there, I will spare you from the fundamental equations, but I’ll need to introduce some primitive mathematical definitions for the sake of the mathematically-inclined audience. There’s certainly no dearth of good theory, when it comes to the works of Rijmen and Daemen; it’s phenomenally eminent stuff. Keep in mind that in between the puddle of terms you’re about to be introduced to, there exist nooks and crannies of mathematical theory, far beyond the scope of this article; think of this as an encyclopedic glimpse into what you probably didn’t know about Rijndael.
First, sear into your memory the term “Boolean permutation”; it is the blood cell of a block cipher, you might say. Essentially, there’s something called a vector Boolean function, which maps one Boolean vector to another, where the coordinates for these vectors are bits. Now, I won’t expect everyone to get the gist behind what this actually means, but what follows should be familiar, conceptually, so hang in there with me. Remember that block ciphers deal with n-bit blocks, basically; that is, if you plug in “128” in the place of n, for instance, you’re referring to a 128-bit block cipher, which means you feed it 128 bits of plaintext and it spits out 128 bits of ciphertext. (“Feed” and “spit,” instead of “input” and “output,” give some personality to it, which is always useful in the field of cryptography, where you need some imagination.) One manner in which you may look at a vector Boolean function is as a table specification, which gives the output value for all 2n values of the input Boolean vector. Also, you can refer to a vector Boolean function as dealing with n-bit states, if the number of input and output bits are equal; this type of function is referred to as a vector Boolean transformation.
Furthermore, if this vector Boolean transformation maps all states of input bits to different output bits, it’s invertible, which – referring to that term that should be seared into your memory already – is what you’d call a vector Boolean permutation. We’re right below the epidermis, now. To balance out these new terms, I’ll throw in some familiarities. What you probably know is that, in layman’s terms, a block cipher transforms plaintext input blocks into ciphertext outputs blocks, of some equal length, in bits, denoted by nb. This transformation process is influenced by a key, denoted by k. Now, let’s tie the aforementioned terminology into the general perception of a block cipher. The block cipher is actually a set of these Boolean permutations that deal with nb-bit vectors; there is such a permutation for each value of k. Look at the key, k, as a Boolean vector, whose length, in bits, is denoted by nk. Therefore, such a block cipher will exhibit 2nk Boolean permutations. This transformation process is more affectionately known as an “encryption algorithm,” in most articles you’ll stumble across, which is usually sufficient for discussing cryptography at a very basic, conceptual level.
Keys have schedules, just like us – well, some of us
I promise we’ll hit home soon, and you won’t feel that just when you thought you were understanding a little pea-sized speck of cryptography, Hurricane Boolean came along and rained on your parade. Now that we’ve established a more in-depth look at the block cipher generalization, let’s hone in on the specifics of Rijndael. Rijndael is a key-iterated block cipher; it’s a few things, but this is the “sub-class” it fits into. It’s an iterative block cipher because it iterates a variable number of key-dependent Boolean permutations; such a permutation is referred to as a round transformation, and each iteration of this transformation is referred to as a round. It’s an iterated block cipher because, with the exception of a slight difference in the last round, where a step is omitted, it iterates the same round transformation. I can just picture the looks on the faces of the Applied Cryptography owners out there, who see the word, “round,” and have already engaged in a promulgation fest of hey-I-knew-thats.
A little while ago, I loosely referred to a key as something that “influences” the plaintext-to-ciphertext transformation. Key material is computed from the key, k, for each round; this is known, cumulatively, as the expanded key. The algorithm that provides the instructions for how these round keys are computed from the key, k, is known as the key schedule. Alright, I have a confession. I said I’d spare you of equation madness, but here’s a quick equation that, I promise, is simple; it’s just for the purpose of showing how the key expansion works. Ready? Me too. The number of bits in the expanded key is determined by: block length times (rounds plus 1). In other words, we know that for AES (implied block length of 128 bits) with a 128-bit key, we have 10 rounds, so the equation would be: 128 times (10 plus 1). 128 times 11 equals 1408. Therefore, the expanded key, in that case, would be composed of 1,408 bits. And, of course, round keys are selected from this expanded key, and are of the same length as the block length. See, that wasn’t so bad. I even omitted symbols for you!
Generating a key and scheduling it – the difference
Not so many moons ago, I wrote a crudely primitive series on “n bits of security” versus “n bits of key length,” which discusses the general methodologies for generating cryptographic keys. Let’s juxtapose this with a key schedule. Imagine that we have two distinct block ciphers. They both require a source of randomness for the key used in this transformation, or encryption, process. We can use the same cryptographically-secure PRNG, or pseudo-random number generator, to generate keys for both block ciphers. In other words, generating the key, k, is usually independent of the block cipher in which it will be used; the key schedule contains the key expansion component which determines how the expanded key will be derived from the key, k. The point is, Rijndael is specific about how the expanded key is derived; it isn’t, however, specific about how the key, k, is derived.
Here’s a quick analogy. Let’s say I’m handing out crisp Franklins. (Not that I’m in the position to nonchalantly do so, but work with me here.) Everyone that I hand a $100 bill to obviously gets it from the same source (me). In other words, while they get it from the same source (PRNG), how they spend it is up to their own preference (key schedule). The former isn’t specified by the block cipher, but the latter is. Oh, and please – no e-mails for cash. Hehe. Key schedules, just like round transformations, can come in more flavors than even Jelly Belly could market; they are intrinsic to the block cipher, and while these aforementioned distinct block ciphers may use key material generated from the same source, their key schedules may use this material in entirely different ways, respectively.
Some conclusive remark(ov)s
So, moving along, we’ve established that Rijndael is an iterated block cipher in the class of iterative block ciphers, but I tossed up the term “key-iterated,” a number of paragraphs above. Don’t worry – I’m almost there. Rijndael is also classed into a group of block ciphers known as key-alternating block ciphers, which, roughly, applies round keys to the state via XOR, in between unkeyed rounds; this is ultimately a sub-class of a Markov cipher. When we stir in the characteristic of iterated block ciphers with this key-alternating structure, we render none other than the key-iterated block cipher sub-class that Rijndael falls under. (Serpent, Twofish, and Rijndael, are all Markov ciphers, but only Serpent and Rijndael are key-alternating; Serpent and Rijndael are also based on a substitution-permutation network (SPN), while Twofish is based on a Feistel network. I thought I’d throw this in for comparison value between AEA finalists.)
I had planned to elaborate on the round transformation of Rijndael, but I’m going to call an audible and save that for a future installment. At least we were able to look at the basic underlying components of a block cipher, terminology-wise, as well as the core of Rijndael – the round transformation – which we’ll break down in the next episode, into its four steps: SubBytes, ShiftRows, MixColumns, and AddRoundKey. I’ll explain a little (and I mean little) about Markov cipher theory, Rijndael’s wide trail strategy, and conclude with my opinionated stance on why advocating the use of a standard, such as the AES, is a Good Thing(TM). That’s all for this edition of the “Unconventional Layman’s Guide.” Until next time, cheers!
If you would like to read the next part in this article series please go to The Layman’s Unconventional Guide to the Advanced Encryption Standard (Part 2).
