What is the importance of AES add round Key (K0)?

Question

A high-level overview of AES is according to Wikipedia

1. Key expansion;
2. Initial round key addition;
3. 9, 11, or 13 rounds;
4. Final round (making 10, 12, or 14 rounds in total).

I can understand all the steps except step 2 which is known as key widening.

What is the importance of the key widening step? How does it contribute to the overall security of AES? What is the importance of this step and how does it contribute to the overall security of AES?

[EDIT] I heard that it helps to in implementing the encryption recursively but can't see how is this possible. as this is done only time at start of encryption and end of decryption. Implementing this in a recursive function will cause each round to XOR the input with 2 keys.

So what exactly are the benefits of this initial add key step?

Answer 1

AES-128 consists of 10 rounds. Each round includes a public permutation (consisting of the composition of public permutations SubByte ShiftRows MixColumns except for the last round where MixColumns is ommited), and secret tranformations AddRoundKey (consisting of a XOR with a key-dependent and round-dependent value) before the first round, in-between rounds, and after the last round. Therefore there are 11 AddRoundKey. The question asks: why the first AddRoundKey?

Because without the first AddRoundKey, the public permutation of the first round would operate on the plaintext, thus be of no cryptographic value in attacks involving known plaintext.

Consider the most basic attack: brute force key search with a known plaintext/ciphertext pair. With the first AddRoundKey, the input of the first public transformation changes for each key, adversaries must compute that permutation for each key tested, and it's output is very different for each key tested. But without the first AddRoundKey, the output of the first public permutation is a constant that adversaries can compute once at negligible cost; essentially, one round of AES is wasted.

---

Addition: the last AddRoundKey is here for the same reason. And the last round's MixColumns is removed because, should it be present, it would be possible to exchange that last round's MixColumns and the last AddRoundKey (after a linear transformation of the last subkey), and then that last round's MixColumns would be a public permutation operating on ciphertext, thus of no cryptographic value.

---

Addition: I do not see any substance to a claim that "the first AddRoundKey helps in implementing the encryption recursively".