Huge Problem with AES?

[MTGAP]

http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf

I think that I have discovered a huge problem with AES. Please explain why I am wrong.

The sub bytes, shift row, and mix column steps are easily computable given the plaintext or the ciphertext. The AddRoundKey part is harder. I think some attacks can find the plaintext and ciphertext for each round. So given those, it is easy to do sub bytes, shift row, and mix column on the plaintext. Then, it is a simple matter of XORing the sub-shifted-mixed plaintext with the ciphertext to find the round key.

This same technique can be done to find multiple round keys, and from those, the key can be deduced.
_________________
This statement is false.

[Antrax]

AES has 10 rounds. Your attack is a known plaintext attack on one-round AES. Because you don't have access to the intermediate calculations, your attack doesn't work against the full cipher.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[MTGAP]

[Antrax]

The "secure" part of AES is, in fact, the byte substitution. Everything else is linear - if you remove that part, you can reverse AES easily. But that's more a philosophical matter - yes, the key mixing is the actual encryption (since nothing else depends on the key). What happens is when you try to go back, you know what the input to the byte substitution stage was - but for every "plaintext" (input from last round after the various shifts) possibility, there's a matching key to yield that input. Repeat a couple of times and you end with a huge tree of possibilities, so that even the relation between round keys doesn't help.

What got you reading about AES?
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Zag]

Since you seem to know about it -- I've had a related question about these sorts of encryption techniques for passwords. I'm thinking, here, of a Unix system where reading the passwords file is typically not that hard, but the passwords in the file are encrypted.

I know that you can't run the encryption backwards to get the original password, as you said. However, since it is just a password, do you really care if you get the original one or not? Can't you run it backwards to get a value which, when entered as the password, will result in that encrypted form? That is, it won't be the same password as the person originally had, but it will produce the same encrypted result, so the system will accept it. No?

[Antrax]

Again, this would require knowledge of the key. AES can be thought of as a function of two things, the key and the plaintext. The key is an unknown input to this function, and it's required to get the "correct" plaintext. You can indeed find a key/plaintext pair by going backwards, setting the key to some value that you like and decrypting the shadowed password using it, but the result of encrypting that plaintext with another (the correct) key will be different.

This isn't like hash functions - encryptions have to be 1:1 with a set key, otherwise you can't decrypt uniquely. What you're probably thinking of is the very common use of a hash functions (like SHA-1) for shadowed passwords. Hash functions have no key, but they are also "hard to invert" (in the sense that we don't know how to -- we can't prove it theoretically, just a bunch of people tried and failed), so with them you can't go backwards. SHA-1 has 80 rounds of binary nonsense going on, compared to AES' 10 rounds, each fairly regular.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[MTGAP]

[Antrax]

Multiplying by three is probably too regular and besides it's not a permutation. You need to keep the size of the data being transformed the same.
However, there are ciphers that mix arithmetic and binary operations. The most famous one is RC6, which was also one of the AES finalists.
I took a lot of courses about cryptography during my Bsc. in computer science. Which brings me to your other question, the answer to which is very interesting.
First of all, there's nothing magical about AES' byte substitution. There are probably many other permutations that could work there. However, not every permutation would fit - permutations have to be resistant to modern cipher-breaking, aka cryptanalysis.
Cryptanalysis has several forms, but the basic idea is always the same: find some property of the byte substitution phase that holds with good probability, and that you can propagate through the rounds of the cipher. The first such property that was thought of was a difference (xor) in input values which causes a difference in output values for many pairs of input to that stage. It was called "Differential Cryptanalysis" and was used to attack DES. The idea in a nutshell is that, say, a XOR of 0x3 in the input yields 0x7 in the output with good probability, then a XOR difference of 0x7 yields 0x4F, which maybe turns through the other stages (byte shifting and the such) to 0x8 and so on. If you can find a chain long enough of properties, such that multiplying all the probabilities yields something significantly larger than the standard deviation (so roughly, with probability no worse than one in the square of the output space size), then you win: just encrypt that many plain texts with the property, find the many cipher texts for which the property holds, use those pairs to figure out what the input in the key mixing stage was, from that you deduce some key bits and hurrah.
It sounds complex, so just go back to the idea: find some properties of input->output of the byte substitution, build a chain through all the cipher, then encrypt a lot of plaintexts and use that property to figure out the key.

So, all modern ciphers that use that structure (or any structure, really) must make sure their byte substitution phase doesn't have such properties with good probability. If you build the difference distribution for the AES S-Box, you'll see that the best properties are very weak (differential is something like 4 pairs max per property, linear* something similar).
Another consideration when choosing that stage is the "nothing up my sleeve" argument - you want people to believe that you didn't choose some permutation that you know how to break with a technique they don't know yet. That's often done by things like choosing known constants (e, pi) or "famous" polynomials, and transforming them to binary form to get the table.

* another type of cryptanalysis, that deals with parity of a subset of input/key bits leading to the same parity of a subset of the output bits. Even more confusing than differential, but breaks DES faster.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[MTGAP]

[Antrax]

Just count all input/output to hold that relation. For instance, DES S-boxes have a 6 bit input and 4 bit output, so it's just a matter of checking all 64 possible input differences (which means 64 times fixing the input and iterating over the differences), and counting how many output differences you got.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[MTGAP]

[Antrax]

An S-Box alone is not secure. However, yes, if you build some other kind of substitution-permutation network, the AES S-Box can be used there.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[MTGAP]

So, the best S-box is one where the change from input x to output y is never the same for two values of x and y?
_________________
This statement is false.

[Antrax]

You might find that to be impossible, and there are other properties. However, yes, the best S-Box is the one that has the most "random" relation between input and output.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[MTGAP]

[Antrax]

I did a lot of work on Serpent, so I'm more familiar with it. The other important property is what's used in "linear cryptanalysis" - basically finding a subset of the input bits, key bits and output bits which XOR to zero.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[MTGAP]

[Antrax]

Not sure I understand completely. Just FYI, it's impossible to find a function that's completely unbiased. You can prove it by induction on the number of inputs, if memory serves.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!