How to Prevent Trustee Collusion in Key Recovery Systems

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

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.