A Comprehensive Study of the Key Enumeration Problem
Open Access
Abstract
In this paper, we will study the key enumeration problem, which is connected to the key recovery problem posed in the cold boot attack setting. In this setting, an attacker with physical access to a computer may obtain noisy data of a cryptographic secret key of a cryptographic scheme from main memory via this data remanence attack. Therefore, the attacker would need a key-recovery algorithm to reconstruct the secret key from its noisy version. We will first describe this attack setting and then pose the problem of key recovery in a general way and establish a connection between the key recovery problem and the key enumeration problem. The latter problem has already been studied in the side-channel attack literature, where, for example, the attacker might procure scoring information for each byte of an Advanced Encryption Standard (AES) key from a side-channel attack and then want to efficiently enumerate and test a large number of complete 16-byte candidates until the correct key is found. After establishing such a connection between the key recovery problem and the key enumeration problem, we will present a comprehensive review of the most outstanding key enumeration algorithms to tackle the latter problem, for example, an optimal key enumeration algorithm (OKEA) and several nonoptimal key enumeration algorithms. Also, we will propose variants to some of them and make a comparison of them, highlighting their strengths and weaknesses.Keywords
Funding Information
- Departamento Administrativo de Ciencia, Tecnologia e Innovacion (568)
This publication has 29 references indexed in Scilit:
- Simpler and More Efficient Rank Estimation for Side-Channel Security Assessment2015
- Cold Boot Attacks in the Discrete Logarithm Setting2015
- An Optimal Key Enumeration Algorithm and Its Application to Side-Channel Attacks2013
- Security Evaluations beyond Computing Power2013
- A Coding-Theoretic Approach to Recovering Noisy RSA Keys2012
- Cold Boot Key Recovery by Solving Polynomial Systems with Noise2011
- Correcting Errors in RSA Private Keys2010
- Reconstructing RSA Private Keys from Random Key Bits2009
- Quantum Mechanics Helps in Searching for a Needle in a HaystackPhysical Review Letters, 1997
- List Viterbi decoding algorithms with applicationsIEEE Transactions on Communications, 1994