In an embodiment, a processor includes: at least one core to execute instructions; and a memory protection logic to encrypt data to be stored to a memory coupled to the processor, generate a message authentication code (MAC) based on the encrypted data, the MAC to have a first value according to a first key, obtain the encrypted data from the memory and validate the encrypted data using the MAC, where the MAC is to be re-keyed to have a second value according to a second key and without the encrypted data. Other embodiments are described and claimed.