Basic Understanding of Block Ciphers or Types of Encryption

For the rest of us non-math majors :D

by JustinT

AES Overview: A Brief Security Analysis

I've decided to elaborate on the underlying AES algorithm, Rijndael, and provide my insight on its security margin, in terms of its role in the future of cryptography. Please excuse any verbosity, as I'll likely cover a few familiar aspects as aforementioned, for the sake of this review's clarity.

*Note: When I discuss Rijndael, I will be referring to the 128-bit version, as standardized specification has it, in FIPS-197.

Along with this review of AES, I'll put Rijndael in perspective, in a brief comparison with other 128-bit and 64-bit algorithms.

AES in a Nutshell

First of all, let's review the AES routine, in brief. Along with this overview, I will provide an array of resources, pointing to the official documentation, as well as graphical representations and schematics to assist in further

research of the algorithm.

AES, a 128-bit block cipher, is based on a different structure than DES, which is a Feistel network. This cipher exhibits a structure which deems it an iterated block cipher, which simply refers to the fact that initial input and key material is transformed multiple times, before output is rendered.

It was incredibly over-designed, with differential and linear cryptanlaysis

in mind. The algorithm, along with its elegant design, parallel-friendly functioning, cryptanalytic resilience, and desirable speed, makes for a suitable encryption standard, for now.

Single Round of Rijndael:

Encryption Routine:

Rounds in succession are similar. The plaintext of 16 bytes is fed through an XOR function, against a round key, of 128 bits. The bits of key material are fed into the side of the XOR routines. The 16 bytes are then utilized as a mapping index, for identical S-boxes, which maps inputs of 8 bits to outputs of 8 bits. The arrangement of bytes is then altered in a particular order.

To cap it off, via a linear function, these bytes are mixed, grouped in four. This completes a single round of Rijndael, in a nutshell. 10 rounds are deployed, in total, as they correlate to the 16-byte (128-bit) key length in use.

Decryption is rather different, in that it requires the S-box's inverse lookup table, as well as the inverse mixing operation, which differs from that of the initial mixing operation.

The structure of Rijndael, although different from DES, has many similar functioning aspects, such as:

- Key material added via XOR

- Non-linearity via S-boxes

- Diffusion via mixing and byte shuffle functions

For complete documentation and specification on the standard 128-bit Rijndael algorithm, along with graphical representations, refer to the following resources:

(under construction)

Official FIPS-197 Documentation (PDF)

Extensive Overview of Rijndael (accompanied by 2D/3D graphical representations)

Animated Executable on Rijndael (Zipped Executable)

Security Concerns and Attack Methodology:

Now to satisfy the aspiration of this overview...

First, I'm going to define the word trust, as the integral meaning of this word is vital in understanding my views.

trust - one in which confidence is instilled; reliance; an entity entrusted to one to be used or cared for in the interest of another; a duty or

charge imposed in faith or confidence.

Alright, now, as the definition is stated, I'll be smug, yet educated, enough to say - I don't quite trust the security of AES. Don't be alarmed, though. A cryptographer's view of trust is a much different perspective, than one might normally assume. There aren't many ciphers we trust, however, we don't necessarily shun the use of an algorithm, just because we can't instill a basis of trust in it. This is a rigorous process that involves analysis, over time. In the mean time, we can provide our opinionated outlook as to whether the new algorithm is cryptographically sound, in terms of how it has held up to current attack methodology, and how well we think it compares to existing, trusted designs. As for now, we'll place our cryptographic faith in AES and accept it as the standard, as we'll suggest its use, as a well-rounded, elegant, and secure block cipher, but it is far from trusted.

Let's begin the analysis overview, shall we?

Rijndael's Idiosyncrasy:

To understand why I don't fully trust the security of AES, you need to have a decent grasp on the idiosyncrasy of the underlying Rijndael algorithm. This lies in its simple, clean, algebraic structure. Cryptographers are rather inexperienced when it comes to this avenue of structure within algorithms. Thus, a new angle of attack methodology is opened. No other algorithm in comparison is based on a structure of this nature, so analysis becomes quite arduous.

