Improved collision-correlation power analysis on first order protected AES

Abstract. The recent results presented by Moradi et al. on AES at CHES 2010 and Witteman et al. on square-and-multiply always RSA exponentiation at CT-RSA 2011 have shown that collision-correlation power analysis is able to recover the secret keys on embedded imple-mentations. However, we noticed that the attack published last year by Moradi et al. is not efficient on correctly first-order protected implemen-tations. We propose in this paper improvements on collision-correlation attacks which require less power traces than classical second-order power analysis techniques. We present here two new methods and show in prac-tice their real efficiency on two first-order protected AES implementa-tions. We also mention that other symmetric embedded algorithms can be targeted by our new techniques