In 1978 the United States was considering adopting a national security protocol designed to enable the USSR to verify how many Minuteman missiles the United States had emplaced in a field of 1000 silos without revealing which silos actually contained missiles. For this protocol to have been acceptable to the USSR, the messages would have had to be digitally signed with signatures which the USSR could verify were authentic, but which the United States could not forge. Subliminal channels were the discovery that these digital signatures could host undetectable covert channels. In general, any time redundant information is introduced into a communication to provide an overt function such as digital signatures, error detection and/or correction, authentication, etc. it may be possible to subvert the purported function to create a covert (subliminal) communications channel. This paper recounts the development of subliminal channels from their origins when only a couple of bits could be communicated covertly to today when potentially a couple of hundred bits can be concealed in signatures generated using the most popular digital signature schemes.

In conjunction with a six-month research program on computer security, cryptology and coding theory hosted by the Isaac Newton Institute of Mathematical Sciences, University of Cambridge, Cambridge, U.K., a Workshop on information hiding was held from May 30 through June 1, 1996. This workshop was devoted to all aspects of information hiding - other than the usual cryptographic concealment of content, including steganography, subliminal channels, fingerprinting, covert channels, etc. Two surprising results pertaining to subliminal channels were presented or grew out of presentations made at this workshop. One is of interest to the secure communications protocol designer concerned with denying the use of subliminal channels, while the other is important to the designer, or user, of subliminal channels. The first raises the question of whether the notion of a "subliminal-free" communication channel is an oxymoron, i.e., is it possible to force the bandwidth of the subliminal channel to be truly zero? The second forces a more precise formulation of a conjecture the author had made that the bandwidth of a subliminal channel is logarithmically limited if the transmitter is unwilling to trust the subliminal receiver unconditionally. Motivated by these results, this paper reexamines the fundamental questions of the bandwidth available for subliminal communication as a function of the trust the transmitter has in the subliminal receiver and of a logically sound interpretation of the term "subliminal-free".

Paradoxically, one of the most important – and at the same time, probably one of the least understood – functions performed by information integrity protocols is to transfer trust from where it exists to where it is needed. Initially in any protocol, there are at least two types of trust: trust tha t designated participants, or groups of participants, will faithfully execute their assigned function in the protocol and trust in the integrity of the transfer mechanism(s) integral to the protocol. Consequently, almost all protocols enforce a set of restrictions as to who may exercise them – either spelled out explicitly or left implicit in the protocol specification. In addition there may be unanticipated or even unacceptable groupings of participants who can also exercise the protocol as a result of actions taken by some of the participants reflecting trusts that exist among them. Formal methods are developed to analyze trust as a fundamental dimension in protocol analysis and proof.

Escrowed Key Cryptosystems hold the promise of faithfully realizing legal guarantees of privacy for users under normal circumstances while at the same time insuring that privacy can be breached by authorities in special circumstances under appropriate legal safeguards. The most attractive feature of these schemes is that it is possible to ensure that the interests of each of the parties—the users, the law enforcement or national security agencies, the court or other monitoring entities and the escrow agents—can all be guaranteed up to the level of integrity of the protocol or cryptosystem. Unfortunately, the first scheme to attempt this, the Clipper protocol as adopted by the U.S., completely fails to do so for either the user(s) or for the monitoring entities. In this paper a new escrowed key protocol and new devices are described that verifiable protect the interests of all parties by positively implementing legal guarantees of privacy and access.

In this lecture examples will be given of key distribution protocols that distribute keys to unintended recipients, secrecy protocols that publicly reveal the contents of (supposedly) secret communications, digital signature protocols that make forgery easy — all based on cryptoalgorithms that are sound so far as is known. In at least one case the cryptographic algorithm that is employed is Vernam encryption/decryption with a properly chosen one time key which is well known to be unconditionally secure; in spite of which the protocol fails totally.

One of the most important functions performed by security protocols is to transfer trust from where it exists to where it is needed. As a result , all protocols enforce a set of restrictions as to who may exercise them-either spelled out explicitly or left implicit in the protocol specification. In addition, there may be unanticipated-even unacceptable-groupings of participants who can also exercise the protocol as a result of trusts existing among some of them. Formal methods are developed to analyze trust as a fundamental dimension in security protocol analysis and proof.>

An identity verification scheme that uses a public authentication channel to validate a private authentication channel belonging to the individual who wishes to prove his identity is described. The user can prove his identity by demonstrating that he can authenticate (suitably chosen) messages in the private channel. It also provides certified receipts for transactions whose legitimacy can later be verified by impartial arbiters who do not need to be designated in advance or be involved in the transaction at the time it takes place.>

The general principles that underlie all authentication schemes are reviewed and illustrated using the examples of an early telegraphy cable code, a US military authentication protocol, and authentication of electronic funds transfers in the US Federal Reserve System. Authentication threats from inside the system (i.e. untrustworthy sender or receiver) are described. The classification of authentication schemes as computationally secure, provably secure, or unconditionally secure is explained, and theoretical results are presented showing that a large number of encoding rules must be available in any unconditionally secure authentication code. Current authentication practices are examined.>

The author presents a solution to the problem of how to make it possible for two mutually distrusting (and presumed deceitful) parties, the host and the monitor, to both trust a data acquisition system that informs the monitor and perhaps third parties, whether the host has or has not violated the terms of a treaty. He starts by assuming that such a data acquisition system exists, and that the opportunities for deception lie only in the manipulation, i.e. forgery, modification, retransmission, etc. The author shows that it is possible to satisfy simultaneously the interests of all parties. The technical device on which this resolution depends is the concatenation of two or more private authentication channels to create a system in which each participant need only trust that part of the whole that he or she contributed. In the resulting scheme, no part of the data need to be kept secret from any participant at any time; no party nor collusion of fewer than all of the parties can utter an undetectable forgery; no unilateral action on the part of any party can lessen the confidence of others as to the authenticity of the data, and third parties, i.e. arbiters, can be logically persuaded of the authenticity of data.>

