Cryptology ePrint Archive: Report 2017/254

Towards Easy Key Enumeration

Changhai Ou and Degang Sun and Zhu Wang and Xinping Zhou

Abstract: Key enumeration solutions are post-processing schemes for the output sequences of side channel distinguishers, the application of which are prevented by very large key candidate space and computation power requirements. The attacker may spend several days or months to enumerate a huge key space (e.g. $2^{40}$). In this paper, we aim at pre-processing and reducing the key candidate space by deleting impossible key candidates before enumeration. A new distinguisher named Group Collision Attack (GCA) is given. Moreover, we introduce key verification into key recovery and a new divide and conquer strategy named Key Grouping Enumeration (KGE) is proposed. KGE divides the huge key space into several groups and uses GCA to delete impossible key combinations and output possible ones in each group. KGE then recombines the remaining key candidates in each group using verification. The number of remaining key candidates becomes much smaller through these two impossible key candidate deletion steps with a small amount of computation. Thus, the attacker can use KGE as a pre-processing tool of key enumeration and enumerate the key more easily and fast in a much smaller candidate space.

Category / Keywords: implementation / key enumeration, KGE, Group Collision Attack, DPA contest v4, divide and conquer, side channel attack

Date: received 19 Mar 2017, last revised 21 Aug 2017

Contact author: ouchanghai at iie ac cn

Available format(s): PDF | BibTeX Citation

Version: 20170822:055607 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]