4
$\begingroup$

I started reading "Cryptography: theory and practice" by Stinson, and I am trying to understand the reason behind the choices for the different components of AES since they seem quite arbitrary.

  1. In the beginning ADDROUNDKEY is performed, why does this not allow for perfect secrecy: the key and plaintext are same key length and xor'd one at time in a stream cipher manner, why is the condition $P[c|p]=P [p]$ not met?

  2. Why does finding the Galois field inverse of an element in the field provide non-linearity, is there a reason behind this type of design?

  3. I read that the reason for block ciphers having rounds is due to the theory behind product ciphers, by why is this secure and how does it counteract the issue with question 1.

Thank you

$\endgroup$
  • 1
    $\begingroup$ 1) Because you lose "perfect secrecy" as soon as you consider a second block. 2) Galois field is non-linear because you simply construct the substitution using simple operations (XORs) 3) linear and differential cryptanalysis (standard techniques in block cipher cryptanlysis) get harder with more rounds $\endgroup$ – SEJPM Jul 3 '15 at 16:56
  • $\begingroup$ @SEJPM I'm still a little confused about why the XORs part makes the Galois field non-linear. Maybe I don't understand what linear means in this context. $\endgroup$ – dylan7 Jul 3 '15 at 22:11
  • 1
    $\begingroup$ Sorry, the second point was bad formulated. In crypto an equation is said to be linear if it can be fully expressed using XORs on certain bits. The usage of the Galois field prevents such linear (systems) of equations quite efficientely. $\endgroup$ – SEJPM Jul 4 '15 at 9:08
  • $\begingroup$ @SEJPM: In Mix-Columns what does the use of Field multiplication provide there? $\endgroup$ – dylan7 Jul 5 '15 at 19:44
  • 1
    $\begingroup$ non-linearity. You can't express this operation using XORs and permutations. $\endgroup$ – SEJPM Jul 5 '15 at 19:52
3
$\begingroup$

Regarding points 2 and 3, cipher designers want to ensure that the relationship between the plaintext, the ciphertext, and the key are complex, so that no attacker can efficiently untangle them. If the ciphertext can be expressed as a linear or sufficiently low-degree system of functions of the plaintext and key then attackers can use efficient algebraic attacks to quickly recover the key.

Linear functions in particular would be trivially solvable, and an attacker could immediately solve for part or all of the key after just one or two blocks were encrypted. Higher degree systems, so long as they were of sufficiently low degree, could similarly be attacked using interpolation attacks. In general, these algebraic attacks grow more expensive (in terms of time and blocks encrypted) the higher the degree of the system.

The finite field inversion is the only non-linear component of AES. It provides non-linearity because the inversion function can only be expressed in the AES Galois field as a very high degree function of the input. Specifically, the exact algebraic expression of the AES s-box (including the affine function composed with the inversion function) is: $$f(x)=05x^{fe}+09x^{fd}+f9x^{fb}+25x^{f7}+f4x^{ef}+01x^{df}+b5x^{bf}+8fx^{7f}+63$$ That's a polynomial of degree 254, almost the highest degree possible in $GF(2^8)$.

In addition to the other excellent answers responding to question 3, the point about needing a high algebraic degree to resist algebraic cryptanalysis is also a reason for iteration of the round function. If there was only one round -one layer of s-boxes- then the 128-bit ciphertext could be expressed as a system of degree 254 functions of the plaintext and key, which would quickly succumb to interpolation attack (in addition to the dozens of other attacks like differential and linear cryptanalysis that would easily break the cipher). But by iterating several layers of s-boxes interleaved with sub-key insertions and layers of highly diffusive linear functions that make each byte a function of several other bytes, you can ensure that the degree of the system is close to $2^{128}$ (and thus immune to interpolation attack).

$\endgroup$
4
$\begingroup$

I can make a few comments regarding points 1 and 3:

