• RSS
  • Twitter
  • FaceBook

Security Forums

Log in

FAQ | Search | Usergroups | Profile | Register | RSS | Posting Guidelines | Recent Posts

AES: Security in a Nutshell

Users browsing this topic:0 Security Fans, 0 Stealth Security Fans
Registered Security Fans: None
Post new topic   Reply to topic   Printer-friendly version    Networking/Security Forums Index -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security

View previous topic :: View next topic  
Author Message
JustinT
Trusted SF Member
Trusted SF Member


Joined: 17 Apr 2003
Posts: 16777215
Location: Asheville, NC, US / Uberlāndia, MG, Brazil

Offline

PostPosted: Sat Jul 12, 2003 10:26 pm    Post subject: AES: Security in a Nutshell Reply with quote

AES Overview: A Brief Algebraic Security Analysis

I've decided to elaborate, briefly, on the underlying AES algorithm, Rijndael, and provide my insight on its security margin, from an entirely algebraic perspective. This covers recent theory that may render AES volatile, and susceptible to extensive algebraic attack methodology. It gives you something to think about, when considering that this algorithm is now evolving to such a wide-scale usage. This simply addresses the current explosion of rumors.

AES in a Nutshell

AES, a 128-bit block cipher, structured around what we call a Substitution-Permutation Network. It was incredibly over-designed, with differential and linear cryptanlaysis in mind. The algorithm, along with its elegant design, parallel-friendly functioning, implementation efficiency, and desirable speed, makes for a suitably decent encryption standard - for now.

Single Round of Rijndael:

Encryption Routine, in layman's terms:

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

Theoretical Concerns and Q&A:

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 feel a bit uneasy with 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 on certain occasions, as a well-rounded, elegant, and relatively decent, block cipher, but it is far from trusted.

Let's begin the analysis overview, shall we?

Rijndael's Idiosyncrasy:

Algebraic Attacks

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 exactly 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 extensively approached from this angle, so we have no definite 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, in this sense, within the fact that no practical algorithm for solving these equations exists, at the moment.

XL/FXL

Adi Shamir, the "S" in RSA, et al. published a paper pertaining to a proposed attack, called XL, and 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.

XSL

Practically, the XL algorithm fails. Rijndael's rendered system has no random nature, but is 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 that Rijndael does have. 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, at approximately best, 2^87. However, no one even knows, for sure, 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.

What are we left with?

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. Our faith will be tested - that is the only definite answer from all of this.

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. It has always been
a volatile game.

So, there you have it. A simple overview of current AES algebraic attack methodology. 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.

If you happen to be a math-head or spec-collector, feel free to ask me for a more technical approach to the concepts I've mentioned in this article, as I'd be glad to elaborate on this, and provide you with a myriad of other resources. In the mean time, I hope this nutshell-of-a-review will be beneficial to some of you.


Last edited by JustinT on Sat Mar 18, 2006 4:07 am; edited 2 times in total
Back to top
View user's profile Send private message Visit poster's website
Dark-Avenger
Just Arrived
Just Arrived


Joined: 21 Apr 2003
Posts: 0
Location: France

Offline

PostPosted: Fri Jul 18, 2003 8:07 pm    Post subject: Reply with quote

OK, but what about the 23 equations which are satisfied every iterations
between entries and output ?
Back to top
View user's profile Send private message
stillbourne
Just Arrived
Just Arrived


Joined: 16 Jul 2003
Posts: 0


Offline

PostPosted: Sat Jul 19, 2003 2:49 am    Post subject: Reply with quote

Wiretapped has info on all the AES canidates that were tested including Rijndael, Twofish, Serpent, RC6, and Crytpon to name a few.
Back to top
View user's profile Send private message Visit poster's website
JustinT
Trusted SF Member
Trusted SF Member


Joined: 17 Apr 2003
Posts: 16777215
Location: Asheville, NC, US / Uberlāndia, MG, Brazil

Offline

PostPosted: Sat Jul 19, 2003 3:24 am    Post subject: Please elaborate... Reply with quote

Dark-Avenger wrote:
OK, but what about the 23 equations which are satisfied every iterations
between entries and output ?


Please elaborate as to what you mean, as I'm not quite understanding your question.

Thanks in advance,

Justin


Last edited by JustinT on Sun Aug 29, 2004 11:50 am; edited 1 time in total
Back to top
View user's profile Send private message Visit poster's website
Dark-Avenger
Just Arrived
Just Arrived


Joined: 21 Apr 2003
Posts: 0
Location: France

Offline

PostPosted: Sun Jul 20, 2003 12:50 pm    Post subject: Reply with quote

One of the 23 equations which are ALWAYS true after each iterations of AES, between entries xi and outputs zi:

