Variable epoch scheduler for proactive cryptography systems

Some conventional secure computer systems protect a secret by distributing shares of the secret to a group of clients. The clients are then able to recover the secret only when at least a threshold number of the clients combine their shares. For example, suppose that the secret to be protected is a number, and that at least m clients are required for recovering the secret. A computer system configured to protect the secret, known as a dealer, generates a polynomial f(x) of degree m−1 such that the secret is the constant term of that polynomial, f(0). The dealer then distributes one of the quantities f(1), f(2), . . . , f(n), to each client when there are n clients. In this way, any m of the n clients can recover the secret using Lagrange interpolation.

Other conventional computer systems proactively update the shares of the secret at regular intervals. To continue the above example, the dealer generates another polynomial g(x) of degree m−1 such that g(0)=0. The constant term of a new polynomial (f+g)(x), also of degree m−1, also reveals the secret. The dealer then distributes one of the quantities g(1), g(2), . . . , g(n), to each client, any m of the n clients recovering the secret using Lagrange interpolation on each of their values of f+g.

It should be understood that there are other ways to split a secret into shares. For example, the secret may be split into shares such that an exclusive or (XOR) operation on all of the shares recovers the secret. In this case, the shares of the same secret can be adjusted by updating two or more shares in such a way as to preserve the secret.

Often, also, in other computer systems one or more secrets, some of which may themselves be possibly shared amongst groups of clients, need be updated. Those secrets that are shared can be updated by updating one or more of the shares they are dispersed into.

In many cases, the dealer is not trusted by the clients to distribute updates that are able to recover the secret. In such a case, the clients themselves may provide updates to each other's shares at the regular intervals.

Unfortunately, there are deficiencies with the above-described conventional secure computer systems. For example, an adversary may learn the regular intervals at which the secrets or secret shares are updated. In that case, the adversary may then calibrate his or her ability to obtain the secrets or secret shares so that the threshold number of shares are recovered between updates. Along these lines, suppose that a secure computer system provides share updates every five timesteps to a pair of clients. Suppose further that an adversary can corrupt both clients within four timesteps of one another, where time is broken down into discrete units of one timestep, and attacks only once at the beginning of a timestep, with no knowledge of the internal states of the clients except for the time. Such an adversary may then recover the secret with 100% probability.

It should be understood that, as the secrets described above typically correspond to cryptographic keys, without loss of generality the term key is to generically denote the secrets in a computer system in the description that follows.

In contrast to the conventional secure computer systems in which an adversary may more efficiently compromise one or more secrets by learning about the regular intervals between secret and/or secret share updates, an improved technique involves protecting a set of resources in a distributed computer system by scheduling epochs for replacing keys that have a variable duration. Along these lines, a Variable Epoch Scheduler (VES) generates schedules of key updates for a set of players in the distributed system such that at least two epochs in the schedules have different durations. For example, the epoch durations within a schedule may vary, or the epoch durations for different players may be different. At the end of each epoch, the VES notifies the distributed system to update the key identified in the schedule as corresponding to that epoch.

Advantageously, the improved technique makes it less likely that an adversary will be able to learn or reconstruct a secret. In fact, the adversary will be less likely to recover the secret even without decreasing the average duration of the epochs. Suppose that two players share a secret, and the VES schedules epochs for each of the players having a duration of either five or six units according to the output of a random number generator having a uniform distribution. In this case, even when the epoch schedules for the players are in lockstep, that same adversary only has a probability of less than 27% of recovering the secret after a sufficient number of epochs have passed, compared to the case in which regular epochs of five units have a 100% probability of the adversary recovering the secret. The VES may further reduce such a probability by varying epoch durations between players.

One embodiment of the improved technique is directed to a method of protecting a set of resources in a distributed computer system. The method includes generating a schedule that includes a set of times, each time of the set of times defining an end of an epoch having a duration over which a key of a set of keys that corresponds to the time is valid, each key of the set of keys being associated with a resource of the set of resources, the set of times including a first time and a second time different from the first time. The method also includes, for a first key that corresponds to the first time, sending a request to update the first key to the distributed system at the first time to produce an updated first key. The method further includes, for a second key that corresponds to the second time, sending a request to update the second key to the distributed system at the second time to produce an updated second key.

