How Secure Backup Systems Prevent Recovery Failures

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

4.2 Reliability Analysis

Since the encrypted backup RK⊙SK is stored on the owner's side, it is critical not to lose the backup. Fortunately, unlike the local storage method that needs a secret place to store the backup, our backup is very secure. Even if an adversary successfully steals the backup, he must first fool enough trustees to recover the temporary key to unlock the secret. The probability is very low, as we have just discussed. Therefore, the owner can be more flexible in selecting the storage forms and locations. An owner can make duplicated copies of the encrypted backup and store them in various places. Thus, it is implausible to lose all backups simultaneously unless large-scale disasters occur.

Another threat to recovery failure is the owner forgetting who the trustees are. Since only the owner knows who the trustees are, without knowing enough trustees, the recovery will fail. However, in this case, the owner may simply ask all candidates from the contact list and slowly identify trustees for recovery. Therefore, failure in this step is unlikely.

The reliability is lowered if trustees are unavailable in the recovery stage. Although the relationship between the owner and trustees cannot be stolen or forgotten, the trustees can be dead or lost at contact for recovery. Nevertheless, a unique advantage of our approach is that the owner can renew the backup process and elect new trustees any time she wishes since the selection process does not require consent from any trustees.

There is a possibility that a trustee may refuse to cooperate and decrypt the backup shared secret even being asked by the authorized owner. Practically, if a trustee becomes untrustworthy, the owner can simply replace the trustee with a new candidate without the need to inform the new and old trustees.

In case trustees change their private keys, although this rarely occurs because of the enormous effort to register a new key to all accounts, we propose to provide a monitoring program to inform the owner if someone changes public keys. To be safe, each owner should renew backups whenever receiving the key change notification.

Besides proactively renewing backups, an owner can enhance reliability with the parameters of secret sharing (k, n). With the choice of (k, n), an owner can tolerate at most (n-k) unavailable or unwilling trustees. We use the same analysis methodology in security estimation by referencing general statistics and experimental data.

As shown in equation (2) and equation (3), we find that the secret sharing parameters (k, n) essentially determines the quality of our approach's security and reliability. There is a tradeoff between security and reliability. Generally, a higher k value leads to a more secure but less reliable result. With the same k value, the larger n value leads to a higher attack success rate. Therefore, it is imperative to balance security and reliability by properly selecting (k, n).

4.3 Recovery Failure Rate Analysis

As discussed above, a successful recovery approach should be secure and reliable. For a more precise evaluation of any recovery approach, we define the recovery failure rate F as the probability that an approach is either not secure or not reliable.

F = 1 - (1 - P) x (1 - Q) = P + Q - PQ,

where

P = the attack success rate in equation (1)

Q = the recovery failure rate in equation (2)

Since, in general, P, Q<<1 and PQ<<P,Q, we have F = P + Q