A first time software is loaded for execution by a device, the software stored in non-secure storage is authenticated. Authenticating the software may involve a cryptographic operation over the software and a digital signature of the software. A verification tag may be generated for the software if authentication of the software is successful, the verification tag based on the software and at least a device-specific secret data. The verification tag may be stored within the device. Each subsequent time the software is loaded for execution it may be verified (not authenticated) by using the verification tag to confirm that the software being loaded is the same as the one used to generate the verification tag while avoiding authentication of the software.