[Search] [txt|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
INTERNET-DRAFT                                                   G Brown
draft-petke-mech-00.txt                                       CompuServe
Expires: 15-May-97                                      15 November 1996

                    Remote Passphrase Authentication
                        Part Two:  The Mechanism

Status of this Memo

   This document is an Internet-Draft.  Internet-Drafts are working
   documents of the Internet Engineering Task Force (IETF), its
   areas, and its working groups.  Note that other groups may also
   distribute working documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six
   months and may be updated, replaced, or obsoleted by other
   documents at any time.  It is inappropriate to use Internet-
   Drafts as reference material or to cite them other than as
   "work in progress."

   To learn the current status of any Internet-Draft, please check
   the "1id-abstracts.txt" listing contained in the Internet-
   Drafts Shadow Directories on ftp.is.co.za (Africa),
   nic.nordu.net (Europe), munnari.oz.au (Pacific Rim),
   ds.internic.net (US East Coast), or ftp.isi.edu (US West Coast).


   Remote Passphrase Authentication provides a way to authenticate a
   user to a service by using a pass phrase over an insecure network,
   without revealing the pass phrase to eavesdroppers. In addition, the
   service need not know and does not learn the user's pass phrase,
   making this scheme useful in distributed environments where it would
   be difficult or inappropriate to trust a service with a pass phrase
   database or to allow the server to learn enough to masquerade as the
   user in a future authentication attempt.

   This draft is part two of a four part series and explains the
   mechanism behind RPA.  Part one of this series
   (draft-petke-ext-intro-00.txt) provides an extended introduction to
   the problems of authentication over insecure networks.  Part three
   (draft-petke-http-auth-scheme-00.txt) explains how to incorporate the
   mechanism into HTTP.  Part four
   (draft-petke-serv-deity-protocol-00.txt) explains the protocol
   between the service and deity.

   This scheme was inspired by Dave Raggett's Mediated Digest
   Authentication paper.

G Brown                                                         [Page 1]

INTERNET-DRAFT              RPA - Part Two              15 November 1996

Table of Contents




   4.1.1 Values and their representation
   4.1.2 The authentication process



1. Introduction

   In this mechanism, we'll authenticate a user to a service and vice
   versa. We'll use pass phrases--actually, they're 128-bit shared
   secrets, but we'll define a way to use textual phrases--so the goal
   is to prove to the service that you know your pass phrase, and vice

   Of course, it's important not to reveal the pass phrase to an
   eavesdropper. It is equally important not to reveal the pass phrase
   to a spoofer.

   Furthermore, the mechanism should work even if the service does not
   know the user's pass phrase. In a distributed environment, with many
   services that wish to authenticate the same set of users, it may be
   difficult to make users' pass phrases available to all services. And
   we might prefer not to do that, if we don't completely trust the
   services. So, not only should the service not have to know the user's
   pass phrase, but the service should not learn the user's pass phrase
   during the authentication process.

   On the other hand, the mechanism should be simple enough to apply
   even in the traditional case where the service knows the user's pass
   phrase; there's no need to use a different mechanism in that case.

   Part one of this specification (draft-petke-ext-intro-00.txt)
   contains an extended introduction that explains the problem and
   various potential solutions and their problems, leading to this
   mechanism. If you find yourself asking, "Why not just...," it might

G Brown                                                         [Page 2]

INTERNET-DRAFT              RPA - Part Two              15 November 1996

   be worth reading part one to see if that explains it. However, it
   contains only background material, so you needn't read part one
   before reading the rest of this specification.

2. Terminology

   Throughout this specification we'll speak of a "user" communicating
   with a "service" that wishes to learn and authenticate the user's
   identity. Often, the user is a "client" and the service is a
   "server," but those terms refer to an implementation.

   The "deity" knows the users' and services' pass phrases, and the
   service talks to the deity during the authentication process.
   Although the term "authentication server" is more conventional, we
   call it a deity because it's got fewer syllables and the term
   "server" is overloaded. If the service knows the pass phrases, then
   it acts as its own deity, simplifying the implementation but
   otherwise having no effect on the mechanism.

   Identities exist in some "realm," and we use that term in its usual
   sense. We often think of a realm as being a relatively large
   collection of users, like compuserve.com or aol.com, but it might
   well consist of a small set of users, e.g., user names and pass
   phrases associated with an individual Web server. We allow the
   service to specify a set of realms, to recognize an identity in any
   of the realms in which it participates.

3. Design criteria

   This authentication mechanism is intended to meet the following

   * The service learns and authenticates the user's identity.

   * The user learns and authenticates the service's identity.

   * The mechanism does not use public-key technology.

   * The mechanism does not use encryption. (By encryption, we're
     referring to reversible encryption, the ability to encrypt
     something and later decrypt it. By avoiding encryption, we avoid
     restrictions on exportability.)

   * The mechanism is based on shared secrets: "pass phrases," although
     they can be arbitrary bit patterns rather than text.

   * Neither the user nor the service needs to know the other's pass

G Brown                                                         [Page 3]

INTERNET-DRAFT              RPA - Part Two              15 November 1996

   * Neither the user nor the service nor eavesdroppers will learn the
     other's pass phrase. However, if the pass phrase is based on text,
     it's important to choose a "good" pass phrase to avoid a dictionary

   * The mechanism is reasonably easy to implement in clients and does
     not require the client to communicate with a third party nor to a
     possess a reliable clock.

   * The mechanism derives a shared secret that may be used as a session
     key for subsequent authentication.

   * The mechanism may be incorporated into almost any protocol. In
     other words, the mechanism is not designed around a protocol; the
     protocol is designed around the mechanism. But the mechanism must
     be suitable for incorporation into protocols like HTTP.

   * The mechanism provides the ability to accept an identity in any of
     a set of realms in which the user and service are members.

4. The Mechanism

   This authentication mechanism consists of three related processes:
   authentication, reauthentication, and reauthentication cheating.

   Authentication is the fundamental process by which a user and a
   service mutually authenticate one another within one of a set of
   realms, without revealing their pass phrases to one another.

   Reauthentication is a process by which a user and service, having
   recently authenticated one another, may again authenticate one
   another. They could, of course, simply repeat the authentication
   process, but that requires interaction with an authentication deity.
   The reauthentication process is faster, requiring no communication
   with a third party. Reauthentication is useful when multiple
   connections between the user and service are established, whether
   sequential as in HTTP or simultaneous. Each connection must be
   authenticated, but the reauthentication process provides a shortcut.

   Reauthentication cheating is a further optimization for HTTP, a
   protocol that is quite unfriendly to challenge-response mechanisms.
   Reauthentication cheating can be performed in parallel with an HTTP
   transaction. True reauthentication is just as simple, but requires
   two sequential requests because of the characteristics of HTTP. By
   using reauthentication cheating, we create a "one-way" handshake.

G Brown                                                         [Page 4]

INTERNET-DRAFT              RPA - Part Two              15 November 1996

4.1 Authentication

   There are three parties involved in the authentication process:

   * the user;

   * the service; and

   * the authentication deity.

   Each user has a name and a pass phrase in some realm of interest.
   Similarly, each service has a name and a pass phrase in that realm.
   The pass phrase isn't really text; it's a 128-bit (16-octet) string
   of bits.

   However, it's often useful to use pass phrases in the conventional,
   textual sense, so we define a procedure for converting a textual
   phrase to the 128-bit value used by the authentication mechanism. If
   such a pass phrase is poorly chosen, it will be subject to dictionary
   attack, and that's why we never use the word password in this
   specification (well, except in this sentence)--use a phrase, not a

   The service may specify a list of realms, and the user chooses one in
   which he has an identity. Thus, a service is not restricted to
   authenticating identities in a single realm. The service must possess
   a name and pass phrase in all realms it lists.

   Each realm has an authentication deity, which knows the names and
   pass phrases of its members. It's the service's responsibility to
   know how to locate an authentication deity for each realm; the user
   never communicates directly with an authentication deity. If the
   service knows the user's pass phrase, it performs the role of the
   authentication deity itself, but this does not affect the mechanism.

4.1.1 Values and their representation

   Following is a glossary of the values involved in the authentication
   process; we'll use these symbols in the following explanation.

       As--Authentication deity's response to service; proves user's

       Au--Authentication deity's response to user; proves service's

       Cs--Challenge from service

       Cu--Challenge from user

G Brown                                                         [Page 5]

INTERNET-DRAFT              RPA - Part Two              15 November 1996

       Kus--Session key for user and service

       Kuss--Session key obscured so visible only to service

       Kusu--Session key obscured so visible only to user

       Nr--Realm name

       Ns--Service name

       Nu--User name

       Ps--Service's pass phrase, a 128-bit value

       Pu--User's pass phrase, a 128-bit value

       Rs--Service's response to challenge (during authentication
           process, goes to authentication deity; during
           reauthentication, goes to user)

       Ru--User's response to challenge (during authentication process,
           goes via service to authentication deity; during
           reauthentication, goes to service)

       Ts--Service's time stamp

       Z--Padding consisting of 48 octets (384 bits) with all bits set
           to zero

       +--Concatenation of octet strings

       xor--Bitwise exclusive or

   Bit patterns for each value must be specified. Imagine, for example,
   that one implementation uses ASCII, another EBCDIC, and another
   Unicode for the user name. Or one implementation converts the name to
   lowercase, another to all caps. Each would generate a different
   result for the same calculation, and authentication would fail.

   Should we leave such details to the underlying protocol? We could,
   but that would make the service-to-deity protocol dependent on the
   user-to-service protocol, so we couldn't have a single deity for each
   realm. If we specify the bit patterns, we can allow any mixture of
   user-to-service and service-to-deity protocols to operate on the same
   data. Therefore, we adopt the following conventions.

   Text strings are represented in the Unicode character set, in
   big-endian byte order, without a trailing null character. Note that
   ASCII can be converted to ISO 8859-1 by prefixing a single 0 bit, and
   ISO 8859-1 can be converted to Unicode by prefixing eight 0 bits.