It should be understood that, in some arrangements, the improved technique involves precomputing the times of the set of times. In other arrangements, however, the improved technique involves automatically generating a new time as each time of the set of times has elapsed.

Additionally, some embodiments of the improved technique are directed to a system constructed and arranged to protect a set of resources in a distributed computer system. The system includes a network interface, memory, and a controller including controlling circuitry constructed and arranged to carry out the method of protecting a set of resources in a distributed computer system.

Furthermore, some embodiments of the improved technique are directed to a computer program product having a non-transitory computer readable storage medium which stores code including a set of instructions to carry the method of protecting a set of resources in a distributed computer system.

The foregoing and other objects, features and advantages will be apparent from the following description of particular embodiments of the invention, as illustrated in the accompanying figures in which like reference characters refer to the same parts throughout the different views.

FIG. 1 is a block diagram illustrating an example electronic environment for carrying out the improved technique.

FIG. 2 is a block diagram illustrating an example variable epoch scheduler within the electronic environment shown in FIG. 1 .

FIG. 3 is a flow chart illustrating an example variable schedule based on epochs of random length within the electronic system shown in FIG. 1 .

FIG. 4 is a flow chart illustrating a method of carrying out the improved technique within the electronic environment shown in FIG. 1 .

An improved technique involves protecting a set of resources in a distributed computer system by scheduling epochs for replacing keys that have a variable duration. Along these lines, a Variable Epoch Scheduler (VES) generates schedules of key updates for a set of players in the distributed system such that at least two epochs in the schedules have different durations. For example, the epoch durations within a schedule may vary, or the epoch durations for different players may be different. At the end of each epoch, the VES notifies the distributed system to update the key identified in the schedule as corresponding to that epoch.

Advantageously, the improved technique makes it less likely that an adversary will be able to learn or reconstruct a secret. In fact, the adversary will be less likely to recover the secret even without decreasing the average duration of the epochs. Suppose that two players share a secret, and the VES schedules epochs for each of the players having a duration of either five or six units according to the output of a random number generator having a uniform distribution. In this case, even when the epoch schedules for the players are in lockstep, that same adversary only has a probability of less than 27% of recovering the secret after a sufficient number of epochs have passed, compared to the case in which regular epochs of five units have a 100% probability of the adversary recovering the secret. The VES may further reduce such a probability by varying epoch durations between players.

It should be understood that the improved technique applies to the case of independent keys and the cases of dependent keys, for example keys that are shares of a particular secrets. In the most general case, some keys are independent, while other keys are secret shares that are configured to combine to form one or more secrets. The example below, however, is directed to the special case where all of the keys are dependent keys that represent a shared secret such as that found in a proactive cryptography system.

FIG. 1 illustrates an example electronic environment 10 for carrying out the improved technique. Electronic environment 10 includes VES 12 , distributed system 14 , external client 22 , and communications medium 32 .

VES 12 is configured to generate schedules 16 of epochs for players 18 during which a key used to recover a secret 28 is valid. VES 12 is also configured to send proactivization signals 24 before the beginning of new epochs for a player 18 to update a key. VES 12 is further configured to receive an event notification 26 and generate schedules 16 based on events in event notification 26 . In some arrangements, VES 12 is a server; in other arrangements, however, VES 12 takes the form of a desktop personal computer or a laptop computer.

Distributed system 14 is configured to distribute proactivization signals 24 from VES 12 from which keys 30 may be derived. Distributed system 14 includes player 18 a , player 18 b , and player 18 c (players 18 ). In some arrangements, distributed system 14 is a part of a network over which players 18 are connected locally, or via communications medium 32 . In other arrangements, however, distributed system 14 is a single system containing players 18 .

