Removable weak keys for discrete logarithm-based cryptography
- PDF / 376,548 Bytes
- 15 Pages / 595.276 x 790.866 pts Page_size
- 69 Downloads / 164 Views
REGULAR PAPER
Removable weak keys for discrete logarithm-based cryptography Michael John Jacobson Jr.1 · Prabhat Kushwaha2 Received: 23 February 2020 / Accepted: 9 November 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract We describe a novel type of weak cryptographic private key that can exist in any discrete logarithm-based public-key cryptosystem set in a group of prime order p where p − 1 has small divisors. Unlike the weak private keys based on numerical size (such as smaller private keys, or private keys lying in an interval) that will always exist in any DLP cryptosystems, our type of weak private keys occurs purely due to parameter choice of p, and hence, can be removed with appropriate value of p. Using the theory of implicit group representations, we present a method to determine whether a public key comes from a weak private key subject to a given computational bound, and if so, recover the private key from the corresponding public key. We analyze several elliptic curves proposed in the literature and in various standards, giving counts of the number of keys that can be broken with relatively small amounts of computation.. Our results show that many of these curves, including some from standards, have a considerable number of such weak private keys. We also use our methods to show that none of the 14 outstanding Certicom Challenge problem instances are weak in our sense, up to a certain weakness bound. Keywords Discrete logarithm problem · Weak keys · Implicit group representation · Elliptic curves Mathematics Subject Classification 94A60
1 Introduction Weak cryptographic private keys are those that cause a cryptographic system to have undesirable, insecure behavior. For example, private keys that can be recovered by an attacker with significantly less computational effort than expected can be considered weak. One recent example of weak keys is described in an April 2019 whitepaper [16] by the Independent Security Evaluators, where numerous private keys protecting users’ Ethereum wallets/accounts were discovered. Private keys are used to generate correspondMichael John Jacobson and Prabhat Kushwaha both authors contributed equally to all aspects of the paper, and have read and approved the final manuscript.
B
Prabhat Kushwaha [email protected] Michael John Jacobson Jr. [email protected]
1
Department of Computer Science, University of Calgary, 2500 University Drive NW, Calgary, AB T2N 1N4, Canada
2
CSE Department, IIT Kharagpur, Kharagpur, West Bengal, India
ing addresses of Ethereum [40] or Bitcoin [29] wallets, and to create digital signatures needed to spend the cryptocurrency. The Ethereum private keys were found easily because they were very small integers, as opposed to integers of the appropriate bit length. At the time of writing this article, it is not clear whether Ethereum wallets were assigning these poor keys due to oversight or error in the implementation, or whether it was done maliciously. In any case, the end result is that all the currency in the cor
Data Loading...