G Brown                                                         [Page 6]

INTERNET-DRAFT              RPA - Part Two              15 November 1996

   Each 16-bit Unicode character is stored in two octets, with its
   high-order 8 bits in the first octet. Representation of characters
   with multiple encodings is for further study. For example, e-acute
   has more than one representation. The form that uses combining
   characters, in character-code order, is probably the most logical.

   Note, by the way, that this specification refers only to values used
   in the authentication calculations, not the underlying protocol. For
   example, it's quite reasonable for a protocol to use ASCII for user
   names, if that character set is adequate. Those ASCII characters must
   be converted to Unicode before using them in authentication
   calculations, but the protocol need not transmit Unicode characters.

   * Names--Nr, Ns, Nu--are converted to lowercase Unicode. Note that
     there is no trailing null character.

   * Challenges--Cs, Cu--are arbitrary strings of octets, not text. They
     may contain any bit patterns, including nulls, and must be at least
     eight octets in length.

   * The time stamp--Ts--is the ISO 646 (ASCII) textual representation
     of the current universal time--UTC--in exactly 14 octets, using
     24-hour time, with leading zeroes: 19950805011344.

   * Pass phrases--Ps, Pu--are 16-octet quantities that contain
     arbitrary bit patterns, including nulls. If the pass phrase is
     based on a textual phrase, the textual phrase is converted to a
     16-octet quantity by the following process.

   * Convert the text string to a sequence of characters in either the
     Unicode or ISO 8859-1 character sets, as appropriate for the

   * Convert each character to its lowercase equivalent, or its
     uppercase equivalent, or leave it alone, as appropriate for the

   * Store the sequence of characters in an octet stream, with each
     Unicode character in two consecutive octets in big-endian order,
     or each ISO 8859-1 character in one octet. Do not append a
     trailing null character.

   * Take the MD5 digest of the resulting string of octets. The result
     is the 128-bit value to use in the authentication calculations.

   A realm will specify which of the preceding options--character set,
   case conversion, and hash function--it uses for the text-to-128-bit
   value transformation; the defaults are Unicode, convert to lowercase,

