home *** CD-ROM | disk | FTP | other *** search
/ Unix System Administration Handbook 1997 October / usah_oct97.iso / rfc / 1000s / rfc1004.txt < prev    next >
Text File  |  1987-04-20  |  21KB  |  451 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                         D.L. Mills
  8. Request for Comments:  1004                       University of Delaware
  9.                                                               April 1987
  10.  
  11.  
  12.               A Distributed-Protocol Authentication Scheme
  13.  
  14.  
  15. Status of this Memo
  16.  
  17.    The purpose of this RFC is to focus discussion on authentication
  18.    problems in the Internet and possible methods of solution.  The
  19.    proposed solutions this document are not intended as standards for
  20.    the Internet at this time.  Rather, it is hoped that a general
  21.    consensus will emerge as to the appropriate solution to
  22.    authentication problems, leading eventually to the adoption of
  23.    standards.  Distribution of this memo is unlimited.
  24.  
  25.  
  26. 1. Introduction and Overview
  27.  
  28.    This document suggests mediated access-control and authentication
  29.    procedures suitable for those cases when an association is to be set
  30.    up between multiple users belonging to different trust environments,
  31.    but running distributed protocols like the existing Exterior Gateway
  32.    Protocol (EGP) [2], proposed Dissimilar Gateway Protocol (DGP) [3]
  33.    and similar protocols. The proposed prcedures are evolved from those
  34.    described by Needham and Shroeder [5], but specialized to the
  35.    distributed, multiple-user model typical of these protocols.
  36.  
  37.    The trust model and threat environment are identical to that used by
  38.    Kent and others [1]. An association is defined as the end-to-end
  39.    network path between two users, where the users themselves are
  40.    secured, but the path between them is not. The network may drop,
  41.    duplicate or deliver messages with errors. In addition, it is
  42.    possible that a hostile user (host or gateway) might intercept,
  43.    modify and retransmit messages. An association is similar to the
  44.    traditional connection, but without the usual connection requirements
  45.    for error-free delivery.  The users of the association are sometimes
  46.    called associates.
  47.  
  48.    The proposed procedures require each association to be assigned a
  49.    random session key, which is provided by an authentication server
  50.    called the Cookie Jar. The procedures are designed to permit only
  51.    those associations sanctioned by the Cookie Jar while operating over
  52.    arbitrary network topologies, including non-secured networks and
  53.    broadcast-media networks, and in the presence of hostile attackers.
  54.    However, it is not the intent of these procedures to hide the data
  55.  
  56.  
  57.  
  58. Mills                                                           [Page 1]
  59.  
  60. RFC 1004                                                      April 1987
  61.  
  62.  
  63.    (except for private keys) transmitted via these networks, but only to
  64.    authenticate messages to avoid spoofing and replay attacks.
  65.  
  66.    The procedures are intended for distributed systems where each user i
  67.    runs a common protocol automaton using private state variables for
  68.    each of possibly several associations simultaneously, one for each
  69.    user j. An association is initiated by interrogating the Cookie Jar
  70.    for a one-time key K(i,j), which is used to encrypt the checksum
  71.    which authenticates messages exchanged between the users. The
  72.    initiator then communicates the key to its associate as part of a
  73.    connection establishment procedure such as described in [3].
  74.  
  75.    The information being exchanged in this protocol model is largely
  76.    intended to converge a distributed data base to specified (as far as
  77.    practical) contents, and does not ordinarily require a reliable
  78.    distribution of event occurances, other than to speed the convergence
  79.    process. Thus, the model is intrinsically resistant to message loss
  80.    or duplication. Where important, sequence numbers are used to reduce
  81.    the impact of message reordering. The model assumes that associations
  82.    between peers, once having been sanctioned, are maintained
  83.    indefinitely.  The exception when an association is broken may be due
  84.    to a crash, loss of connectivity or administrative action such as
  85.    reconfiguration or rekeying. Finally, the rate of information
  86.    exchange is specifically designed to be much less than the nominal
  87.    capabilities of the network, in order to keep overheads low.
  88.  
  89.  
  90. 2. Procedures
  91.  
  92.    Each user i is assigned a public address A(i) and private key K(i) by
  93.    an out-of-band procedure beyond the scope of this discussion. The
  94.    address can take many forms: an autonomous system identifier [2], an
  95.    Internet address [6] or simply an arbitrary name. However, no matter
  96.    what form it takes, every message is presumed to carry both the
  97.    sender and receiver addresses in its header. Each address and its
  98.    access-control list is presumed available in a public directory
  99.    accessable to all users, but the private key is known only to the
  100.    user and Cookie Jar and is not disclosed in messages exchanged
  101.    between users or between users and the Cookie Jar.
  102.  
  103.    An association between i and j is identified by the bitstring
  104.    consisting of the catenation of the addresses A(i) and A(j), together
  105.    with a one-time key K(i,j), in the form [A(i),A(j),K(i,j)]. Note that
  106.    the reciprocal association [A(j),A(i),K(j,i)] is distinguished only
  107.    by which associate calls the Cookie Jar first. It is the intent in
  108.    the protocol model that all state variables and keys relevant to a
  109.    previous association be erased when a new association is initiated
  110.    and no caching (as suggested in [5]) is allowed.
  111.  
  112.  
  113.  
  114. Mills                                                           [Page 2]
  115.  
  116. RFC 1004                                                      April 1987
  117.  
  118.  
  119.    The one-time key K(i,j) is generated by the Cookie Jar upon receipt
  120.    of a request from user i to associate with user j. The Cookie Jar has
  121.    access to a private table of entries in the form [A(i),K(i)], where i
  122.    ranges over the set of sanctioned users. The public directory
  123.    includes for each A(i) a list L(i) = {j1, j2, ...} of permitted
  124.    associates for i, which can be updated only by the Cookie Jar. The
  125.    Cookie Jar first checks that the requested user j is in L(i), then
  126.    rolls a random number for K(i,j) and returns this to the requestor,
  127.    which saves it and passes it along to its associate during the
  128.    connection establishment procedure.
  129.  
  130.    In the diagrams that follow all fields not specifically mentioned are
  131.    unencrypted. While the natural implementation would include the
  132.    address fields of the message header in the checksum, this raises
  133.    significant difficulties, since they may be necessary to determine
  134.    the route through the network itself. As will be evident below, even
  135.    if a perpetrator could successfully tamper with the address fields in
  136.    order to cause messages to be misdelivered, the result would not be a
  137.    useful association.
  138.  
  139.    The checksum field is computed by a algorithm using all the bits in
  140.    the message including the address fields in the message header, then
  141.    is ordinarily encrypted along with the sequence-number field by an
  142.    appropriate algorithm using the specified key, so that the intended
  143.    receiver is assured only the intended sender could have generated it.
  144.    In the Internet system, the natural choice for checksum is the 16-
  145.    bit, ones-complement algorithm [6], while the natural choice for
  146.    encryption is the DES algorithm [4] (see the discussion following for
  147.    further consideration on these points). The detailed procedures are
  148.    as follows:
  149.  
  150.       1. The requestor i rolls a random message ID I and sends it and
  151.       the association specifier [A(i),A(j)] as a request to the Cookie
  152.       Jar. The message header includes the addresses [A(i),A(C)], where
  153.       A(C) is the address of the Cookie Jar. The following schematic
  154.       illustrates the result:
  155.  
  156.       +-----------+-----------+
  157.       |   A(i)    |   A(C)    |       message header
  158.       +-----------+-----------+
  159.       |     I     | checksum  |       message ID
  160.       +-----------+-----------+
  161.       |   A(i)    |   A(j)    |       assoc specifier
  162.       +-----------+-----------+
  163.  
  164.       2. The Cookie Jar checks the access list to determine if the
  165.       association [A(i),A(j)] is valid. If so, it rolls a random number
  166.       K(i,j) and constructs the reply below. It checksums the message,
  167.  
  168.  
  169.  
  170. Mills                                                           [Page 3]
  171.  
  172. RFC 1004                                                      April 1987
  173.  
  174.  
  175.       encrypts the j cookie field with K(j), then encrypts it and the
  176.       other fields indicated with K(i) and finally sends the reply:
  177.  
  178.       +-----------+-----------+
  179.       |   A(C)    |   A(i)    |       message header
  180.       +-----------+-----------+
  181.       |     I     | checksum  |       message ID (encrypt K(i))
  182.       +-----------+-----------+
  183.       |   K(i,j)  |                   i cookie (encrypt K(i))
  184.       +-----------+
  185.       |   K(i,j)  |                   j cookie (encrypt K(j)K(i))
  186.       +-----------+
  187.  
  188.       3. Upon receipt of the reply the requestor i decrypts the
  189.       indicated fields, saves the (encrypted) j cookie field and copies
  190.       the i cookie field to the j cookie field, so that both cookie
  191.       fields are now the original K(i,j) provided by the Cookie Jar.
  192.       Then it verifies the checksum and matches the message ID with its
  193.       list of outstanding requests, retaining K(i,j) for its own use. It
  194.       then rolls a random number X for the j cookie field (to confuse
  195.       wiretappers) and another I' for the (initial) message ID, then
  196.       recomputes the checksum.  Finally, it inserts the saved j cookie
  197.       field in the i cookie field, encrypts the message ID fields with
  198.       K(i,j) and sends the following message to its associate:
  199.  
  200.       +-----------+-----------+
  201.       |   A(i)    |   A(j)    |       message header
  202.       +-----------+-----------+
  203.       |     I'    | checksum  |       message ID (encrypt K(i,j))
  204.       +-----------+-----------+
  205.       |  K(i,j)   |                   i cookie (encrypt K(j))
  206.       +-----------+
  207.       |     X     |                   j cookie (noise)
  208.       +-----------+
  209.  
  210.       4. Upon receipt of the above message the associate j decrypts the
  211.       i cookie field, uses it to decrypt the message ID fields and
  212.       verifies the checksum, retaining the I' and K(i,j) for later use.
  213.       Finally, it rolls a random number J' as its own initial message
  214.       ID, inserts it and the checksum in the confirm message, encrypts
  215.       the message ID fields with K(i,j) and sends the message:
  216.  
  217.       +-----------+-----------+
  218.       |   A(j)    |   A(i)    |       message header
  219.       +-----------+-----------+
  220.       |     J'    | checksum  |       message ID (encrypt K(i,j))
  221.       +-----------+-----------+
  222.  
  223.  
  224.  
  225.  
  226. Mills                                                           [Page 4]
  227.  
  228. RFC 1004                                                      April 1987
  229.  
  230.  
  231.       5. Subsequent messages are all coded in the same way. As new data
  232.       are generated the message ID is incremented, a new checksum
  233.       computed and the message ID fields encrypted with K(i,j). The
  234.       receiver decrypts the message ID fields with K(i,j) and discards
  235.       the message in case of incorrect checksum or sequence number.
  236.  
  237.  
  238. 3. Discussion
  239.  
  240.    Since the access lists are considered public read-only, there is no
  241.    need to validate Cookie Jar requests. A perpetrator might intercept,
  242.    modify and replay portions of Cookie Jar replies or subsequent
  243.    messages exchanged between the associates. However, presuming the
  244.    perpetrator does not know the keys involved, tampered messages would
  245.    fail the checksum test and be discarded.
  246.  
  247.    The "natural" selection of Internet checksum algorithm and DES
  248.    encryption should be reconsidered. The Internet checksum has several
  249.    well-known vulnerabilities, including invariance to word order and
  250.    byte swap. In addition, the checksum field itself is only sixteen
  251.    bits wide, so a determined perpetrator might be able to discover the
  252.    key simply by examining all possible permutations of the checksum
  253.    field. However, the procedures proposed herein are not intended to
  254.    compensate for weaknesses of the checksum algorithm, since this
  255.    vulnerability exists whether authentication is used or not. Also note
  256.    that the encrypted fields include the sequence number as well as the
  257.    checksum. In EGP and the proposed DGP the sequence number is a
  258.    sixteen-bit quantity and increments for each successive message,
  259.    which makes tampering even more difficult.
  260.  
  261.    In the intended application to EGP, DGP and similar protocols
  262.    associations may have an indefinite lifetime, although messages may
  263.    be sent between associates on a relatively infrequent basis.
  264.    Therefore, every association should be rekeyed occasionally, which
  265.    can be done by either associate simply by sending a new request to
  266.    the Cookie Jar and following the above procedure. To protect against
  267.    stockpiling private user keys, each user should be rekeyed
  268.    occasionally, which is equivalent to changing passwords. The
  269.    mechanisms for doing this are beyond the scope of this proposal.
  270.  
  271.    It is a feature of this scheme that the private user keys are not
  272.    disclosed, except to the Cookie Jar. This is why two cookies are
  273.    used, one for i, which only it can decrypt, and the other for j,
  274.    decrypted first by i and then by j, which only then is valid. An
  275.    interceptor posing as i and playing back the Cookie Jar reply to j
  276.    will be caught, since the message will fail the checksum test. A
  277.    perpetrator with access to both the Cookie Jar reply to i and the
  278.    subsequent message to j will see essentially a random permutation of
  279.  
  280.  
  281.  
  282. Mills                                                           [Page 5]
  283.  
  284. RFC 1004                                                      April 1987
  285.  
  286.  
  287.    all fields. In all except the first message to the Cookie Jar, the
  288.    checksum field is encrypted, which makes it difficult to recover the
  289.    original contents of the cookie fields before encryption by
  290.    exploiting the properties of the checksum algorithm itself.
  291.  
  292.    The fact that the addresses in the message headers are included in
  293.    the checksum protects against playbacks with modified addresses.
  294.    However, it may still be possible to destabilize an association by
  295.    playing back unmodified messages from prior associations. There are
  296.    several possibilities:
  297.  
  298.       1. Replays of the Cookie Jar messages 1 and 2 are unlikely to
  299.       cause damage, since the requestor matches both the addresses and
  300.       once-only sequence number with its list of pending requests.
  301.  
  302.       2. Replays of message 3 may cause user j to falsely assume a new
  303.       association. User j will return message 4 encrypted with the
  304.       assumed session key, which might be an old one or even a currently
  305.       valid one, but with invalid sequence number. Either way, user i
  306.       will ignore message 4.
  307.  
  308.       3. Replays of message 4 or subsequent messages are unlikely to
  309.       cause damage, since the sequence check will eliminate them.
  310.  
  311.    The second point above represents an issue of legitimate concern,
  312.    since a determined attacker may stockpile message 3 interceptions and
  313.    replay them at speed. While the attack is unlikely to succeed in
  314.    establishing a working association, it might produce frequent
  315.    timeouts and result in denial of service. In the Needham-Shroeder
  316.    scheme this problem is avoided by requiring an additional challenge
  317.    involving a message sent by user j and a reply sent by user i, which
  318.    amounts to a three-way handshake.
  319.  
  320.    However, even if a three-way handshake were used, the additional
  321.    protocol overhead induced by a determined attacker may still result
  322.    in denial of service; moreover, the protocol model is inherently
  323.    resistant to poor network performance, which has the same performance
  324.    signature as the attacker. The conclusion is that the additional
  325.    expense and overhead of a three-way handshake is unjustified.
  326.  
  327.  
  328. 4. Application to EGP and DGP
  329.  
  330.    This scheme can be incorporated in the Exterior Gateway Protocol
  331.    (EGP) [2] and Dissimilar Gateway Protocol (DGP) [3] models by adding
  332.    the fields above to the Request and Confirm messages in a
  333.    straightforward way. An example of how this might be done is given in
  334.    [3]. In order to retain the correctness of the state machine, it is
  335.  
  336.  
  337.  
  338. Mills                                                           [Page 6]
  339.  
  340. RFC 1004                                                      April 1987
  341.  
  342.  
  343.    convenient to treat the Cookie Jar reply as a Start event, with the
  344.    understanding that the Cookie Jar request represents an extrinsic
  345.    event which evokes that response.
  346.  
  347.    The neighbor-acquisition strategy intended in the Dissimilar Gateway
  348.    Protocol DGP follows the strategy in EGP. The stability of the EGP
  349.    state machine, used with minor modifications by DGP, was verified by
  350.    state simulation and discussed in an appendix to [2]. Either
  351.    associate can send a Request command at any time, which causes both
  352.    the sender and the receiver to reinitialize all state information and
  353.    send a Confirm response. In DGP the Request operation involves the
  354.    Cookie Jar transaction (messages 1 and 2) and then the Request
  355.    command itself (message 3). In DGP the keys are reinitialized as well
  356.    and each retransmission of a Request command is separately
  357.    authenticated.
  358.  
  359.    In DGP the Request command (message 3) and all subsequent message
  360.    exchanges assume the keys provided by the Cookie Jar. Use of any
  361.    other keys results in checksum discrepancies and discarded messages.
  362.    Thus the sender knows its command has been effected, at least at the
  363.    time the response was sent. If either associate lost its state
  364.    variables after that time, it would ignore subsequent messages and it
  365.    (or its associate) would eventually time out and reinitiate the whole
  366.    procedure.
  367.  
  368.    If both associates attempt to authenticate at the same time, they may
  369.    wind up with the authentication sequences crossing in the network.
  370.    Note that the Request message is self-authenticating, so that if a
  371.    Request command is received by an associate before the Confirm
  372.    response to an earlier Request command sent by that associate, the
  373.    keys would be reset.  Thus when the subsequent Confirm response does
  374.    arrive, it will be disregarded and the Request command resent
  375.    following timeout. The race that results can only be broken when, due
  376.    to staggered timeouts, the sequences do not cross in the network.
  377.    This is a little more complicated than EGP and does imply that more
  378.    attention must be paid to the timeouts.
  379.  
  380.    A reliable dis-association is a slippery concept, as example TCP and
  381.    its closing sequences. However, the protocol model here is much less
  382.    demanding. The usual way an EGP association is dissolved is when one
  383.    associate sends a Cease command to the other, which then sends a
  384.    Cease-ack response; however, this is specifically assumed a non-
  385.    reliable transaction, with timeouts specified to break retry loops.
  386.    In any case, a new Request command will erase all history and result
  387.    in a new association as described above.
  388.  
  389.    Other than the above, the only way to reliably dis-associate is by
  390.    timeout. In this protocol model the associates engage in a
  391.  
  392.  
  393.  
  394. Mills                                                           [Page 7]
  395.  
  396. RFC 1004                                                      April 1987
  397.  
  398.  
  399.    reachability protocol, which requires each to send a message to the
  400.    other from time to time. Each associate individually times out after
  401.    a period when no messages are heard from the other.
  402.  
  403.  
  404. 5. Acknowledgments
  405.  
  406.    Dan Nessett and Phil Karn both provided valuable ideas and comments
  407.    on early drafts of this report. Steve Kent and Dennis Perry both
  408.    provided valuable advice on its review strategy.
  409.  
  410.  
  411. 6. References
  412.  
  413.  
  414.    [1]  Kent, S.T., "Encryption-Based Protection for Interactive
  415.         User/Computer Communication", Proc. Fifth Data Communications
  416.         Symposium, September 1977.
  417.  
  418.  
  419.    [2]  Mills, D.L., "Exterior Gateway Protocol Formal Specification",
  420.         DARPA Network Working Group Report RFC-904, M/A-COM Linkabit,
  421.         April 1984.
  422.  
  423.  
  424.    [3]  Mills, D.L., "Dissimilar Gateway Protocol Draft Specification",
  425.         in preparation, University of Delaware.
  426.  
  427.  
  428.    [4]  National Bureau of Standards, "Data Encryption Standard",
  429.         Federal Information Processing Standards Publication 46, January
  430.         1977.
  431.  
  432.  
  433.    [5]  Needham, R.M., and M.D. Schroeder, "Using Encryption for
  434.         Authentication in Large Networks of Computers", Communications
  435.         of the ACM, Vol. 21, No. 12, pp. 993-999, December 1978.
  436.  
  437.  
  438.    [6]  Postel, J., "Internet Protocol", DARPA Network Working Group
  439.         Report RFC-791, USC Information Sciences Institute, September
  440.         1981.
  441.  
  442.  
  443.  
  444.  
  445.  
  446.  
  447.  
  448.  
  449.  
  450. Mills                                                           [Page 8]
  451.