Authors:
(1) Wei-Hsin Chang, Deepmentor Inc. (mailggwhc@gmail.com);
(2) Ren-Song Tsay, Computer Science Department, National TsingHua University, Hsinchu, Taiwan (rstsay@cs.nthu.edu.tw). Authors: Authors: (1) Wei-Hsin Chang, Deepmentor Inc. (mailggwhc@gmail.com); (2) Ren-Song Tsay, Computer Science Department, National TsingHua University, Hsinchu, Taiwan (rstsay@cs.nthu.edu.tw). Table of Links Abstract and 1. Introduction Abstract and 1. Introduction Related Work
2.1 The Alternative-Authenticator Approach
2.2 The Original-Authenticator Approach


The Proposed Secret Backup Approaches
3.1 Notations
3.2 Assumptions
3.3 The Direct-Escrow Method
3.4 Our Proposed Algorithms


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)


Comparison


Conclusion, Acknowledgment, and References Related Work
2.1 The Alternative-Authenticator Approach
2.2 The Original-Authenticator Approach Related Work 2.1 The Alternative-Authenticator Approach 2.1 The Alternative-Authenticator Approach 2.2 The Original-Authenticator Approach 2.2 The Original-Authenticator Approach The Proposed Secret Backup Approaches
3.1 Notations
3.2 Assumptions
3.3 The Direct-Escrow Method
3.4 Our Proposed Algorithms The Proposed Secret Backup Approaches 3.1 Notations 3.1 Notations 3.2 Assumptions 3.2 Assumptions 3.3 The Direct-Escrow Method 3.3 The Direct-Escrow Method 3.4 Our Proposed Algorithms 3.4 Our Proposed Algorithms 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) Security and Reliability Analysis Security and Reliability Analysis 4.1 Security Analysis 4.1 Security Analysis 4.2 Reliability Analysis 4.2 Reliability Analysis 4.3 Recovery Failure Rate Analysis 4.3 Recovery Failure Rate Analysis 4.4 Real World Parameters 4.4 Real World Parameters 4.5 Failure Rate Optimization of (k,n) 4.5 Failure Rate Optimization of (k,n) Comparison Comparison Comparison Conclusion, Acknowledgment, and References Conclusion, Acknowledgment, and References Conclusion, Acknowledgment, and References Appendix Appendix Abstract—In this paper, we propose a very secure and reliable owner self-managed private key recovery method. In recent years, Public Key Authentication (PKA) method has been identified as the most feasible online security solution. However, losing the private key also implies the risk of losing the ownership of the assets associated with the private key. For key protection, the commonly adopted something-you-x solutions require a new secret to protect the target secret and fall into a circular protection issue as the new secret has to be protected too. To resolve the circular protection issue and provide a truly secure and reliable solution, we propose separating the permission and possession of the private key. Then we create secret shares of the permission using the open public keys of selected trustees while having the owner possess the permission-encrypted private key. Then by applying the social authentication method, one may easily retrieve the permission to recover the private key. Our analysis shows that our proposed indirect-permission method is six orders of magnitude more secure and reliable than other known approaches. Abstract 1 INTRODUCTION digital authentication has become more integrated into our daily life in this Information Age. The most widely employed authentication method is the password method, which is known to be inherently vulnerable to attacks. In a data breach investigations report [32], 81% of data breaches are hacked through stolen or weak passwords. Even the enhanced multifactor verification method, which checks several independent pieces of evidence for authentication, may be subject to intercepting and forwarding attacks [2][3]. Therefore, researchers are anxiously looking for better alternative solutions The Public Key Authentication (PKA) method has been identified as the most secure authentication method available [33]. The PKA method adopts an asymmetrical cryptography system that uses pairs of keys: openly circulated public keys and owners' private keys. A private-key owner can generate a unique unforgeable signature and allow the account login server to verify whether the signature is genuine using the paired public key. The PKA method is known to be secure if each person can safely keep the personal private key. To this issue, some have proposed a convenient and secure key management approach using Cryptographic Mobile Devices (CMDs), such as smartphones, wearables [6], or implanted chips [34]. Most CMDs adopt biometric sensors to provide a highly secure key storage and verification implementation. With the CMD solution, one can apply the highly secure PKA approach for everyday account authentications. For example, FIDO [4][56] proposes a universal password-less authentication protocol by integrating the PKA and the CMD solutions. It is becoming popular for people to use wearable CMDs to authenticate personal accounts instead of using passwords, physical keys, or cards [5][6]. However, there exists a detrimental risk. If a CMD owner loses or breaks the CMD, then the owner loses all private keys and consequently the accessibility to all corresponding accounts. Many people do lose their accounts because of losing private keys [35]. Therefore, it is critical to be able to recover private keys. In other words, we need to provide a highly secure and reliable backup authentication method for private key recovery in case of a broken or lost primary authenticator, such as CMD, discussed here. An essential requirement for the backup authenticator is that it must be at least equally secure as the primary authenticator. Otherwise, the overall system security level is degraded since the weakest element of a system determines the actual security level [21]. Additionally, the backup authenticator needs to be very reliable. Whenever one needs to perform recovery, the backup authenticator can be reliably applicable, although there is no definite time when one may need it; otherwise, the person in need may disastrously lose all accounts. Existing backup authentication methods can be classified into two categories, the alternative-authenticator and the original-authenticator approaches, differentiated by whether to recover the original authenticator. The alternative-authenticator approach is to register another authenticator specifically for backup authentication in advance. The original-authenticator approach is to store a backup of the original authenticator. We review both methods in the following. Most online service providers do provide backup authentication schemes using alternative authenticators. Examples are backup code, backup account, registered phone number, or face recognition. Nevertheless, all these recovery processes are less secure than the PKA method and hence are inappropriate. In contrast, the recently emerging decentralized cryptocurrency frameworks, such as bitcoin and ethereum, have no service providers to help to recover user accounts. Therefore, an account owner has to manage their private key to avoid permanent loss of the account access right using the original-authenticator approach. In other words, providing a secure and reliable private key backup and recovery scheme is essential to making the PKA method practical. Since the private key is a secret created by the owner, the problem of private key backup is equivalent to the problem of protecting and recovering a secret indefinitely. Therefore, we use the term "secret" in a general sense to also cover the private key to simplify later discussion. For security reasons, only the owner can access the secret. According to Brainard et al., there are four access-right authentication methods, i.e., something-you-have, something-you-know, something-you-are, and someone-you-know [21]. For convenience, we simply name these the something-you-x methods. The first three something-you-x authentication methods are known to be insecure or unreliable. The something-you-have method is to store the secret at a secret place that requires something, such as a physical key or token, to open the secret place for accessing the secret. The issue of the physical key or token is its vulnerability to theft. For theft prevention, a secret can be encrypted by a password or something-you-know. However, a simple and memorable password is vulnerable to dictionary attacks [14]. In contrast, a long, complex password is more secure but hard to memorize. Hence the long, complex password usually has to be recorded, and then the record suffers the same security issue that occurs in the method of something-you-have. Finally, the method of something-you-are is to protect the secret using personal biometric information, which cannot be stolen or lost. However, the biometric is an exposed pattern that can attract spoofing attacks [50][60]. Also, the method lacks reliability because aging or accidents can alter personal biometrics. The fundamental issue of the three methods above is that they all require a new secret to protect the original secret, and the new secret needs to be protected too. Therefore, they all fall into the circular protection issue and are defective. Lately, Brainard et al. proposed a social authentication (or someone-you-know) method [21] for fallback authentication of online accounts. The social authentication method leverages the fact that the trusted contacts (trustees) of an owner of a secret can easily recognize (authenticate) the owner simply by live interaction (seeing or hearing). The advantage of the social authentication method is that the intangible social relationship cannot be stolen or lost. Since the social relationship is unique to everyone and requires no protection, the method effectively breaks the circular protection issue. Vu et al. [52] extend the social authentication method for secret recovery by direct escrow of the secret to someone the owner trust. Furthermore, since trustees may not be trustworthy, Vu et al. combine a secret sharing method [24] to avoid betraying trustees by dividing a secret into pieces and escrowing each piece to a different trustee. Then for secret recovery, the owner simply contacts trustees and gathers a threshold number of secret shares. Vu's method has dramatically improved all previous techniques but is still at risk of trustees' collusive attacks [52]. To eliminate the collusion attack issue, we propose a highly secure and reliable, indirect-escrow method by leveraging the non-circular protection property of the social authentication method and the effectiveness of the PKA encryption method. We briefly introduce the idea below. We first introduce the concept of possession (where the secret is stored) and permission (the access right to the secret) to analyze the effectiveness of secret protection methods in depth. In general, a secret protection method has to protect both the secret's possession and permission. For example, a printed secret by itself provides both permission and possession. Whoever possesses the printed secret naturally has permission to reveal the secret. If now the secret is stored in a safe box, then for any person to reveal the secret, the person will need to not only possess the safe box but also have the safe key for permission to unlock the safe box to retrieve the secret. The three something-you-x secret protection methods essentially separate the permission from the possession. Nevertheless, a defect is that the permission becomes a new target to be protected and falls into the circular protection issue. In contrast, the direct-escrow method gives each trustee partial permission and possession. Hence the method is subject to the risk of collusive attacks. The direct-escrow way is not sufficiently secure as the trustees have both permission and possession. Therefore, one idea is to give trustees only permission but not possession to fix the problem. Therefore, we propose an improved indirect-escrow method that separately stores the possession at the owner's side but escrows the permission to trustees. Essentially, the indirect-escrow method creates encrypted secret shares using trustees' public keys and stores the secret shares locally. The owner can then recover the original secret by sending the encrypted secret shares to trustees for social authentication to decrypt the secret. The indirect-escrow method leverages the unique advantages of the PKA method and social authentication. Most uniquely, the proposed indirect-escrow social authentication method does not need to let trustees know that they are trustees. Hence, no one possesses any secret share except the owner. In this way, the proposed indirect-escrow approach eliminates the possibility of collusive attacks and is highly reliable and secure. However, the above-proposed approach can still be under collusive attacks after performing the secret recovery since the recovery process also exposes the list of trustees who each possess a secret share sent from the owner. After secret recovery, the situation becomes similar to the direct-escrow method and is at risk of collusive attacks. To further eliminate this collusion possibility, we devise an improved indirect-permission method that pre-encrypts the secret to be protected using a randomly selected symmetric key and perform an indirect-escrow of the random key instead of the secret itself. Therefore, trustees know only the tentative random symmetric key even after secret recovery, not the secret itself. In this way, the collusive attack is avoided. The most significant contribution of our proposed indirect-permission method is that it is straightforward to implement and is highly secure against all known attacks, such as theft, password cracking, biometric spoofing, and collusion. Details are to be elaborated on in later sections. This paper is organized as the following. We first review related work in Sec. 2 and present our proposed methods in Sec. 3. Then, we summarize in Sec. 4 our experimental results and compare them quantitatively with other approaches in Sec. 5. Finally, we conclude the paper in Sec. 6. This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Public

Breaking the Circular Security Problem in Key Recovery

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Why Backup Authentication Methods Often Fail

The Original-Authenticator Approach to Private Key Recovery

Encrypted Key Recovery via Social Trust Models

How to Prevent Trustee Collusion in Key Recovery Systems

How to Evaluate Security and Reliability in Key Recovery Systems

How Secure Backup Systems Prevent Recovery Failures

Why Backup Authentication Methods Often Fail

The Original-Authenticator Approach to Private Key Recovery

Encrypted Key Recovery via Social Trust Models

How to Prevent Trustee Collusion in Key Recovery Systems

How to Evaluate Security and Reliability in Key Recovery Systems

How Secure Backup Systems Prevent Recovery Failures

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps