The Original-Authenticator Approach to Private Key Recovery

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

2.2 The Original-Authenticator Approach

This approach assumes that only the original authenticator can be used to access the account. The PKA approach is typical in this category. Therefore, the focus is to provide a secure backup and recovery method for the original authenticator. Depending on who possesses the backup, we classify the backup methods into the owner-possessed and the direct-escrow approaches. We then further classify each category into sub-categories according to who owns the permission.

2.2.1 The owner-possessed approach

a) Local storage (something-you-have): The most intuitive backup approach is to have a physical copy and store the document in a local offline place. This approach requires no password to remember, and the offline backup is resistant to online attacks. The backup can be on paper [15] or metal (good for long-term backup) [40]. However, whoever possesses the printed private key naturally has permission to reveal the private key and access the account. Therefore, this method is vulnerable to theft.

For theft prevention, the backup must be protected by authorized permission. An example is a key or password to a safe box. However, the new permission needs to be protected, and the additional protection becomes a circular issue. Another risk is that the locally stored backup can be destroyed permanently in a fire or disaster.

b) Password protection (something-you-know): Password-protected backup is resistant to theft. For example, a digital wallet containing private keys is protected by a password [16], and a backup is a copy of the wallet stored in another place. The security of this method highly depends on the strength of the password. Although the password space theoretically is huge, researchers found that specific patterns exist in human-made passwords [42]. Therefore, an attacker with the backup may guess a password by applying the known patterns. Recent research showed that one could guess in 16 days 40% of real-world passwords simply by using a recently leaked password set with an NVidia GeForce GTX 980 Ti [42].

Although one may generate a long and randomized password to defend against guessing, a complex password is hard to memorize and must be recorded on something and stored somewhere. The additional record again becomes a circular protection issue.

Some generate private keys via passwords [17][47] and allow the owner to recover the lost private key using the corresponding password. However, since the password approach is fundamentally not secure, the security level is downgraded. For example, by password scanning, M. Vasek et al. [48] identified 884 active bitcoin accounts worth around $100K in 2015.

c) Biometric protection (something-you-are): Instead of password protection, the backup can be protected using biometric methods. It is harder to reproduce a person's biometric than a password. In practice, an owner may secure private keys in a device equipped with a biometric authenticator [52]. However, if the entrusted device breaks, as everything has a limited lifetime, the owner loses all the private keys and access rights to associated accounts.

Alternatively, some proposed biometric-generated private key methods [50] are resistant to guessing because of the complexity of the biometric information. However, attackers may spoof the owner's biometric data and generate the desired private key [50][60].

Another general concern of the biometric approach is that no one can control the long-term biometric variations caused by aging, disease, or accident [49].

2.2.2 The direct-escrow approach

a) Escrow to the server(s): Instead of keeping private keys locally, as in the owner-managed approach, private keys can be stored online and accessed using a password or a 2-factor authentication method [43]. However, all the password or multi-factor-related issues, such as the MitM attack issue, occur here [44]. Additionally, since the online servers store many private keys, they become the target of attacks [46].

To overcome the server attack problem, S. Jarecki et al. [45] proposed a "Password Protected Secret Sharing (PPSS)" approach, which divides each private key into pieces by secret sharing [24] and stores them in different servers. The owner may recover the private key after valid authentications over a threshold number of servers. In other words, an attacker must hack over the threshold number of servers to steal the private key; hence, the multiple-hacking task is much more difficult.

For further security enhancement, some proposed a proactive secret sharing method [58] that periodically renews the secret sharing process to defend against server hacking. This method is based on the observation that attackers cannot break enough servers in a short time and hence proposes a periodic renewal process to invalidate the attacker-gained information. Fundamentally, how to remember and protect the server login method, such as password, is an unresolved circular issue.

b) Direct-Escrow to trustees: L. H. Vu et al. proposed a social-authentication-based private key backup method for the distributed online social network (DOSN) [51]. The private key is divided into secret shares by secret sharing [24], and each share is stored in the selected trustee's server, which is assumed to be well protected by the trustee. To recover the private key, the owner contacts the trustees and retrieves the private key after collecting a threshold number of secret shares. The essence of this social authentication approach is that it does not require new permission to be protected and hence eliminates the circular protection issue. The reason is that social relationship is a naturally decentralized authentication scheme that is very difficult to reproduce. The only possible threat to this approach is that the trustees may collude to steal the owner's private keys.

Some attempted to design a better trustee selection algorithm to resolve the collusion issue. Vu [51] suggested selecting trustees from different sets of friends and encrypting the secret shares using passwords. The problem is that the trustees may eventually know each other and collude with others to recover the key. Also, the encryption password suffers the same issues as the password protection methods discussed before.

Nojoumian et al. [59] proposed a reputation-based secret shares distribution scheme to identify reputable secret holders iteratively. An issue with this approach is that the private key may leak through collusion before truly reputable trustees are identified.

In summary, we observe that the critical issue for potential collusive attacks is because trustees directly possess the secret shares and have the chance for collusion. To be free from collusive attacks while avoiding circular permission issues, we propose improved methods to be elaborated below, with no trustees directly possessing secret shares.