Private Key Recovery Combination Attacks: On Extreme Fragility of Popular Bitcoin

---

Private Key Recovery Combination Attacks:
On Extreme Fragility of Popular Bitcoin
Key Management, Wallet and Cold Storage Solutions
in Presence of Poor RNG Events
Nicolas T. Courtois
1
Pinar Emirdag
2
Filippo Valsorda
3
1
University College London, UK
2
Independent market structure professional, London, UK
3
CloudFlare, London, UK
Abstract. In this paper we study the question of key management and
practical operational security in bitcoin digital currency storage systems.
We study the security two most used bitcoin HD Wallet key management
solutions (e.g. in BIP032 and in earlier systems). These systems have ex-
tensive audit capabilities but this property comes at a very high price.
They are excessively fragile. One small security incident in a remote
corner of the system and everything collapses, all private keys can be re-
covered and ALL bitcoins within the remit of the system can be stolen.
Privilege escalation attacks on HD Wallet solutions are not new. In this
paper we take it much further. We propose new more advanced combi-
nation attacks in which the security of keys hold in cold storage can
be compromised without executing any software exploit on the cold sys-
tem, but through security incidents at operation such as bad random
number or related random events.
In our new attacks all bitcoins over whole large security domains can be
stolen by people who have the auditor keys which are typically stored
in hot systems connected to the Internet and can be stolen easily. Our
combination attacks allow to recover private keys which none of the
earlier attacks in isolation could hope to recover. Classical bad random
attacks typically concern only very few bitcoin accounts, and only some
very lucky holders of bitcoins can actually steal other people’s bitcoins.
In this paper we go beyond identical random attacks and show several
attacks which also work with related random events, which events are
more probable and yet less likely to be detected before it is too late. We
also present several attacks which work across distinct security domains
which share no common setup, code or keys. Yet in certain circumstances
all the bitcoins in each domain can be stolen. All our attacks are
practical and realistic given the numerous relevant events have already
happened in the bitcoin blockchain hundreds of times, some as recently
as September 2014.
It is not clear if this problem can be repaired, i.e. if there exists a key
management solution with similar audit capabilities as BIP032 which
would be immune against this sort of advanced combination attacks.
Key Words:
applied cryptography, bitcoin, key management, security
management, audit capability, digital signatures, ECDSA, HD Wallets,
BIP032, privilege escalation attacks, bad RNG, RFC6979.

---

1
Introduction
Bitcoin has been in existence for more nearly 6 years [15]. It is a digital
currency, payment and final clearing/settlement system and technology,
a distributed property register and digital notary service, all in one.
Current bitcoin suffers from a number of obvious and well known tech-
nical problems: slow transactions acceptance [8], large storage at all full
network nodes, poor anonymity [18, 13], high volatility, cyber attacks,
to name just a few. In theory many different digital currency systems
could exist [3]. In practice no real alternatives to bitcoin exist: all major
digital currencies are essentially clones of bitcoin with small variations.
They massively reproduce bitcoin, massively re-use open source code of
bitcoin, and inherit all the security problems of bitcoin such as studied
in this paper.
Bitcoins cultivates a certain type of “cryptographer’s dream” in which