Human relationships rely on trust, which is the reason that the authentication and related digital signatures are the most complex and confusing areas of cryptography. The Massage Authentication Codes (MACs) could be built from cryptographic hash functions or block cipher modes of operations. Substitution-Box (S-Box) is the unique nonlinear operation in block ciphers, and it determines the cipher performance. The stronger S-Box, the stronger and more secure the algorithm. This paper focuses on the security considerations for MACs using block cipher modes of operations with the Hierocrypt-3 block cipher. the Hierocrypt-3 could be considered as a week cipher. It could be enhanced by changing its S-Box with a new one that has better performance against algebraic attack with using different modes of operations. The mathematical model for the new S-Boxes with its properties is provided. The result of this change appeared in the mirror of Average Strict Avalanche Criterion (SAC) and some other properties. SAC could be improved from 0.80469 to 0.16406. The Hierocrypt-3 could be enhanced for more security.