NEW DIRECTIONS IN CRYPTOGRAPHY 31 the secure channel might be a weekly courier and the insecure added modulo 2 to the bits of the plaintext.Block ciphers act channel a telephone line. in a purely combinatorial fashion on large blocks of text,in A cryptographic system is a single parameter family such a way that a small change in the input block produces a (Sk);ZkEKz)of invertible transformations major change in the resulting output.This paper deals primarily with block ciphers,because this error propagation property is Sx:{P}→{C} (1) valuable in many authentication applications. In an authentication system,cryptography is used to guaran- from a space p)of plaintext messages to a space C of tee the authenticity of the message to the receiver.Not only ciphertext messages.The parameter K is called the key and is must a meddler be prevented from injecting totally new,authen- selected from a finite set (K)called the keyspace.Ifthe message tic looking messages into a channel,but he must be prevented spaces(P)and (C)are equal,we will denote them both by (M).from creating apparently authentic messages by combining,or When discussing individual cryptographic transformations Sk,merely repeating,old messages which he has copied in the we will sometimes omit mention of the system and merely past.A cryptographic system intended to guarantee privacy refer to the transformation K. will not,in general,prevent this latter form of mischief. The goal in designing the cryptosystem {Sk)is to make To guarantee the authenticity of a message,information is the enciphering and deciphering operations inexpensive,but to added which is a function not only of the message and a secret ensure that any successful cryptanalytic operation is too com-key,but of the date and time as well,for example,by attaching plex to be economical.There are two approaches to this prob-the date and time to each message and encrypting the entire lem.A system which is secure due to the computational cost sequence.This assures that only someone who possesses the of cryptanalysis,but which would succumb to an attack with key can generate a message which,when decrypted,will contain unlimited computation,is called computationally secure:while the proper date and time.Care must be taken,however,to use a system which can resist any cryptanalytic attack,no matter a system in which small changes in the ciphertext result in how much computation is allowed,is called unconditionally large changes in the deciphered plaintext.This intentional error secure.Unconditionally secure systems are discussed in [3]and propagation ensures that if the deliberate injection of noise on 4]and belong to that portion of information theory,called the the channel changes a message such as "erase file 7"into a Shannon theory.which is concerned with optimal performance different message such as "erase file 8,"it will also corrupt the obtainable with unlimited computation. authentication information.The message will then be rejected Unconditional security results from the existence of multiple as inauthentic. meaningful solutions to a cryptogram.For example,the simple The first step in assessing the adequacy of cryptographic substitution cryptogram XMD resulting from English text can systems is to classify the threats to which they are to be sub- represent the plaintext messages:now,and,the,etc.A computa-jected.The following threats may occur to cryptographic sys- tionally secure cryptogram,in contrast,contains sufficient tems employed for either privacy or authentication. information to uniquely determine the plaintext and the key. A ciphertext only attack is a cryptanalytic attack in which Its security resides solely in the cost of computing them. the cryptanalyst possesses only ciphertext. The only unconditionally secure system in common use is A known plaintext attack is a cryptanalytic attack in which the the one time pad,in which the plaintext is combined with a cryptanalyst possesses a substantial quantity of corresponding randomly chosen key of the same length.While such a system plaintext and ciphertext. is provably secure,the large amount of key required makes it A chosen plaintext attack is a cryptanalytic attack in which impractical for most applications.Except as otherwise noted, the cryptanalyst can submit an unlimited number of plaintext this paper deals with computationally secure systems since messages of his own choosing and examine the resulting these are more generally applicable.When we talk about the cryptograms. need to develop provably secure cryptosystems we exclude In all cases it is assumed that the opponent knows the general those,such as the one time pad,which are unwieldly to use. system {Sk)in use since this information can be obtained by Rather,we have in mind systems using only a few hundred studying a cryptographic device.While many users of cryptog- bits of key and implementable in either a small amount of raphy attempt to keep their equipment secret,many commercial digital hardware or a few hundred lines of software. applications require not only that the general system be public We will call a task computationally infeasible if its cost as but that it be standard. measured by either the amount of memory used or the runtime A ciphertext only attack occurs frequently in practice.The is finite but impossibly large. cryptanalyst uses only knowledge of the statistical properties Much as error correcting codes are divided into convolutional of the language in use (e.g.,in English,the letter e occurs 13 and block codes,cryptographic systems can be divided into percent of the time)and knowledge of certain"probable"words two broad classes:stream ciphers and block ciphers.Stream (e.g.,a letter probably begins "Dear Sir:").It is the weakest ciphers process the plaintext in small chunks(bits or characters),threat to which a system can be subjected,and any system usually producing a pseudorandom sequence of bits which is which succumbs to it is considered totally insecure.NEW DIRECTIONS IN CRYPTOGRAPHY 31 the secure channel might be a weekly courier and the insecure added modulo 2 to the bits of the plaintext. Block ciphers act channel a telephone line. in a purely combinatorial fashion on large blocks of text, in A cryptographic system is a single parameter family such a way that a small change in the input block produces a {SK};zKP{K;z} of invertible transformations major change in the resulting output. This paper deals primarily with block ciphers, because this error propagation property is SK:{P} → {C} (1) valuable in many authentication applications. In an authentication system, cryptography is used to guaran￾from a space {P} of plaintext messages to a space {C} of tee the authenticity of the message to the receiver. Not only ciphertext messages. The parameter K is called the key and is must a meddler be prevented from injecting totally new, authen￾selected from a finite set {K} called the keyspace. If the message tic looking messages into a channel, but he must be prevented spaces {P} and {C} are equal, we will denote them both by {M}. from creating apparently authentic messages by combining, or When discussing individual cryptographic transformations SK, merely repeating, old messages which he has copied in the we will sometimes omit mention of the system and merely past. A cryptographic system intended to guarantee privacy refer to the transformation K. will not, in general, prevent this latter form of mischief. The goal in designing the cryptosystem {SK} is to make To guarantee the authenticity of a message, information is the enciphering and deciphering operations inexpensive, but to added which is a function not only of the message and a secret ensure that any successful cryptanalytic operation is too com- key, but of the date and time as well, for example, by attaching plex to be economical. There are two approaches to this prob- the date and time to each message and encrypting the entire lem. A system which is secure due to the computational cost sequence. This assures that only someone who possesses the of cryptanalysis, but which would succumb to an attack with key can generate a message which, when decrypted, will contain unlimited computation, is called computationally secure; while the proper date and time. Care must be taken, however, to use a system which can resist any cryptanalytic attack, no matter a system in which small changes in the ciphertext result in how much computation is allowed, is called unconditionally large changes in the deciphered plaintext. This intentional error secure. Unconditionally secure systems are discussed in [3] and propagation ensures that if the deliberate injection of noise on [4] and belong to that portion of information theory, called the the channel changes a message such as “erase file 7” into a Shannon theory, which is concerned with optimal performance different message such as “erase file 8,” it will also corrupt the obtainable with unlimited computation. authentication information. The message will then be rejected Unconditional security results from the existence of multiple as inauthentic. meaningful solutions to a cryptogram. For example, the simple The first step in assessing the adequacy of cryptographic substitution cryptogram XMD resulting from English text can systems is to classify the threats to which they are to be sub￾represent the plaintext messages: now, and, the, etc. A computa- jected. The following threats may occur to cryptographic sys￾tionally secure cryptogram, in contrast, contains sufficient tems employed for either privacy or authentication. information to uniquely determine the plaintext and the key. A ciphertext only attack is a cryptanalytic attack in which Its security resides solely in the cost of computing them. the cryptanalyst possesses only ciphertext. The only unconditionally secure system in common use is A known plaintext attack is a cryptanalytic attack in which the the one time pad, in which the plaintext is combined with a cryptanalyst possesses a substantial quantity of corresponding randomly chosen key of the same length. While such a system plaintext and ciphertext. is provably secure, the large amount of key required makes it A chosen plaintext attack is a cryptanalytic attack in which impractical for most applications. Except as otherwise noted, the cryptanalyst can submit an unlimited number of plaintext this paper deals with computationally secure systems since messages of his own choosing and examine the resulting these are more generally applicable. When we talk about the cryptograms. need to develop provably secure cryptosystems we exclude In all cases it is assumed that the opponent knows the general those, such as the one time pad, which are unwieldly to use. system {SK} in use since this information can be obtained by Rather, we have in mind systems using only a few hundred studying a cryptographic device. While many users of cryptog￾bits of key and implementable in either a small amount of raphy attempt to keep their equipment secret, many commercial digital hardware or a few hundred lines of software. applications require not only that the general system be public We will call a task computationally infeasible if its cost as but that it be standard. measured by either the amount of memory used or the runtime A ciphertext only attack occurs frequently in practice. The is finite but impossibly large. cryptanalyst uses only knowledge of the statistical properties Much as error correcting codes are divided into convolutional of the language in use (e.g., in English, the letter e occurs 13 and block codes, cryptographic systems can be divided into percent of the time) and knowledge of certain “probable” words two broad classes: stream ciphers and block ciphers. Stream (e.g., a letter probably begins “Dear Sir:”). It is the weakest ciphers process the plaintext in small chunks (bits or characters), threat to which a system can be subjected, and any system usually producing a pseudorandom sequence of bits which is which succumbs to it is considered totally insecure