 |
Description  |
|
|
CROSS-REFERENCE TO RELATED APPLICATION
The invention described in this application is related to the invention
described in our co-pending patent application Ser. No. 08/203,973 filed
concurrently herewith for "A Mechanism for Keeping a Key Secret from
Mobile Eavesdroppers" now U.S. Pat. No. 5,412,723 issued May 2, 1995. The
disclosure of that application is incorporated herein by reference.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to communication and computation
among several processors connected by a communication network. Examples of
such systems include distributed processing systems and client/server data
processing systems. More particularly, the invention is directed to a
method of assuring secure communication and distributed computation in a
distributed environment which contains insecure communication links and
processors.
2. Description of the Prior Art
The need for ensuring secure communication between processors communicating
over insecure channels is becoming increasingly acute. Solutions are
usually based on cryptographic methods that provide secrecy and
authentication of the information sent among a pair (or a set) of
processors if the processors, but only the processors, know some secret
cryptographic key. However, in many applications, processors may
occasionally fall under the control of a malicious adversary. The
adversary would be able to find the cryptographic keys stored in the
controlled processors and foil the security of the communication.
At any given instant in time, a large fraction of the processors may be
controlled by a malicious adversary. The identities of the processors
controlled by the adversary may change with time, as the adversary gains
control of more processors and is expelled from others. When a processor
is controlled by the adversary, the adversary learns the information held
by the invaded processor and may even maliciously alter the behavior of
this processor. The adversary may also have access to all, or a subset of,
the communication links. That is, the communication links may be tapped,
and even tampered with so that messages may be maliciously lost, modified
or generated. Such adversarial activity also may be maliciously
coordinated.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a mechanism
for securing the communication and computation between processors in an
insecure distributed environment.
It is another object of the invention to provide a method to maintain
secret values for a sequence of periods, each secret value being shared by
two or more processors for one or several periods, where the processors
are connected by a communication network.
According to a first aspect of the invention, there are provided efficient
"compilers" for a protocol between processors. The protocol is one that
assures some input-output relation when executed by processors which are
not all trusted but with secret and authenticated communication links
between every two processors. This protocol is transformed by a compiler
according to the invention into a protocol that guarantees essentially the
same input-output relations in the presence of (the same type of) insecure
processors and insecure communication links. Furthermore, these
constructions essentially retain the resiliency of the protocol (with
respect to the number of maliciously controlled processors).
In the description of the invention, the term "virus" is used to refer to a
maliciously controlled processor. In most of the description of the
invention, the identities of the processors controlled by the malicious
adversary changes over time, corresponding to the adversary gaining
control of new processors and losing control of others as a continuing
dynamic process. This model is similar to the behavior of computer viruses
and "worms".
There are several cases. The viruses may be "stationary", they may be
"mobile eavesdroppers", or they may be "mobile Byzantine". In the
stationary case, once a party becomes faulty (i.e., it is invaded by a
virus), it remains faulty throughout the computation. The total number of
faults does not exceed a certain limit, t. In the case of mobile
eavesdroppers, viruses can "move" between parties, as long as in each
communication round the number of faulty parties does not exceed a certain
limit, t. In this case, it is assumed that the faulty parties continue to
follow their protocols. However, once a party has been invaded, the entire
contents of its memory becomes known to the adversary controlling the
viruses. In the case of viruses which are mobile Byzantine, in addition to
the capabilities viruses had in the previous case, faulty parties may now
diverge from the protocol, and their memory may be changed.
For each of the cases outlined above, the invention provides a "secure
compiler". The input of the compiler, C, is a protocol .pi. that assures
some input-output relationship in the presence of some type of faults
within parties, assuming secure communication. The output, C(.pi.), of the
compiler is a protocol that assures essentially the same input-output
relationship in the presence of the same type of faults within parties and
insecure communication.
According to another aspect of the invention, there is provided a mechanism
whereby different cryptographic keys are established for each period of
communication. Essentially, the effect of exposures is contained to the
period in which they occur, or to a minimal number of following periods,
and the effect of exposures is contained to the processors exposed. More
precisely, at each period a processor is called nonfaulty if the adversary
does not control it. A processor is called secure at a given period if it
is non-faulty and also has a secret key, unknown to the adversary. In our
related patent application, U.S. Pat. No. 5,412,723, we show a method to
ensure that if processor i is secure at period p, processor i' is
non-faulty at period p+1, and the adversary does not intercept a message
sent from i to i' on the end of period, p, then i' would be secure at
period p+1. As described below, the present invention extends this result
to pairs of processors. The invention also may be extended to arbitrary
sized sets of processors.
A pair of processors is called "secure" at a given period if both
processors are nonfaulty, and the adversary does not have any information
on the key each of them keep to communicate with the other. This does not
require that the two processors would have the same key. It only requires
that the adversary would not know the key. A pair of processors (i,j) may
be secure while for some non-faulty k, the pair (i,k) is insecure. The
method of the present invention ensures that if i', j' are non-faulty at
period p+1, then they are also secure, if there is a pair of processors
i,j which is secure at period p (possibly i=j) where the adversary does
not intercept a message sent from i' to i and a message sent from j' to j
at the end of period p.
BRIEF DESCRIPTION OF THE DRAWINGS
The foregoing and other objects, aspects and advantages will be better
understood from the following detailed description of a preferred
embodiment of the invention with reference to the drawings, in which:
FIG. 1 is a block diagram showing a distributed dam processing system of
the type on which the invention may be implemented;
FIG. 2 is a functional block diagram showing the flow of the process
according to a first embodiment of a first aspect of the invention;
FIG. 3 is a functional block diagram showing the flow of the process
according to a second embodiment of a first aspect of the invention;
FIG. 4 is a flow chart showing the logic of an O(n.sup.4) messages
construction for key synchronization according to a first embodiment of a
second aspect of the invention;
FIG. 5 is a flow chart showing the logic of an O(n.sup.3) messages
construction for key synchronization according to a second embodiment of a
second aspect of the invention; and
FIG. 6 is a block diagram illustrating how the two embodiments of the
second aspect of the invention illustrated in FIGS. 4 and 5 may be
combined.
DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT OF THE INVENTION
Referring now to the drawings, and more particularly to FIG. 1, there is
shown a typical distributed data processing system, sometimes referred to
as a client/server network, comprising a plurality of servers and clients
connected via a communication network. A client/server system is a
distributed system comprising a plurality of processors 10.sub.1 to
10.sub.n interconnected by a communication network 11. The communication
network 11 may be, for example, a local area network (LAN), a wide area
network (WAN) or other similar network. The processors may be configured
as clients or servers or both and are provided with respective storage
devices 12.sub.1 to 12.sub.n, some or all of which may be accessible all
or less than all the processors. This type of architecture makes use of
the "distributed intelligence" of the servers and clients (i.e.,
workstations) as intelligent, programmable devices, thus exploiting the
full computing power of each. The advantage of the client/server
architecture is that the clients and servers work together to accomplish
the processing of the application, thereby increasing the processing
power. Such a distributed data processing system may be connected as a
local area network (LAN) or wide area network (WAN), and the servers may
be microcomputers, minicomputers or mainframes or a combination. Thus, it
will be appreciated that the system shown in FIG. 1 is generic in its
illustration, and in a specific installation may be considerably more
complex. The present invention applies to server and clients alike, and
for purposes of this disclosure we will refer to servers, or sometimes
more generally to processors or parties.
A secure "compiler" may be defined as follows. Consider a synchronous
network of n parties. Recall that the input of our compiler, C, is a
protocol, .pi., that assures some input-output relationship in the
presence of some type of faults within parties, assuming secure
communication. The output, C(.pi.), of our compiler, is a protocol that
assures "essentially" the same input-output relationship in the presence
of the same type of faults within parties, and insecure communication.
Clearly, an adversary may "disconnect" (some of) the links, thereby
preventing communication over them. It is possible to deal with this by
sending over other links, if the amount of links disconnected is limited.
We will simply assume that the original protocol, .pi., is capable of
dealing with link failures, i.e., this is a protocol for secure but
unreliable communication.
In a more subtle attack, a strong adversary may be able to "exchange" a
processor by a "malicious ghost", such that the other processors are not
aware that they are communicating with the adversary controlled "ghost"
rather than with the correct processor. This situation is unavoidable;
however, the "exchanged" processor may detect this. Implicitly, we assume
that if a processor detects that it has been "exchanged by a ghost", then
that processor will initiate an alarm and the results of the computation
are irrelevant. The goal is that the adversary will not gain any advantage
(except the ability to abort the execution). We therefore emulate the
situation where an adversary may, in addition to controlling some of the
processors, also press an "abort button" which would make the computation
invalid. Therefore, with respect to this strong adversary, we require that
the output C(.pi.), of our compiler, would have the same input-output
distributions relationship as that of the original protocol .pi. when run
with some adversary which has the same control of processors but no
control over links, but also with the ability to "abort" the protocol
whereby all outputs are set to some special value .perp..
These requirements imply that if the original protocol, .pi., is secure
(namely, the faulty parties gather no information from the computation,
other than their inputs and specified outputs) then the compiled protocol
C(.pi.) is secure as well. Note that we do not require that all parties
output .perp. unanimously (say, in case of link-failure). As will be seen
in the sequel, such a unanimity requirement is impossible to implement, in
some scenarios. Moreover, it not necessary since, once a processor has
output .perp., it may alert an operator who will notify other parties in
some ways external to the network. This scenario is related to the message
authentication problem, where entities authenticate each other using
insecure communication links. See, for example, Ray Bird, Inder Gopal,
Amir Herzberg, Phil Janson, Shay Kutten, Refik Molva, and Moti Yung,
"Systematic design of a family of attack-resistant authentication
protocols", IEEE Journal on Selected Areas in Communications, vol. 11, no.
5, pp. 679-693, June 1993, Special issue on Secure Communications, and
Mihir Bellare and Phil Rogaway, "Models of entity authentication",
Advances in Cryptology: Proc. of Crypto 93, August 1993. However, there
are two major differences. In the case of the present invention, the
adversary cannot interact separately and repeatedly with each party, in
order to enhance its capabilities. This is so, since the network is
synchronous; whenever some party identifies some unexpected situation, it
outputs .perp. and halts. In addition, the solutions provided by the
invention concentrate on allowing the adversary to control some of the
processors for some of the time, whereas the cited publications assume
that all of the processors are completely secure and trusted.
In our implementation, we distinguish three cases, described below. In all
three cases we assume that the network is initialized so that each two
parties share a secret, random session key.
Stationary faults. The faults are "stationary". That is, once a processor
becomes malicious (i.e., it is "invaded" by a virus), it remains faulty
throughout the computation. We do not distinguish between the cases where
the identities of the malicious processors are chosen before the
computation starts, or during the computation itself. The solution for
this case is simple. First, encrypt each message using part of the key
common with the recipient party. Next, apply some message authentication
protocol to the encrypted message, using another part of the common key.
Note that the adversary may still remove messages; however, we assume this
is dealt with by the original protocol .pi.. It can be easily seen that if
the original protocol is t-resilient (i.e., the input-output relations are
assured as long as at most t parties become faulty), then the compiled
protocol is also t-resilient.
When limited randomness is available from physical or other sources, it
could be used to enhance the randomness of the invention by using
additional random inputs to the computation of intermediate values or of
new secrets/round keys.
Mobile eavesdroppers. The faults (viruses) can "move" between parties, as
long as in each communication round the number of faulty parties does not
exceed a certain limit, t. In this case, we assume that faulty parties
continue to follow their protocols. However, once a party has been
invaded, the entire contents of its memory becomes known to the adversary
controlling the viruses. Clearly, the protocol for the stationary case
would fail here. Once a party has been faulty, all its private information
is known to the adversary, even when the fault "moves on". In this way,
within few rounds, the adversary will know all the private information of
all the parties. Moreover, in a first look a solution seems impossible.
Once the adversary got hold of a party, and controls all the links
outgoing from this party, it can "simulate" this party (from the point of
view of the rest of the network) and continue doing so even when the fault
has "moved on". We overcome this difficulty by making sure that in this
case, the disconnected party itself will output .perp..
A first embodiment of the invention proceeds as follows. Messages are still
authenticated and encrypted using the secret session keys. However, we use
a public key cryptosystem in order to choose new session keys in each
round. FIG. 2 illustrates the scheme according to a first embodiment of
the invention in order to recover from a fault once it has "moved on".
FIG. 2 assumes that there are three processors, P.sub.1, P.sub.2 and
P.sub.3, in the distributed data processing system, and what is
specifically illustrated is the operations performed at processor P.sub.2,
the operations at processors P.sub.1 and P.sub.3 being the same.
Step 1. In each round each processor P.sub.i selects a new pair of public
and private keys, and broadcasts the public key, signed by the old private
key. This is done by using a random number generator 201 and a
public/private key generator 202. The new private key, NPRN2, for
processor P.sub.2 is stored in register section 203, and the new public
key, NPUB.sub.2, is stored in register section 204. The new public key,
NPUB.sub.2, is then is signed in operation block 205 by the old private
key held in register 206 and broadcast to processors P.sub.1 and P.sub.3.
The new public keys, NPUB.sub.1 and NPUB.sub.3, broadcast by processors
P.sub.1 and P.sub.3 are received by receive function block 207 and
temporarily held in respective register sections of that block.
Step 2. Optionally, each processor P.sub.j "echoes" the public key received
from each of the other processors P.sub.i, signed using the (old) session
key of P.sub.i and P.sub.j, back to the sending processor, P.sub.i.
Step 3. P.sub.j broadcasts the vector v.sub.j of all public keys received
in this round, signed using the (old) private key of P.sub.j. More
specifically, the old public keys are stored in register 208 which is
accessed by operation block 209 to verify the signatures of the received
new public keys from processors P.sub.1 and P.sub.3. The verified new
public keys NPUB.sub.1 and NPUB.sub.3 are temporarily held in respective
registers 210 and 211 from which the new public keys are read and,
together with the public key, NPUB.sub.2, held in register section 204,
form vector v.sub.2 in operation block 212. The vector v.sub.2 is signed
in operation block 213 using the old private key in register 206 and then
broadcast to processors P.sub.1 and P.sub.3. The vectors v.sub.1 and
v.sub.3 broadcast by processors P.sub.1 and P.sub.3, respectively, are
received in receive function block 214 and temporarily held in respective
register sections of that block.
Step 4. Operation block 221 of each processor checks all signatures of the
received vectors held in receive function block 214 using the old public
keys held in function block 208. The verified vectors v.sub.1 and v.sub.3
plus vector v.sub.2 from block 212 are stored in register 215. All the
claimed values of the public keys of each other party are compared in
majority compare logic 216. If there is any disagreement between new
public keys claimed for any processor, or any invalid signature, an
appropriate warning is issued in alert function block 217. If more than t
parties disagree on a value (or their signatures were invalid), then
.perp. is output and the execution halted. Otherwise, for each other party
the majority value for its public key is adopted and stored in block 208
for the next round.
Step 5. Erase old private keys by reading the new private key in register
203 and overwriting the value stored in block 206.
Steps 3 to 4 are necessary. Without them, the adversary could "get in
between" a link between two parties, P,Q, that were both faulty at the
previous round and are nonfaulty in the current round. Namely, the
adversary could act as P in the eyes of Q without being caught.
Furthermore, at the same time the adversary can act as Q in the eyes of P.
It can be seen that our construction retains the resiliency of the
original protocol. Here the resiliency is measured as the maximum allowed
number of faulty parties in each round.
A second embodiment of the invention is shown in FIG. 3, which is similar
to FIG. 2 and wherein like reference numerals represent the same
operations. In this embodiment, session keys are used by inserting the
following step between steps 4 and 5:
Step 6. Each pair of processors use the new public keys to agree on a fresh
session key. More specifically, a session key generator 218 receives the
output of random number generator 201 and generates a session key which is
exchanged with the other processor of the pair. The new session keys, one
generated by session key generator 218 and the other generated by a
corresponding session key generator in the other processor are temporarily
held in register 219. The old session keys held in block 220 are used in
step 2 instead of the old private key in block 206. As with the private
key, the old session keys are overwritten in block 220 after the
verification.
In another embodiment, in step 1 the public key would be sent to each party
authenticated by the shared session key. In yet another embodiment, the
signature in steps 1 and 2 would be omitted unless a warning was issued
before, and whenever a warning is issued, the procedure is restarted.
Mobile Byzantine viruses. Let us first note that if no further assumptions
are made on the security of the network, then no solution to our problem
exists in this model. As in the eavesdropping case, once the adversary
knows all the secret information of some party, it can "disconnect" this
party from the rest of the network and "simulate" this party on all its
outgoing links, even after this party is no longer faulty. However, if the
viruses are only eavesdropping, then the adversary is unable to "simulate"
the rest of the network in the eyes of the disconnected party. Thus, this
party will notice that something went wrong, and will output .perp.. If
the viruses are allowed to modify the contents of the memories of faulty
parties, then the adversary will be able to "disconnect" a faulty party,
and "convince" this party that it is communicating with the real network,
even after this party is no longer faulty!
There are two ways to overcome this difficulty. First, one may assume a
"core", well protected memory which is untouchable by the virus. This
memory is required to support both read and write operations. This brings
us back to the solution of the mobile eavesdropping viruses.
A second possible assumption is that not all the links in the networks are
insecure; i.e., the adversary does not have enough resources to tamper
with all the links.
According to another aspect of the invention, them is provided a solution
to the mobile faults scenario where an attacker gains, from time to time
temporary control of the processor, so that eventually all processors may
be broken into (but not at once). This scenario has been studied by Rafail
Ostrovsky and Moti Yung in "How to withstand mobile virus attacks", Proc.
of the 10th Annual A CM Symposium on Principles of Distributed Computing,
Montreal, Quebec, Canada, 1991, pp. 51-59. Ostrovsky and Yung showed how
to securely compute any function and how to securely maintain a
distributed database. However, their scheme assumes that the links are
secure and does not provide mechanisms to ensure link security (i.e.,
cryptographic link keys).
The present invention extends our invention disclosed in U.S. Pat. No.
5,412,723 which deals with a key unique to each processor, and not with
keys shared between processors. The results of that invention may be used
to provide, at each period and at each nonfaulty processor, a secret key
which is known only to this processor and to the "user" which knows all
original keys. This requires complete trust of the "user", while the
present invention, which treats all parties equally (and none is
completely trusted), places heavy communication and computation
requirements on all parties.
The two solutions deal with the two major scenarios of key distribution and
authentication systems such as Kerberos (implemented in DCE) and NetSP.
The present invention can be used to secure communication between
processors in the network, and our invention disclosed in U.S. Pat. No.
5,412,723 can be used to authenticate the user using his password or
smartcard (from which we generate all original keys).
In the first aspect of the present invention, we dealt with a problem very
similar to the one of the second aspect. In the first aspect, we allowed
the adversary to intercept all messages; however, we assumed that the
adversary cannot modify the memory of processors, and the solution relied
both on the use of public-key cryptography and on the existence of a
trusted source of unpredictable randomness in each processor. Therefore,
the first and second aspects of the present invention have complementing
properties, as the second aspect of the invention allows arbitrary changes
to the storage of adversary-controlled processors and does not use either
public key or trusted source of randomness. In fact, as a part of the
invention we show how to combine both methods.
This aspect of the invention supplies pairs of processors with a shared
secret key. It may appear that an alternative to withstand
adversary-controlled processors would be to use public key techniques,
such as RSA (for Revist, Shamir and Arielman). In fact, public key
techniques does not give any protection against the kind of threat we
consider where the adversary controls at each period a different set of
processors (mobile faults). Even using public key techniques, once a
processor is controlled, any secret (private) information stored in it
becomes known to the adversary, and in particular any cryptographic keys.
When an adversary controls a processor, we allow it to read and modify all
of the storage of that processor. However, when the processor becomes
non-faulty, we assume that it runs the correct software. This assumption
seems reasonable as it may be supported by several practical means, such
as periodical re-booting followed by comparison against archival copies or
by hardware read-only to the system software (e.g., system software on ROM
with dedicated address space). This may be contrasted with several earlier
works which dealt with providing security in an untrusted processor
environment, based on a small tamper-resistant hardware module which is
assumed perfectly secure.
The invention provides secure pseudo-random numbers (keys) shared by pairs
of processors in a way which provides security against attackers which may
control all processors and communication links (but not all of them at
once). Furthermore, the schemes implemented by the invention are simple,
efficient and provably secure.
We present schemes for maintaining secret keys shared between pairs of
processors in the presence of a mobile, transient adversary that
occasionally breaks into servers in order to gather information on the
keys. When the adversary breaks into (or controls) a server, it is able to
read and modify all of the storage. However, when the processor recovers
(becomes nonfaulty), we assume it executes the original, non-corrupted
program.
The idea underlying the schemes according to the invention is to use a
different key at each time period (where the length of the period is a
parameter, defined according to security requirements). An "ideal"
refreshment scheme proceeds as follows. Initially, each pair of processors
has a common private key known only to them. Every period (say, every
week), a new key is chosen completely at random for each pair of
processors, and miraculously handed to both processors. Such an ideal
scheme is clearly "the most we can hope for". The adversary has no
knowledge of the key common to a pair of processors which are nonfaulty at
the current period. Using the terminology suggested before, the ideal
scheme ensures that every pair of nonfaulty processors is also secure.
The schemes according to the invention achieve almost the same situation,
as long as the adversary is limited to reasonable computational and
eavesdropping abilities. For the purposes of the present disclosure, we
use the following simple model; however, it is easy to modify the methods
to operate under most practical communication models and systems, with
minor changes to the method or to its properties.
The system contains n processors, and each pair of processors may
communicate directly; e.g., using a dedicated communication link. We
consider a synchronous system in which all processors have access to a
completely synchronized and accurate clock. Execution is divided to
overlapping periods of fixed length T.sub.p +T.sub.c >1, where T.sub.p is
the time gap between periods and T.sub.c is the overlap. Namely, the ith
period is [iT.sub.p,(i+1)T.sub.p +T.sub.c ]. Message transmission delay is
always at most one time unit. However, the adversary may interfere with
message transmission, by reading messages, modifying them, changing their
delay or removing them, or by transmitting forged messages. If the
adversary interfered in any way with the communication from processor v to
processor u at period i, we say that link (u,v) was faulty at period n.
Otherwise, we say that (v,u) was nonfaulty.
The adversary may also interfere with the processing. Normally, each
processor executes the protocol to be described below. However, the
adversary may gain control of any processor and operate it differently,
having complete access to the storage of the processor and the ability to
send and receive messages. If the adversary gains control of processor v
at period i, we say that v is faulty at period i; otherwise, v is
nonfaulty at i. At the end of the overlap between period i and the
previous period i-1, i.e., at iT.sub.p +T.sub.c, each processor v computes
a set of keys {K.sub.v,u (i)}. Intuitively, K.sub.v,u (i) is the key to be
used to secure communication between v and u during period i. Clearly,
this is an over-simplified model for any realistic system. However, it is
easy to understand and analyze the method while considering this model.
In the ideal execution, the keys K.sub.v,u (i) and K.sub.u,v (i) are
identical, and they are completely unknown to the attacker. In the methods
according to the second aspect of our invention, there is a tradeoff
between these two goals: .cndot. Key synchronization: produce identical
keys at each pair, i.e., K.sub.v,u (i)=K.sub.u,v (i), and .cndot. Key
secrecy: keep the keys K.sub.v,u (i) and K.sub.u,v (i) secret from an
attacker. The methods disclosed put a stronger emphasis on keeping the
keys secret. In particular, the first two methods disclosed ensure that
K.sub.u,v (i) is unknown to the attacker whenever v and u are nonfaulty at
period i, some v',u' are nonfaulty at period i-1, and the links (v',v) and
(u',u) are nonfaulty at the overlap of periods i-1 and i. However, an
attacker so inclined may cause the keys to differ. We later show some
techniques which protect the key synchronization (i.e., u and v would
compute the same key); however, these results would provide weaker
protection of secrecy (i.e., require more nonfaulty links and processors).
Our constructions use pseudorandom functions. We briefly sketch the
definition of a pseudorandom function family. For a fuller definition see
Mihir Bellare and Phil Rogaway, supra. Let s be a security parameter. For
every value of s, let
##EQU1##
be a family of functions. Intuitively, we say that the collection
F={F.sub.s } is pseudorandom if no polynomial time bounded adversary can
distinguish between a function chosen at random from F.sub.s and a random
function (from {0,1}.sup.y(s) to {0,1}.sup.z(s)) for every large enough s.
We note that pseudorandom collections exist, given that one-way functions
exist. In fact, we need only a simple case where the domain and the range
are both {0,1}.sup.k where k is some security parameter. For k=64, the DES
cryptosystem, with the key serving as the input, is believed to be a good
candidate. Many other candidates are known, and there are standard
efficient extensions for larger values of k.
We describe our constructions for secure link key refreshment. We begin
with a simple construction and then show a variant with reduced
communication requirements. Next, we show a simple extension to both
constructions which ensures secrecy of link keys even if other link keys
are exposed (by a poorly designed link protocol). Finally, we discuss
variations which gain some protection of key synchronization (K.sub.v,u
=K.sub.u,v) but require stronger assumptions to ensure key secrecy. All
constructions assume that initially each processor pair of processors u,v
is initiated with randomly chosen, secret values (keys) K.sub.v,u
(O)=K.sub.u,v (O).
We also assume that each processor v has a random value (key) K.sub.v (p)
at any period p. This random value could be generated by a source of
physical randomess or by a pseudo-random number generator secure against
an attacker which dynamically gains and loses control of all processors
(not at once). Such a pseudo-random number generator could be implemented
using a tamper-proof hardware module or using the technique we describe in
our U.S. Pat. No. 5,412,723.
An O(n.sup.4) messages construction. In this construction, at the beginning
of period i, each processor v sends to each processor v' a table of
n.sup.2 values denoted X.sub.v,v' (u,u')[i], for u,u'=1, . . .,n. We now
describe how v computes each pair of values X.sub.v,v' (u,u')[i],
X.sub.v,u' (u,v')[i]. We assume without loss of generalization that u'<v'.
First, v computes a pseudo-random offset R as a function of v, v', u, and
u'. On possible embodiment is:
R.sub.v,v' (u,u')=f.sub.Kv,u(i-1) (u,v',u')
Next, v sets X.sub.v,v' (u,u')[i] as a function of v, v', u, u', and i,
such as:
##EQU2##
where .sym. represents the combination operation, and we deal with the
special case v=u by setting K.sub.v,v (i)=K.sub.v (i).
The new key K.sub.v',u' (i) is computed by v' as the exclusive OR of all
the X.sub.v,v' (u,u') values received from different sources v and with
different u values, one recommended implementation being:
##EQU3##
The keys resulting from this computation are completely unknown to an
attacker, even if this attacker has complete control over all processors,
except u',v' during period i and some u,v during period i-1, provided that
K.sub.u,v (i-1) and K.sub.v,u (i-1) were also completely unknown to the
attacker, and that the links (v',v) and (u',u) were non-faulty during the
overlap between period i and period i-1. This property allows secure pairs
of processors to pass along the security to new pairs of nonfaulty
processors.
FIG. 4 shows the process for the case of three processors, the method
illustrated being for the steps performed at processor P.sub.1. The keys,
K.sub.1,1 (l-1), K.sub.1,2 (l-1) and K.sub.1,3 (l-1), for the last round,
l-1, stored in block 40 are used in function block 41 to compute
X.sub.1,v' (u,u')[l] for u,v',u'=1,2,3. The value X.sub.1,v' (u,u')[l] is
sent to v' in function blo | | |