Certain DES keys have been called weak or semiweak based upon the number of distinct round keys which they produce. For the weak keys, all 16 round keys are identical and encryption is the same as decryption. For the semiweak keys, there are only two distinct round keys but no specific weakness of the DES with these keys has been demonstrated.

At the 1982 Symposium on Security and Privacy, a software protection scheme [1] devised by George Purdy, James Studier and the present author was presented. Unfortunately, the cryptographic protocol in that scheme was fatally flawed making it possible for a "pirate" who observed the communica-tions between a software vendor and a legitimate licensee to forge a license that would permit him to also use the protected software. In the course of analyzing the reasons for this weakness in the protocol and of finding an improved one, the cryptographic protocol reported here was found that permits the originator of a cipher message to specify precisely the subset of receivers out of a much larger potential audience who will be able to decrypt the cipher but who will be unable to pass along this ability to any other receiver not designated by the originator of the message. We shall first describe the flaw in the original software protection scheme that prompted this work, and then systematically develop the selective broadcast protocol . Finally, almost as a footnote to the discussion of the secure broadcast protocol, we show how the original software protection problem has also been solved.

In a series of papers, the author has documented the evolution at the Sandia National Laboratories of a solution to the problem of how two mutually deceitful and distrusting parties -- the host and the monitor -- can both trust a data acquisition system whose function is to inform the monitor, and perhaps third parties, whether the host has or has not violated the terms of a treaty. The national interests of the various participants, host, monitor and third parties, at first appear to be mutually irreconcilable, however the conclusion of this paper will be that it is possible to simultaneously satisfy the interests of all parties. The technical device on which this fourth, and hopefully final, iteration of treaty verification systems is based is the concatenation of two or more two key cryptographic systems. In the resulting system no part of the rneasage need be kept secret from any participant at anytime; no party, nor collusion of fewer than all of the parties can utter an undetectable forgery; no unilateral action on the part of any party can lessen the confidence of the others as to the authenticity of the data and finally third parties can be logically persuaded of the authenticity of messages. Thus, finally after a decade of development a complete technical solution is in hand for the problem of the verification of treaty compliance.

We discuss a technological means of protecting software from unauthorized duplication and use, which does not at the same time limit its sale or distribution on rely on a trusted authority.

In symmetric cryptosystems that depend on a single (secret) key for both encryption and decryption, a cryptanalyst -- since the key is unknown to him -- must either work backward from the cipher or else from the cipher and some known pairs of plain-text messages and matching ciphers in attempting to recover the plaintext. In an asymmetric (two key) cryptosystem used in the public key, i.e., privacy channel, mode where the encryption key is publicly expcxsedso that anyone who wishes can encrypt messages that can mly be decrypted by the person having the (secret) decryption key, a cryptanalytic weakness may occur that has no counterpart in symmetric systems. If the entropy of the input messages is too small (roughly speaking if it is computationally feasible to search through the most likely messages) either because the total number of messages is small or because a small number of the messages occur with high probabilities, the cryptanalyst can pre-encrypt these messages to form a cipher file that can then be matched against observed ciphers to accomplish a simple substitution decryption. This forward search cryptanalytic weakness of a public key privacy channel is purely a function of the entropy of the plaintext messages and does not depend on the existence of any cryptanalytic weakness in the concealment of the secret decryption key from a knowledge of the public encryption key in the underlying public key algorithm.

The familiar failing of digital signatures formed using an individual's private key in a public key cryptosystem is that the signature can be disavowed, in the sense that an impartial arbiter cannot prove otherwise, by the holder of the Private key either disclosing, or claiming, the disclosure of his key. In various guises this failure characterizes all individual identification systems which equate identity with the possession of a piece of information that was once known to be in the private possession of the individual identified. This paper describes a means of associating an individual with an unforgeable piece of information, such that the association is feasible to verify whenever the individual needs to be identified. Consequently, the bearer canbe identified (associated) with the information and the problem described above solved. An application of this principle to access control at sensitive nuclear facilities has been made and is described briefly.

The functions of secrecy, identification of the transmitter and of authentication of messages, and combinations of these, are in principle all achievable using either symmetric or asymmetric cryptosystems. Since secure communications depend on authenticated data exchanges between and/or authenticated actions by some of the parties to the communication, the fundamentals of authentication using symmetric or asymmetric techniques are developed. The surprising conclusion is that they differ only in the secure exchanges required to achieve further secure communications. The problem of authenticating a public-key directory is discussed in the light of these findings.

The aperiodic binary correlation function or correlogramX \ast Yoccurs as the output of the detector in the correlation detection of a binary code wordYin an unsynchronized code streamX. In most applications, such as self-synchronizing data links, the correlation properties are determined by the desired system characteristics, and the problem is to find codes that approximate the desired correlation. As a partial solution to this problem, the general algebraic properties ofX \ast Yas a function of the code wordsXandYare developed in this paper. In particular, sufficient conditions for the general quadratic equationX \ast Y = W \ast Zto possess solutions are demonstrated, as well as for the restricted cases in whichW = \pm YandZ = \pm X, i.e., commutative or anticommutative code word pairs, orY = XandZ = W. The principal tool used in this development is a repeated Kronecker product of palindromic factor code words, which we call pseudo-Rademacher-Walsh (PRW) codes since the simplest examples of such products are the normal Rademacher-Walsh codes. The PRW codes are used as a basis for constructing arbitrarily many nontrivial solutions to each of the four possible correlogram identities.