0 = x3+x5+x6+x1+x2z2+x5z7+x7z4+x7z1+x7z3+x0z1+x6z5+x6z3+
x7z7+x4z6+x4z1+x4z5+x4z0+x4z2+x1z5+x1z3+x5z5+x5z3+x5z0+
x3z1+x3z+x6z6+x3z4+x2z3+x2z6+x4z7+x0z5+x0z3+x1z+x1z7+
x6z1+x3z0+x4z3+x0z7+x1z6+x2z5

Why these equations are not a weakness ?

nb: thanks for IWASAWA, i started reading.
----
Back to top
View user's profile Send private message
JustinT
Trusted SF Member
Trusted SF Member


Joined: 17 Apr 2003
Posts: 16777215
Location: Asheville, NC, US / Uberlāndia, MG, Brazil

Offline

PostPosted: Mon Jul 28, 2003 6:45 am    Post subject: MQ... Reply with quote

Dark-Avenger wrote:
One of the 23 equations which are ALWAYS true after each iterations of AES, between entries xi and outputs zi:

0 = x3+x5+x6+x1+x2z2+x5z7+x7z4+x7z1+x7z3+x0z1+x6z5+x6z3+
x7z7+x4z6+x4z1+x4z5+x4z0+x4z2+x1z5+x1z3+x5z5+x5z3+x5z0+
x3z1+x3z+x6z6+x3z4+x2z3+x2z6+x4z7+x0z5+x0z3+x1z+x1z7+
x6z1+x3z0+x4z3+x0z7+x1z6+x2z5

Why these equations are not a weakness ?

nb: thanks for IWASAWA, i started reading.
----


I have a feeling you are referring to Rijndael's S-boxes. If so,
it's like this. There's x. If this value != 0, always, then
there are 24 quadratic equations, which are linear and
independent. The 24th equation is of a particular significance,
in terms of truth probability, as is 255/256. The interest extends
if all of the S-boxes are true, in probability (where x!=0).
The probability of this, as aforementioned, is around:

(255/256)^4*Nb*Nr+4*(1+1N k>6)*Nr

Which translates to around:

128-bit - 1/2
256-bit - 1/9

If an attack of sorts is to work much better with the entire
set of 24 equations, then all are usually used, with the attack
iterated between 2 to 9 times. If the iterations range from 1-2,
we consider r equal to 24, otherwise, we set r = 23.

Now, with ciphers such as with S-boxes that can be defined as
a set of algebraic equations, one can analyze the cipher in terms
of it being a problem, in which they must be able to solve the
system of equations in question. As Serpent and Rijndael both
exhibit multivariate quadratic equations, they are applied to an
attack known as "MQ", for Multivariate Quadratic.

This methodology is harbored under the XL/XSL attack semantics,
of which I mention in the parent post of this thread. So, as these
equations don't necessarily pose an inherent weakness, we, as
cryptographers, aren't able to prove this, thus leaving a gap in
between practical security and theoretical security. This gap, for
what it is worth, is also merely theoretical at the moment, so the
primary goal now is to analyze these equations, in search of
answers as to whether or not they pose a threat to the overall
security of the algorithm. The attacks aren't practical, yet, but
we are still in limbo between what we can prove and what we
cannot, in regards to the true theoretical security of Rijndael.

So, it's not so much that these equations are not prone to
weakness, but rather, the fact that we are unsure if that is
the case.

Glad to hear you are enjoying the Iwasawa papers. :]

Cheers.
Back to top
View user's profile Send private message Visit poster's website
Dark-Avenger
Just Arrived
Just Arrived


Joined: 21 Apr 2003
Posts: 0
Location: France

Offline

PostPosted: Sun Aug 29, 2004 9:42 am    Post subject: Reply with quote

Have you read Eric Filiol's paper about block cyphers weakness ?
What do you think of it ?

http://www-rocq.inria.fr/codes/Eric.Filiol/PDRC.html
Back to top
View user's profile Send private message
ghost16825
Just Arrived
Just Arrived


Joined: 24 Nov 2003
Posts: 2


Offline

PostPosted: Sun Aug 29, 2004 2:44 pm    Post subject: Reply with quote

Thanks Justin yet again for an insightful and interesting overview of AES.

Re: the part about 8000 quadratic equations, accompanied by 1600 binary unknowns:

To get a general comparison in terms of present computing power does anyone have any figures on the present upper limit of "unknown" variables and/or number of equations that can be calculated by today's supercomputers?
A good starting point would be from information on any computers used for making weather estimates.

(Any kind of arbitary estimate would be welcome)
Back to top
View user's profile Send private message
data
Forum Fanatic
Forum Fanatic


Joined: 08 May 2004
Posts: 16777211
Location: India

Offline

PostPosted: Fri Apr 08, 2005 7:16 pm    Post subject: Reply with quote

hi,

I am new to Rijndael and I was going through this as suggested by Justin. I have the following doubts

1. On page 7 of the above mentioned document, its says: "Clearly C(x) can no loner be represented by a 4 byte vector". 4 byte is 32 bit and all we need is 7 bits to store the co-efficients of a degree 7 polynomial. Why do they suggest 4 bytes?