Although this isn't an inherent proof that an attack exists, it is, however, justification enough to be skeptical, as algorithm design hasn't been approached from this angle, so we have no clue as to whether or not an attack exists.

To give you an idea as to how volatile this is, consider the following. AES can be defined as a closed algebraic formula, over a 256-element finite field. This is relatively simple. If these formulas can be solved, then AES is compromised.

Courtois and Pieprzyk, in a recently proposed paper, show that to recover a 128-bit Rijndael key from a single plaintext, you can write the problem as a system of 8000 quadratic equations, accompanied by 1600 binary unknowns. This ideology is that of displaying Rijndael as an over-defined multivariate quadratic equation system. Again, the security of Rijndael lies within the fact that no algorithm for solving these equations

exists, at the moment.

Adi Shamir, the "S" in RSA, published a paper pertaining to a proposed attack, called XL, and/or FXL that seemingly solves this system of equations in sub-exponential time. With this in mind, the security of ciphers, as Rijndael, would not see exponential growth as the number of rounds is increased. This, in itself, would be a cryptographic epiphany, as classical block cipher attack methodology, ranging from linear and differential to techniques by Jakobsen and Knudsen operate exponentially, based on the number of rounds.

Practically, the XL algorithm fails. Rijndael's system has no entropy, as the system has an over-defined structure. With this in mind, Courtois and Pieprzyk conjectured a new, improved class of attacks, as an extension to XL, in such a way as to adapt it to the special properties of Rijndael. This attack methodology, known as XSL, is extremely difficult to determine,

complexity-wise. Theoretically, these attacks can be extended to 256-bit AES, but that's not a definite. These equations can be written as GF(256), rather than GF(2), as the sparse nature of GF(256) is like that of Rijndael's structure. Robshaw and Murphy, having proposed this idea, led to an XSL attack, over GF(256), that would break AES in 2^87. However, no one even knows the complexity of these attacks, or if they will even work, in practice, so the future of AES attack methodology is questionable, in terms of deploying XSL attacks.

Among all this algebraic rumble, many questions have been raised, but answers have not surfaced, to avail. Seems quite risky to place trust in an algorithm whose structure's security is uncertain, even in the eyes of the most seasoned cryptographers, doesn't it? The problem is, even though we can't prove that an attack exists, we can't disprove it. However, to criticize AES in this fashion isn't fair, as any algorithm may very easily be attacked in the future. This is just an analytical observation that may prove critical in the future of its life-span as our current cryptographic standard.

So, to conclude this overview, we need to answer a few questions. I feel a mini-FAQ coming on, perhaps? Alright, let's tackle some widely asked questions and media hype, shall we?:

Q:I heard AES was compromised. Is it true that it is broken?

A:No, AES isn't practically compromised. Attack methodology exists, but no proofs of practicality exist. Therefore, we are still a pipe-dream away from demolishing the current security margin of Rijndael, with any of the proposed algebraic attacks.

Q:Should we still use AES?

A:Of course, it's going to become the industry standard soon, so for compatibility's sake, by all means, do. Besides, it's not an insecure cipher. It has remained resilient to the most common array of block cipher analysis. It is just a new cipher, so time and analysis is vital to its reputation.

Q:I thought Rijndael was the best algorithm?

A:Well, in a sense, that is true. Rijndael was the best, in terms of satisfying the AES selection criteria, as it did so better than the other candidates. It has a decent balance of efficiency, security, and speed, which the AES selection crew was looking for. Hence, it was chosen for the AES because it met the best overall balance of the required criteria. However, this is based largely on implementation efficiency and speed, not highest security margin.

(You want a higher margin of security? Go with Twofish or Serpent. Had Serpent been as fast as Rijndael, it would have been the AES. Twofish is a nice balance between the two.)

Q:Should I be worried about these proposed attacks on AES?

A:You should be cautious, but not worried. These attacks are nothing more than theoretical at the moment. Theoretical attacks exist against most, if not all, algorithms. You should only worry when attacks become practical. However, the aforementioned methodology isn't even thought to be practical, at this time, or possibly even at all, for that matter.