G Brown                                                         [Page 7]

INTERNET-DRAFT              RPA - Part Two              15 November 1996

   and MD5. More options might be added in the future. The user-service
   protocol should be designed to convey the appropriate options for
   each realm from the service to the user, if other than the defaults
   are to be supported, to avoid requiring the (human) user to manually
   configure software.

4.1.2 The authentication process

   Here we describe the individual steps. Taken literally, one might
   envision many messages between the service and deity, but an actual
   implementation within a protocol combines steps. [Perhaps we should
   add a "sample protocol" section showing a three-way handshake
   version.] For example, "The user sends a random challenge" is shown
   as a separate step for clarity, but it needn't be a separate message
   to the service, nor must it be sent at the point shown--if it makes
   sense in the underlying protocol, the user's challenge might be
   included with the user's response to the service.

   * The service supplies a sequence of realms, with the service's name
     in each realm, to the user. For example,

         foo@compuserve.com bar@aol.com

     means "Please identify yourself with a CIS user ID. If you don't
     have one, your AOL ID will do." The service indicates its realm
     preferences in most-preferred to least-preferred order; by
     specifying only one realm, the service requires identification in
     that realm.

   * The user chooses a realm, Nr, and gives it and his name in that
     realm, Nu, to the service. That, in turn, determines Ns, the
     service's name in that realm. Note that a protocol might allow the
     service to include a null realm name, meaning "I'll accept you as
     an anonymous user if you wish." The user might make this choice by
     supplying a null name; the process stops here, and no
     authentication is performed.

   * The service transmits a random challenge, Cs, and a time stamp, Ts.
     The challenges are random values that make each authentication
     unique. The time stamp is, in effect, a third challenge, which the
     deity will ensure is recent. The user may examine it, but most
     users lack an accurate source of universal time, so most users will
     treat it as an opaque value.

   * The user sends a random challenge, Cu.