If you are going to encrypt only one block, your first assumption is not that misled. However, you will almost always need to encrypt a file longer (maybe way longer) than the key length (let's say 128 bits). Without considering encryption modes, that means that for every block of 128 bits, you will encrypt with the same key. There are $2^{128}$ ways to encrypt the first block, but once you choose one, you have no freedom to choose the second.

(As a note, if you were to use different keys for each block, you would face the similar practical difficulties that make One Time Pad unpractical).

About rounds, the shortest answer is that the higher the amount of rounds, the "more scrambled" the text can get, but after a certain point, the improvement obtained by an additional round is not worth the overhead in performance.

There are two basic "operations" in cryptography. I have seen them by different names, but I first saw them as substitution and transposition. Substitution is like Caesar's cipher: you assign a different value for a character, but the value of every position is not affected by the others ( $E(M_1M_2M_3)=E(M_1)||E(M_2)||E(M_3)$). Transposition is like an anagram, or a Spartan scytale: the positions of the characters change, but the characters are untouched.

The aim is to mix this two techniques in such a way that the outcome yields no information about the original message. As you will see, each Feistel round will only have a small effect: a given bit will only affect a few bits on the ciphertext. Your target is that all bits of the plaintext affect all parts of the ciphertext.

Up to a certain amount (I believe 9), rounds are insufficient and they leak information. In cryptography, you do not want to live with the bare minimum, so several additional rounds were added.

$\endgroup$
  • 2
    $\begingroup$ I quite like the terms "confusion and diffusion". Confusion describes taking some quantum of information (e.g. a byte) and turning it into something else, and diffusion describes taking some information and rearranging it so that the information is randomly spread about. $\endgroup$ – Polynomial Jul 3 '15 at 20:09
  • $\begingroup$ Regarding the One Time Pad. It seems to be only impractical in the sense of Internet security, due to the fact that speed and efficiency are of at most importance to users. But if you could generate very long keys GB's length at no cost and people were willing to give up the efficiency for absolute security, for situations that weren't happening constantly, i.e. https requests on the web, then the OTP becomes very practical, correct ? $\endgroup$ – dylan7 Jul 4 '15 at 14:18
  • $\begingroup$ I would say that it is rather impractical. Why waste half of your storage capacity in key material? Also, it has another defect that you probably do not want in your encryption algorithm: it is malleable. If you know a certain bit has a certain value (because it's part of the protocol or it is public knowledge, for instance), you can flip it, and the decrypted message will have that bit flipped (you can tamper the plaintext wihtout knowing it). $\endgroup$ – Sergio Andrés Figueroa Santos Jul 4 '15 at 18:38
  • $\begingroup$ But aren't most ciphers without integrity added malleable? Or is tempering a message not thr same as being malleable ? $\endgroup$ – dylan7 Jul 4 '15 at 20:04
  • $\begingroup$ One of the nicest consequences of the difussion property in the best algorithms is known as avalanche effect: the change of one bit in the plaintext changes half of the bits of the ciphertext. In other words, the value of a specific bit in the ciphertext may or may have not been affected by every bit in the plaintext, which makes malleability at bit level practically impossible. Keep in mind that you are still vulnerable to other simple attacks, like replay attacks. $\endgroup$ – Sergio Andrés Figueroa Santos Jul 4 '15 at 20:45
3
$\begingroup$

I will specifically address your question 3; that is, quite a lot of block ciphers (and hash functions) consist of a regular round structure (where you repeatedly do the same thing over and over); why is this?

Well, one incentive for doing that is that it makes the cipher easier to analyze; we can study the round function in depth; once we've done that, we can generalize that to every instance of that round function within the cipher. On the other hand, if we had each round function being different, we'd have to analyze them all separately.

Now, this might immediately strike you as nonintuitive; after all, don't we want to frustrate attackers? Well, yes, we'd prefer to; however attackers aren't the only ones that should be analyzing the system. The designers themselves ought to be analyzing the system. In fact, we can say that the designers have a significantly harder job; their goal is to ensure that there are no attacks; that all the possible avenues have been covers. In contrast, the attacker's job is to find only one. Because of this, a regular round structure helps us to be able to ensure that the cipher is sound.

Of course, another incentive is that a regular round structure makes it more implementation friendly; many implementations find it cheaper to repeatedly do the same thing over and over. However, IMHO, the ease-of-analyse is more important than the implementation aspect.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.