Table of Links 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 Appendix 3.3 The Direct-Escrow Method The main weakness of the approach is that, since each trustee knows they are a trustee of the owner, the trustees may attempt to contact each other and collude to steal SK. Furthermore, a research report [23] revealed a non-negligible possibility for the trustees to be cheated into submitting secret shares. For this approach, an adversary only needs to cheat or collude k trustees to steal the owner's SK. Although the direct-escrow method has excellent improvement over the traditional methods, the approach is still vulnerable to collusive attacks, and its security can be further improved. 3.4 Our Proposed Algorithms In this section, we introduce our proposed indirect-escrow and indirect-permission backup methods, which mainly reduce the collusion possibility and are both highly secure and highly reliable. 3.4.1 Indirect-escrow Method This indirect-escrow method does prevent trustees from direct collusion as they do not have secret shares. However, since the owner cannot obtain the private keys of the trustees for decryption, they need to send the secret shares to the trustees when needing recovery. At that time, the trustees will possess the secret shares after decryption, and then the situation becomes similar to that of the direct escrow as the trustees may collude to get the whole secret. Therefore, the indirect-escrow approach still has a security hole, although it is much more secure than the direct-escrow method. 3.4.2 Indirect-permission Method For further improvement, we propose an indirect-permission method that prevents the trustees from possessing the secret SK even after the owner requests recovery. The main idea is to preencrypt the to-be-protected secret SK using a randomly selected symmetric key RK and perform an indirect escrow of the random symmetric key RK instead of the secret. Since RK, which is indirectly escrowed, is the permission to the owner-possessed encrypted secret RK⊙SK, we, therefore, name this approach the indirect-permission method. Even with collusion, the trustees can obtain only RK but not the encrypted secret RK⊙SK during the recovery phase. After recovery, the owner should have the SK and can update a new random key and a new set of trustees for a new backup setup. At the same time, the owner deletes the previously encrypted secret. Therefore, the indirect-permission method solves both the circular permission issue and the collusion problem. For our approach, the trustees do not know that they are selected trustees until receiving recovery requests, while for the direct-escrow approach, trustees know who is the owner of the escrowed backup. Since, for our approach, anyone may request recovery, the trustee must validate the actual ownership of the request to avoid the attacker's false request. Therefore, in our approach, we further require the owner digitally sign each secret share along with a decryption instruction to the trustee using the owner's private key so the trustees can use the owner's public key to verify the signature and know how to proceed. In the following, we elaborate on the backup and recovery algorithms of the indirect-permission approach. More implementation details are discussed later. The Backup Phase: The architecture of the backup algorithm is illustrated in Fig. 1, and the details are described below. (1) Encrypt the target secret The owner generates a random symmetric key, RK, and encrypts SK into RK⊙SK, as shown in Fig. 1. The specification and length of RK conform to contemporary standards. (2) Select trustees and perform secret sharing There are a few known trustee selection strategies [51][59], all of which can work well with our approach. In practice, we suggest that the owner evaluates the security and reliability level of trustee candidates under different conditions and then chooses the ones with higher security and reliability. (3) Recovery instruction to trustees Although we cannot expect everyone to follow the instruction, we believe most of them will follow the instruction for recovery since trustees are those the owner trusts. (4) Digital signature (5) Download trustees' public keys Download each trustee's public key pki from her account or interaction history. (6) Encrypt using trustees' public key The Recovery Phase: The architecture of the recovery algorithm is shown in Fig. 2, and the details are described below. (1) Request for recovery (2) Trustee follows the recovery instruction (3) Verify ownership (4) Decrypt secret shares (5) Recover the owner's private key The owner repeats steps 1~4 until collecting k secret shares. With the accumulated secret shares, the owner reconstructs the temporary key RK following Shamir's secret sharing method and then applies the reconstructed RK to decrypt the backup copy of RK⊙SK and recover the private key SK. Since the trustees, after recovery, are now exposed, they may collude to regenerate the temporary key RK. Nevertheless, they will need to steal the encrypted backup RK⊙SK to recover the private key SK. To eliminate such a possibility, the owner shall destroy all backups after each recovery and choose a new temporary key with a new set of trustees for a new run. Therefore, the proposed indirect-permission approach can be highly secure and reliable. 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). This paper is available on arxiv under CC BY 4.0 DEED license. 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 3.3 The Direct-Escrow Method The main weakness of the approach is that, since each trustee knows they are a trustee of the owner, the trustees may attempt to contact each other and collude to steal SK. Furthermore, a research report [23] revealed a non-negligible possibility for the trustees to be cheated into submitting secret shares. For this approach, an adversary only needs to cheat or collude k trustees to steal the owner's SK. Although the direct-escrow method has excellent improvement over the traditional methods, the approach is still vulnerable to collusive attacks, and its security can be further improved. 3.4 Our Proposed Algorithms In this section, we introduce our proposed indirect-escrow and indirect-permission backup methods, which mainly reduce the collusion possibility and are both highly secure and highly reliable. 3.4.1 Indirect-escrow Method 3.4.1 Indirect-escrow Method This indirect-escrow method does prevent trustees from direct collusion as they do not have secret shares. However, since the owner cannot obtain the private keys of the trustees for decryption, they need to send the secret shares to the trustees when needing recovery. At that time, the trustees will possess the secret shares after decryption, and then the situation becomes similar to that of the direct escrow as the trustees may collude to get the whole secret. Therefore, the indirect-escrow approach still has a security hole, although it is much more secure than the direct-escrow method. 3.4.2 Indirect-permission Method 3.4.2 Indirect-permission Method For further improvement, we propose an indirect-permission method that prevents the trustees from possessing the secret SK even after the owner requests recovery. The main idea is to preencrypt the to-be-protected secret SK using a randomly selected symmetric key RK and perform an indirect escrow of the random symmetric key RK instead of the secret. Since RK, which is indirectly escrowed, is the permission to the owner-possessed encrypted secret RK⊙SK, we, therefore, name this approach the indirect-permission method. Even with collusion, the trustees can obtain only RK but not the encrypted secret RK⊙SK during the recovery phase. After recovery, the owner should have the SK and can update a new random key and a new set of trustees for a new backup setup. At the same time, the owner deletes the previously encrypted secret. Therefore, the indirect-permission method solves both the circular permission issue and the collusion problem. For our approach, the trustees do not know that they are selected trustees until receiving recovery requests, while for the direct-escrow approach, trustees know who is the owner of the escrowed backup. Since, for our approach, anyone may request recovery, the trustee must validate the actual ownership of the request to avoid the attacker's false request. Therefore, in our approach, we further require the owner digitally sign each secret share along with a decryption instruction to the trustee using the owner's private key so the trustees can use the owner's public key to verify the signature and know how to proceed. In the following, we elaborate on the backup and recovery algorithms of the indirect-permission approach. More implementation details are discussed later. The Backup Phase: The architecture of the backup algorithm is illustrated in Fig. 1, and the details are described below. The Backup Phase: (1) Encrypt the target secret (1) Encrypt the target secret The owner generates a random symmetric key, RK, and encrypts SK into RK⊙SK, as shown in Fig. 1. The specification and length of RK conform to contemporary standards. (2) Select trustees and perform secret sharing (2) Select trustees and perform secret sharing There are a few known trustee selection strategies [51][59], all of which can work well with our approach. In practice, we suggest that the owner evaluates the security and reliability level of trustee candidates under different conditions and then chooses the ones with higher security and reliability. (3) Recovery instruction to trustees (3) Recovery instruction to trustees Although we cannot expect everyone to follow the instruction, we believe most of them will follow the instruction for recovery since trustees are those the owner trusts. (4) Digital signature (4) Digital signature (5) Download trustees' public keys (5) Download trustees' public keys Download each trustee's public key pki from her account or interaction history. (6) Encrypt using trustees' public key (6) Encrypt using trustees' public key The Recovery Phase: The architecture of the recovery algorithm is shown in Fig. 2, and the details are described below. The Recovery Phase: (1) Request for recovery (1) Request for recovery (2) Trustee follows the recovery instruction (2) Trustee follows the recovery instruction (3) Verify ownership (3) Verify ownership (4) Decrypt secret shares (4) Decrypt secret shares (5) Recover the owner's private key (5) Recover the owner's private key The owner repeats steps 1~4 until collecting k secret shares. With the accumulated secret shares, the owner reconstructs the temporary key RK following Shamir's secret sharing method and then applies the reconstructed RK to decrypt the backup copy of RK⊙SK and recover the private key SK. Since the trustees, after recovery, are now exposed, they may collude to regenerate the temporary key RK. Nevertheless, they will need to steal the encrypted backup RK⊙SK to recover the private key SK. To eliminate such a possibility, the owner shall destroy all backups after each recovery and choose a new temporary key with a new set of trustees for a new run. Therefore, the proposed indirect-permission approach can be highly secure and reliable. 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). 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.

How to Evaluate Security and Reliability in Key Recovery Systems

Encrypted Key Recovery via Social Trust Models

EScholar Technologies

Too Long; Didn't Read

CTA: Download the FREE AI Productivity Shift report

How to Prevent Trustee Collusion in Key Recovery Systems

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

Smart Cards, IPv6 Packets, and the Future of Post-Quantum Security

Breaking the Circular Security Problem in Key Recovery

Why Backup Authentication Methods Often Fail

The Original-Authenticator Approach to Private Key Recovery

Encrypted Key Recovery via Social Trust Models

Smart Cards, IPv6 Packets, and the Future of Post-Quantum Security

Breaking the Circular Security Problem in Key Recovery

Why Backup Authentication Methods Often Fail

The Original-Authenticator Approach to Private Key Recovery

Encrypted Key Recovery via Social Trust Models

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps