Cutting Private Key Backup Failures by 6 Orders of Magnitude

Table of Links

Abstract and 1. Introduction

2. Related Work

   2.1 The Alternative-Authenticator Approach

   2.2 The Original-Authenticator Approach

3. The Proposed Secret Backup Approaches

   3.1 Notations

   3.2 Assumptions

   3.3 The Direct-Escrow Method

   3.4 Our Proposed Algorithms

4. Security and Reliability Analysis

   4.1 Security Analysis

   4.2 Reliability Analysis

   4.3 Recovery Failure Rate Analysis

   4.4 Real World Parameters

   4.5 Failure Rate Optimization of (k,n)

5. Comparison

6. Conclusion, Acknowledgment, and References

Appendix

6. CONCLUSION

This paper proposes indirect-escrow and indirect-permission methods for private key backup and recovery. Unlike previous approaches that keep both the possession and permission of the private key backup to either the owner or trustees, our approach lets trustees have only the permission of the backup while the owner has the possession. Our approach is highly secure due to the difficulty of locating all trustees and is highly reliable because of the redundancy of trustees. We also propose a backup failure rate measure that considers both security and reliability and suggests the optimal choice of the threshold number for each choice of the number of trustees. According to the failure rate analysis, our approach is about six orders of magnitude better than other best-known results with the same number of trustees. Therefore, we conclude that our approach provides a very secure and reliable private key backup and recovery method, which is essential for the public-key-based authentication infrastructure. The method can also be applied to protect secrets other than private keys. The indirect-permission approach can also be extended to be a multi-layer indirect-permission approach or adopt multiple sets of trustees for even better security protection.

ACKNOWLEDGMENT

This work was supported in part by Taiwan NSTC grant 111- 2221-E-007-077.

REFERENCES

[1] https://www.google.com/landing/2step/

[2] Siadati, Hossein, et al. “Mind your SMSes: Mitigating social engineering in second factor authentication.” computers & security 65 (2017): 14-28.

[3] Siadati, Hossein, Toan Nguyen, and Nasir Memon. “Verification code forwarding attack (short paper).” International Conference on Passwords. Springer, Cham, 2015.

[4] https://fidoalliance.org/

[5] https://support.apple.com/en-us/HT203027

[6] https://nymi.com/ [7] Gupta, Surbhi, Abhishek Singhal, and Akanksha Kapoor. “A literature survey on social engineering attacks: Phishing attack.” 2016 international conference on computing, communication and automation (ICCCA). IEEE, 2016.

[8] Eskandari, Shayan, et al. “A first look at the usability of bitcoin key management.” arXiv preprint arXiv:1802.04351 (2018).

[9] Peng, Sancheng, Shui Yu, and Aimin Yang. “Smartphone malware and its propagation modeling: A survey.” IEEE Communications Surveys & Tutorials 16.2 (2014): 925-941.

[10] Zaidi, Syed Farhan Alam, et al. “A Survey on Security for Smartphone Device.” International Journal of Advanced Computer Science and Applications-2016 (2016).

[11] Nakamoto, Satoshi. “Bitcoin: A peer-to-peer electronic cash system.” (2008): 28.

[12] Wood, Gavin. “Ethereum: A secure decentralised generalised transaction ledger.” Ethereum Project Yellow Paper 151 (2014).

[13] https://support.google.com/accounts/answer/1187538?hl=en

[14] Han, Aaron L-F., Derek F. Wong, and Lidia S. Chao. “Password cracking and countermeasures in computer security: A survey.” arXiv preprint arXiv:1411.7803 (2014).

[15] https://bitcoinpaperwallet.com/

[16] https://bitcoin.org/en/bitcoin-core/

[17] https://brainwallet.io/

[18] http://www.elek-kingdom.com/product.asp?classid=21

[19] Rathgeb, Christian, and Andreas Uhl. “A survey on biometric cryptosystems and cancelable biometrics.” EURASIP Journal on Information Security 2011.1 (2011): 3.