Players 18 are each configured to generate keys 30 upon receiving a proactivization signal 24 from VES 12 . In some arrangements, players 18 are also configured to send generated keys 30 to other players 18 as part of a verification scheme. In some arrangements, each player 18 a , 18 b , and 18 c is a personal computer; in other arrangements, however, some or all players 18 may take the form of a laptop computer, a tablet computer, or any type of device with a processor and a network interface.

External client 32 is configured to send event notification 26 to VES 12 in order to determine epoch durations for certain players 18 .

Communication medium 32 provides network connections between VES 12 , distributed system 14 , and external client 22 . Communications medium 32 may implement a variety of protocols such as TCP/IP, UDP, ATM, Ethernet, Fibre Channel, combinations thereof, and the like. Furthermore, communications media 32 may include various components (e.g., cables, switches/routers, gateways/bridges, NAS/SAN appliances/nodes, interfaces, etc.). Moreover, the communications medium 32 are capable of having a variety of topologies (e.g., queue manager-and-spoke, ring, backbone, multi drop, point to-point, irregular, combinations thereof, and so on).

During operation, VES 12 generates schedules 16 , specifically, schedule 16 a for player 18 a , schedule 16 b for player 18 b , and schedule 16 c for player 18 c . Each schedule, schedule 16 a for example, includes a set of epochs having indices; in FIG. 1 , each schedule shows five epochs with indices 1, 2, 3, 4, 5 as indicated. The duration of an epoch is indicated by the width of the rectangle representing the epoch; this, in schedule 16 a , the epoch of index 1 has a longer duration than the epoch of index 2. Further, the placement of the epochs with schedules 16 represent a time at which each epoch begins and ends. For example, the epoch of index 1 in schedule 16 a begins earlier than the epoch of index 1 in schedule 16 b , which begins earlier than the epoch of index 1 in schedule 16 c.

It should be understood that schedules 16 have epochs that may vary not only within a schedule 16 , but between schedules 16 corresponding to different players 18 , or both. For example, the epoch having the index of one in schedule 16 a has a longer duration than the epoch having the index of one in schedule 16 b.

Prior to the beginning of a new epoch in, say, schedule 16 a , VES 12 sends proactivization signal 24 a to player 18 a via communications medium 32 . Proactivization signal 24 a includes information on when player 18 a needs to derive a new key 30 a . In some arrangements, player 18 a derives its own key 30 a from information in proactivization signal 24 a . For example, signal 24 a contains parameters from which player 18 a may derive key 30 a . In other arrangements, however, player 18 a derives, for example, key 30 c and sends key 30 c to player 18 c via communications medium 32 .

It should be understood that, as players 18 generate keys 30 in response to signals 24 , only certain keys may be combined to recover secret 28 . Along these lines, suppose that, among the three keys 30 a , 30 b , and 30 c , players 18 need two keys 30 to recover secret 28 . Suppose further that VES 12 has sent a signal 24 c to player 18 c to generate key 30 c for the epoch having an index of one. According to schedules 16 in FIG. 1 , there is a small window in time during which any of keys 30 a , 30 b , and 30 c may be combined with another key 30 to recover secret 28 . After this time window, VES 12 will have sent player 18 b signal 24 b to update key 30 b , so that key 30 b corresponds to an epoch having an index of two. Key 30 b will then not be able to combine with keys 30 a and 30 c until at least one of players 18 a and 18 c generates a new key 30 corresponding to their next epoch (i.e., epochs of index two).

It should be understood that secret 28 may either be static in time or it may change when a key 30 changes.

It should also be understood that VES 12 , in some arrangements, precomputes each schedule 16 . In other arrangements, however, VES 12 computes a new time in some schedules as a time of the set of times elapses.

There are various mechanisms by which VES 12 generates schedules 16 . Further details of VES 12 will be discussed below with respect to FIG. 2 .

FIG. 2 illustrates further details of an example VES 12 . VES 12 includes controller 40 which in turn includes processor 44 and memory 46 , and network interface 42 .

Network interface 42 takes the form of an Ethernet card; in some arrangements, network interface 42 takes other forms including a wireless receiver and a token ring card.

Memory 46 is configured to store code which includes schedule generation code 52 and random number generation code 54 . Memory 46 generally takes the form of, e.g., random access memory, flash memory or a non-volatile memory.