So, there you have it. A simple overview of current AES attack methodology.

Now, as I said, I will place Rijndael amongst other commonly deployed algorithms. First, I'll briefly describe the cipher. Second, I'll compare the ciphers, based on criteria you'll learn of, further into reading. By doing so, you'll see how I feel AES, as well as other ciphers, fares in its class.

Other Block Ciphers:An Opinionated Juxtaposition

Twofish:

Alright, I'll start with Twofish. Twofish, as you may already know, is a 128-bit Feistel Network. It's nearly the same speed as Rijndael, but holds a much higher security margin. The current best attack on Twofish compromises 8 of the 16 rounds, but that still doesn't deter the algorithm from retaining its level of security, which is quite sufficient. Of all the AES finalist candidates, I view this algorithm as the best, alongside Serpent.

Serpent:

Next, although you didn't mention this algorithm, I'll bring up Serpent. This algorithm, in my opinion, is a much more conservative, and better, choice, as opposed to Rijndael, even though the two are similar in structure. Ringing in with 32 rounds, it's the most robust algorithm I've reviewed, in juxtaposition with the other AES candidates. The best of attacks, thus far as I know, only cover 10 of the 32 full rounds. The only drawback is its lack of speed. This is where Rijndael steps in, with its speed and algebraic simplicity. Again, along with Twofish, I recommend this algorithm over Rijndael.

These 3 algorithms I've just mentioned can be classed together, since they are all 128-bit block ciphers. Now, we'll move on to the 64-bit class.

Blowfish:

Blowfish, another fine spawn of Schneier's cryptographic genius, is a 64-bit Feistel Network, of which has seen more widespread use than most new block ciphers. It's lightweight, fast, simple, and secure. Enough said, really, as in my opinion, Blowfish is the best 64-bit block cipher, to date.

IDEA:

IDEA, another 64-bit block cipher, was heavily analyzed and considered to be one of the most secure block ciphers during its tenure. Although it is still relatively secure, it is illogical to recommend its use, as there are much better ciphers available, which are also much faster, and not to mention, hold a higher security margin. Besides, it is patented, so that, in itself, is a cryptographic con.

DES:

Otherwise known as DEA, this time-evolved algorithm has withstood cryptanalysis and deemed itself as the most widely used algorithm available. Because of its 56-bit key length, as adopted by the standard, it is not wise to use this algorithm in terms of the practicality of being susceptible to a key exhaust, or brute force. However, in terms of the security of the algorithm's structure, it is stout and sufficient, overall. As a standard, it's a good choice. As an everday choice, I wouldn't go with it. Go with Blowfish, instead, if speed and security is of the essence.

Now, on to the final algorithm in question, which exhibits the trait of multiple encryption.

Triple-DES:

Last, but not least, we move on to Triple-DES. The cream of the crop. The mack daddy of legacy algorithms. The algorithm that put crypt in ography. As this algorithm is a concatenation of DES, in a triple succession, it doesn't behave as an ideal block cipher, therefore, its use is highly cautioned. Current attack methodology, based on MITM, theoretically reduces the complexity of Triple-DES from anywhere around 2^108 - 2^112. However, you are still working with a key length of 108 to 112 bits, so all is sufficient, in the security department. The reason Triple-DES has become such a legacy, and highly recommended cipher, stems from the fact that no other algorithm has undergone such rigorous analysis and surfaced over 30 years later, retaining a sufficient security margin in today's modern cryptographic world.

I've said it numerous times, and I'll say it again, Triple-DES provides a user with a level of confidence and trust that no other algorithm is capable of doing.

A Side Note On DES/3DES:

Although you still see DES in applications today, it has outlived its overall usefulness. This isn't breaking news, as the implication of an AES answers the call for an algorithm of sufficiency.

However, DES still finds practical use, in the form of 3DES, be it for legacy purposes, or based on the fact that DES is the best analyzed algorithm, to date. Why not use 3DES? After all, you have a sufficient key size, backed by decades of analytical scrutiny...

Well, the answer isn't quite clear on the surface. In all actual senses, 3DES is still considered a "good" cipher, in terms of analyzed security, and will continued to be used because of this.