[20] ftp://ftp.rfc-editor.org/in-notes/rfc4251.txt

[21] Brainard, John, et al. “Fourth-factor authentication: somebody you know.” Proceedings of the 13th ACM conference on Computer and communications security. ACM, 2006.

[22] “introducing trusted contacts” goo.gl/xHmVHA

[23] Schechter, Stuart, Serge Egelman, and Robert W. Reeder. “It’s not what you know, but who you know: a social approach to last-resort authentication.” Proceedings of the sigchi conference on human factors in computing systems. 2009.

[24] Shamir, Adi. “How to share a secret.” Communications of the ACM 22.11 (1979): 612-613.

[25] https://namecoin.org/

[26] Ieee standard for biometric open protocol. IEEE Std 2410-2015, pages 1–37, Nov 2015

[27] https://www.yubico.com/start/ [28] https://ifaa.org.cn/en

[29] Hadid, Abdenour, et al. “Biometrics systems under spoofing attack: an evaluation methodology and lessons learned.” IEEE Signal Processing Magazine 32.5 (2015): 20-30.

[30] Marasco, Emanuela, and Arun Ross. “A survey on antispoofing schemes for fingerprint recognition systems.” ACM Computing Surveys (CSUR) 47.2 (2015): 28.

[31] Bonneau, Joseph, et al. “Secrets, lies, and account recovery: Lessons from the use of personal knowledge questions at google.” Proceedings of the 24th international conference on world wide web. 2015.

[32] Bassett, Gabriel, et al. “Data breach investigations report.” Verizon DBIR Team, Tech. Rep (2022).

[33] Ylonen, Tatu, and Chris Lonvick. The secure shell (SSH) protocol architecture. No. rfc4251. 2006.

[34] Foster, Kenneth R., and Jan Jaeger. “RFID inside.” IEEE Spectrum 44.3 (2007): 24-29.

[35] Voas, Jeffrey, and Nir Kshetri. “Lost and never found.” Computer 54.07 (2021): 12-13.

[36] Maqbali, Fatma Al, and Chris J. Mitchell. “Web password recovery: a necessary evil?.” Proceedings of the Future Technologies Conference. Springer, Cham, 2018.

[37] Gelernter, Nethanel, et al. “The password reset MitM attack.” 2017 IEEE Symposium on Security and Privacy (SP). IEEE, 2017.

[38] Engel, Tobias. “Ss7: Locate. track. manipulate.” Talk at 31st Chaos Communication Congress. 2014.

[39] N. Z.Gong and D.Wang, “On the Security of Trustee-Based Social Authentications,” IEEE Trans. Inf. Forensics Secur., vol. 9, no. 8, pp. 1251–1263, Aug.2014.

[40] https://cryptosteel.com/

[41] https://ucr.fbi.gov/crime-in-the-u.s/2016/crime-in-the-u.s.- 2016/topic-pages/burglary

[42] Melicher, William, et al. “Fast, Lean, and Accurate: Modeling Password Guessability Using Neural Networks.” USENIX Security Symposium. 2016.

[43] https://blockchain.info/wallet/#/

[44] https://blog.talosintelligence.com/2018/02/coinhoarder.html

[45] S.Jarecki, A.Kiayias, H.Krawczyk, andJ.Xu, “Highly-efficient and composable password-protected secret sharing (Or: How to Protect Your Bitcoin Wallet Online),” Proc. – 2016 IEEE Eur. Symp. Secur. Privacy, EURO S P 2016, pp. 276–291, 2016.

[46] https://www.reddit.com/r/NiceHash/comments/7i0s6o/official_pr ess_release_statement_by_nicehash/

[47] Krivoruchko, Taisya, James Diamond, and Jeff Hooper. “Storing rsa private keys in your head.” 2006 12th Pacific Rim International Symposium on Dependable Computing (PRDC’06). IEEE, 2006.

