Cryptology ePrint Archive: Report 2016/571

Simple Key Enumeration (and Rank Estimation) using Histograms: an Integrated Approach

Romain poussier and François-Xavier Standaert and Vincent Grosso

Abstract: The main contribution of this paper, is a new key enumeration algorithm that combines the conceptual simplicity of the rank estimation algorithm of Glowacz et al. (from FSE 2015) and the parallelizability of the enumeration algorithm of Bogdanov et al. (SAC 2015) and Martin et al. (from ASIACRYPT 2015). Our new algorithm is based on histograms. It allows obtaining simple bounds on the (small) rounding errors that it introduces and leads to straightforward parallelization. We further show that it can minimize the bandwidth of distributed key testing by selecting parameters that maximize the factorization of the lists of key candidates produced by the enumeration, which can be highly beneficial, e.g. if these tests are performed by a hardware coprocessor. We also put forward that the conceptual simplicity of our algorithm translates into efficient implementations (that slightly improve the state-of-the-art). As an additional consolidating effort, we finally describe an open source implementation of this new enumeration algorithm, combined with the FSE 2015 rank estimation one, that we make available with the paper.

Category / Keywords: Key enumeration, Key rank, side-channel analysis

Original Publication (in the same form): IACR-CHES-2016

Date: received 3 Jun 2016, last revised 6 Jun 2016

Contact author: romain poussier at uclouvain be

Available format(s): PDF | BibTeX Citation

Version: 20160606:121619 (All versions of this report)

Short URL: ia.cr/2016/571

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]