Processor 44 takes the form of, but is not limited to, Intel or AMD-based MPUs, and can include a single or multi-cores each running single or multiple threads. Processor 44 is coupled to memory 46 and is configured to execute instructions from schedule generation code 52 and random number generation code 54 . Processor 44 includes schedule generation engine 48 and random number generation engine 50 which are configured to execute instructions derived from schedule generation code 52 and random number generation code 54 , respectively.

During operation, schedule generation engine 48 generates schedules 16 (see FIG. 1 ) based on a set of criteria. For example, processor 48 receives information from, e.g., external client 22 via network interface 42 , about relative levels of risk associated with users 20 associated with players 18 . Such a level of risk is encapsulated in a risk score between, e.g., 0 and 1000, with zero representing minimum risk and 1000 representing maximum risk. Consider a set of schedules 16 that VES 12 has set to the same among players 18 . Suppose that user 20 a has a risk score of 200, user 20 b has a risk score of 900, and user 20 c has a risk score of 600. (For example, the risk scores may be indicative of how a user's email account is used.) Schedule generation engine 48 is then configured to decrease epoch durations for those players associated with users having higher risk scores (e.g., users 20 b and 20 c ) and increase epoch durations for those players associated with users having lower risk scores (e.g., player 20 a ).

It should be understood that such adjustments to epoch durations can be changed with new risk scores. For example, suppose that processor 44 receives a message via event notification 26 updating the risk scores for users 20 . Schedule generation engine 48 is then configured to adjust both future and current epochs of schedules 16 to reflect the new levels of risk associated with users 20 .

In some arrangements, risk scores are indicative of a user's role within a role-based access control (RBAC) system in an organization. For example, suppose that the RBAC relates to information concerning a potential merger involving the organization. Suppose further that the role assigned to user 20 a represents a worker uninvolved with the merger, while that assigned to user 20 b represents an attorney working on the merger. The level of risk associated with user 20 a will be small, as player 18 a will likely store no documents relating to the merger, and an adversary will be less likely to attempt to compromise player 18 a . On the other hand, the level of risk associated with user 20 b will be large because player 20 b will likely have such documents and the adversary will be more likely to attempt to compromise player 18 b.

In some arrangements, schedule generation engine 48 adjusts schedules 16 based on resources protected by players 18 . For example, a data loss prevention (DLP) system (not pictured) is configured to scan a player for particular documents. The DLP may also associate particular documents it finds with a classification and send the classification to VES 12 . Along these lines, suppose that a DLP system scans players 18 for documents labeled “Confidential”. Suppose further that the DLP system finds no documents labeled “Confidential” on player 18 a , but an appreciable fraction of data on player 18 b consists of documents labeled “Confidential”. In such a case, processor 44 may receive a message with information pointing to a lower classification] for player 18 a and a higher classification for player 18 b . Schedule generation engine 48 is then configured to increase future epoch durations of epochs of schedule 16 a (low-rate proactivization) and decrease epoch durations of epochs of schedule 16 b (high-rate proactiviztion). Further, schedule generation engine 48 is configured to adjust future epoch durations in response to new classification information.

In other arrangements, schedule generation engine 48 is configured to store information concerning pre-planned events from which schedule generation engine 48 is configured to adjust future epoch durations of epochs of schedules 16 . For example, suppose that player 18 b is associated with the office of the chief financial officer of an organization. Schedule generation engine 48 is then configured to adjust epoch durations of epochs of schedule 16 b downward for the final two weeks of a quarter due to an increased risk of attempts by an adversary to gain access to sensitive financial information stored on player 18 b.

In still other arrangements, however, processor 44 is configured to receive one-time event data from event notification 26 . For example, suppose that user 20 b is about to be laid off from the organization. Processor 44 receives notification 26 of such a one-time event and, in response, schedule generation engine 48 is configured to adjust future epoch durations of epochs of schedule 16 b downward in response, as player 18 b is at a high risk of being compromised by user 20 b . One-time event data may also include threat assessments.