[48] Vasek, Marie, et al. “The bitcoin brain drain: Examining the use and abuse of bitcoin brain wallets.” International Conference on Financial Cryptography and Data Security. Springer, Berlin, Heidelberg, 2016.

[49] Lanitis, Andreas. “A survey of the effects of aging on biometric identity verification.” International Journal of Biometrics 2.1 (2010): 34.

[50] Rathgeb, Christian, and Andreas Uhl. “A survey on biometric cryptosystems and cancelable biometrics.” EURASIP journal on information security 2011.1 (2011): 1-25.

[51] https://www.amazon.com/Allcomponents-FINGERPRINTIDThumbprint-Security-Reader/dp/B000HHHP7C

[52] Vu, Le-Hung, et al. “Enabling secure secret sharing in distributed online social networks.” 2009 annual computer security applications conference. IEEE, 2009.

[53] Liu, Yu-li, Wenjia Yan, and Bo Hu. “Resistance to facial recognition payment in China: The influence of privacy-related factors.” Telecommunications Policy 45.5 (2021): 102155.

[54] Girmay, Siem, Faniel Samsom, and Asad Masood Khattak. “AI based Login System using Facial Recognition.” 2021 5th Cyber Security in Networking Conference (CSNet). IEEE, 2021.

[55] http://fortune.com/2017/12/07/nicehash-bitcoin-hackcryptocurrency/

[56] Kunke, Johannes, et al. “Evaluation of Account Recovery Strategies with FIDO2-based Passwordless Authentication.” arXiv preprint arXiv:2105.12477 (2021).

[57] https://support.google.com/accounts/answer/1187538?hl=en

[58] Herzberg, Amir, et al. “Proactive secret sharing or: How to cope with perpetual leakage.” Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1995.

[59] Nojoumian, Mehrdad, Douglas R. Stinson, and Morgan Grainger. “Unconditionally secure social secret sharing scheme.” IET information security 4.4 (2010): 202-211.

[60] Xu, Yi, et al. “Virtual U: Defeating Face Liveness Detection by Building Virtual Models from Your Public Photos.” USENIX security symposium. 2016.

[61] https://crime-dataexplorer.app.cloud.gov/pages/explorer/crime/property-crime

[62] Jin, Lei, James BD Joshi, and Mohd Anwar. “Mutual-friend based attacks in social network systems.” Computers & security 37 (2013): 15- 30.

[63] Feng, Shihui, et al. “The Internet and Facebook usage on academic distraction of college students.” Computers & Education 134 (2019): 41- 49.

[64] Florencio, Dinei, and Cormac Herley. “A large-scale study of web password habits.” Proceedings of the 16th international conference on World Wide Web. ACM, 2007.

[65] Mura, Valerio, et al. “LivDet 2017 fingerprint liveness detection competition 2017.” 2018 International Conference on Biometrics (ICB). IEEE, 2018.

APPENDIX

In the appendix, we derive the worst-case probability P shown in equation (1) for a successful adversary attack and the approximated probability shown in equation (2).

Wei-Hsin Chang received a B.S. degree in Electrical Engineering from National Tsing Hua University, in 2014 and an M.S. degree in Electrical Engineering from National Tsing Hua University, in 2018. He is currently working at DeepMentor and taking charge of the hardware platform.

Ren-Song Tsay, nicknamed “Dr. Zero-Skew”, is the inventor of the famous industry standard zero-skew clock tree design method. He received his Ph. D. degree from UC Berkeley in 1989 and worked for IBM T. J. Watson Research Center before he started his Silicon Valley ventures. He was the person who designed the first commercially successful performance optimization physical design system and then jointly founded Axis Systems and developed a breakthrough logic verification system using reconfigurable computer technology. After that, he helped a few start-up companies as a consultant or investor and is now teaching at National Tsing-Hua University. He received the IEEE Transaction on CAD Best Paper Award.

---