A new method of black box power analysis and a fast algorithm for optimal key search

This paper suggests a new method of power analysis, similarity power analysis, which overcomes the numerics and complexity problems of the template attacks. Similarity power analysis learns characteristics of the device to attack in a profiling phase and is then able to determine a secret key from a single power trace. Similarity power analysis is a black box attack; it does not make any assumptions on the algorithm attacked or its implementation. Since similarity power analysis usually gives wrong results for a small number of key bits, it is supplemented with a new fast algorithm for optimal key search, which enables an attacker to try the keys with the highest probability of success first. Both similarity power analysis and the fast optimal key search algorithm were experimentally tried on DES.