G Brown                                                         [Page 8]

INTERNET-DRAFT              RPA - Part Two              15 November 1996

   * The user calculates a response, Ru:

         Ru = MD5(Pu + Z + Nu + Ns + Nr + Cu + Cs + Ts + Pu)

     and sends it to the service.

     Only the real user can generate the correct response, because it
     depends on the user's pass phrase, Pu. No one can determine the
     user's pass phrase from a captured response, because it's generated
     by a one-way function, although there is the risk of a dictionary
     attack if Pu is based on a poorly chosen pass phrase.

   * The service calculates a response, Rs:

         Rs = MD5(Ps + Z + Nu + Ns + Nr + Cu + Cs + Ts + Ru + Ps)

     This response is not sent to the user; it would do no harm if the
     user saw it, but the user won't need it.

   * The service sends a request to the authentication deity for the
     realm in question. The request contains

     - The realm name, Nr (included so the same deity can serve more
       than one realm)

     - The user's name, Nu

     - The service's name, Ns

     - The user's challenge, Cu

     - The service's challenge, Cs

     - The time stamp, Ts

     - The user's response, Ru

     - The service's response, Rs

   * The deity verifies the time stamp per previously agreed upon
     criteria. In some applications, one might require it within a few
     minutes; in others, one might want to allow 25 hours to eliminate
     problems of misconfigured time zones. Beware of overzealousness,
     though; this time stamp went from the service to the user, then
     back to the service, then to the deity, perhaps with human
     interaction--typing a pass phrase--introducing further delay. The
     deity might implement a replay cache.

   * The deity uses Nr, Ns, and Nu to look up the user's and service's
     pass phrases.

G Brown                                                         [Page 9]

