RFC 1004

A Distributed-Protocol Authentication Scheme 🎀

Author: D.L. Mills, University of Delaware 🧑‍💻 Stream: Network Working Group ✨ Request for Comments: 1004 📜 Date: April 1987 📅 Category: not listed in the title block. The memo itself says the proposals are not intended as Internet standards at this time 💅 Obsoletes / Updates: neither is listed in the title block 🙈

---

Status of this Memo 📝

okay so the whole point of this one is to get everyone talking about authentication problems on the Internet and the ways we could actually fix them 🗣️ the proposed solutions are not standards for the Internet right now, so think of this as a conversation starter rather than a rulebook 💬 the hope is that a general consensus shows up eventually, and that leads to real standards down the line 🌈 distribution of this memo is unlimited, so share it with your whole group chat 💌

---

1. Introduction and Overview 🦋

okay so this doc suggests mediated access-control and authentication procedures for when an association needs to be set up between multiple users who belong to different trust environments but are running distributed protocols like the existing Exterior Gateway Protocol (EGP) [2], the proposed Dissimilar Gateway Protocol (DGP) [3], and similar ones 🌸 the procedures are evolved from the ones Needham and Shroeder described [5], just specialized for the distributed, multiple-user model these protocols use 💖

the trust model and threat environment are identical to the one Kent and others use [1], so it's giving "we're copying the best" energy ✨ an association is defined as the end-to-end network path between two users. the users themselves are secured, but the path between them is not 😤 the network might drop, duplicate, or deliver messages with errors. on top of that, a hostile user (host or gateway) might intercept, modify, and retransmit messages 💀 an association is kinda like a traditional connection, but without the usual connection requirements for error-free delivery 🧚 the users of the association are sometimes called associates 👯

here's the main idea 🔑 every association gets a random session key, and that key comes from an authentication server called the Cookie Jar 🍪 the Cookie Jar only lets sanctioned associations happen, and it does that even when the network is basically the wild west: arbitrary topologies, non-secured networks, broadcast-media networks, and hostile attackers all included 😭 the goal is not to hide the data (except private keys) moving across these networks. the goal is just to authenticate messages so nobody can spoof them or replay them 🫶

the procedures are built for distributed systems where each user i runs a common protocol automaton. that automaton keeps private state variables for each of possibly several associations running at the same time, one for each user j 🧩 an association kicks off when user i asks the Cookie Jar for a one-time key K(i,j). that key is used to encrypt the checksum that authenticates the messages exchanged between the users 🔐 then the initiator passes the key along to its associate as part of a connection establishment procedure, such as the one described in [3] 🎀

the info being exchanged in this model is mostly meant to get a distributed database to converge to specified contents (as far as is practical). it doesn't usually need reliable delivery of event occurrences, except to speed up convergence 🏃‍♀️ that means the model is naturally resistant to message loss or duplication ✨ when it matters, sequence numbers help reduce the impact of messages arriving out of order 🔢 the model assumes that associations between peers, once sanctioned, stay up indefinitely 💜 an association gets broken when there's a crash, loss of connectivity, or administrative action like reconfiguration or rekeying 🛠️ and finally, the rate of information exchange is deliberately much lower than what the network can nominally handle, which keeps the overhead low 🌿

---

2. Procedures 💅

each user i gets a public address A(i) and a private key K(i) through an out-of-band procedure that's beyond the scope of this discussion 🗝️ the address can take a lot of forms: an autonomous system identifier [2], an Internet address [6], or just an arbitrary name 🌍 no matter what form it takes, every message is presumed to carry both the sender and receiver addresses in its header 📬 each address and its access-control list is presumed to be in a public directory that everyone can access. the private key, though, is known only to the user and the Cookie Jar, and it never gets disclosed in messages exchanged between users or between users and the Cookie Jar 🤫

