research-article

The Exact Security of BIP32 Wallets

Authors:

Sebastian Faust,

Siavash RiahiAuthors Info & Claims

CCS '21: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security

Pages 1020 - 1042

https://doi.org/10.1145/3460120.3484807

Published: 13 November 2021 Publication History

Abstract

In many cryptocurrencies, the problem of key management has become one of the most fundamental security challenges. Typically, keys are kept in designated schemes called wallets, whose main purpose is to store these keys securely. One such system is the BIP32 wallet (Bitcoin Improvement Proposal 32), which since its introduction in 2012 has been adopted by countless Bitcoin users and is one of the most frequently used wallet system today. Surprisingly, very little is known about the concrete security properties offered by this system. In this work, we propose the first formal analysis of the BIP32 system in its entirety and without any modification. Building on the recent work of Das et al. (CCS '19), we put forth a formal model for hierarchical deterministic wallet systems (such as BIP32) and give a security reduction in this model from the existential unforgeability of the ECDSA signature algorithm that is used in BIP32. We conclude by giving concrete security parameter estimates achieved by the BIP32 standard, and show that by moving to an alternative key derivation method we can achieve a tighter reduction offering an additional 20 bits of security (111 vs. 91 bits of security) at no additional costs.

References

[1]

2013. Version bytes for BIP32 extended public and private keys. https://electrum.readthedocs.io/en/latest/xpub_version_bytes.html.

[2]

2014. Ledger Support,Ledger Nano OS. https://support.ledger.com/hc/en-us/articles/115005297709-Export-your-accounts.

[3]

2014. Trezor Wiki,Cryptocurrency standards,Hierachical deterministic wallets. https://wiki.trezor.io/Cryptocurrency_standards.

[4]

Nabil Alkeilani Alkadri, Poulami Das, Andreas Erwig, Sebastian Faust, Juliane Krämer, Siavash Riahi, and Patrick Struck. 2020. Deterministic Wallets in a Quantum World. In ACM CCS 20: 27th Conference on Computer and Communications Security, Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna (Eds.). ACM Press, Virtual Event, USA, 1017--1031. https://doi.org/10.1145/3372297.3423361

Digital Library

[5]

Myrto Arapinis, Andriana Gkaniatsou, Dimitris Karakostas, and Aggelos Kiayias. 2019. A Formal Treatment of Hardware Wallets. In FC 2019: 23rd International Conference on Financial Cryptography and Data Security (Lecture Notes in Computer Science, Vol. 11598), Ian Goldberg and Tyler Moore (Eds.). Springer, Heidelberg, Germany, Frigate Bay, St. Kitts and Nevis, 426--445. https://doi.org/10.1007/978--3-030--32101--7_26

[6]

Mikhail J. Atallah, Marina Blanton, Nelly Fazio, and Keith B. Frikken. 2009. Dynamic and Efficient Key Management for Access Hierarchies. ACM Trans. Inf. Syst. Secur. 12, 3, Article 18 (Jan. 2009), 43 pages. https://doi.org/10.1145/1455526.1455531

Digital Library

[7]

BitcoinExchangeGuide. 2018. CipherTrace Releases Report Exposing Close to $1 Billion Stolen in Crypto Hacks During 2018. https://coinexchangeguide.com/ciphertrace-releases-report-exposing-close-to-1-billion-stolen-in_-crypto-hacks-during-2018/.

[8]

Bloomberg. 2018. How to Steal $500 Million in Cryptocurrency. http://fortune.com/2018/01/31/coincheck-hack-how/.

[9]

Dan Boneh, Manu Drijvers, and Gregory Neven. 2018. Compact Multi-signatures for Smaller Blockchains. In Advances in Cryptology -- ASIACRYPT 2018, Part II (Lecture Notes in Computer Science, Vol. 11273), Thomas Peyrin and Steven Galbraith (Eds.). Springer, Heidelberg, Germany, Brisbane, Queensland, Australia, 435--464. https://doi.org/10.1007/978--3-030-03329--3_15

[10]

Joachim Breitner and Nadia Heninger. 2019. Biased Nonce Sense: Lattice Attacks Against Weak ECDSA Signatures in Cryptocurrencies. In FC 2019: 23rd International Conference on Financial Cryptography and Data Security (Lecture Notes in Computer Science, Vol. 11598), Ian Goldberg and Tyler Moore (Eds.). Springer, Heidelberg, Germany, Frigate Bay, St. Kitts and Nevis, 3--20. https://doi.org/10.1007/978--3-030--32101--7_1

[11]

Michael Brengel and Christian Rossow. 2018. Identifying Key Leakage of Bitcoin Users. In Research in Attacks, Intrusions, and Defenses, Michael Bailey, Thorsten Holz, Manolis Stamatogiannakis, and Sotiris Ioannidis (Eds.). Springer International Publishing, Cham, 623--643.

[12]

Vitalik Buterin. 2013. Deterministic Wallets, Their Advantages and their Understated Flaws. https://bitcoinmagazine.com/articles/deterministic-wallets-advantages-flaw-1385450276/.

[13]

Jean-Sébastien Coron. 2002. Optimal Security Proofs for PSS and Other Signature Schemes. In Advances in Cryptology -- EUROCRYPT 2002 (Lecture Notes in Computer Science, Vol. 2332), Lars R. Knudsen (Ed.). Springer, Heidelberg, Germany, Amsterdam, The Netherlands, 272--287. https://doi.org/10.1007/3--540--46035--7_18

[14]

Nicolas T. Courtois, Pinar Emirdag, and Filippo Valsorda. 2014. Private Key Recovery Combination Attacks: On Extreme Fragility of Popular Bitcoin Key Management, Wallet and Cold Storage Solutions in Presence of Poor RNG Events. Cryptology ePrint Archive, Report 2014/848. https://eprint.iacr.org/2014/848.

[15]

Poulami Das, Sebastian Faust, and Julian Loss. 2019. A Formal Treatment of Deterministic Wallets. In ACM CCS 2019: 26th Conference on Computer and Communications Security, Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz (Eds.). ACM Press, 651--668. https://doi.org/10.1145/3319535.3354236

Digital Library

[16]

Jack Doerner, Yashvanth Kondi, Eysa Lee, and abhi shelat. 2018. Secure Two- party Threshold ECDSA from ECDSA Assumptions. In 2018 IEEE Symposium on Security and Privacy. IEEE Computer Society Press, San Francisco, CA, USA, 980--997. https://doi.org/10.1109/SP.2018.00036

[17]

Manuel Fersch, Eike Kiltz, and Bertram Poettering. 2016. On the Provable Security of (EC)DSA Signatures. In ACM CCS 2016: 23rd Conference on Computer and Communications Security, Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi (Eds.). ACM Press, Vienna, Austria, 1651--1662. https://doi.org/10.1145/2976749.2978413

Digital Library

[18]

Manuel Fersch, Eike Kiltz, and Bertram Poettering. 2017. On the One-Per-Message Unforgeability of (EC)DSA and Its Variants. In Theory of Cryptography, Yael Kalai and Leonid Reyzin (Eds.). Springer International Publishing, Cham, 519--534.

[19]

Marc Fischlin and Nils Fleischhacker. 2013. Limitations of the Meta-reduction Technique: The Case of Schnorr Signatures. In Advances in Cryptology -- EURO- CRYPT 2013 (Lecture Notes in Computer Science, Vol. 7881), Thomas Johansson and Phong Q. Nguyen (Eds.). Springer, Heidelberg, Germany, Athens, Greece, 444--460. https://doi.org/10.1007/978--3--642--38348--9_27

[20]

Nils Fleischhacker, Johannes Krupp, Giulio Malavolta, Jonas Schneider, Dominique Schröder, and Mark Simkin. 2016. Efficient Unlinkable Sanitizable Signatures from Signatures with Re-randomizable Keys. In PKC 2016: 19th International Conference on Theory and Practice of Public Key Cryptography, Part I (Lecture Notes in Computer Science, Vol. 9614), Chen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano, and Bo-Yin Yang (Eds.). Springer, Heidelberg, Germany, Taipei, Taiwan, 301--330. https://doi.org/10.1007/978--3--662--49384--7_12

[21]

Rosario Gennaro, Steven Goldfeder, and Arvind Narayanan. 2016. Threshold-Optimal DSA/ECDSA Signatures and an Application to Bitcoin Wallet Security. In ACNS 16: 14th International Conference on Applied Cryptography and Network Security (Lecture Notes in Computer Science, Vol. 9696), Mark Manulis, Ahmad-Reza Sadeghi, and Steve Schneider (Eds.). Springer, Heidelberg, Germany, Guildford, UK, 156--174. https://doi.org/10.1007/978--3--319--39555--5_9

[22]

Gus Gutoski and Douglas Stebila. 2015. Hierarchical Deterministic Bitcoin Wallets that Tolerate Key Leakage. In FC 2015: 19th International Conference on Financial Cryptography and Data Security (Lecture Notes in Computer Science, Vol. 8975), Rainer Böhme and Tatsuaki Okamoto (Eds.). Springer, Heidelberg, Germany, San Juan, Puerto Rico, 497--504. https://doi.org/10.1007/978--3--662--47854--7_31

[23]

Saqib A. Kakvi and Eike Kiltz. 2018. Optimal Security Proofs for Full Domain Hash, Revisited. Journal of Cryptology 31, 1 (Jan. 2018), 276--306. https://doi.org/10.1007/s00145-017--9257--9

Digital Library

[24]

Eike Kiltz, Daniel Masny, and Jiaxin Pan. 2016. Optimal Security Proofs for Signatures from Identification Schemes. In Advances in Cryptology -- CRYPTO 2016, Part II (Lecture Notes in Computer Science, Vol. 9815), Matthew Robshaw and Jonathan Katz (Eds.). Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 33--61. https://doi.org/10.1007/978--3--662--53008--5_2

[25]

Yashvanth Kondi, Bernardo Magri, Claudio Orlandi, and Omer Shlomovits. 2019. Refresh When You Wake Up: Proactive Threshold Wallets with Offline Devices. Cryptology ePrint Archive, Report 2019/1328. https://eprint.iacr.org/2019/1328.

[26]

Yehuda Lindell and Ariel Nof. 2018. Fast Secure Multiparty ECDSA with Practical Distributed Key Generation and Applications to Cryptocurrency Custody. In ACM CCS 2018: 25th Conference on Computer and Communications Security, David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang (Eds.). ACM Press, Toronto, ON, Canada, 1837--1854. https://doi.org/10.1145/3243734.3243788

Digital Library

[27]

Adriano Di Luzio, Danilo Francati, and Giuseppe Ateniese. 2020. Arcula: A Secure Hierarchical Deterministic Wallet for Multi-asset Blockchains. In CANS 20: 19th International Conference on Cryptology and Network Security (Lecture Notes in Computer Science, Vol. 12579), Stephan Krenn, Haya Shulman, and Serge Vaudenay (Eds.). Springer, Heidelberg, Germany, Vienna, Austria, 323--343. https://doi.org/10.1007/978--3-030--65411--5_16

[28]

Antonio Marcedone, Rafael Pass, and abhi shelat. 2019. Minimizing Trust in Hardware Wallets with Two Factor Signatures. In FC 2019: 23rd International Conference on Financial Cryptography and Data Security (Lecture Notes in Computer Science, Vol. 11598), Ian Goldberg and Tyler Moore (Eds.). Springer, Heidelberg, Germany, Frigate Bay, St. Kitts and Nevis, 407--425. https://doi.org/10.1007/978--3-030--32101--7_25

[29]

Claus-Peter Schnorr. 1990. Efficient Identification and Signatures for Smart Cards. In Advances in Cryptology -- CRYPTO'89 (Lecture Notes in Computer Science, Vol. 435), Gilles Brassard (Ed.). Springer, Heidelberg, Germany, Santa Barbara, CA, USA, 239--252. https://doi.org/10.1007/0--387--34805-0_22

[30]

Victor Shoup. 2004. Sequences of games: a tool for taming complexity in security proofs. Cryptology ePrint Archive, Report 2004/332. https://ia.cr/2004/332.

[31]

Rhys Skellern. 2018. Cryptocurrency Hacks: More Than $2b USD lost between 2011--2018. https://medium.com/ecomi/cryptocurrency-hacks-more-than-2b-usd-lost-between-2011--2018_-67054b342219.

[32]

Mathieu Turuani, Thomas Voegtlin, and Michaël Rusinowitch. 2016. Automated Verification of Electrum Wallet. In FC 2016 Workshops (Lecture Notes in Computer Science, Vol. 9604), Jeremy Clark, Sarah Meiklejohn, Peter Y. A. Ryan, Dan S. Wallach, Michael Brenner, and Kurt Rohloff (Eds.). Springer, Heidelberg, Germany, Christ Church, Barbados, 27--42. https://doi.org/10.1007/978--3--662--53357--4_3

[33]

Bitcoin Wiki. 2018. BIP32 proposal. https://en.bitcoin.it/wiki/BIP_0032.

[34]

Zongyang Zhang, Yu Chen, Sherman S. M. Chow, Goichiro Hanaoka, Zhenfu Cao, and Yunlei Zhao. 2015. Black-Box Separations of Hash-and-Sign Signatures in the Non-Programmable Random Oracle Model. In ProvSec 2015: 9th International Conference on Provable Security (Lecture Notes in Computer Science, Vol. 9451), Man Ho Au and Atsuko Miyaji (Eds.). Springer, Heidelberg, Germany, Kanazawa, Japan, 435--454. https://doi.org/10.1007/978--3--319--26059--4_24

Cited By

Hu MLiu ZZhou Y(2024)Efficient post-quantum secure deterministic wallet schemeCybersecurity10.1186/s42400-024-00216-w7:1Online publication date: 3-Aug-2024
https://doi.org/10.1186/s42400-024-00216-w
Das PErwig AFaust S(2024)Shared-Custodial Password-Authenticated Deterministic WalletsSecurity and Cryptography for Networks10.1007/978-3-031-71073-5_16(338-359)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71073-5_16
Pöhn DGrabatin MHommel W(2023)Analyzing the Threats to Blockchain-Based Self-Sovereign Identities by Conducting a Literature SurveyApplied Sciences10.3390/app1401013914:1(139)Online publication date: 22-Dec-2023
https://doi.org/10.3390/app14010139
Show More Cited By

Index Terms

The Exact Security of BIP32 Wallets
1. Security and privacy

Recommendations

How Does Blockchain Security Dictate Blockchain Implementation?
CCS '21: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security

Blockchain protocols come with a variety of security guarantees. For example, BFT-inspired protocols such as Algorand tend to be secure in the partially synchronous setting, while longest chain protocols like Bitcoin will normally require stronger ...
A Formal Treatment of Deterministic Wallets
CCS '19: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security

In cryptocurrencies such as Bitcoin or Ethereum, users control funds via secret keys. To transfer funds from one user to another, the owner of the money signs a new transaction that transfers the funds to the new recipient. This makes secret keys a ...
A Decentralized Mnemonic Backup System for Non-custodial Cryptocurrency Wallets
Foundations and Practice of Security
Abstract
When using non-custodial cryptocurrency wallets such as Exodus (Bitcoin), Metamask (Ethereum), and Keplr (Osmosis), the private keys are directly stored on the user’s device. Using such a wallet comes with the risk of losing all crypto assets when ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '21: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security

November 2021

3558 pages

ISBN:9781450384544

DOI:10.1145/3460120

General Chairs:
Yongdae Kim
KAIST, Republic of Korea
,
Jong Kim
POSTECH, Republic of Korea
,
Program Chairs:
Giovanni Vigna
University of California, Santa Barbara / VMware, USA
,
Elaine Shi
Carnegie Mellon University, USA

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 November 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

DFG

Conference

CCS '21

Sponsor:

SIGSAC

CCS '21: 2021 ACM SIGSAC Conference on Computer and Communications Security

November 15 - 19, 2021

Virtual Event, Republic of Korea

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
531
Total Downloads

Downloads (Last 12 months)87
Downloads (Last 6 weeks)4

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hu MLiu ZZhou Y(2024)Efficient post-quantum secure deterministic wallet schemeCybersecurity10.1186/s42400-024-00216-w7:1Online publication date: 3-Aug-2024
https://doi.org/10.1186/s42400-024-00216-w
Das PErwig AFaust S(2024)Shared-Custodial Password-Authenticated Deterministic WalletsSecurity and Cryptography for Networks10.1007/978-3-031-71073-5_16(338-359)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71073-5_16
Pöhn DGrabatin MHommel W(2023)Analyzing the Threats to Blockchain-Based Self-Sovereign Identities by Conducting a Literature SurveyApplied Sciences10.3390/app1401013914:1(139)Online publication date: 22-Dec-2023
https://doi.org/10.3390/app14010139
Guo CWang XXie XYu Y(2023)The Multi-User Constrained Pseudorandom Function Security of Generalized GGM Trees for MPC and Hierarchical WalletsACM Transactions on Privacy and Security10.1145/359260826:3(1-38)Online publication date: 26-Jun-2023
https://dl.acm.org/doi/10.1145/3592608
Dong CZhang JLv ZZhang R(2023)Lightweight Hierarchical Deterministic Wallet Supporting Stealth Address for IoT2023 IEEE 22nd International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)10.1109/TrustCom60117.2023.00069(387-393)Online publication date: 1-Nov-2023
https://doi.org/10.1109/TrustCom60117.2023.00069
Zhou LXiong XErnstberger JChaliasos SWang ZWang YQin KWattenhofer RSong DGervais A(2023)SoK: Decentralized Finance (DeFi) Attacks2023 IEEE Symposium on Security and Privacy (SP)10.1109/SP46215.2023.10179435(2444-2461)Online publication date: May-2023
https://doi.org/10.1109/SP46215.2023.10179435
Hanzlik LLoss JWagner B(2023)Token meets Wallet: Formalizing Privacy and Revocation for FIDO22023 IEEE Symposium on Security and Privacy (SP)10.1109/SP46215.2023.10179373(1491-1508)Online publication date: May-2023
https://doi.org/10.1109/SP46215.2023.10179373
Zhong LWang YDing YDu JHe KZhang A(2023)Distributed Key Derivation for Multi-Party Management of Blockchain Digital Assets2023 IEEE 29th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS60453.2023.00109(715-720)Online publication date: 17-Dec-2023
https://doi.org/10.1109/ICPADS60453.2023.00109
Xue JShi LLiu LZhang XLi F(2023)Anonymity-enhancing decentralized protocol for coin mixing based on ring signatures and key derivationPeer-to-Peer Networking and Applications10.1007/s12083-023-01567-w16:6(2761-2774)Online publication date: 13-Oct-2023
https://doi.org/10.1007/s12083-023-01567-w
Gilda SJain TDhalla A(2023)None Shall Pass: A Blockchain-Based Federated Identity Management SystemInventive Computation and Information Technologies10.1007/978-981-19-7402-1_24(329-352)Online publication date: 2-Mar-2023
https://doi.org/10.1007/978-981-19-7402-1_24

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents