In this paper, we extend previous results in the design and administration of information networks under partial orderings [1] by introducing a 'digital diode' which can be used as a basic component in the control of information flow. We summarize previous results, and introduce the digital diode as the only necessary component in a general purpose flow control network. We show that with this component, we can build any desired POset network and show its information flow properties. We show a design for a digital diode, show it's correctness, show that any desired reliability of transmission can be attained, and show that no covert channels are present. We then show variations of this scheme with well defined and easily limited covert channels that allow end to end confirmation. We show means by which audit trails may be generated, cryptographic security may be provided, and automated administrative assistance may be made available for the administrator of the plugboard. We summarize results, make conclusions, and propose further work.
Protection of information in modern information networks depends primarily on the ability to control the flow of information, and the partial ordering appears to be the most general mathematical structure required to accurately model information flow in a general purpose transitive information network [5].
We assume throughout this paper that general purpose computing systems are used, and thus that transitivity holds for information flow [2]. We assume that there is no real difference from the standpoint of information flow, between subjects and objects [5], and study the effects of information flow disregarding this distinction. We call the undistinguished subject/object an "information domain", abbreviated "domain". We view the effects of a human subject having access to multiple domains as a collusion between domains, and thus keep the mathematical analysis simple and yet general. The information flow relation "f" is specified in [5] as:
(S,{f}): for all a,b,c in S,
[(a f a) ;reflexive
and (a f b) and (b f c) => (a f c) ;transitive
and (a f b) and (b f a) => (a = b)] ;antisymetric
An example network and its corresponding flow control matrix are given in figure 1 [5].
a b c d e f g a f - f f - - - b - f - f f - - c - - f - - - - d - - - f - f - e - - - - f f f f - - - - - f - g - - - - - - f Figure 1 - A Flow Control Matrix and the Corresponding Network
The effective POset under transitivity is formed by applying transitivity to information flow, and is easily displayed in matrix form. This answers the question of reachability immediately. We call the effective POset under transitivity a "Flow Control POset" (FCP). Domains can always be labeled so as to produce an upper triangular FCP matrix.
The corruptive effects of domain collusion can be easily determined by ORing rows of any set of colluding domains in the FCP to find their effective joint flow. Similarly, the information accessible to a set of colluding domains can be derived by ORing the respective columns of the FCP matrix [5]. An algorithm for determining the time transitivity of information flow exists [5], and techniques for hierarchical and distributed administration of these networks have been shown [1].
Trusted and untrusted computing bases may be connected to form a provably correct trusted information network which enforces POset properties [1]. A 'trusted computing base' (TCB) is a computing base in which we can trust the system to prevent information flow between domains, while an 'untrusted computing base' (UCB) we cannot trust the system to prevent flow between domains. Two communications environments are of interest; those with trusted paths, and those with untrusted paths [3]. Simple design rules guide the connectivity of systems, and these rules extend transitively to networks [1,3,5].
In a UCB, we cannot trust the system to prevent flow between domains, and therefore, from the standpoint of systems which flow information to or from a UCB, the UCB must be treated as a single domain. In an environment with trusted communications paths, two UCBs can communicate iff they are the same domain. If we have a means for unidirectional communication, we can further permit UCBa to communicate to UCBb iff (a f b). In such an environment, we can form a POset TCB by using the physical properties of unidirectional connectivity to protect information from illicit flow, and the physical structure of the network to form the POset [1]. Figure 2 shows these conclusions pictorially.
UCB UCB UCB ----------------- ----- \ / ----- | --- \ / --- | | A |<-X->| B | | |A| X |B| | ----- / \ ----- | --- / \ --- | ----------------- UCB UCB UCB (AfB) UCB ----- ----- ----- ----- | A |<--->| A | | A |---->| B | ----- ----- ----- ----- Figure 2 - Flow Rules Between UCBs
In the case of TCBs communicating in a trusted communications environment, we may permit any domain (A) in TCB1 to communicate to any domain (B) in TCB2 iff (A f B) [1]. Again, this requires unidirectional communication. If bidirectional communications are used, we may only allow connections of the form (A f B) if A=B. UCBs can be used for passing information, so long as:
for all domains A that flow to X, (A f Xd) AND for all domains C that X flows to, (Xd f C)
Given the mathematical flow relation and its desirable properties, a means for physically implementing this relation in a provably correct and uncircumventable manner is sufficient to provide provably correct and uncircumventable protection in a physical information network. Devices that provide unidirectional current flow in electrical systems are called diodes, and thus we will call devices that provide unidirectional information flow in information systems diodes. As we are predominantly concerned with digital information (or other information represented in digital form), we are interested in the digital form of a diode, and thus use the name 'digital diode', and abbreviate it 'DD' where convenient.
Analog diodes have several problems with analogies in digital diodes. In particular, analog diodes are imperfect in at least two important ways:
In order for a digital diode to provide provably correct and uncircumventable flow control in an information network, no information may be allowed to leak back through the DD, and in order to provide adequate assurance that a transmitted message is received in tact, output must be equivalent to input. These constraints correspond respectively to security and integrity constraints on information networks. We note that these constraints may be in opposition to each other [2], since common techniques for assuring information integrity involve end to end confirmation, and this presents a well known covert channel. [4]
The utility of a digital diode for building a provably secure information network is clear when we examine the flow control matrix (figure 1). In order to form a provably correct network with provably correct digital diodes, we form connections as given in the connection rule, rule C.
Rule C: For each pair of processors (r,c) in the flow relation, f in (row r, column c) <=> 1) a connection from an output of system r to the source of some DD 'x' and 2) a connection from the sinc of 'x' to an input of system c
If we assume that information only flows through inputs and outputs, it is clear that no information can flow unless f is in (r,c) because this is a necessary condition for connection. Information only flows between pairs with flow allowed by the flow control matrix because f in (r,c) it is both a necessary and sufficient condition for flow. It then follows from 1 and 2 that outputs only flow to DD sources and inputs only come from DD sincs. By assumption and rule C, we see that outputs and inputs in the flow relation are only linked through DDs. Since DDs only allow information flow from source to sinc (by assumption), information only flows as specified in the flow control matrix. Any flow control matrix can trivially be implemented in this way, and since all POsets can be mapped into flow control matrices [5], any POset network can be implemented using DDs as described in rule C.
The principal constraints of the digital diode are that it reliably transfer information from an incoming information 'source' to an outgoing information 'sinc', and that it provably prevent information flow from sinc to source. The incoming channel from the source may have noise, and standard information theoretic techniques [6] may be applied to reduce the probability of error to the desired degree. The outgoing channel to the sinc may have noise that may similarly be compensated for. We are then left with the problem of designing a reliable method for provably making one directional information transfers within the DD. Figure 4 shows an example DD in respect to incoming and outgoing information channels. Information flows from a Source to an Error Correcting Code (ECC) Unit, over a channel (C), to a corresponding ECC unit. It then flows into the DD, and out to another ECC unit, through a second channel (B), into a final ECC unit, and finally into the sinc. ECC units are thus paired so as to cover errors in channels C and B.
----- ----- ---- ----- -----
source-->|ECC|<-C->|ECC|--->|DD|--->|ECC|<-B->|ECC|--->sinc
----- ----- ---- ----- -----
Figure 4 - The Digital Diode in a System
Even in a system where bidirectional communications is permitted, the communication from a source to its error correcting unit is unidirectional, as is the communication from the receiving ECC unit to the sinc. If we wish to use error correcting code between the source (or sinc) and its respective ECC unit, we only introduce another ECC unit in the sequence from the initial source to the final sinc, and don't actually change the unidirectionality of the first and last information transfers. Regardless of the steps we take to eliminate this problem, it will always remain, and thus we will always have the possibility of error. Our task as designers is to make the likelihood of such an error sufficiently low for the application at hand, while keeping costs acceptable.
Reliable communication through arbitrarily noisy channels has been proven possible [6], as has the ability to devise an implementation of any finite state machine such that in the presence of any given number of errors, the machine continues to operate properly [7,8]. In this example, channels C and B are covered by error correction codes, and we assume that these codes are adequate to detect and/or correct errors to within the level appropriate to the task at hand. The channel into and out of the DD as well as the DD itself must also be protected to a degree sufficient for the task at hand. As we will see later, this presents some intriguing problems.
We begin our task by demonstrating a finite state machine (FSM) which we can prove provides one directional information flow. This is of course trivial, since we merely need a gate which passes out what is passed into it. We cannot use a wire since a wire does not prevent output from passing back to input, so we are left with a 'pass gate', or 'buffer' as it is sometimes called. In figure 5, we show a design for such a gate consisting of a pair of inverters.
|\ |\ in---| >O---| >O---out |/ |/ Figure 5 - A Simple Digital Diode
We may make a redundant version of such a gate if additional reliability is desired [7,8], and may use as much redundancy in hardware and information as is required to provide adequate probabilities of correct reception. We may also choose to provide built in self test features to assure that failures in the DD have a sufficiently small probability of going undetected as to meet the requirements of the system at hand.
There is one major problem with such a system. Since information only flows in one direction, it is impossible for the sender to be sure that a message was properly received. In effect, this is true of all systems in that a sufficiently improbable combination of errors could cause a set of errors to be aliased as no error at all. In the case of the DD however, even relatively easy to detect errors cannot be detected without allowing information to pass from sinc to source.
To make this clearer, we take the example of an ideal DD connected to an ideal sinc. If there is an error in the connection, the source cannot detect it without being able to get information from the sinc. If the sinc can provide this information to the source, the information can be forged so as to provide a covert channel from sinc to source. The best we can do with a perfect DD in the ideal situation is to provide sufficient redundancy to allow the sinc to detect and correct errors and reduce the probability of undetected errors to an acceptable level. Because of the extreme simplicity of the DD design shown above, the complexity of test circuits, and the inherent impossibility of covering faults in connections without feedback from sinc to source, it appears that it is always more cost effective to add redundant DDs than it is to build self test circuits for those already provided.
The design as it stands is a memoryless system which is incapable of even holding data in the case of a recipient failure (such as a system crash). We may augment this system with a memory unit that allows some amount of information to be stored such that failures of less than any given duration for a given channel bandwidth can be sustained without error. We simply include a memory with the DD so that data passes through the memory before being sent to the sinc. Thus we have a system which looks like that shown in figure 6.
----- ----- ---- --- ----- -----
source-->|ECC|<-C->|ECC|--->|DD|--->|M|--->|ECC|<-B->|ECC|--->sinc
----- ----- ---- --- ----- -----
Figure 6 - The Digital Diode with Memory in a System
The system must have an adequate degree of redundancy to allow errors in the memory to be compensated for just as other errors are compensated for. We may also provide built in self test for the memory to test is outputs.
We have now added another problem in that the signals passing through the DD must now be timed so as to allow the memory to adequately capture their content. This can be handled by either limiting the bandwidth of the channel and using a sequence of memory locations to store successive values at a rate at least twice that of the channel [9], or by using a synchronous system wherein the timing of the memory is synchronized to that of the incoming channel through common signaling techniques. Note that if the input timing is synchronized to the memory, we may introduce a covert channel, as this would require that information pass from sinc to source through the DD. An example design without such a problem is given in figure 7.
|\ |\ ------------- Data in---| >O---| >O---|Data(in) | |/ |/ | Data(out)|-- Data out source |FIFO QUEUE | sinc |\ |\ | Clock(out)|-- Clock out Clock in---| >O---| >O---|Clock(in) | |/ |/ ------------- Figure 7 - Digital Diodes with Memory Using Timing and Data Channels
The system in figure 7 uses one DD for a data channel and the other for a clock channel. Since flow from source to sinc is only through DDs, information can only flow in one direction, and thus the system meets the required flow constraints.
This then ends our discussion of the design of provably correct digital diodes with absolutely no covert channels. In the following discussion, we will consider the design of digital diodes wherein a known covert channel of provably limited bandwidth exists and is used to allow end to end confirmations, reports of communications failures, and other such information flows.
We begin by noting that the bandwidth of the DD has not yet been considered in our discussion. We may clearly allow the bandwidth to go as high as feasible under current technology. The other side of the bandwidth issue is the limitation of bandwidth. Consider that we may allow a limited bandwidth covert channel by simply using a limited bandwidth DD in the reverse direction. In the case of a DD system with memory, we may simply limit the memory clock speed to the desired channel width, and the resulting system will be limited appropriately. A one bit memory may be used for this purpose, and thus we may design a quite simple limited bandwidth DD.
There is at least one important use for a limited bandwidth covert channel from sinc to source. The covert channel may be used to allow end to end confirmation of the reception of a message or notification of the failure the receiving machine. The reason this may result in a covert channel is that the sinc may effectively transmit a bit by either; correctly confirming (or simply receiving) a message to indicate a 1; and incorrectly confirming (or refusing reception of) a message to indicate a 0. Shannon showed that this can be done with arbitrarily reliability, even in an arbitrarily noisy channel, at the expense of bandwidth [6]. We note that the measurement of covert channel bandwidth may be significantly complicated by the use of time or space as information. For example, a single bit at a specific second of the day, indicates one of 86,400 possible times, over 16 bits of information. Thus a signal that appears to be only a single bit, may indicate many more bits by its time or space properties.
There are several defenses that can be used to further limit the use of these covert channels. The use of an arbitrary delay on the transmission of information in the covert direction makes the use of timing to indicate information very difficult. Covert signals may also be scrambled so that the ordering of the returns is unknown, or limited to a small number of total bits before administrative intervention is required to reactivate the channel.
As an example, we may allow a sinc failure to be reported after a random delay of between 1 and 10 minutes, and not allow the channel to be reopened until an administrator intervenes. Thus, the most information that can be sent through the covert channel before administrative intervention is the time of the failure to within a span of 10 minutes. This is at most 1 bit per 10 minutes, assuming that the administrator is willing to continue to reset the channel without noticing the strange behavior. An example design of this sort is given in figure 8.
FIGURE MISSING Figure 8 - A Reliable Digital Diode With a 1 Bit Covert Channel
The design in figure 8 has several intersting features. The channel from source to sinc is redundant in that some number of simultaneous signals may be sent. Although coding could be used to allow the same degree of information reliability, most hardware failures (all but N simultaneous equivalent failures) are covered by virtue of the redundant communication channels. Similarly, the covert channel is covered against all but a given number of simultaneous equivalent hardware failures.
Built in self test (BIST) was considered for this design, but it is quite straight forward to see that any amount of built in self test does not cover failures in the outgoing wires, and since these failures cover all internal failures, there is no added coverage attained by adding this sort of test. In addition, the probability of failure increases with the number of components, and since the BIST structures are significantly more complex than the original circuit, adding BIST would increase the failure rate. Other redundant structures such as voting are unnecessary as the voting can be implemented in the sinc as a basis for the return of a failure signal.
The covert failure return path is similarly covered by redundant structure. Since the sinc must periodically return signals to prevent a failure return to the source, inaction is all that is required for error reporting. The chances of multiple simultaneous failures causing proper activity signals on all lines is certainly low, and the use of dual rail signaling makes this particularly unlikely to be accidentally generated by a set of either transient or permanent faults. The output resistor and capacitor (RC) pair act to limit the bandwidth of the covert channel, and a suitable set of values can be used to vary this delay. The design as shown requires operator intervention for resetting the covert link, but a simple RC delayed reset could be used to automate this function with a suitable built in delay.
Half of the lights used in the display (the ones marked G) are used to indicate that the link is operating properly, while the other half (the ones marked R) are used to indicate failure. Again, partial failures don't prevent the observer from detecting an erroneous state. With the use of automated resetting of the channel, outputs to the display may be replaced by outputs to counters or external devices that audit and/or limit the use of covert channels.
In general, in a system with finite resources, it is impossible to have both ideal security and ideal integrity. Beyond the obvious probability of undetected errors (e.g. multiple errors causing a transformation from one valid codeword to another valid codeword), as we noted for the example design above, it is impossible to even assure that a connection still exists if there is no means for sending information from sinc to source. Since perfect security requires no such message be sendable, and perfect integrity requires that any such error be detectable by the source, we cannot have both perfect security and perfect integrity.
Even in a TCB, it is impossible to eliminate covert channels if there are finite shared 'logical' resources between a sinc and source. We note that there may be ways of sharing physical resources so as to prevent all sharing of 'logical' resources, but that no such techniques have yet been published in the open literature as far as we know. An example of physical sharing without logical sharing is the case where domains only physically share a processor, each domain using a fixed portion of the processor time at fixed intervals. This is analogous in every way to the elimination of covert channels in networks [3], and is subject to the same constraints and techniques.
Another potential problem with an ideal DD network is that information cannot be requested (read) by the sinc, it can only be sent (written) by the source. In order to allow the sinc to get any desired information from the source, all information from the source must be sent to the sinc. If we wish to allow read access, we must provide a means by which a covert channel may be used to request information. We may limit the bandwidth of the channel and assure that the information sent over the channel appears to make sense, but this does not prevent its use as a covert channel. In the case of a TCB source, we may limit the effective bandwidth of the covert channel even further by making the detection of access patterns very difficult, but again, as long as we have finite shared logical resources, some information will get through.
Several features besides provably correct information flow may be desirable in a trusted computer network. In particular, distributed and hierarchical administration, automated administrative assistance, cryptographic communication, auditing, accounting, and interfaces to a variety of physical devices may be desirable. Without going into great depth, we outline here, methods by which these goals may be achieved.
Distributed and hierarchical administration of DD networks is a straight forward application of recent results in POset networks [1], and will not be covered further here except to note that since any POset can be implemented with DDs, a distributed and/or hierarchical network can be so implemented. Similarly, automated administrative assistance can be provided using previous results [5], although this requires that administrative processors be associated with the DD switch(es) in the network.
Cryptographic communication can easily be accomplished by end to end encryption in which the DD simply passes information without being able to interpret the contents, and/or by link encryption in which the links from source to DD and from DD to sinc are encrypted without either knowing the keys required to decrypt the others' messages. Combinations of these techniques may of course be used as desired.
In the former case, cryptographic security and its responsibility are distributed throughout the network, and the number of encryption keys required goes as the number of communicating pairs, because each pair of communicating parties needs an independent key.
In the latter case, cryptographic security and its responsibility are centralized in the trusted communications switch which contains the DDs, and the number of encryption keys goes as the number of domains rather than the number of pairs of domains, because, each domain may use the same key with all of its sources and sincs. The use of distributed and hierarchical administration significantly reduces the risk associated with a particular communications switch without dramatically effecting the number of keys. In particular, a key for each (domain,switch) pair is sufficient, and thus the number of keys required is simply the number of pairs of (domain,switch) pairs. Additional assurance may also be afforded by the use of cryptographic keys in this way, since a wrong connection is unlikely to result in communication because the cryptographic keys are unlikely to match up.
Audit in a DD network can take two basic forms. We can attempt to audit the processors themselves, but because we may have numerous UCBs, it is unlikely that they will be able to provide adequate assurance in the auditing function. TCBs may of course audit their internal behavior if they are able to, and this provides one aspect of audit. The second form of audit is the audit of communications paths. Since all communications are supposed to be through DDs where the DDs correspond to places in the flow relation, it seems appropriate to verify the operation of the DDs and the connections to them. This may be done in an ongoing method by physical security and inventory control techniques as well as through the use of cryptographic methods mentioned above, depending on the cost benefit tradeoffs. DDs should regularly be selected from the normal operating environment and tested with an adequate test set to assure the desired degree of coverage. Covert channels through DDs can be well controlled and audited, as was described earlier in this paper.
Accounting in a DD network may be done both at the computing base level and at the network level. Since UCBs cannot be trusted to maintain accurate accounting records, we must rely on the DDs for this function except in TCBs which have appropriate facilities. Since DDs only cover the communications aspects of the network, we can only account for this aspect of behavior in our accounting. It is relatively simple to count the number of bits sent through a DD and the source and destination are fixed by the physical connections, so accounting seems straight forward.
Interfaces to a variety of physical devices may be desirable. Where this requires additional design, it does not significantly change the previously discussed aspects of DDs, and doesn't introduce any severe stumbling blocks that we can see at this point.
We have shown the value of a provably correct digital in the implementation of provably correct information networks, demonstrated the design of a digital diode, addressed the issues associated with its implementation in actual networks, and shown the basic principles of an implementation.
With a DD, we can design and implement provably correct and uncircumventable protection in an information network with provable information flow properties. This allows TCBS and UCBs to be connected so as to form a trusted computing network. Without such a component, we are left with the problem of proving properties about each component in the network and proving that these properties hold in all possible configurations of interoperating components.
We can only conclude that the digital diode is a practical and available security and integrity component which can be used to build provably correct trusted information networks by combining TCBs and UCBs, and that its use will soon become widespread. It also appears that the DD would be an ideal component for use as a building block in future TCBs, since they are information networks just as computer networks are.
[1] F. Cohen, "Design and Administration of Distributed and Hierarchical Information Networks Under Partial Orderings" Computers and Security, V6#1, 1987
[2] F. Cohen, "Computer Viruses", Dissertation at U. of Southern California, Jan. 1986
[3] F. Cohen, "A Secure Computer Network Design", Computers and Security, V5#3, 1985
[4] Lampson, "A Note on the Confinement Problem", CACM Oct. 1973
[5] F. Cohen, "Protection and Administration of Information Networks under Partial Orderings", Computers and Security, 1986.
[6] C. Shannon, "A Mathematical Theory of Communications", Bell Systems Technical Journal, V27 #3,4 July+Oct, 1948 pp. 379-423, 623-656
[7] E. Moore, C. Shannon, "Reliable Circuits Using Less Reliable Relays", J. Franklin Inst #262 pp 191-208, Sept 1956
[8] J. von Neumann, "Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components", Automata Studies, Princeton University, University Press, pp 43-98, 1956
[9] R. Ziemer, W. Tranter, "Principles of Communication", P71, Houton and Mifflin, 1976