If you missed the first part in this article series please read The Layman’s Unconventional Guide to the Advanced Encryption Standard (Part 1).
An Instant AESnack: Sub, Shift, Mix, and Add
Oh, hello! It’s that time again – part deux of our crypto-saga. Okay, so maybe we’re a bullwhip and fedora short of a saga, but you get the idea. Previously, you became acquainted with mathematical terminology that, despite its almost Nash-esque voodoo connotations, was presented in a Joe McEasyBakeOven manner. Now that we’ve eased into the generalities, such as the round transformation and key schedule, let’s put them under the wordoscope and see what else we can dissect. When I wrap this article up, I’ll conclude by providing references for those of you who might be contesting, saying, “I’m a mathematics major – give me more theory!”
A little more mortar between a few more foundational bricks
Well, I have my sweet iced tea – the nectar of this southern cryptographer – and by the light of the cathode ray, with trowel in hand, I’m ready. I imagine that some of you are wondering about the obscure references to masonry (i.e., mortar, bricks, and trowel). Wonder no more; here comes the first new term: bricklayer permutation. There’s some contextual, prerequisite seasoning I need to sprinkle on first. More primitively, we need to define a bricklayer function. We can decompose this function into a number of Boolean functions that operate, independently, on subsets of the input vector’s bits; a partition of the input vector’s bits is formed by these subsets. To be more specific, they are partitioned into bundles (i.e., 8-bit bytes and 32-bit columns in Rijndael). In essence, what you have consists of multiple Boolean functions that operate on smaller inputs, applied in parallel.
When we consider a bricklayer function that operates on a state, we call this a bricklayer transformation; the state refers to the intermediate information that Rijndael’s steps operate on during the encryption and decryption routines. It might help to look at it in the following way. When you feed plaintext to the encryption algorithm, the state is the intermediate result until ciphertext is spit out, or extracted, from the state; when you feed the decryption algorithm ciphertext, the state is the intermediate result until the plaintext is spit out, or extracted, from the state. Let’s get back to laying bricks. The bricklayer transform defines a bundle partition, as it operates, independently, on a number of that state’s subsets; it follows that the bricklayer transformation’s component transformations operate, independently, on a number of bundles.
If I were the gambling type, I’d open my wallet to the bet that at least a few of you are hearing these terms for the first time. Perhaps the following will ring a bell: if these Boolean functions are non-linear, they are referred to, most affectionately, as S-boxes. You might ask, “What if the Boolean functions are linear?” “Well,” I would reply, “if they’re linear, they’re referred to as D-boxes.” Oh, and to ameliorate the confusion that is possibly hovering over you, due to this alphabet soup naming convention, the S stands for substitution, and the D stands for diffusion. It’s vital that both the S-boxes and D-boxes are permutations, in order for a bricklayer transformation to be invertible; it is this invertible bricklayer permutation that we call a bricklayer permutation.
The aforementioned bell that should be ringing is S-box, since you’ll find these in the majority of block ciphers, such as DES, Blowfish, Twofish, and Serpent. Just as with key schedules, there are numerous design philosophies for constructing S-boxes, with cryptanalytical resistance in mind. If you thought Baskin Robbins had a lot to choose from, I invite you to check out a few of the many flavorful routes of S-box design. If you’re up for an intense, theoretical KO, study some of Kaisa Nyberg’s research; it packs a mental Sugar Ray Leonard-esque punch, though, so be prepared. One more thing – as we get started, keep in mind that we’re dealing with Rijndael as it is instantiated in the AES specification, which fixes the block length at 128 bits.
Taking our first step with Rijndael – literally
Now that we’ve completed our tenure as figurative brick masons, let’s inspect the gears that make Rijndael turn. I’ll spare you any ado and jump right into the first step of Rijndael, dubbed, SubBytes. In fact, this step is the only non-linear transformation you’ll find in Rijndael; it’s a bricklayer permutation, and if you prepend “non-linear” to that, you might be inclined to ask if there’s an S-box involved. You’d be right to ask, since that’s essentially what SubBytes is composed of – an S-box. This S-box operates on the state’s individual bytes, or 8-bit bundles, and the design criteria behind it is emphatic about resisting linear cryptanalysis and differential cryptanalysis, as well as interpolation attacks. Nyberg’s work was quite influential, in this case.
A cryptographic maelstrom – the metaphorical tides are cyclically shifting
Next in line, we have ShiftRows. This step is a transposition of bytes, that shifts the state’s rows, cyclically, according to specified offsets (i.e., 0, 1, 2, and 3, for a 128-bit block length). These offsets were chosen based on criteria including simplicity, resistance to truncated differential attacks and saturation attacks, and diffusion optimality (i.e., all the offsets are different) with regards to resisting linear cryptanalysis and differential cryptanalysis. Although this section was quick like Road Runner, it’s an important step in the round transformation, to say the least.
Where’s Betty Crocker? The columns need mixing
ShiftRows has already dealt with rows, and it’s MixColumns function to operate on columns. As such, we can define MixColumns as a bricklayer permutation that operates on the state’s columns, or 32-bit bundles. You’ve seen the term “bricklayer” before, a little while ago, when we defined SubBytes. While SubBytes and MixColumns are both bricklayer permutations, the former is non-linear, while the latter is linear. If you’ve been following along, you might be wondering, “Well, if ‘non-linear’ corresponded to an S-box, then perhaps this linear transformation is where a D-box comes in.” Once again, you’d be on the right track. To juxtapose the two a little more, while SubBytes’ non-linear S-boxes operate on the state’s bytes independently, MixColumns’ linear D-boxes operate on the state’s columns, independently.
The linearity criterion, along with that of diffusion, are products of the wide trail strategy, which are the “blueprints,” if you will, from which Rijndael was erected. Galois might not have been a gaucho, but to pay him due respect, it’s time to saddle up and saunter into the polynomial pampas. Let’s look at the state’s columns as polynomials over GF(28), where the “GF” simply stands for “Galois field.” These columns are multiplied, modulo x4 + 1, with the fixed polynomial, 03 * x3 + 01 * x2 + 01 * x + 02, which, being coprime to x4 + 1, is invertible. The coefficients were meticulously chosen, such that the branch number of MixColumns was five, which is maximal, given the dimensions of the transformation. You can say that ShiftRows is the Robin to MixColumns’ Batman, without tights; together, with their diffusion powers, they thwart the linear and differential cryptanalytical foes of math and mayhem.
Anyone seen my round keys? I thought I left them on the counter
Conceptually, this should be a fairly simple explanation to follow. The last step that we’ll look at is referred to as AddRoundKey. The round key and block length are equal. The state is combined, via XOR, with a round key. The expanded key, to which the “master” cipher key is mapped to, is the collective array of round keys, which are selected from the expanded key. This happens during key scheduling.
Each round needs a round key. For AES with 10 rounds, which implies a fixed 128-bit block length and a 128-bit key length, 1,408 bits of round key material is necessary; these 1,408 bits make up the aforementioned expanded key. No need to break out your TI-83+ to figure this one out. Add one to the number of rounds (10 + 1 = 11), then multiply that with the block length (11 * 128 = 1,408); that’s how many bits will be in the expanded key. So, the expanded key is essentially the concatenation of the round keys, sequentially.
Key schedules are labyrinthine machines in and of themselves. There’s no universal discipline for how they must be designed, but regardless, they fill some pretty important shoes. In the case of Rijndael, this is reflected in various ways. To prevent attacks and weaknesses (i.e., weak keys) that exploit symmetry in the round transformation and in between rounds, asymmetry is introduced in the recursive key expansion function.
Before you frenetically react with, “Woah, woah, woah – asymmetry? I thought Rijndael was a symmetric block cipher?” It is. Simmer down. No worries. “Symmetry,” in this context, refers to the observation that Rijndael’s round transformation handles all of the states’ bytes in, largely, the same way; the round transformation is also the same, round after round, excluding the final round. Round-dependent round constants, within the key schedule, eliminate the symmetries imposed by those observations; that is, they eliminate symmetry, or introduce asymmetry. Slide attacks, for example, prey on such symmetry.
SubByte’s key-independent S-box ensures non-linearity, which repels the existence of weak keys, such as those found in IDEA, and along with diffusion, aims to defend against related-key attacks. Also, the key schedule has a defense against scenarios where the key may be partially known, completely known, or even chosen, such as when a block cipher is used as the compression function of a hash function. It’s a chimera of components, really, and one that harnesses simplicity and good key agility.
Tree-less branches, wide trails, and Markov theory, for $500 please
In my sempiternal odyssey of laymanizing the more intimate personalities of cryptography, I’ll exclude the byzantine ancestry that resides at the innermost core of Rijndael’s foundation; to be fair, though, I’ll open the door a little – you can take it from there. The branch number, from a couple of sections ago, corresponds to the diffusion property, which is defined a bit differently within the context of the wide trail strategy, as opposed to Shannon’s definition, with which more of you should be familiar with; the branch number corresponds to linear trail correlation and differential trail probability, in regards to the supplying of bounds for them.
The key-alternating structure you were introduced to in the last episode is aimed at providing resistance to linear and differential cryptanalysis; it is the wide trail strategy that revolves around the design philosophy of the round transformations in block cipher that exhibit this structure. To be efficient and resistant to cryptanalysis is the general premise. A Markov cipher, such as Rijndael, is iterative, and contains a round transformation that satisfies a criterion related to average difference propagation probability, which has a specifically strong hand in differential cryptanalysis. It’s worth noting, on two respectively separate accounts, that Markov cipher theory extends to linear cryptanalysis as well, and the wide trail strategy isn’t limited to key-alternating block ciphers.
While I’ve presented some of the design principles for Rijndael, you’ll find that there is analysis for reduced-round variants of Rijndael. So, for you mathematicrusaders out there with an appetite for more, I recommend the works of Lai, Massey, and Murphy, for Markov cipher theory, as well as Rijmen and Daemen’s outlook on it, along with their research in the wide trail design strategy. The works of Biham, Kelsey, and Ferguson, are fundamental starting points for familiarizing yourself with related-key attacks, in general, and how they apply to cryptanalyzing Rijndael, such as the cryptanalysis by Ferguson, Kelsey, Lucks, Schneier, Stay, Wagner, and Whiting.
Check out Jakobsen and Knudsen’s work on interpolation attacks, Biryukov and Wagner’s work on slide attacks, and Lucks’ work on saturation attacks, of which you will see similar research regarding Knudsen’s “Square” attack, Biryukov and Shamir’s “structural” attack, and Ferguson’s advancements. These are some names to keep in mind, when foraging through the wealth of useful analysis that applies the design philosophy of Rijndael, and the Rijndael-oriented analysis that was born during the AES competition.
Cryptographic standards make good, cryptographic sense
Before I throw in the towel on this triple-scoop series on the Advanced Encryption Standard, I’d like to share my opinion on some concerns of those who live a few houses down from cryptography, but aren’t quite home with it. What do Starbucks and unfounded, speculative, paranoia-ridden statements about cryptography have in common? They’re everywhere. The politics – I’ll spare you. As simply as I can utter these words: use the AES. That is, unless it is unsuitable for your design criteria, I suggest using it, when possible. The security layman delegates the substance of their trust to those with an expertise in security; the same holds true for the interdisciplinary field of cryptography. All too often, I hear, “It’s a federal standard, so it must be weak. The government would never promote anything that’s actually too strong for them to break.” I give them a second to adjust their tinfoil beret after its de-positioning from their animated ranting.
Afterwards, I explain some simple logic that I’ll share with you. When referring to us, the public, academic community, and the NSA, the private, no-such-agency, we can say there are two types of cryptographer: Ours and theirs. Obviously, since we are public, we all have access to our own cryptanalysis. However, since they are private, we do not have access to their cryptanalysis. Not only do they have access to their own private cryptanalysis, they have access to our public cryptanalysis. These are just some obvious observations; it’s nothing we need to outsource to Sherlock. Of course, it wouldn’t make sense for us to say that it’s impossible for them to be far ahead; just as well, it wouldn’t make sense for us to say that it’s impossible for us both to be neck and neck. This isn’t something that can be resolved, given what little we know for a fact, and speculation has no provable payoff. Regardless of how you look at it, this fact holds.
Cryptanalysis is a virtue
As such, I trust the cryptographers who participated in the design and dissection process for the competition from which the AES was crowned. Personally, NIST made a choice that I agree with. Overall, the AES is a cryptographic success story. And so it goes that once Rijndael was selected, it became a target for cryptanalysis. When it fell into synonymity with the word, “standard,” it also became even more of an attention-vacuum. More cryptanalytical eyes have turned towards Rijndael than any of the other AES finalists. Why? Because it’s a target. Why is it a target? Because it’s the standard from which many new protocols will be built and many old protocols will transition to. For a block cipher, or any other primitive, for that matter, to “earn its bones,” so to speak, it must hold up under cryptanalysis. Why? Because cryptanalysis is a virtue. Wait; it’s the virtue.
Although I think practical paranoia is a good thing, I’m not one for purchasing stock in speculation – especially when there’s no foundation under it, rationality behind it, or substance within it. Don’t get me wrong; there’s no denying that cryptographers rely on assumptions for security that’s without absolute proof. Keep in the mind, though, that there’s a difference between these educated assumptions, based on academic research, and the conspiracy theories, based on incompetence. The former is the best we’ve got, and I’m okay with that, because I know that if the All Seeing Eye(TM) would like to see plaintext, there’s almost always an easier, non-cryptographic way of getting at it. This is a byproduct of the fact that cryptography is rarely ever the weakest pea in the security pod.
In closing, I’ll take the last sentence of the previous paragraph and extend it. If any of you folks out there can say that good, properly implemented, cryptography (i.e., AES in CTR mode and CMAC-AES) is the weakest component of your infrastructure, e-mail me your mailing address, so I can ship you a Lay-Z-Boy recliner, in which you can relax, knowing that you’ve got one of the most robust systems ever. Albeit one heck of a design metric to follow – that is, building systems such that the cryptography is the weakest link – it’s usually quite the contrary. After weighing these factors, it seems logical enough to make the best cryptographic judgment we can, given the capabilities that our state-of-the-art research has bestowed upon us. Rijndael makes good cryptographic sense, and believe the pros outweigh any potential cons that some may toss its way; it’s design philosophy is conservative, in my regards, as well as the rationale for using a standard that is receiving, and withstanding, cryptanalysis.
Don’t get me wrong though – I’m an advocate of many of the design principles of Twofish and Serpent, which are, in various ways, much more conservatively engineered. All things considered, the AES selection process is the epitome of how standardization should take place, and it promotes the rigorous cryptanalysis that Rijndael has been taking advantage of, and rightfully so. The NIST and academia amalgamated for what has been the design metric of choice for cryptographic design processes to come. To recap: Cryptanalysis is a virtue – the “earning your bones” of a primitive, if you will. Rijndael is the most interesting target for cryptanalysis – a magnet for scrutiny, that sees more scrutiny than any other candidate from the AES selection process. If you can use Rijndael – do it. Now if you fine folks will excuse me, dinner is calling, so I’ll catch up with y’all soon. Tchau!
If you missed the first part in this article series please read The Layman’s Unconventional Guide to the Advanced Encryption Standard (Part 1).
