View previous topic :: View next topic 
Author 
Message 
JustinT Trusted SF Member
Joined: 17 Apr 2003 Posts: 16777215 Location: Asheville, NC, US / Uberlāndia, MG, Brazil

Posted: Sat Jul 12, 2003 10:26 pm Post subject: AES: Security in a Nutshell 


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 widescale usage. This simply addresses the current explosion of rumors.
AES in a Nutshell
AES, a 128bit block cipher, structured around what we call a SubstitutionPermutation Network. It was incredibly overdesigned, with differential and linear cryptanlaysis in mind. The algorithm, along with its elegant design, parallelfriendly 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 Sboxes, 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 16byte (128bit) key length in use.
Decryption is rather different, in that it requires the Sbox'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
 Nonlinearity via Sboxes
 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 wellrounded, 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 256element 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 128bit 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 overdefined 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 subexponential 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 overdefined 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, complexitywise. Theoretically, these attacks can be extended to 256bit 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 lifespan 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 miniFAQ 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 pipedream 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 ruleofthumb, don't take hype at face value, but always consider the spontaneous eruption of mathematical breakthrough possibilities.
If you happen to be a mathhead or speccollector, 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 nutshellofareview 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 


DarkAvenger Just Arrived
Joined: 21 Apr 2003 Posts: 0 Location: France

Posted: Fri Jul 18, 2003 8:07 pm Post subject: 


OK, but what about the 23 equations which are satisfied every iterations
between entries and output ?


Back to top 


stillbourne Just Arrived
Joined: 16 Jul 2003 Posts: 0

Posted: Sat Jul 19, 2003 2:49 am Post subject: 


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 


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

Posted: Sat Jul 19, 2003 3:24 am Post subject: Please elaborate... 


DarkAvenger 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 


DarkAvenger Just Arrived
Joined: 21 Apr 2003 Posts: 0 Location: France

Posted: Sun Jul 20, 2003 12:50 pm Post subject: 


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 


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

Posted: Mon Jul 28, 2003 6:45 am Post subject: MQ... 


DarkAvenger 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 Sboxes. 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 Sboxes 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:
128bit  1/2
256bit  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 12,
we consider r equal to 24, otherwise, we set r = 23.
Now, with ciphers such as with Sboxes 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 


DarkAvenger Just Arrived
Joined: 21 Apr 2003 Posts: 0 Location: France


Back to top 


ghost16825 Just Arrived
Joined: 24 Nov 2003 Posts: 2

Posted: Sun Aug 29, 2004 2:44 pm Post subject: 


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 


data Forum Fanatic
Joined: 08 May 2004 Posts: 16777211 Location: India

Posted: Fri Apr 08, 2005 7:16 pm Post subject: 


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 coefficients 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 coeffieients 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 


comrade Just Arrived
Joined: 15 Feb 2005 Posts: 0

Posted: Fri Apr 08, 2005 10:35 pm Post subject: 


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


Back to top 


data Forum Fanatic
Joined: 08 May 2004 Posts: 16777211 Location: India

Posted: Sat Apr 09, 2005 4:50 am Post subject: 


hi there,
Since the math is done in F(2^m), it means that the coefficients 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 coefficients 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 


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

Posted: Sat Apr 09, 2005 12:49 pm Post subject: Brief comments. 


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 coefficients 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 coeffieients 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.
Performancewise, 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 32bit architectures, in implementations that combine the steps of the round transformation within a single set of lookup 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 Dbox 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 


data Forum Fanatic
Joined: 08 May 2004 Posts: 16777211 Location: India

Posted: Thu Apr 14, 2005 2:57 pm Post subject: Re: Brief comments. 


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 


