Cryptology ePrint Archive: Report 2018/019

Two Sides of the Same Coin: Counting and Enumerating Keys Post Side-Channel Attacks Revisited.

Daniel P. Martin and Luke Mather and Elisabeth Oswald

Abstract: Motivated by the need to assess the concrete security of a device after a side channel attack, there has been a flurry of recent work designing both key rank and key enumeration algorithms. Two main competitors for key ranking can be found in the literature: a convolution based algorithm put forward by Glowacz et al. (FSE 2015), and a path counting based algorithm proposed by Martin et al. (Asiacrypt 2015). Both key ranking algorithms can be extended to key enumeration algorithms (Poussier et al. (CHES 2016) and Martin et al. (Asiacrypt 2015)). The two approaches were proposed independently, and have so far been treated as uniquely different techniques, with different levels of accuracy. However, we show that both approaches (for ranking) are mathematically equivalent for a suitable choice of their respective discretisation parameter. This settles questions about which one returns more accurate rankings. We then turn our attention to their related enumeration algorithms and determine why and how these algorithms differ in their practical performance.

Category / Keywords: implementation / side channels

Original Publication (in the same form): CT RSA 2018

Date: received 5 Jan 2018, last revised 5 Jan 2018

Contact author: elisabeth oswald at bristol ac uk

Available format(s): PDF | BibTeX Citation

Version: 20180105:142645 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]