an association between i and j is identified by the bitstring made by catenating A(i) and A(j), together with a one-time key K(i,j). it looks like this: [A(i),A(j),K(i,j)] 🧵 the reciprocal association [A(j),A(i),K(j,i)] is only told apart by which associate calls the Cookie Jar first 👀 the intent in the protocol model is that all state variables and keys tied to a previous association get erased when a new association starts, and no caching (as suggested in [5]) is allowed 🧹

the one-time key K(i,j) is generated by the Cookie Jar when it gets a request from user i to associate with user j 🍪 the Cookie Jar has access to a private table of entries in the form [A(i),K(i)], where i covers the set of sanctioned users. the public directory includes, for each A(i), a list L(i) = {j1, j2, ...} of permitted associates for i, and only the Cookie Jar can update it 📖 the Cookie Jar first checks that the requested user j is in L(i). then it rolls a random number for K(i,j) and returns it to the requestor, which saves it and passes it along to its associate during the connection establishment procedure 🎁

in the diagrams that follow, all fields that aren't specifically mentioned are unencrypted. the natural implementation would include the address fields of the message header in the checksum, but that raises big difficulties, since those fields may be needed to figure out the route through the network itself 🗺️ as you'll see below, even if a perpetrator could tamper with the address fields to get messages misdelivered, the result still wouldn't be a useful association 🙅‍♀️

the checksum field is computed by an algorithm that uses all the bits in the message, including the address fields in the message header. then it's ordinarily encrypted along with the sequence-number field, using an appropriate algorithm and the specified key. that way, the intended receiver is assured that only the intended sender could have generated it 🔏 in the Internet system, the natural choice for checksum is the 16-bit, ones-complement algorithm [6], and the natural choice for encryption is the DES algorithm [4]. the discussion that follows goes further into these points 💭 here are the detailed procedures ✨

1. the requestor i rolls a random message ID I and sends it, along with the association specifier [A(i),A(j)], as a request to the Cookie Jar 📨 the message header includes the addresses [A(i),A(C)], where A(C) is the address of the Cookie Jar. here's the schematic:

+-----------+-----------+
|   A(i)    |   A(C)    |       message header
+-----------+-----------+
|     I     | checksum  |       message ID
+-----------+-----------+
|   A(i)    |   A(j)    |       assoc specifier
+-----------+-----------+

2. the Cookie Jar checks the access list to see whether the association [A(i),A(j)] is valid 🔍 if it is, the Cookie Jar rolls a random number K(i,j) and builds the reply below. it checksums the message, encrypts the j cookie field with K(j), then encrypts that along with the other indicated fields using K(i), and finally sends the reply 💌

+-----------+-----------+
|   A(C)    |   A(i)    |       message header
+-----------+-----------+
|     I     | checksum  |       message ID (encrypt K(i))
+-----------+-----------+
|   K(i,j)  |                   i cookie (encrypt K(i))
+-----------+
|   K(i,j)  |                   j cookie (encrypt K(j)K(i))
+-----------+

3. when the reply arrives, the requestor i decrypts the indicated fields and saves the (encrypted) j cookie field. then it copies the i cookie field into the j cookie field, so both cookie fields are now the original K(i,j) that the Cookie Jar provided 🍪✨ next it verifies the checksum and matches the message ID against its list of outstanding requests, keeping K(i,j) for its own use. then it rolls a random number X for the j cookie field (to confuse wiretappers 😈) and another I' for the (initial) message ID, and recomputes the checksum. finally, it inserts the saved j cookie field into the i cookie field, encrypts the message ID fields with K(i,j), and sends this message to its associate 🚀

+-----------+-----------+
|   A(i)    |   A(j)    |       message header
+-----------+-----------+
|     I'    | checksum  |       message ID (encrypt K(i,j))
+-----------+-----------+
|  K(i,j)   |                   i cookie (encrypt K(j))
+-----------+
|     X     |                   j cookie (noise)
+-----------+