In some arrangements, distributed system 14 has an upper bound on the number of proactivization operations per unit time interval that it can process. In cases where VES 12 sends more signals 24 per unit time interval than this upper bound, processor 44 is then configured to send at least some of signals 24 to a scheduler (which may be included in external client 32 ). Such a scheduler is configured to send signals 24 at an appropriate rate.

Such a scheduler may provide an advantage when players 18 are divided into a slow group and a fast group of updaters. Such a division may be necessary when epoch schedules 16 cease to provide epochs of common indices for secret sharing (e.g., when one player is consistently judged to be a high risk). In this case, processor 44 sends signals 24 for the fast group to the scheduler while sending signals 24 for the slow group directly to the players in that group.

The above discussion concerned situations in which epoch durations varied between schedules 16 for different players 18 . As mentioned above, the improved technique also applies to scheduling epochs having durations that vary within a schedule. Such a situation is discussed in detail below with respect to FIG. 3 .

FIG. 3 illustrates an example situation in which VES 12 is configured to schedule epochs of an epoch schedule 16 having durations that vary according to output of random number generation engine 50 . In this example, random number generation engine 50 is configured to output either a zero or a one according to a uniform probability distribution (i.e., a 50% chance of getting a zero or a one). In other arrangements, random number generation engine 50 is configured to output either a zero or a one according to another distribution such as a Poisson distribution or an exponential distribution. Schedule generation engine 48 is then configured to set a duration of an epoch equal to the sum of this output in a time interval unit and a constant, say five time interval units. A resulting schedule 60 shows the random distribution of epochs having durations of five and six time interval units throughout schedule 60 .

Suppose that schedule 60 is generated in lockstep for players 18 a and 18 c to protect secret 28 (see FIG. 1 ). Suppose further that some secure computer system provides share updates every five timesteps to players 18 a and 18 c , where time is broken down into discrete units of one timestep. Consider an adversary 62 that can corrupt both players 18 within four timesteps of one another, and attacks only once at the beginning of a timestep, with no knowledge of the internal states of the clients except for the time. Because the epoch durations were generated according to a uniform distribution, adversary 62 can only guess as to when an epoch starts or ends. In this way, the probability of adversary 62 recovering the secret is 4/15, as opposed to unity in for the case of regular time intervals of five for the epoch durations. That is, the use of random number generation engine 50 has dramatically decreased the chances of adversary 62 recovering secret 28 even thought the epoch durations did not decrease.

FIG. 4 illustrates a method 70 of protecting a secret by sharing the secret among a set of players within a distributed system, including steps 72 , 74 , and 76 . In step 72 , a schedule that includes a set of times is generated, each time of the set of times defining an end of an epoch having a duration over which a key of a set of keys that corresponds to the time is valid, each key of the set of keys being associated with a resource of the set of resources, the set of times including a first time and a second time different from the first time. In step 74 , for a first key that corresponds to the first time, a request to update the first key is sent to the distributed system at the first time to produce an updated first key. In step 76 , for a second key that corresponds to the second time, a request to update the second key is sent to the distributed system at the second time to produce an updated second key.

While various embodiments of the invention have been particularly shown and described, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims.

For example, it should be understood that the improved technique applies to independent keys as well as the shared keys that were illustrated in the examples above.

Furthermore, it should be understood that some embodiments are directed to VES 12 , which is constructed and arranged to protect a set of resources in a distributed computer system. Some embodiments are directed to a process of protecting a set of resources in a distributed computer system. Also, some embodiments are directed to a computer program product which enables computer logic to protect a set of resources in a distributed computer system.

In some arrangements, VES 12 is implemented by a set of processors or other types of control/processing circuitry running software. In such arrangements, the software instructions can be delivered, within VES 12 , in the form of a computer program product 120 (see FIG. 2 ), each computer program product having a computer readable storage medium which stores the instructions in a non-volatile manner. Alternative examples of suitable computer readable storage media include tangible articles of manufacture and apparatus such as CD-ROM, flash memory, disk memory, tape memory, and the like.