In AES, the S-box substitution of each byte is depends on the input byte value only. In this paper, a novel method for substituting each byte is introduced. In this method, the substitution of each byte is depending not only on its value but also depend on the input key and the derived subkeys. The keys are used to generate two parameters that are
used for mapping the substituted value horizontally and vertically to a random location in the S-box. The first parameter, subkey plus the input value, are used to rotate the row horizontally to the new location. The second parameter, subkey plus substituted value result from first parameter, are used to rotate the column vertically to new location which
is final substitution value. The required modifications are made for the inverse substitution saving the non-linearity relationship between the Sbox and its inverse. In this technique, we can get up to 256! Substitutions values instead of 256 values as in normal AES algorithm which increase the encryption complexity and complicate the cryptanalysis process. The results show that this is achieved with negligible extra delay. The increase of the substitution domain achieved from this Technique doesn't require to construct a new S-box, or inverse S-box as it does in the dynamic Sbox
approaches in which the need for re-evaluation and proved against cryptanalysis after every new S-box construction is compulsory.