The master may need to be updated if it is a version of Salt lower than 2014.7.0, or
If you are confident that you are connecting to a valid Salt Master, then remove the master public key and restart the Salt Minion.
The master public key can be found at:
/etc/salt/pki/minion/minion_master.pub
2015-01-31 16:15:34,862 [salt.crypt                               ][ERROR   ] The master key has changed, the salt master could have been subverted, verify salt master's public key
2015-01-31 16:15:34,863 [salt.crypt                               ][CRITICAL] The Salt Master server's public key did not authenticate!
The master may need to be updated if it is a version of Salt lower than 2014.7.0, or
If you are confident that you are connecting to a valid Salt Master, then remove the master public key and restart the Salt Minion.
The master public key can be found at:
/etc/salt/pki/minion/minion_master.pub