If you have to perform any cryptographic operation on an incoming message before verifying its MAC, you are doomed.