Improved Template Attacks

This article describes some observations made during our still on-going experiments on template attacks. Taking an unsecured software implementation of the AES on a smart card with highly data depen-dent current consumption, we try out methods given in the literature as well as some own ideas. Our currently best method is able to de-termine the complete 16-byte key correctly given just one power trace using a search over less than one million key candidates in the worst case. Parts of the paper can be found in detail in the diploma thesis of the first author [Bär08]. 1 Template Attacks In [CRR02] S. Chari, J. Rao and P. Rohatgi introduced template attacks, a new kind of attacks that try to extract the maximal possible information from observed side channels like the power consumption of a cryptographic operation performed on a smart card. The underlying attack model is quite powerful: before attacking a device with unknown key the attacker has full access to an identical device and is able to record side channel data for chosen keys and plaintexts. After this profiling phase the attacker should be able to extract the key of the attacked device from a single measurement with given or chosen plaintext. In practice this requirement is often relaxed to allow several measurements for different plaintexts to increase the success rate. The basic idea of the template attack is to model the power consumption as a high dimensional Gaussian distribution dependent on few key bits. Its key-dependent mean and covariance matrix are then estimated using the dat