# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
MTGAP
Daedalian Member

 Posted: Fri Feb 20, 2009 6:14 pm    Post subject: 1 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
ESL Student

 Posted: Fri Feb 20, 2009 7:07 pm    Post subject: 2 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
Daedalian Member

Posted: Sat Feb 21, 2009 5:47 pm    Post subject: 3

 Antrax wrote: 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.

So it's the Add Round Key step at the beginning (and at every round) that protects it?
_________________
This statement is false.
Antrax
ESL Student

 Posted: Sat Feb 21, 2009 7:04 pm    Post subject: 4 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
Tired of his old title

Antrax
ESL Student

 Posted: Sat Feb 21, 2009 8:20 pm    Post subject: 6 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
Daedalian Member

Posted: Thu Feb 26, 2009 1:00 am    Post subject: 7

 Antrax wrote: .... byte substitution .... What got you reading about AES?

I got interested in cryptography when I got a book about prime numbers that had a chapter on RSA. My interest spread out from there.

Why is the byte substitution so important? It seems like if you don't know the key, you can't break the cipher whether or not it has the byte substitution. (thinking out loud here) With a chosen-plaintext attack, the cipher can be broken. But with the byte substitution, it is changed after the key is added, so that an unknown value is scrambled, and the input and output are made more independent of each other. Yes, I get it.

But why does it use the byte substitution that it uses? Why not just, say, multiply by three?

Edit: How did you learn so much about AES?
_________________
This statement is false.
Antrax
ESL Student

 Posted: Thu Feb 26, 2009 6:24 am    Post subject: 8 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
Daedalian Member

Posted: Mon Mar 02, 2009 8:06 pm    Post subject: 9

 Antrax wrote: find some property of the byte substitution phase that holds with good probability, and that you can propagate through the rounds of the cipher.

How does one prove that the byte substitution "holds with good probability"?
_________________
This statement is false.
Antrax
ESL Student

 Posted: Tue Mar 03, 2009 5:32 am    Post subject: 10 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
Daedalian Member

Posted: Sat Mar 07, 2009 5:27 pm    Post subject: 11

 Antrax wrote: 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.

Does that mean that the AES s-box would be almost as secure in some other cipher, or is the s-box specific to AES?
_________________
This statement is false.
Antrax
ESL Student

 Posted: Sat Mar 07, 2009 7:12 pm    Post subject: 12 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
Daedalian Member

 Posted: Mon Mar 09, 2009 11:22 pm    Post subject: 13 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
ESL Student

 Posted: Tue Mar 10, 2009 10:47 am    Post subject: 14 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
Daedalian Member

Posted: Tue Mar 10, 2009 12:46 pm    Post subject: 15

 Antrax wrote: 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.

What are other important properties?

From Serpent:

 Quote: -each differential characteristic has a probability of at most 1/4, and a one-bit input difference will never lead to a one-bit output difference; -each linear characteristic has a probability in the range 1/2 +/- 1/4, and a linear relation between one single bit and one single bit in the output has a probability in the range 1/2 +/- 1/8; -the nonlinear order of the output bits as a function of the input bits is the maximum, namely 3.

I'm not sure what all of that means, but I sort of get the idea.
_________________
This statement is false.
Antrax
ESL Student

 Posted: Tue Mar 10, 2009 12:53 pm    Post subject: 16 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
Daedalian Member

Posted: Tue Mar 10, 2009 10:25 pm    Post subject: 17

 Antrax wrote: 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.

I was just looking at linear cryptanalysis. I think I understand how to protect against it:

(to make it easier to read, I have changed binary bits from 0 and 1 to false and true)

For a set of input bits (for example, the first and third bits) and a set of output bits, we will call the XOR of all the bits a. For exactly half of all possible input numbers, a = false, and for the other half, a = true.

But this causes a problem. Let's say we are using 4-bit S-boxes.

We select input bits 1 thru 4 and output bits 1 thru 4. For inputs 0-7, let's say that the xor of all the bits is false. And for inputs 8-15, the xor of all the bits is true.

Now we select input bits 1 thru 4, and output bits 1 thru 3. For inputs 1-8, let's say that the xor of all bits is false. And for inputs 9-15 and 0, the xor of all the bits is true.

Now we try to solve for bit 4 of the output based on this information. Output from input numbers 1-7 and 9-15 must have false as the last output bit, since nothing changes between the two sets of selected bit. And inputs 0 and 8 must have true as the last output bit. But this makes no sense, because all odd numbers end in true and evens end in false. Shouldn't it be half and half? The only possible outputs that make this work is if outputs 0-3 and 12-15 are false, and 4-11 are true, or vice versa. But the problem there is that it becomes messed up once again when you choose input bits 1 thru 4, and output bits 1 and 2: it means that the third output bit must be false for 0-3 and 12-15, and true for 4-11, which is exactly the same as the values for the fourth output bit. What is the problem here?
_________________
This statement is false.
Antrax
ESL Student

 Posted: Wed Mar 11, 2009 8:55 am    Post subject: 18 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!
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersAntraxMTGAPZag Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can 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