INTERNET-DRAFT              RPA - Part Two              15 November 1996

   * The deity uses the values in the request, plus the service's pass
     phrase, Ps, to verify Rs. If it is incorrect, the deity returns a
     negative response; this request apparently did not come from a
     legitimate service.

   * Having verified the requesting service's identity, the deity uses
     the values in the request, plus the user's pass phrase, Pu, to
     verify Ru. If it is incorrect, the deity returns a failure response
     to the service; the user does not know the correct pass phrase.

          [Think about the effects of replaying the authentication
          request. I think the answer is that there's no problem
          because it reveals no new information.]

   * Having verified both the user's and service's identity, the deity
     creates a random, 128-bit session key, Kus, for use by the user and
     service. They might use it for session encryption; in addition, it
     will be used in the reauthentication process described later.

   * The deity generates two obscured copies of the session key:

     - Kuss = Kus xor MD5(Ps + Z + Ns + Nu + Nr + Cs + Cu + Ts + Ps)

     - Kusu = Kus xor MD5(Pu + Z + Ns + Nu + Nr + Cs + Cu + Ts + Pu)

       The obscuring masks resemble Ru and Rs, but differ, of course, so
       an eavesdropper cannot recover Kus.

   * The deity generates a pair of authentication "proofs":

     - Au = MD5(Pu + Z + Ns + Nu + Nr + Kusu + Cs + Cu + Ts + Kus + Pu)

     - As = MD5(Ps + Z + Ns + Nu + Nr + Kuss + Cs + Cu + Ts + Kus + M +

       Here "M" is the message transmitted from the deity to the
       service; it is included in the calculation to authenticate the
       response to the service. Refer to part four of this
       specification (draft-petke-serv-deity-protocol-00.txt) for more

   * The deity sends the four values Kuss, Kusu, As, and Au to the

   * The service extracts its copy of the session key from Kuss by
     calculating the obscuring mask value and XORing. (The service can
     determine the user's key-obscuring value by calculating Kus xor
     Kusu; and if the user sees Kuss, it can do likewise. But the
     obscuring masks reveal nothing.)

G Brown                                                        [Page 10]

INTERNET-DRAFT              RPA - Part Two              15 November 1996

   * The service verifies As by performing the same calculation and
     comparing the result. If it matches, the service knows that someone
     who knows its pass phrase--the deity--replied, having verified that
     the user is who he claims to be.

   * The service forwards Kusu and Au to the user.

   * The user extracts its copy of the session key from Kusu by
     calculating the mask value and XORing.

   * The user verifies Au by computing it and comparing. If it matches,
     the user knows that someone who knows his pass phrase--the
     deity--replied, having verified that the service is who it claims
     to be. Of course, if the service itself knows the user's pass
     phrase, it can assert any service identity; but this is the case
     where the service is trusted and acts as its own deity.

   Now the user and service are confident of each others' identities,
   and the two parties share a session key that they may use for
   encryption, if they so choose.

        [Perhaps we should add another value to the authentication
        calculations, opaque to the mechanism, provided by the
        protocol in which this mechanism is embedded. This value
        would, of course, have to be added to the service-to-deity
        protocol, and its generation and interpretation would be up
        to the lower-level protocol. For example, HTTP might choose
        to include the Web server's IP address and, perhaps, the
        URL in the authentication calculations, making it harder to
        do a man-in-the-middle attack. (Of course, that problem
        cannot be completely solved without using the session key
        to authenticate data, which is a protocol issue outside the
        scope of this mechanism.)]

4.2 Reauthentication

   Reauthentication is a process by which a user and service, having
   recently authenticated each other, may again mutually authenticate
   without talking to a deity. This is useful with protocols like HTTP,
   which involve a sequence of connections that must be independently
   authenticated. It's also useful with parallel connections--imagine a
   scheme in which a user and service are connected, and wish to
   establish a second connection.

   To reauthenticate one another, the user and service prove to each
   other that they both possess a secret 128-bit key--the session key,
   Kus, derived during the authentication process. The reauthentication
   process is essentially an ordinary challenge-response mechanism in
   which the session key is used as a pass phrase.

G Brown                                                        [Page 11]

INTERNET-DRAFT              RPA - Part Two              15 November 1996

   * The service sends a challenge, Cs, to the user.

   * The user sends a challenge, Cu, to the service.

   * The user calculates

         Ru = MD5(Kus + Z + Ns + Nu + Nr + Cs + Cu + Kus)

     and sends it to the service.

   * The service verifies the result. If correct, it calculates

         Rs = MD5(Kus + Z + Nu + Ns + Nr + Cu + Cs + Kus)

     and sends it to the user. Both responses involve the same set of
     values, but they're used in a different order, so the responses are

   * The user verifies the result.

4.3 Reauthentication cheating

   In HTTP, one can shortcut the reauthentication process by cheating,
   for an increase in efficiency.

   A naive approach allows the user to repeat its authentication data,
   presumably in the form of an Authorization header. If the service
   recognizes the same Authorization header, it presumes that it's
   talking to the previously authenticated user; essentially, we pretend
   that we reauthenticated with the same challenges. But this approach
   is vulnerable to replay attacks during the period of time the service
   considers the data valid. The service can check the user's IP address
   to reduce the risk, but IP addresses mean surprisingly little. Even
   neglecting address spoofing, multiple users share an IP address when
   they're on the same host or routed through a proxy or SOCKS server.

   There's a better solution. We begin by noting why it's
   desirable--from an efficiency, not security, point of view--to allow
   the Authorization header to be replayed. To embed a
   challenge-response mechanism in HTTP, we require at least two HTTP
   transactions for authentication, because we cannot send a challenge
   and receive a response in one HTTP transaction. If we could challenge
   the user without sending a challenge to the user, we could
   authenticate in one HTTP transaction. And we can do exactly that by
   treating the URI as a challenge.

   * The first time, the user and service perform the authentication

G Brown                                                        [Page 12]

INTERNET-DRAFT              RPA - Part Two              15 November 1996

   * The user and service remember the session key (Kus), challenges (Cu
     and Cs), and timestamp (Ts).

   * When the user generates an HTTP request, he includes an
     Authorization header containing a response calculated as

         MD5(Kus + Z + Ns + Nu + Nr + Cs + Cu + Ts + method + URI + Kus)

   The method and URI are canonicalized by taking the big-endian Unicode
   representation and converting all characters to lowercase; the URI
   should not include the scheme://host:port. It always begins with a
   slash; for "http://www.foo.com" the one-character string "/" would be

   Now the authentication response is unique for each URI, and
   calculable only by the authenticated user, even without a unique
   challenge. This doesn't completely eliminate the risk of replay, of
   course, but an attacker can replay only a previously referenced URI
   during the window in which the service considers the session key to
   be valid. Is that acceptable?

   Sometimes. If we're reading Web pages, and the only impact of replay
   is that the attacker could re-read the page, it might be
   acceptable--after all, the attacker saw the page, anyway, when he
   captured it along with the original request. On the other hand, if
   we're charging the user per page, or if the request "did" something,
   replay might not be so harmless.

   One strategy is to maintain some history. In its simplest form, the
   service sets a flag for this session when it does something for which
   replay would be harmful. If the user tries reauthentication cheating,
   and the flag is set, the service forces reauthentication. Because the
   cheating response is based on Cu and Cs, and those values change
   during reauthentication, the correct response for a given URI changes
   after reauthentication. Thus, reauthentication creates a boundary
   after which previous requests cannot be replayed.

   Or the service can maintain a history of URIs for which replay would
   be harmful, and force reauthentication only if the user tries
   reauthentication cheating on one of those URIs.

5. Security Considerations

   This entire document is about security.

G Brown                                                        [Page 13]

INTERNET-DRAFT              RPA - Part Two              15 November 1996

6. Author's Address

   Gary S. Brown
   CompuServe Incorporated
   5000 Britton Rd
   P.O. Box 5000
   Hilliard OH 43026-5000

   +1 614 723 1127

This Internet-Draft expired on May 15, 1997.

G Brown                                                        [Page 14]