Theoretically, what if I were to change some magic numbers in, say, AES?

Question

Purely theoretically. I know it's a bad idea to try to invent your own encryption and that's not the intention here. Just a thought experiment.

Say, I change some or all of the magic numbers used in, say, AES (but this would also apply to other algorithms) and create "AES-RobIII". Of course, this would be incompatible with the current AES algorithm.

1. First: I know these numbers are chosen (usually) very carefully (sometimes maybe even crafted so that they can contain a secret backdoor, but I'm not interested in conspiracy theories, etc). How are these numbers chosen generally and I assume there are many ('infinite') variations possible? Do they come from an 'RNG' (tuned to some specific rules)? Are they chosen 'manually'? I know they have to satisfy some polynomial(s) but do they (the cryptographers designing the algorithm) just start with a random seed or pick a specific number or...?
2. Since these magic numbers are, along with the algorithm, out in the open (as any good encryption algorithm should be), I could theoretically pad the encrypted message with them and 'load' these tables with the numbers before the algorithm is kicked off to encrypt/decrypt, right?
3. Then why have these numbers as constants in the algorithm (unless size is a priority of course) in the first place? Or why don't we have, say, AES-I, AES-II, and AES-III with the only difference being another set of magic numbers? You could even consider the table(s) of magic numbers used a sort of "extra key" so, say, a company could use their generated ^{(similar to how private/public keypairs are generated for example)} set of numbers internally for extra added security when stuff would leak. I realise it won't add much (if anything at all) but added complexity but I was just wondering.

Again, I realise this won't add any advantage of any meaning (probably), if at all, but I was just wondering. Also, this question is based on the assumption that if I change any of the magic numbers and encrypt something with it and then try to decrypt it (with the same, altered, magic numbers) it would still decrypt correctly.

Update: the answers so far seem to focus primarily on AES, but that was just an example. I could've picked any algorithm (though I realise that details may differ per algorithm). I also realise that AES is plenty strong enough and that AES is implemented in a lot of hardware; though I don't see a problem if you can load these magic values in some 'registers' or 'dedicated ram for this purpose' (but I understand it would be a lot less performant and use up a whole lot more wafer space). I was/am looking more from a theoretical point of view where speed or practicality don't (really) matter.

Answer 1

How are these (magic) numbers chosen?

It heavily depends on what algorithm and which of its magic numbers. They seldom are entirely arbitrary. In AES, it is often taken the lowest value such that a certain mathematical property holds, with that property (demonstrably or plausibly) working towards security. In other algorithms, it could be values that pre-existed in another context (like mathematical constants), often screened so that some criteria is met (e.g. being odd).

Are they chosen 'manually'?

Quite often so. Or, as is the case in AES S-boxes, an auxiliary program is used.

I could theoretically pad the encrypted message with them and 'load' these tables with the numbers before the algorithm is kicked off to encrypt/decrypt, right?

Yes.

Then why have these numbers as constants in the algorithm?

Occam's razor. And other good reasons, among which:

• Introducing parameters rather than constants, especially along messages, could very realistically open to attack. For example, if AES S-boxes where a parameter prefixed to a short AES-GCM message, an attacker could change a bit in these constants in the prefix and see if the message gets nevertheless accepted by the receiver despite that change, meaning with high likelihood that the particular S-box entry for this bit was not active during decryption, which would reveal a lot of information about message and key. That could allow recovery of message and key with a realistic number of attempted decryptions.
• Changing constants to variables would make hardware implementations slower, larger, more power-hungry and complex. In the case of AES, the standard constants are carved into modern CPUs.
• Changing constants may invalidate complex optimizations (for speed or side-channel leakage) that went into translating the constants to hardware or software. In the case of AES S-boxes, see e.g. Joan Boyar and René Peralta: A Small Depth-16 Circuit for the AES S-Box, in proceedings of SEC 2012.

You could even consider the table(s) of magic numbers used a sort of "extra key"

There are better ways to obtain that. For example, what's fed to the key input of AES could be obtained with a Key Derivation Function applied to the normal key and extra key.

Answer 2

The Wikipedia page on the Rijndael S-box describes how the numbers were chosen (Note: Rijndael was the winner of the competition that produced AES).

First, the input is mapped to its multiplicative inverse in GF(2⁸) = GF(2)[x]/(x⁸ + x⁴ + x³ + x + 1), Rijndael's finite field. Zero, which has no inverse, is mapped to zero. This transformation is known as the "Nyberg S-box" after its inventor Kaisa Nyberg. The multiplicative inverse is then transformed using [an] affine transformation

It also states some of the reasoning:

The Rijndael S-Box was specifically designed to be resistant to linear and differential cryptanalysis. This was done by minimizing the correlation between linear transformations of input/output bits, and at the same time minimizing the difference propagation probability.

The Rijndael S-Box can be replaced in the Rijndael cipher, which defeats the suspicion of a backdoor built into the cipher that exploits a static S-box. The authors claim that the Rijndael cipher structure should provide enough resistance against differential and linear cryptanalysis if an S-Box with "average" correlation / difference propagation properties is used.

A few other reasons to have fixed constants:

• Adding the SubBytes table as part of the key would require an additional 256 bytes (2048 bits) of information to the "key". There are 256! = 10⁵⁰⁶ possible permutations, so that could theoretically be reduced to about 1600 bits, but this is still far larger than a typical symmetric key. Having pre-defined AES-II, AES-III, etc. variants could reduce that considerably, but would still add some bits to specify which variant was used.
• Embedded systems can be very memory limited. The ATmega328 (used in the Arduino Uno) has only 2048 bytes of RAM, so a 256-byte table would occupy one-eighth of available RAM. It also has only 32 KB of program memory, so even the use of pre-defined tables would be limited.
• Several processors, including current x86 and ARM processors, have AES instructions.

Finally, AES is currently strong enough. Quoting the wikipedia article on AES:

At present, there is no known practical attack that would allow someone without knowledge of the key to read data encrypted by AES when correctly implemented.

Note: The above sentence is in reference to attacks on AES as an algorithm, and is before the section on side-channel attacks.