4. when the message above arrives, the associate j decrypts the i cookie field and uses it to decrypt the message ID fields. then it verifies the checksum and keeps I' and K(i,j) for later use 🧠 finally, it rolls a random number J' as its own initial message ID, inserts it and the checksum into the confirm message, encrypts the message ID fields with K(i,j), and sends the message 🎉

+-----------+-----------+
|   A(j)    |   A(i)    |       message header
+-----------+-----------+
|     J'    | checksum  |       message ID (encrypt K(i,j))
+-----------+-----------+

5. every message after that is coded the same way 🔁 as new data is generated, the message ID gets incremented, a new checksum is computed, and the message ID fields are encrypted with K(i,j). the receiver decrypts the message ID fields with K(i,j) and discards the message if the checksum or sequence number is incorrect 🗑️ no drama, just vibes 💜

3. Discussion ✨

okay bestie, the access lists are considered public read-only 📖, so there's no need to validate Cookie Jar requests. nothing to guard there 💅. a perpetrator (the villain 😈) might intercept, modify and replay portions of Cookie Jar replies or subsequent messages between the associates. BUT presuming the perpetrator doesn't know the keys, the tampered messages fail the checksum test and get tossed 🗑️. iconic.

ngl the "natural" pick of Internet checksum algorithm and DES encryption should be reconsidered 🤔. the Internet checksum has a few well-known vulnerabilities, including invariance to word order and byte swap. and the checksum field is only sixteen bits wide, so a determined perpetrator might be able to find the key just by checking all possible permutations of the checksum field 😭. however, these procedures aren't meant to make up for weaknesses in the checksum algorithm, since that vulnerability exists whether authentication is used or not. also, the encrypted fields include the sequence number as well as the checksum. in EGP and the proposed DGP the sequence number is a sixteen-bit quantity that increments for each successive message, which makes tampering even more difficult 🔒.

in the intended application to EGP, DGP and similar protocols, associations may have an indefinite lifetime, although messages may be sent between associates pretty infrequently 🦋. so every association should be rekeyed occasionally, and either associate can do it by simply sending a new request to the Cookie Jar and following the above procedure. to protect against stockpiling private user keys, each user should be rekeyed occasionally too, which is basically like changing passwords 🔑. the mechanisms for doing this are beyond the scope of this proposal.

the private user keys are never disclosed, except to the Cookie Jar. that's the whole point of the scheme ✨

this is why two cookies are used: one for i, which only it can decrypt, and one for j, which gets decrypted first by i and then by j, and only then is valid 🎀. an interceptor posing as i and playing back the Cookie Jar reply to j will get caught, since the message fails the checksum test 🙅‍♀️. a perpetrator with access to both the Cookie Jar reply to i and the subsequent message to j will just see essentially a random permutation of all fields 🌀. in all messages except the first one to the Cookie Jar, the checksum field is encrypted, which makes it hard to recover the original contents of the cookie fields before encryption by exploiting the properties of the checksum algorithm itself 💜.

the addresses in the message headers are included in the checksum, which protects against playbacks with modified addresses 🙌. however, it may still be possible to destabilize an association by playing back unmodified messages from prior associations. there are several possibilities:

1. replays of the Cookie Jar messages 1 and 2 are unlikely to cause damage, since the requestor matches both the addresses and the once-only sequence number against its list of pending requests.
2. replays of message 3 may cause user j to falsely assume a new association. user j will return message 4 encrypted with the assumed session key, which might be an old one or even a currently valid one, but with an invalid sequence number. either way, user i will ignore message 4 🙄.
3. replays of message 4 or subsequent messages are unlikely to cause damage, since the sequence check will eliminate them.

the second point above is a legit concern 🚨, since a determined attacker may stockpile message 3 interceptions and replay them at speed. the attack is unlikely to succeed in establishing a working association, but it might produce frequent timeouts and result in denial of service 💀. in the Needham-Shroeder scheme this problem is avoided by requiring an additional challenge involving a message sent by user j and a reply sent by user i, which amounts to a three-way handshake 🤝.

