Distributed Services and Replication Management

Background - Secret Sharing

In our last lecture on secret sharing we talked about how to use secret sharing in building an online service in general, where the service maintains a certain secret. The objective is to achieve both availability and confidentiality of the secret.

Replication is a standard approach to improving availability of an online service. However, replication of a secret increases vulnerability, and thus it is easy to see how secret sharing could be beneficial in such a distributed system.

In this class, we assume the following failure model. A server may crash or may be broken into by an attacker. The attacker may steal information from the server it breaks into, but is unable to modify the states or the code of that server (there are mechanisms that deal with more powerful adversaries where an adversary can modify a corrupted server in any arbitrary way. We assume this more benign case to simplify the discussion). A server is compromised if the server either crashes or is broken into. Our objective is to design the on-line service that could tolerate up to t-1 compromised servers.

Secret sharing in an online environment introduces new concerns. In an (n,t) sharing scheme, it only takes (>= t) servers to be compromised before an attacker can obtain access to the secret. Thus, an attacker might eventually gain access to any secret given enough time to break into t machines. Suppose the service is going to run for 5 years, the adversary has 5 years to compromise t servers in order to overthrow the service.

To counteract this, the idea of a proactive secret sharing (PSS) scheme was introduced. In an execution of PSS, servers generate new shares from old ones and delete the old ones. The secret is never reconstructed during the entire process. The new shares are independent of the old ones and constiture a new (n,t) sharing of the same secret s. (refer to Secret Sharing lecture )

By executing of PSS at intervals, we seek to reduce the time period during which the adversary has to compromise t servers in order to discover the secret. For example, with periodic execution of PSS every month, the adversary has to compromise t servers within a month (between two executions of PSS) in order to obtain the secret (more precisely, between the start of a PSS to the end of the next PSS). The previous lecture contains a much more detailed explanation of our PSS scheme.

Constructing a Certification Authority with Secret Sharing

With this concrete example, we have to worry about how such a replicated service uses the shares to perform its operations. In the online CA case, the operation is to sign a certain message (a CRL, a certificate, or a validation confirmation of a certicate).

Well, we know that, with an (n,t) sharing, t servers can get together and reconstruct the secret (i.e., the private key of the CA). However, no server can construct the private key on-the-fly and then use the private key to sign a message. Otherwise, if the server is compromised after collecting the shares, then the private key of the service is disclosed, which would imply that the service cannot tolerate even a single compromised server.

We need a scheme for the servers to sign a message without recovering the private key first. We have been using simple and specific examples to illustrate the fundamental ideas of various concepts. This time, we actually try a different approach: let's generalize the idea first.

In abstraction, what we need is still a sharing of a secret s among n parties. However, we are not interested in the capability of these parties to recover the secret. Instead, we are interested in applying a certain function (e.g., fs) on any input m using the secret s. We are in fact constructing a sharing of fs. So, this variation of secret sharing is also called function sharing. In the case of the CA, the function f is to generate a signature from a message m using a private key k.

An (n,t) function sharing of function f with respect to a secret s should achieve the following properties:

1. if (>= t) out of n parties get together, they can generate fs(m) for any possible input m, which means they can apply the function fs
2. if (< t) out of n parties get together, they cannot generate fs for an arbitrary input m.

Usually, function sharing is performed in the same manner as secret sharing: s is divided into n shares, one for each party. In addition, function sharing provides a function g. Now, instead of recovering the secret from the shares, the n parties may be asked to perform function f on a certain input. So, instead of submitting the shares to recover the secret, each party i applies function g on the input m using its share si and submit the result g(si, m). These results are called partial results.

The partial results have the property that: with at least t partial results, fs(s) can be computed; otherwise, fs(m) cannot be constructed. A function sharing scheme provides another function g' that generates the final result (fs(m)) from t partial results.

Let's illustrate the feasibility of function sharing through a very simple example. Suppose we have a secret s and want to share function fs(m)= ms for any input m. Let's say we want to construct a (2,2) sharing.

Three components of function sharing:

• How to split the secret into shares
• Function g to compute partial results using shares
• Function g' to generate the final result from 2 partial results

Here is how we generate the two shares: we randomly select shares s1 and s2 so that s = s1 + s2. As we have shown in the last class, these two shares constitute a (2,2) sharing of s.

Now we give these two shares to two parties and would like the two parties to compute function fs for an input m without reconstructuring s. Let g(m, si) = msi and g'(x,y) =x * y.

For an input m,

1. Party 1 computes partial result g(m, s1) = ms1.
2. Party 2 computes partial result g(m, s2) = ms2.
3. Party 1 and party 2 submit ms1 and ms2.

With both ms1 and ms2, we can easily compute ms = g'(ms1, ms2) = ms1 * ms2.

We have to be very careful here: not all functions can be shared. We may not be able to disclose partial results in certain cases if shares or the secret can be inferred from these partial results. More specifically, the secret s and the shares should not be disclosed during the entire process of applying the function. That corresponds to requiring both f and g to be one-way functions(e.g., signing a message is such an function). If we re-represent the example in a certain finite field (i.e., doing modular exponentiation ms mod N , where s and N satisfy certain properties), then the scheme would satisfy this requirement.

Threshold Cryptography

After more than a decade of research, researchers have found threshold cryptography schemes for most popular public key cryptography schemes such as discrete-logarithm-based public key crypto schemes (e.g., DSS: Digital Signature Standard) and schemes such as RSA. We are not going to give details for these schemes -- this requires deeper understanding of the specific public key crypto schemes. In fact, the threshold RSA scheme has a similar flavor as the example we just gave.

Now go back to our CA. We can now use a threshold cryptography scheme. The scheme provides a way to split the private key into n shares and give one share to one server. The scheme also provides a function g to compute partial results (partial signature to generate signatures) and a function g' to generate the final result (signature or decrypted message) from partial results.

Here is how servers generate a signature for a given input m (sent to every server).

Each server i generates a partial signature g(m, si), where si is the share held by the server. Server i then broadcasts the partial signature to all other servers.

When a server collects t partial signatures, according to the property of function sharing, it can compute {m}s (i.e. the signature of m signed by the private key of the CA) using function g'.

Proactive schemes can also be constructed for threshold cryptography. The idea is the same as PSS, where the servers refresh their shares without reconstructing the private key. Servers perform proactive threshold cryptography scheme periodically to enhance the security of the on-line CA.

Now we have this replicated online CA that can tolerate t compromised servers (n >= 2t+1) within a short period of time (between executions of the proactive scheme). The service can sign certificates (or CRLs) online without disclosing any secret information.