2. On page 7, they write out equations for finding d0,d1,d2,d3 which are the co-effieients of the multiplied polynomials modulo another polynomial in the same field. They have not mentioned particularly how th values of d0,d1,d2 and d3 are determined, as equations of XORed values. I remeber an earlier post here where we do this trick to speed up multiplication. I am sure that the math works but does any one know the theory behind it or how the math works?

Thanks.
Back to top
View user's profile Send private message Visit poster's website Yahoo Messenger
comrade
Just Arrived
Just Arrived


Joined: 15 Feb 2005
Posts: 0


Offline

PostPosted: Fri Apr 08, 2005 10:35 pm    Post subject: Reply with quote

ax^7 + bx^6 + cx^5 + dx^4 + ex^3 + fx^2 + gx^1 + hx^0

looks like 8 bytes here for a 7th degree, and four bytes for the cubic.

not that i have ANY clue as to how the above relates to the context Mad
Back to top
View user's profile Send private message
data
Forum Fanatic
Forum Fanatic


Joined: 08 May 2004
Posts: 16777211
Location: India

Offline

PostPosted: Sat Apr 09, 2005 4:50 am    Post subject: Reply with quote

hi there,

Since the math is done in F(2^m), it means that the co-efficients are binary and can take values 0 or 1.

Quote:
ax^7 + bx^6 + cx^5 + dx^4 + ex^3 + fx^2 + gx^1 + hx^0



The values of a,b,c,d,e,f,g,h are 0 or 1.

For e.g.
X^7+x^2+1 is represented by the bit string
10000101

That is a=1,f=1,h=1 and the rest of the co-efficients are 0. The degree of the polynomial is found as their respective place values. In all this should only take 7 bits to store the above polynomial.

Data.
Back to top
View user's profile Send private message Visit poster's website Yahoo Messenger
JustinT
Trusted SF Member
Trusted SF Member


Joined: 17 Apr 2003
Posts: 16777215
Location: Asheville, NC, US / Uberlāndia, MG, Brazil

Offline

PostPosted: Sat Apr 09, 2005 12:49 pm    Post subject: Brief comments. Reply with quote

datah wrote:

I am new to Rijndael and I was going through this as suggested by Justin. I have the following doubts

1. On page 7 of the above mentioned document, its says: "Clearly C(x) can no loner be represented by a 4 byte vector". 4 byte is 32 bit and all we need is 7 bits to store the co-efficients of a degree 7 polynomial. Why do they suggest 4 bytes?

2. On page 7, they write out equations for finding d0,d1,d2,d3 which are the co-effieients of the multiplied polynomials modulo another polynomial in the same field. They have not mentioned particularly how th values of d0,d1,d2 and d3 are determined, as equations of XORed values. I remeber an earlier post here where we do this trick to speed up multiplication. I am sure that the math works but does any one know the theory behind it or how the math works?


In the MixColumns step in Rijndael, you basically have a bricklayer permutation that is performed over columns of the state; these columns are realized as polynomials, over GF(2^8), and are multiplied modulo x^4+1, using a fixed polynomial, c(x), which is invertible, since it is coprime to x^4+1. On a side note, I could prepare some LaTeX renditions of the equations that I can't reproduce here, if that would aid in the comprehension of what's going on.

Performance-wise, roughly speaking, no processing is required, if multiplied with "00" and "01"; multiplication with "02" is efficiently performed with a specific, dedicated routine, and "03" is computed as multiplication with "02", with an additional XOR. Defining columns as 4 bytes was due in part to adding efficiency on 32-bit architectures, in implementations that combine the steps of the round transformation within a single set of look-up tables. In regards to diffusion, the coefficients were meticulously chosen to give the transformation an optimal branch number (5), based on its dimensions.

The diffusion criterion and performance criterion played a role in how the D-box was constructed; the dimensions criterion was largely an architectural decision. The reasoning basically boils down to those three, which are predominantly associated with the MixColumns step, so it may be helpful to investigate that part of the round transformation further. Also, much of the theoretical strategy can be found in research of the wide trail strategy.
Back to top
View user's profile Send private message Visit poster's website
data
Forum Fanatic
Forum Fanatic


Joined: 08 May 2004
Posts: 16777211
Location: India

Offline

PostPosted: Thu Apr 14, 2005 2:57 pm    Post subject: Re: Brief comments. Reply with quote

hi,

JustinT wrote:


On a side note, I could prepare some LaTeX renditions of the equations that I can't reproduce here, if that would aid in the comprehension of what's going on.


Please, when you find some time.

Thank you,
Data.
Back to top
View user's profile Send private message Visit poster's website Yahoo Messenger
Display posts from previous:   

Post new topic   Reply to topic   Printer-friendly version    Networking/Security Forums Index -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security All times are GMT + 2 Hours
Page 1 of 1


 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Community Area

Log in | Register