however, even with a three-way handshake, the extra protocol overhead induced by a determined attacker may still result in denial of service. plus, the protocol model is inherently resistant to poor network performance, which has the same performance signature as the attacker 😤. the conclusion? the extra expense and overhead of a three-way handshake is unjustified. periodt 💅.

---

4. Application to EGP and DGP 🧚

this scheme can be incorporated into the Exterior Gateway Protocol (EGP) [2] and Dissimilar Gateway Protocol (DGP) [3] models by adding the fields above to the Request and Confirm messages in a straightforward way. an example of how this might be done is given in [3] 📝. to keep the state machine correct, it's convenient to treat the Cookie Jar reply as a Start event, with the understanding that the Cookie Jar request is an extrinsic event that evokes that response 🌸.

the neighbor-acquisition strategy intended for the Dissimilar Gateway Protocol DGP follows the strategy in EGP. the stability of the EGP state machine, which DGP uses with minor modifications, was verified by state simulation and discussed in an appendix to [2] 👑. either associate can send a Request command at any time, which causes both the sender and the receiver to reinitialize all state information and send a Confirm response. in DGP the Request operation involves the Cookie Jar transaction (messages 1 and 2) and then the Request command itself (message 3). in DGP the keys are reinitialized as well, and each retransmission of a Request command is separately authenticated 🔁.

in DGP the Request command (message 3) and all subsequent message exchanges assume the keys provided by the Cookie Jar. using any other keys results in checksum discrepancies and discarded messages 🗑️. so the sender knows its command has been effected, at least at the time the response was sent. if either associate lost its state variables after that time, it would ignore subsequent messages, and it (or its associate) would eventually time out and reinitiate the whole procedure ⏰.

if both associates try to authenticate at the same time, their authentication sequences may cross in the network 🌀. the Request message is self-authenticating, so if a Request command is received by an associate before the Confirm response to an earlier Request command sent by that associate, the keys would be reset. so when the subsequent Confirm response does arrive, it gets disregarded, and the Request command is resent following a timeout. the race can only be broken when, thanks to staggered timeouts, the sequences don't cross in the network 🏃‍♀️. this is a little more complicated than EGP and does mean more attention must be paid to the timeouts 🫶.

a reliable dis-association is a slippery concept, as TCP and its closing sequences show 😵. the protocol model here is much less demanding, though. the usual way an EGP association is dissolved is when one associate sends a Cease command to the other, which then sends back a Cease-ack response. however, this is specifically assumed to be a non-reliable transaction, with timeouts specified to break retry loops. in any case, a new Request command will erase all history and result in a new association as described above ✨.

other than the above, the only way to reliably dis-associate is by timeout ⏳. in this protocol model the associates engage in a reachability protocol, which requires each to send a message to the other from time to time. each associate individually times out after a period when no messages are heard from the other 🦋.

---

5. Acknowledgments 🫶

Dan Nessett and Phil Karn both provided valuable ideas and comments on early drafts of this report 💖. Steve Kent and Dennis Perry both provided valuable advice on its review strategy 🌈.

---

6. References 📚

[1] Kent, S.T., "Encryption-Based Protection for Interactive User/Computer Communication", Proc. Fifth Data Communications Symposium, September 1977.

[2] Mills, D.L., "Exterior Gateway Protocol Formal Specification", DARPA Network Working Group Report RFC-904, M/A-COM Linkabit, April 1984.

[3] Mills, D.L., "Dissimilar Gateway Protocol Draft Specification", in preparation, University of Delaware.

[4] National Bureau of Standards, "Data Encryption Standard", Federal Information Processing Standards Publication 46, January 1977.

[5] Needham, R.M., and M.D. Schroeder, "Using Encryption for Authentication in Large Networks of Computers", Communications of the ACM, Vol. 21, No. 12, pp. 993-999, December 1978.

[6] Postel, J., "Internet Protocol", DARPA Network Working Group Report RFC-791, USC Information Sciences Institute, September 1981.