+% begin text
+
+\banner
+
+\section{Introduction}
+Initially,
+a brief model of a user community employing a trusted mail service is
+introduced.
+Following this introduction,
+a prototype system is described which attempts to meet the needs of a user
+community.
+Finally,
+open issues are discussed,
+which are currently not satisfied by the prototype system or its model of
+operation.
+
+Two or more entities,
+called {\it users},
+wish to communicate in a {\it secure} environment.
+Depending on their available resources,
+different levels of security are possible.
+At the extreme,
+two parties with substantial resources may wish to communicate in a fashion
+which prevents any third parties,
+known as {\it adversaries},
+from observing their communication.
+At this level,
+not only is an adversary unable to capture the communication for analysis,
+but in fact, the adversary is unaware that any communication is occurring at
+all.
+In most applications,
+this level of security is prohibitively expensive.
+A more economic method is to translate messages into a form which is useless
+to an adversary and then to communicate those messages on an insecure medium.
+
+This latter method requires the two users to have some sort of {\it key}
+with which to ``lock'' the plaintext into ciphertext when transmitting,
+and then to ``unlock'' the ciphertext back into useful form when receiving.
+Hence, there are two central issues to deal with:
+\underbar{first},
+keys must be generated, distributed, and maintained in a secure fashion;
+and,
+\underbar{second},
+the keys must be ``intricate'' enough so that sense can't be made out of the
+ciphertext without knowledge of the key.
+The first part is handled by a {\it key distribution center} (\KDC/),
+which maintains a list of users and a set of keys for each pair of users.
+The second part relies on sophisticated encryption and decryption algorithms.
+It is beyond the scope of this paper to describe cryptographic techniques in
+detail.
+For a detailed survey of this area, the reader should consult \cite{VVoyd83}.
+
+\tagfigure{1}{The \MTS/ Model}{mtsmodel}
+In the context of our discussion (using the terminology of \cite{X.400}),
+the medium used to transport is supplied
+by a {\it message transport system} (\MTS/),
+which is composed of one or more {\it message transport agents} (\MTA/s).
+Usually,
+the entire \MTS/ is distributed in nature,
+and not under a single administrative entity;
+in contrast, an \MTA/ is usually controlled by a single administration and
+resides in a particular domain.
+At every end-point in the medium,
+a {\it user agent} (\UA/) acts on behalf of a user and interfaces
+to a local \MTA/.
+This model is briefly summarized in Figure~\mtsmodel.
+
+A message, in our context, consists of two parts:
+the {\it headers} and the {\it body}.
+The headers are rigorously structured;
+they contain addressing information and other forms useful to a \UA/.
+The body is freely formatted and is usually not meaningful to a \UA/.
+
+When a message is sent from one user to another,
+the following activities occur:
+The originating user indicates to the \UA/ the address of the recipient;
+the \UA/ then posts the message through a {\it posting slot} to an \MTA/,
+which involves a posting protocol in which the validity of the address
+and the syntax of the message are considered.
+Upon successful completion of the protocol,
+the \MTA/ accepts responsibility for delivering the message,
+or if delivery fails, to inform the originating user of the failure.
+The \MTA/ then decides if it can deliver the message directly to the
+recipient;
+if so, it delivers the message through a {\it delivery slot} to the
+recipient's \UA/,
+using a delivery protocol.
+If not, it contacts an adjacent \MTA/, closer to the recipient,
+and negotiates its transfer (using a protocol similar to the posting protocol).
+This process repeats until an \MTA/ is able to deliver the message,
+or an \MTA/ determines that the message can't be delivered.
+In this latter case,
+a failure notice is sent to the originating user.
+
+\tagfigure{2}{Mappings in the \MTS/ model}{mappings}
+It is important to note that there are two mappings which occur here.
+The first, which is performed implicitly by the originating user,
+maps the name of the recipient into the recipient's address;
+the second, which is performed explicitly by the \MTS/,
+maps the address of the recipient into a route to get from the originator's
+\MTA/ to the recipient's \MTA/.
+These mappings are depicted in Figure~\mappings.
+
+Obviously, there is no guarantee that the \MTS/ can be made secure,
+in {\it any} sense of the word.
+This is particularly true if it is under several administrations.
+Regardless of the number of administrations in the \MTS/,
+this problem quickly degenerates to a problem of
+Byzantine generals\cite{LLamp82}.
+Further, trying to secure each \MTA/ in the path that a message travels is
+equally questionable.
+
+\tagfigure{3}{Modifications to the \MTS/ model}{tmodel}
+To support secure communications in this environment,
+a new entity,
+the {\it trusted mail agent} (\TMA/) is introduced into our model.
+A solution is to have the \UA/ interact with this entity
+both when posting a message and when taking delivery of a message.
+The \UA/ first contacts a \TMA/ to encrypt the body of the message for the
+recipient,
+prior to pushing it through the posting slot.
+Upon receipt from the destination \MTA/,
+the \UA/ examines the message and contacts
+the \TMA/ to decipher the body of the message from the source.
+An overview of the relationship between the standard \MTS/ model
+and the augmentations made for the \trustedmail/ system is shown in
+Figure~\tmodel.
+
+To achieve these tasks,
+the \TMA/ interacts with a {\it key distribution service} (\KDS/),
+which manages keys between pairwise users.
+At this point, a third mapping takes place:
+the \UA/ must be able to map addresses into the identifier(s)
+by which the originator and recipient are known by the \TMA/ and \KDS/.
+These identifiers are known as \KDS/ IDs, or simply IDs.
+Usually, a fourth mapping also occurs,
+which maps the ID of a user into the name of a user.
+In our context,
+there is an exact one-to-one mapping between the name of a user and the ID
+of that user.
+In contrast,
+there may be a one-to-many mapping between the name of a user and
+that user's address in the \MTS/.
+Further, there are usually many different routes which a message may traverse
+when going from an originating user to a recipient user.
+
+The \TMA/ is said to be {\it trusted} because it can be relied on to perform
+only those actions specifically requested by the user.
+In the context of this paper,
+this means, given proper construction and maintenance of the \TMA/,
+that the software will communicate with the \KDC/ in some secure fashion to
+negotiate key relationships and that it will not disclose those key
+relationships to other parties.
+Furthermore,
+the body of mail messages exchanged between users which employ
+a trusted mail agent will be unintelligible to other parties.
+Finally,
+a recipient of a message receives authenticated information from the
+trusted mail agent as to the identify of the sender.
+
+Hence,
+when each user employs a \TMA/,
+end-to-end encryption occurs at the \UA/ level
+(to avoid any problems with malicious \MTA/s).%
+\nfootnote{Note that in the scope of this system,
+the end-points are the user agents, not the hosts they reside on.
+In fact,
+it may very well be the case that the user agent and the local message
+transport agent do not reside on the same host.}
+Any adversary listening in on the \MTS/,
+may observe messages,
+but make no sense out of them
+(other than rudimentary traffic analysis).
+Note, however,
+that since the medium itself is not secure,
+an adversary may still introduce new messages,
+corrupt messages,
+or remove messages,
+as they traverse the \MTS/.
+In the first two cases, however,
+the recipient would be suspicious
+because the adversary lacks the encrypting key employed by the source user.
+In the third case,
+the source user can retransmit the message after a suitable time.
+Of course,
+there is no built-in retransmission policy~---~this aspect depends on the
+user's sending mail and is beyond the scope of the system.
+
+It is important to understand the target community for the \trustedmail/ system
+described herein.
+In particular,
+the \TMA/ is intended for a commercial and not a military environment.
+This distinction is important,
+since it is the {\it fundamental} assumption of this paper that
+the latter community has much stricter requirements than the former.
+Because of this,
+the prototype system is able to make certain simplifying assumptions which
+permit it to operate in a mode which is less secure than military
+applications would permit.
+Although these issues are explored in greater detail at the end of the paper,
+for the moment recall that, like most qualities, trustedness is not absolute:
+there are varying degrees of trustedness,
+and as a system becomes more trusted,
+it becomes more expensive, in some sense, to operate and maintain.
+
+It is perhaps instructive at this point to consider why the introduction of a
+key distribution center is appropriate in this environment,
+and why the {\it fundamental} assumption that trusted mail agents do not
+directly communicate with each other is necessary.
+Although a user agent is able to converse with the local message transport
+agent in real-time,
+it is frequently not able to communicate with other user agents in real-time.
+Furthermore,
+considering the vast problems and overhead
+of trying to establish secure communications from ``scratch''
+(a problem far beyond the scope of this paper),
+it is would not be a good idea to try and communicate key relationships with
+other user agents,
+even if it were always possible to do so.
+In addition,
+by separating the trusted aspects of the message transport system from the
+system itself,
+many other advantages can be seen.
+These are presented in greater detail at the end of the paper.
+
+The discussion thus far has considered only a single recipient.
+In practice, a user might wish to send to several others,
+using a different key for each.
+Hence each copy of the message is encrypted differently,
+depending on the particular recipient in question.
+Note that this has the effect of {\it un-bundling} message transfer in the
+\MTS/,
+as advanced \MTA/s tend to keep only a single copy of the message for any
+number of recipients in order to save both cpu, disk, and I/O resources.
+
+For example,
+in some existing mail systems,
+if a message was sent to $n$ users on a remote system,
+then the $n$ addresses would be sent from the source \MTA/ to the remote \MTA/
+along with one copy of the message.
+Upon delivery,
+the remote \MTA/ would deliver a copy to each of the $n$ recipients,
+but the virtual wire between the source \MTA/ and the recipient \MTA/ was
+burdened with only one copy of the message.
+But in a secure environment,
+since a different key is used by the source user when communicating with each
+of the $n$ recipients,
+$n$ different messages will be posted with the local \MTA/,
+and the advantages of recipient bundling are lost.
+
+Along these lines however,
+private discussion groups may wish to avoid this problem by establishing
+access to a single ID for their use.
+In this case,
+a subscriber to the \KDS/ may actually have more than one ID,
+one for ``personal'' use and one for each discussion group.
+The appropriate ID is used when posting messages to the discussion group.
+Naturally the administrative policy for deciding who is allowed to use the
+\KDS/ ID of a discussion group is left to the moderator of the group.
+Observant readers will note that this vastly decreases the aspect of
+secure communications for the discussion group.
+This method is suggested as a compromise
+which permits the bundling of messages for multiple recipients
+to reduce \MTS/ traffic.
+The price is high however,
+as a compromise on behalf of {\it any} member of the discussion group
+compromises the entire group.
+For large discussion groups and a bandwidth limited \MTS/,
+this price may be worth paying.
+The prototype implementation of the \TMA/ supports multiple recipients but
+not multiple \KDS/ IDs.
+
+Having described this environment for communication,
+the designs of a \KDS/ and \TMA/ which form the heart of the \TTI/
+\trustedmail/ system are discussed.
+The prototype system was developed on a \vax/-11/780 running 4.2\bsd/ \unix/.
+The system is based on the \ansi/ draft\cite{FIKM}
+for financial key management,
+but diverges somewhat in operation
+owing to the differences between the electronic mail (CBMS)
+and electronic funds (EFT) environments.
+Note however that the \ansi/ data encryption algorithm\cite{DEA,FIPS46} is
+used in the current implementation.
+A public-key cipher system was not considered as the basis for the prototype
+since, to the authors' knowledge,
+an open standard for a public-key system has yet to be adopted by the
+commercial community.
+In contrast,
+the \ansi/ draft for financial key management appears to be receiving
+wide support from the commercial community.
+
+\tagtable{4}{Abbreviations used in this paper}{terms}
+In the description that follows,
+a large number of acronyms are employed to denote commonly used terms.
+In order to aid the reader,
+these are summarized in Table~\terms.
+
+\section{The Key Distribution Service}
+The prototype version of the \KDS/
+was designed to provide key distribution services for
+user agents under both the same or different administrations.
+As a result,
+the means by which a trusted mail agent connects to a key distribution server
+is quite flexible.
+For example,
+the prototype system supports connections via
+standard terminal lines,
+dial-ups (e.g., over a toll-free 800 number),
+\unix/ pipes,
+and over TCP sockets\cite{IP,TCP}.
+In the interests of simplicity,
+for the remainder of this paper,
+a TCP/IP model of communication is used.
+Initially,
+a server on a well-known service host in the ARPA Internet community
+listens for connections on a well-known port.%
+\nfootnote{The term {\it well known} in this context means that the
+location of the service is known {\it a priori} to the clients.}
+As each connection is established,
+it services one or more transactions over the lifetime of the session.
+When all transactions for a session have been made,
+the connection is closed.
+If the necessary locking operations are performed by the server
+to avoid the usual database problems,
+then more than one connection may be in progress simultaneously.
+Of course,
+a time-out facility should also be employed to prevent a rogue agent from
+monopolizing the key distribution server.
+
+Once a session has been started,
+the client (a.k.a.~\TMA/) initiates transactions with the server
+(a.k.a.~\KDS/).
+Each transaction consists of the exchange of two or three
+{\it cryptographic service messages} (\CSM/s):
+the client sends a request,
+the server attempts to honor the request and sends a response,
+and,
+if the server responded positively,
+the client then acknowledges the transaction.
+By exchanging these cryptographic service messages,
+the \KDS/ and the \TMA/ are able to communicate key relationships.
+Obviously, the relationships themselves must be transmitted in encrypted
+form.%
+\nfootnote{Otherwise an adversary could simply impersonate a \TMA/ and ask
+for the desired key relationships.
+Similarly, this also prevents an adversary from successfully impersonating a
+key distribution server.}
+Hence, not only are key relationships between two \TMA/s communicated,
+but key relationships between the \KDS/ and the \TMA/ are communicated as well.
+
+This leads us to consider the key relationships that exist
+between a \TMA/ and the \KDS/.
+A client usually has three keys dedicated for use with the server.
+The first is the {\it master key} (denoted MK),
+which has an infinite cryptoperiod, and is rarely used.
+This key is distributed manually.
+The second is the {\it key-encrypting key} (denoted KK),
+which has a shorter cryptoperiod.
+Whenever a KK is transmitted to the \TMA/,
+it is encrypted with the master key.
+The third is the {\it authentication key} (denoted KA),
+which is used to authenticate transactions that do not contain data keys
+(a count field is also used to avoid play-back attacks).
+Whenever a KA is transmitted to the \TMA/,
+it is encrypted with the key-encrypting key.
+When transactions contain keys,
+an associated count field is included to indicate the number of
+keys encrypted with the key-encrypting key used.
+Although not used by the prototype implementation,
+a production system would employ audit mechanisms to monitor usage histories.
+
+Currently four types of requests are honored by the \KDS/:
+two key relationship primitives, and two name service primitives.
+The type is indicated by the {\it message class} (MCL) of the first
+cryptographic service message sent in the transaction.
+As each message class is discussed,
+the appropriate datastructures used by the \KDS/ are introduced.
+Space considerations prevent a detailed description of the information
+exchanged in each transaction.
+Appendix~B of this paper presents a short example of an interaction between
+the \KDS/ and a \TMA/.
+
+The first two requests are used to create (or retrieve) key relationships,
+and to destroy key relationships:
+
+The {\it request service initialization} (RSI) message class
+is used to establish a {\it key-encrypting key} (KK) relationship
+between the \TMA/ and another \TMA/,
+or between the \TMA/ and the \KDS/.
+As implied by the name,
+a key-encrypting key is used to cipher keys which are used to cipher data
+exchanged between peers.
+These other keys are called {\it data keys} (KDs).
+
+The {\it disconnect service message} (DSM) message class
+is used to discontinue a KK-relationship
+between the \TMA/ and another \TMA/,
+or between the \TMA/ and the \KDS/.
+This prevents keys which are felt to have been compromised,
+or are vulnerable to compromise,
+from receiving further use in the system.
+It should be noted that,
+owing to mail messages (not \CSM/s) in transit,
+a discontinued key relationship
+may be needed to decipher the key used to encipher a mail message.
+The prototype \KDS/ supports this capability.
+
+In addition to maintaining an MK/KK/KA triple for each \TMA/,
+the \KDS/ also remembers KK-relationships between \TMA/s.
+The reason for this stems from a fundamental difference between the
+electronic funds transfer and computer-based message system worlds.
+The \KDS/ assumes that no two arbitrarily chosen \TMA/s can communicate in
+real-time,
+and as a result,
+\TMA/s do not exchange cryptographic service messages.
+(See Appendix~C for a more detailed discussion.)
+This means that when a \TMA/ establishes a KK-relationship with another \TMA/,
+the former \TMA/ may start using the KK before the latter \TMA/ knows of the
+new KK-relationship.
+In fact,
+it is quite possible for a KK-relationship to be established,
+used,
+and then discontinued,
+all unilaterally on the part of one \TMA/.
+It is up to the \KDS/ to retain old cryptographic material
+(possibly for an indefinite period of time),
+and aid the latter \TMA/ in reconstructing KK-relationships as the need arises.
+Naturally,
+discontinued KKs are not used to encode any new information,
+but rather to decode old information.
+(Again, refer to Appendix~C for additional details.)
+
+The other two requests are used to query the directory service aspects of the
+key distribution server:
+
+The {\it request user identification} (RUI) message class
+is used to identify a subscriber to the \KDS/.
+Both the \KDS/ and \TMA/ are independent of any underlying mail transport
+system (\MTS/).
+As a result,
+a subscriber to the \KDS/ is known by two unique attributes:
+a ``real-world'' name,
+and a \KDS/ identifier (ID).
+The user of a mail system,
+or the \UA/,
+is responsible for mapping an \MTS/-specific address
+(e.g., {\tx MRose@UDEL.ARPA})
+to the person associated with that maildrop
+(e.g., \eg{Marshall\ T.\ Rose}).
+When conversing with the \KDS/,
+the \TMA/ uses the \KDS/ ID of another user to reference that person's \TMA/.
+Since it is inconvenient to remember the IDs (as opposed to people's names),
+the \KDS/ provides the RUI message class to permit a \TMA/ to query the
+mapping between names and IDs.
+If the \KDS/ cannot return an exact match,
+it may respond with a list of possible matches
+(if the identifying information given was ambiguous),
+or it may respond with a response that there is no matching user.
+
+Finally,
+the {\it request identified user} (RIU) message class
+performs the inverse operation:
+given a \KDS/ ID, a ``real-world'' name is returned.
+This request is useful for disambiguating unsuccessful RUI requests
+and in boot-strapping a \TMA/.
+
+The \KDS/ maintains two directories:
+a private directory and a public directory.
+The private directory contains all information on all clients to the \KDS/.
+The public directory is a subset of this,
+and is used by the \KDS/ when processing RUI and RIU requests.%
+\nfootnote{In the prototype implementation,
+the two directories are, for the moment, identical.}
+As a result,
+certain clients of the \KDS/ may have unlisted IDs and names.
+
+\section{The Trusted Mail Agent}
+The prototype version of the \TMA/
+was designed to interface directly to the user agent in order to maximize
+transparency to the user.
+In present form,
+the \TMA/ is available as a load-time library under 4.2\bsd/ \unix/,
+although efforts are currently underway to transport the \TMA/ to a PC-based
+environment.
+
+The software modules which compose the \TMA/ contain a rich set of interfaces
+to the \KDS/.
+In addition,
+the \TMA/ manages a local database,
+so responses from the \KDS/ may be cached and used at a later time.
+In all cases,
+the \KDS/ is consulted only if the information is not present
+in the \TMA/ database,
+or if the information in question has expired (e.g., KK-relationships).
+This caching activity minimizes connections to the \KDS/.
+Although connections are relatively cheap in the ARPA Internet,
+substantial savings are achieved for PCs which contact the \KDS/ over a
+public phone network (dial-up) connection.
+
+The \TMA/ performs mappings between pairs of the following objects:
+user names, \KDS/ IDs, and \MTS/ addresses.
+The \TMA/ considers all trusted mail agents, including itself,
+as a user name, \KDS/ ID, and one or more \MTS/ addresses.
+Although the \TMA/ does not interpret addresses itself,
+in order to simplify mail handling,
+the \TMA/ remembers the relationship between these objects so the user enters
+this information only once.
+
+Initially,
+when a \TMA/ is booted,
+the user supplies it with the master key and the user's \KDS/ ID.
+Both of these quantities are assigned by the personnel at the key
+distribution center,
+and subsequently transmitted to the user via an alternate, bonded service.%
+\nfootnote{In this fashion,
+the problems of boot-strapping over an unsecure medium are avoided.}
+The \TMA/ connects with the \KDS/ and verifies its identity.
+From this point on,
+the \TMA/ manages its KK-relationships between the \KDS/ and other \TMA/s
+without user intervention.
+
+The current implementation of the \TMA/ assumes a ``general memo framework''
+in the context of the Standards for ARPA Internet Text Messages\cite{DCroc82}:
+\smallskip
+{\advance\leftskip by\parindent
+\item{1.} A message consists of two parts:
+the {\it headers} and the {\it body}.
+A blank line separates the headers from the body.
+
+\item{2.} Each (virtual) line in the headers consists of a keyword/value
+pair, in which the keyword is separated from the value by a colon (:).
+The headers are rigorously structured in the sense that they contain
+addressing and other information useful to a user agent.
+
+\item{3.} The body is freely formatted and must not be meaningful to a
+user agent.
+However, as will be seen momentarily,
+the body of encrypted messages must have an initial fixed format which the
+\TMA/ enforces.
+\smallskip}
+\noindent
+This format is widely called ``822'' after the number assigned to the
+defining report\cite{DCroc82}.%
+\nfootnote{Although an 822--style framework is employed by the \TMA/ prototype,
+the 822 \eg{Encrypted:} header is not currently present in encrypted messages.
+This is due to a design decision which assumes that nothing in the headers of
+a message is sacred to the transport system,
+and that ``helpful'' munging might occur at any time.
+In the real world, such helpfulness is often a problem.}
+
+To support the cipher activities described below,
+the \TMA/ contains internal routines to perform the following DES functions:
+electronic code book (ECB) for key encryption,
+cipher block chaining (CBC) for mail message encryption,
+checksumming (CKS) for mail message and \CSM/ authentication.
+Readers interested in these different modes of operation for the DES should
+consult \cite{FIPS81}.
+
+\subsection{Encrypting Mail}
+To encipher a message, the method used is a straightforward adaptation
+of the standard encrypting/authentication techniques
+(though the terminology is tedious).
+Consider the following notation:
+\smallskip
+{\advance\leftskip by\parindent
+\itemm $a_x(s)$ the checksum of the string $s$ using the key $x$
+(DEA~{\it checksumming} authentication)
+
+\itemm $a_{x+y}(s)$ the checksum of the string $s$ using the exclusive-or
+of the two keys $x$ and $y$
+
+\itemm $e_x(y)$ the encryption of the key $y$ using the key $x$
+(DEA~{\it electronic code book} encryption)
+
+\itemm $e_{x,y}(s)$ the encryption of the string $s$ using the key $x$
+and initialization vector $y$
+(DEA~{\it cipher block chaining} encryption)
+
+\itemm $h$ the headers of the message
+
+\noindent and,
+
+\itemm $b$ the body of the message
+\smallskip}
+\noindent
+For each message to be encrypted,
+a data key, initialization vector, authentication key (KD/IV/KA)
+triple is generated by a random process.
+(It goes without saying that the integrity of the system depends on the
+process being {\it random\/}).
+Then, for each user to receive a copy of the encrypted message,
+the following actions are taken:
+
+First, the headers of the message are output in the clear.
+Then, a {\it banner} string, $i$, is constructed and placed at the beginning
+of the body of the message:
+\example ENCRYPTED MESSAGE: TTI TMA\endexample
+which identifies the message as being encrypted by the \TTI/ \TMA/.
+Following the banner string is a structure, $m$,
+which takes on the syntax and most of the semantics of a cryptographic
+service message:
+$$\displayindent=\leftskip \advance\displayindent by1.5\parindent
+ \halign{\hfil#/& \enspace#\hfil\cr
+ MCL& MAIL\cr
+ RCV& rcvid\cr
+ ORG& orgid\cr
+ IDK& kkid\cr
+ KD& $e_{kk}(ka)$\cr
+ KD& $e_{kk}(kd)$\cr
+ IV& $e_{kd}(iv)$\cr
+ MIC& $a_{ka}(b)$\cr
+ MAC& $a_{kd+ka}(m)$\cr
+}$$
+After this, the encrypted body is output, $e_{kd,iv}(b)$.
+In short, the entire output consists of
+$$h+i+m+e_{kd,iv}(b).$$
+
+The purpose of the structure $m$ is many-fold.
+The MCL field indicates the structure $m$'s type;
+currently only the type MAIL is generated and understood.
+The RCV and ORG fields identify the intended recipient of the message
+and the originator.
+The IDK field identifies the key-encrypting key, KK,
+used to encrypt the next two fields.
+The first KD field has the encrypted authentication key, KA,
+used to calculate the MIC of the plaintext of the body of the message.
+After the body of the message is deciphered, $a_{ka}(b)$ is calculated and
+compared to the value of the MIC field.
+Hence, the MIC field authenticates the message body.
+The second KD field has the encrypted data encrypting key, KD,
+which along with the encrypted initialization vector in the IV field
+was used to generate the ciphertext of the body.
+Finally, the MAC field authenticates the $m$ structure itself.
+The use of a data key, initialization vector, authentication key (KD/IV/KA)
+triple permits us to perform key distribution in a hierarchical fashion and
+allows the system to use a KK-relationship over a longer cryptoperiod
+without fear of compromise.
+
+The \TMA/ provides three primary interfaces to a \UA/ to send encrypted mail:
+the first takes a file-descriptor to a message
+and returns a structure $g$ (called a {\it group})
+describing the ciphertext version of the body
+(this structure contains a KD, IV, and KA generated at random,
+along with a file-descriptor to the plaintext headers,
+a file-descriptor to the ciphertext body,
+and the checksum of the plaintext body);
+the second takes a user entry (or \MTS/ address) and $g$,
+and returns a file-descriptor to the encrypted message
+for that user (or \MTS/ address);
+the third takes $g$ and performs clean-up operations.
+The chief advantage to this scheme of encryption
+is that if the message is to be sent to more than one recipient,
+then the MIC and the encrypted body need only be calculated once,
+since the KD, IV, and KA remain constant
+(only the KK's change with each recipient,
+hence for each copy of the encrypted message,
+only the structure $m$ need be re-calculated).
+
+There are, however, a few subtleties involved:
+\underbar{first},
+the \MTS/ usually accepts only 7--bit characters,
+so the encrypted text is exploded to consist of only printable characters;%
+\nfootnote{%
+As a rule, in all \CSM/s,
+when encrypted information is transmitted,
+it is exploded after encryption by the sender,
+and imploded prior to decryption by the receiver.}
+\underbar{second},
+since the \MTS/ may impose limits on the length of a line,
+each line of output is limited to 64~characters;
+and,
+\underbar{third},
+since the body may require trailing padding,
+during encryption
+one last unit of 8~bytes is written (and encrypted),
+naming the number of characters (presently, nulls) padded in the
+previous 8~bytes ($0\tdots7$).
+
+\subsection{Decrypting Mail}
+To decipher a message, the method is also straightforward:
+The headers are output in the clear.
+The banner string is essentially ignored,
+and the structure $m$ is consulted to identify the correct key-encrypting key.
+The \TMA/ checks to see if it knows of that KK.
+If not, it asks the \KDS/ to supply it.
+From that point,
+the KA, KD, and IV are deciphered.
+The $m$ structure is then authenticated.
+With the correct key,
+the remainder of the body is deciphered,
+and all except for the last 16~bytes are output.
+The last 8~bytes indicate how many of the previous 8~bytes should be output.
+So,
+the appropriate number of bytes is output,
+and the plaintext body is authenticated and compared to the MIC.
+Needless to say,
+as the body is deciphered,
+it is imploded back to 8--bit characters and lines are restored to their
+previous lengths.
+To indicate that the message was correctly deciphered,
+a new header of the form
+\example X-KDS-ID: orgid (originator's name)\endexample
+is appended to the headers of the message.
+Note that this provides an authentication mechanism.
+Note, further,
+that the \UA/ did not have to know the identity of the sender of the message.
+
+\section{Modifications to MH}
+\MH/ is a public domain \UA/ for \unix/,
+which is widely used in dealing with both a large number of electronic mail
+application and a large number of messages.
+Although this document does not intend to describe \MH/,
+parts of the system are described as they relate to the \TMA/.
+Readers interested in \MH/ should consult either the user's
+manual\cite{MRose85a} for a detailed description,
+or \cite{MRose85d} for a higher-level description.
+
+To modify \MH/ in order to make use of a \TMA/,
+three programs were changed (with a high degree of transparency to the user),
+and two new programs were introduced.
+
+In \MH/,
+when a user wishes to send a composed draft
+(which may be an entirely new message,
+a re-distribution of a message,
+a forwarding of messages,
+or a reply to a message),
+the user invokes the \pgm{send} program.
+This program performs some minor front-end work for a program called
+\pgm{post} which actually interacts with the \MTS/.
+A new option to the \pgm{send} and \pgm{post} programs,
+the \switch{encrypt} switch,
+is introduced.
+If the user indicates
+\example send\ -encrypt\endexample
+then \pgm{post} encrypts the messages it sends.
+
+When sending an encrypted message,
+\pgm{post} first checks that each addressee has a mapping to a \KDS/ ID
+during address verification.
+Then, instead of batching all addresses for a message in a single posting
+transaction,
+for each addressee,
+\pgm{post} consults the \TMA/ for the appropriately encrypted text and
+posts that instead.
+(Appendix~A discusses the reasons for this more fully.)
+Hence,
+assuming the user has established mappings between \MTS/ addresses
+and \KDS/ IDs,
+the \TMA/ does all the work necessary to encrypt the message,
+including contacting the \KDS/ as necessary.%
+\nfootnote{Once the \TMA/ establishes a connection to the \KDS/,
+it retains that connection until the \UA/ terminates.
+This is done to minimize connections to the \KDS/.
+In the context of \MH/,
+since the trusted mail agent is active over the lifetime of an invocation of
+a program such as \pgm{post},
+this means that the connection is terminated just before the program
+terminates.}
+
+In \MH/,
+when a user is notified that new mail has arrived,
+the \pgm{inc} program is run.
+As each message is incorporated into the user's message handling area,
+a scan (one-line) listing of the message is generated.
+
+By default,
+the \pgm{inc} program upon detecting one or more encrypted messages,
+after the scanning process,
+asks the \TMA/ to decipher the message,
+and if successful,
+scans the deciphered messages.
+This action can be inhibited with the \switch{nodecrypt} switch.
+Hence, if the user wishes to retain messages in encrypted form,
+\pgm{inc} can be told to note the presence of encrypted messages,
+but otherwise not to process them.
+By using the \MH/ user profile mechanism,
+\pgm{inc} can be easily customized to reflect the user's tastes.
+Again,
+the actions of the \TMA/ are transparent to the user.
+In fact,
+if encrypted mail is received from users unknown to the \TMA/,
+it queries the \KDS/ as to their identity prior to retrieving the
+KK-relationship.
+
+If \pgm{inc} fails to decrypt a message for some reason,
+or if \pgm{inc} was told not to decrypt a message,
+the \pgm{decipher} program can be used.
+This simple program merely deciphers each message given in its argument
+list.
+The \pgm{decipher} program can be given the \switch{insitu} switch,
+which directs it to replace the ciphertext version of the message with the
+plaintext version;
+or,
+the \switch{noinsitu} switch can be used indicating that the ciphertext
+version of the message should be left untouched and the plaintext version
+should be listed on the standard output.
+
+Finally,
+the \pgm{tma} program is used to manipulate the \TMA/ database,
+containing commands to boot the database,
+add new users to the database,
+and to establish mappings between addresses and users in the \TMA/ database.
+This program can also be used to disconnect KKs between other \TMA/s,
+and the KK/KA between itself and the \KDS/.
+
+Appendix~A of this paper contains a transcript of an \MH/ session.
+
+\section{Remarks}
+We now consider the merit of the system described.
+After presenting some of the basic strengths of the system
+and a few unresolved questions,
+the discussion centers on the simplifying assumptions made by the system,
+and how these can be defended in a non-military environment.
+
+\subsection{Strengths}
+It can be argued that the prototype system
+(and the augmented model in which it finds its basis)
+present many strengths.
+
+Perhaps the most important is the high-level of independence from the \MTS/
+enjoyed by the system.
+As a result,
+since the \TMA/ does not interact directly with the \MTS/,
+it can be made to be completely free from any \MTS/-specific attributes,
+such as naming, addressing, and routing conventions.
+Furthermore,
+when interfacing a \trustedmail/ system,
+no modifications need be made to the \MTS/ or local \MTA/.
+
+In addition to the systems-level advantage to this scheme,
+users of the system profit as well,
+since many disjoint \MTS/s can be employed by a user with a single \TMA/.
+This reduces the number of weaknesses in the system and allows a user to keep
+a single database of ``trusted'' correspondents.
+It should also make analysis and verification of the \TMA/ easier.
+
+Of course from the user-viewpoint,
+once the \TMA/ has been initially booted,
+all key management is automatic.
+Not only does this reduce the risk of compromise of cryptographic material
+(given proper construction and maintenance of the \TMA/),
+but it relieves the user of a tedious and error-prone task.
+
+Finally,
+although the \KDS/ described herein is used to support \trustedmail/,
+other applications which require key management,
+could employ the services offered by the key distribution center.
+
+\subsection{Open Questions}
+At present, there are many restrictions on the prototype implementation
+described.
+Some of these result from that fact that the implementation is a prototype
+and not a production system.
+Others deal with more fundamental issues.
+
+In terms of the \TMA/,
+the expiration delay for keys is hard-wired in;
+it should be user-settable.
+In the prototype version,
+the KK and KA with the \KDS/ are good for 2~days or 10~uses
+(whichever comes first),
+while a KK for use with another \TMA/ is good for 1~day or 5~uses.
+In actual practice,
+keys with long cryptoperiods might be good for 6~months or 100~uses,
+while keys with short cryptoperiods might be good for 1~month or 25~uses.
+The choice of actual values is an open question
+beyond the scope of prototype system.%
+\nfootnote{The current values were chosen by guess work.
+Although not necessarily technically sound,
+the small numbers were very good for debugging purposes.}
+In many respects, this issue is a classic trade-off:
+with relatively small cryptoperiods,
+an adversary has less chance of breaking a key,
+but with longer cryptoperiods less connections have to be made to the key
+distribution server.
+
+A fundamental issue,
+owing to differences between the EFT and CBMS environments,
+is that the \KDS/ implements only a subset of the \ansi/ draft
+and the semantics of certain operations have changed somewhat.
+It would be nice to unify the CBMS and EFT views
+of a {\it key distribution center}
+(in the former environment, the center is called a \KDC/,
+while in the latter environment, the center is known as a \CKD/).
+Appendix~C of this paper discusses the differences between the two
+perspectives in greater detail.
+
+At present,
+the relationship between errors in the \TMA/ and the posting process is an
+open question.
+For example,
+if an address doesn't have a mapping in the \TMA/ database,
+\pgm{post} treats this as an address verification error.
+This prevents the draft from being posted.
+The philosophy of the \UA/ is unclear at this point,
+with respect to how recovery should occur.
+A second area, also in question, deals with the way in which plaintext and
+ciphertext versions of a message are present in a system.
+Clearly, it is a bad idea to make both versions available,
+but since the \TMA/ doesn't try to concern itself with first party
+observation,
+there seems to be little possibility of preventing this behavior.
+The best that can be done,
+at this stage,
+is simply to choose a consistent policy that user's should attempt to adhere
+to.
+The software can help somewhat in implementing this policy,
+but it certainly can't circumvent the user.
+
+The prototype is built on the assumption that a single key
+distribution server is present.
+Since the \ansi/ draft\cite{FIKM} makes provisions for
+{\it key translation centers},
+the \trustedmail/ prototype should perhaps be made to operate in a more diverse
+environment.
+Until the issues become clearer,
+this remains open.
+
+Finally,
+for distribution lists,
+a large number of people would need to share the same \KDS/ ID.
+The current implementation doesn't support this.
+Each \TMA/ database is for a particular ID.
+A user with multiple IDs would need multiple databases,
+or the database should be re-organized.
+
+\subsection{Weaknesses}
+As pointed out earlier,
+this prototype system situates itself in a commercial, not military,
+environment.
+With respect to this decision,
+several aspects of the system are now discussed,
+which we feel are acceptable in a commercial environment,
+but which would be considered weaknesses in a military environment:
+
+\item{1.} Traffic Flow\hbreak
+The prototype \TMA/ makes no attempt whatsoever to prevent or confuse traffic
+analysis by augmenting traffic flow.
+
+\item{2.} The Database of \KDS/ Subscribers\hbreak
+Since information returned by the request user identification (RUI)
+and request identified user (RIU) MCLs are returned in the clear,
+this allows an adversary to ascertain subscribers to the \KDS/,
+and perhaps deduce some information about the system.
+Without knowledge of the master key however,
+an adversary could not impersonate a subscriber though.
+Still, in the military sense, this is a weakness.
+However,
+all this assumes that the database maintained by the \KDS/ accurately
+reflects the real-world.
+
+\item{3.} Multiple Recipients\hbreak
+It is possible, though not proven to the authors' knowledge,
+that the scheme used to avoid encrypting the body of a message more than once
+for multiple recipients might permit one of the recipients who is also an
+adversary to compromise the key relationship between the sender and another
+recipient.
+
+\item{} The scenario goes like this:
+When a message is being prepared for encryption,
+a single KD/IV/KA triple is generated to encrypt the body.
+Since the sender has a different key relationship with each recipient,
+each message sent is different, since the structure $m$ depends not only on
+the KD/IV/KA triple but also on the key relation between the sender and a
+particular recipient.
+Now suppose that one of the recipients, $r_1$,
+in addition to receiving the copy of the message meant for him/her also
+intercepts a copy of the message destined for another recipient, $r_2$.
+At this point,
+the recipient $r_1$ has both the plaintext and ciphertext version of the body,
+the plaintext version of the KD/IV/KA triple,
+and the ciphertext version of the KD/IV/KA triple that was generated using
+the key relationship between the sender and the recipient $r_2$.
+The question is:
+can $r_1$ now deduce the key relationship between the sender and $r_2$?
+
+\item{} If so, then the way that the \TMA/ attempts to minimize the use of
+encryption resources is a weakness.
+But, even if this is possible,
+given relatively short cryptoperiods for key relationships between \TMA/
+peers,
+this becomes a non-problem.
+
+\item{4.} Discussion Groups\hbreak
+As discussed earlier,
+the proposed method of associating a single \KDS/ ID with the membership of a
+discussion group does introduce a significant weakness for the security of
+messages sent to the discussion group.
+Since the \TMA/ does not assume a general broadcast facility,
+it appears that there are no good solutions to the problem of discussion
+group traffic.
+Of course,
+it is easy enough to simply send to each member of the group.
+
+\item{} For the sake of argument,
+let's assume that the discussion group has $n$ members.
+Now,
+since a different key relationship would exist between the sender and
+each of the $n$ recipients,
+the structure $m$ would be different for each recipient
+and so a different message would have to be sent to each recipient.
+To make matters worse,
+if one rejects the way the \TMA/ handles multiple recipients,
+not only does the \MTS/ get burdened with $n$ different messages,
+but the sender's \TMA/ gets burdened by having to encrypt
+the body of the message $n$ times.
+For meaningful values of $n$ (say on the order of~500, or even~25),
+the amount of resources required for any trusted discussion group are simply
+too costly.
+
+\subsection{Compromises, Compromises}
+Each of the possible weaknesses discussed above represent a compromise
+between the expense of the system and the level of security it can provide.
+
+The first two areas, if addressed by the \TMA/,
+could result in much less background information being available to an
+adversary.
+In an application where it is important that an adversary not know who is
+talking to whom,
+or who can talk at all,
+this is very important.
+It is the authors' position that in the commercial environment,
+this issue is not paramount.
+By ignoring the issue of traffic flow,
+the \TMA/ has a lot less work to do and the \MTS/ is kept clear of
+``useless'' messages.
+By keeping the information returned by the RUI and RIU MCLs in the clear,
+the complexity of the \TMA/ is significantly reduced.
+
+The second two areas, if addressed by the \TMA/,
+could result in a lesser probability of traffic being deciphered by an
+adversary.
+Regardless of the application,
+this is always extremely important.
+However,
+the authors' feel that the compromise made by the \TMA/ in these two issues
+is not substantial,
+and does not result in an explicit weakness when a message is sent to
+multiple recipients
+(note that when there is only a single recipient of a message,
+these two policies can not introduce weaknesses).
+In return, efficient use can be made of both the \MTS/ and the \TMA/ when
+messages are being sent to multiple recipients.
+Given scarce resources or large numbers of recipients,
+this approach may prove to be quite winning.
+
+Of course, much work remains to be done to prove the success of the \TMA/ in
+all four of these areas.
+
+\section{Acknowledgements}
+The prototype implementation described herein utilizes a public domain
+implementation of the DES algorithm\cite{DEA}
+which was originally implemented by James J.~Gillogly in May, 1977
+(who at that time was with the Rand Corporation,
+and is now affiliated with Gillogly Software).
+Interfaces to Dr.~Gillogly's implementation were subsequently coded by
+Richard W.~Outerbridge in September, 1984
+(who at that time was with the Computer Systems Research Institute
+at the University of Toronto,
+and is now affiliated with Perle Systems, Incorporated).
+
+The authors would like to acknowledge Dennis Branstad,
+Elaine Barker, and David Balensen of the National Bureau of Standards
+for their comments on the prototype system
+and insights on the ANSI draft\cite{FIKM}.
+In particular, Dr.~Branstad originally suggested the method used for
+encrypting a single message for multiple recipients under different keys.
+
+The authors (and all those who have read this paper) would like to thank
+Willis H.~Ware of the Rand Corporation,
+and Jonathon B.~Postel of the USC/Information Sciences Institute.
+Their extensive comments resulted in a much more readable paper.
+In addition,
+the authors would like to thank
+Dr. Stephen P.~Smith and Major Douglas A.~Brothers
+for their insightful comments.
projects / unix-history / commitdiff