Deep down, however, there are elements of 3DES that cryptographers find diminishing to its theoretical value. Although, in theory, it has held up, it inherits two properties of DES that keep it from meeting the standards of good, modern ciphers. Not only does it suffer from having a 64-bit block size, it shares the weak keys and complementation property that DES

exhibits.

I have said, and will continue to say, 3DES has proven itself as the most confidence-worthy cipher, in theory and practice. Cryptographers won't shun its use, but will also not recommend its inclusion in newer protocols.

128-bit ciphers are the big guys now. They make efficient sense. DES or any of its variants may have retained there legacy as a secure cipher family, but they haven't retained their efficiency nor have they met the criteria for modern cryptographic algorithms. There are more efficient algorithms now, that satisfy the suggested cryptographic criteria. Efficiency comes into play where cryptography is needed most. When the demand arises, the efficiency, or lack thereof, is more noticeable. This is why programmers are constantly optimizing DES/3DES for modern processing.

However, cryptographers are pre-optimizing ciphers for modern processing, so programmers and developers don't have to. This is where DES falls short.

So, the reasoning is as follows. DES has the longest track record, therefore, 3DES has proven to be secure. AES has only started in this race to proven security. This does not mean that DES is the most secure. What it does mean, however, is that we can prove the security of DES, because

we have thrown it through the cryptanalysis cycle time and time again. We can't, however, prove the security lifespan of AES, nor any other modern cipher, such as Twofish, Blowfish, etcetera. We can only rely on the fact that they have withstood attacks thus far. We, as cryptographers, base our trust and use of a cipher on its analysis, and the time frame of which this analysis takes place. With this reasoning, it is only logical to continue using 3DES, regardless of how inefficient it may be, when compared to modern ciphers.

We can't, however, use it forever. That is why we develop new algorithms and propose new standards for more efficient and secure cryptography. This is why AES exists. The goal is to prove AES worthy, while slowly making a transition from the use of DES/3DES. So, 3DES, is our "backup", so to speak, at the moment.

It's like that old truck sitting in the garage. May not be the most fuel efficient or good looking piece of machinery around, but it gets you where you need to go, with no problems, unlike that new car you just bought, supposedly the "best in its class", but is already showing signs of transmission problems. Familiar analogy? It's all about using the best we have until we can justify using something better.

So, why not continue to use 3DES? Well, we still do and will, for years to come, until eventually, the transition from 3DES to a new standard will become more noticeable. An interim standard, if you will.

Recommendations:

So, to give you my educated opinion on how you should utilize the ciphers in question, refer to the following:

Ranging from 1, least favored, to 3, decent choice, to 5, highly recommended.

The criteria for my choices is based on an overall exhibit of speed, efficiency, security, and simplicity.

128-bit block ciphers:

Twofish: *****

Serpent: ****

Rijndael: ***

64-bit block ciphers:

IDEA: *

Blowfish: *****

*DES: ***

* aside from the insecure 56-bit key length, DES has with retained its security margin, in regards to a slew of cryptanalytic attacks, over 3 decades.

Triple-DES doesn't behave like an ideal block cipher, as it is an example of multiple encryption, so I won't place it in the same class as the above ciphers. However, I will rank it as follows, in a breakdown of elements:

Triple-DES:

Speed: *

Efficiency: **

Simplicity: ****

Security: *****

Overall: ***

Although it only received a 3, it is a stout 3, as it will continue to remain a juggernaut for time to come. The most prominent cipher, by far, in terms of analysis and respect.

Conclusion:

So, you see, Rijndael may be the AES, but it's far from being the saviour of modern cryptography. It is, however, the most efficient, for its security. It holds up well and I recommend it, for most applications. However, it's not my favorite. In this conclusion, I highly recommend Twofish or Serpent, over any other recent block cipher designs.

Overall, keep sporting your AES. It's a decent algorithm. As a cryptographic rule-of-thumb, don't take hype at face value, but always consider the spontaneous eruption of mathematical breakthrough possibilities.

Rijndael had what it took to be dubbed the AES.

AES has one goal now - prevail.