So is AES-256 more secure or less secure than AES-128 after all?

It seems there are attacks that work more effectively on AES-256 than AES-128, which makes it less secure in some cases. But the bigger key size should add some safety margin on the other hand, for example making it immune to even quantum computers. And I have heard some people say that more rounds make it less secure, and others say that it makes it more secure.

The problem is that you are trying to put a generic security comparison on AES-128 and AES-256. I would argue that if you're going to dig deeper - as you currently do - then this idea that there is a "generic security level" as I would coin it, is flawed.

As you said, there is a related key attack that is only valid for AES-256, mainly related to the key schedule. However, such related key attacks are only possible in very specific circumstances, e.g. when AES-256 would be used as a primitive to create a hash algorithm. AES-256 offers a security of ~99 bits for this specific use case, which is indeed lower than the ~128 bit security you'd expect for AES-128. This already indicates that AES-128 is sometimes more secure than AES-256, although in general AES-256 should be considered more secure. This is however a niche use case, as the 128 bit block size would not make AES a good candidate in the first place. The Whirlpool hash function (among others) e.g. is build upon a function that has been derived from AES, not AES itself.

The key schedule is somewhat related to the number of rounds, but in general having more rounds just makes a cipher more secure, not less.

In short, AES-256 beats AES-128. Use AES-256 which is the golden standard;

Cryptanalysis

The attacks on AES-256 doesn't make it insecure practically, even after 20 years the best attack has the complexity of $2^{254.3}$ for AES-256 and $2^{126.0}$ for AES-128

• 2015 Improving the Biclique Cryptanalysis of AES, Biaoshuai Tao and Hongjun Wu.

The related key attacks as well-known ( as mentioned by Maarten,too), are not related to encryption, it is important if you initiate the compression function of the Merkle-Damgard Construction with AES. These attacks can create internal collisions that can be exploited. Actually, we don't need this, since it has too small block size.

If you look at the above attack AES-128 is less secure in comparison, losing 2 bits in 128 vs losing 2 bits in 256.

128-bit encryption is less secure in various ways;

• Multi-target attack in which the attacker obtains plaintext-ciphertext pairs with different keys. In this case, they can find some of the keys faster than brute force. For a $t$ target the expected cost of finding a key is $2^{128}/t$. If the attackers obtained a billion targets then they will be able to find the first key much lower than 128-bit security. The cost would be below $2^{100}$ and the time would be below $2^{70}$. This attack applies not only to AES but all block ciphers.

  This attack has been executed with the parallel version of Oechslin's rainbow tables, or read in our canonical Q/A.

• Quantum attack: Grover search algorithm that can have quadratic speed will make any 128-bit block cipher insecure, $\approx 2^{64}$-time. This rough calculation omits the important details;

  Grover's attack for AES-128 requires approximately $2^{64}$ successive AES evaluations. It is not clear how one will achieve this, even we assume one second per evaluation, the time will be immense - 5.846×10^11 average Gregorian years. It is a very big number and with a similar argument, we can talk about that AES-192 and AES-256 certainly not achievable.

  Also, note that Grover's algorithm is also parallelizable, a $k$ parallel Grover's algorithm can only provide $\sqrt{k}$ improvement. Not a big gain!.

Forget AES-128, use 256-bit encryption as the golden standard. No fear of

• Cryptanalysis,
• Multi-target attack,or
• Quantum attacks.

Use AES-256-GCM( possible with SIV, too) or ChaCha20-Poly1305 ( better use xChaCha20-Poly1305 for better nonce security 192-bit nonces)

More round makes more secure

Even the simple round of the Tiny Encryption algorithm is secure after 32 rounds. This work simply showed us that, we can secure even simple rounds after many rounds; Twofish: A 128-Bit Block Cipher Schneier et al., 1998;

However, with enough rounds, even bad round functions can be made to be secure.

There was a session at the 3rd AES conference that (high probably) Rose Anderson wished 32-round Rijndael. More round is more secure and this is common knowledge.