Recent-Secure Authentication: Enforcing Revocation in Distributed Systems
`
`Stuart G. Stubblebine
`AT&T Bell Laboratories
`101 Crawfords Corner Rd., Holmdel, NJ 07733-3030
`stubblebine @research.att.com
`
`Abstract
`A general method is described for formally specifying
`and reasoning about distributed systems with any
`desired degree of immediacy for revoking authentica-
`tion. To effect revocation,
`‘authenticating entities ’
`impose freshness constraints on credentials or authenti-
`cated statements made by trusted intermediaries. If
`fresh statements are not presented, then rhe authentica-
`tion is questionable. Freshness constraints are derived
`from initial policy assumptions and authentic Atate-
`ments made by trusted intermediaries. By adjusting
`freshness constraints, the dela-y for certain rebocution
`can be arbitrarily bounded. We illustrate how the inclu-
`sion of freshness poliries within certificates enablec the
`design of a secure and highly available revocation ser-
`vice. We illustrate the application of the method and
`new techniques in an cxample.
`
`1. INTRODUCTION
`
`An authentication architecture that scales globally
`is desirable to support authentication and authorization
`for electronic commerce A characteristic of universal
`electronic commerce is that clients and commercial
`servers not previously known to one another must inter-
`act. An essential feature of an authentication service in
`large distributed systems is revocation. Revotrrtion
`entails rescinding authentication and authorization
`statements that have become invalid. Revocahori is
`needed because authentication information changes
`with time, perhaps, due to a compromise or suspected
`compromise of an entity’s private hey, change of affilia-
`tion, or cessation ot an entity’s operation. Whcn a
`compromise is discovered, rapid revocation of informa-
`to prevent unduthorized u\e of
`tion
`is required
`resources and electronic fraud.
`Understanding re vocation is an important business
`concern to service providers as well as to users of an
`authentication service, it has been estimated that the
`yearly running expenses of an authentication infrastruc-
`ture derive mainly from administrating revocation [ 3 ] .
`A service for revoking authentication should have
`the following desirable properties.
`Definite. Revocation should be fail-safe or asured
`with bounded delay5
`
`Available and Recent. The mechanisms for posting
`and retrieving updates must be highly available and
`retrieved information should be recent (if not current).
`Adjustable. Protection and performance trade-off
`should be adjustable to suit varying risk adversity.
`is
`a compromise
`Bounded Recovery. When
`discovered, delays in revocation should be decidedly
`bounded in time.
`Contained. A compromised revocation
`service
`should
`not
`allow
`illegitimate
`identification
`credentials to be issued.
`Factors inherent to the difficulty of revocation in a
`large distributed environment include:
`Size. Numerous entities not previously known to one
`another may need to interact securely.
`the
`Trust. Entities have different views of
`trustworthiness of intermediaries and of each other.
`Security. Protection of computing environments are
`variable and uncertain.
`Distributed and Faulty. The authenticating entity’s
`knowledge of authentication information can be
`inaccurate due to communication latency, failures,
`and active wiretapping.
`and
`Authentication
`Temporal
`Dynamics.
`authorization information changes with time and is
`unpredictable.
`To date, little has been published focusing on revo-
`cation in large distributed systems, perhaps, because
`few large scale authentication architectures exist that
`cross multiple autonomous realms. Network authentica-
`tion services, such as Kerberos [ 181 and DCE [21]
`(which is built on Kerberos), have seen reasonable
`deployment within local autonomous realms. However,
`experience with inter-realm authentication is somewhat
`limited by the current dearth of inter-realm applica-
`tions. Authentication services based on shared-secret
`cryptosystems (e.g., DES I17]), have inherent draw-
`backs to scaling to large distributed systems. In
`particular, authentication requires trusted on-line inter-
`action potentially with numerous intermediate servers
`for each initial authentication. Also, they require on-
`line servers to maintain the confidentiality of shared
`secrets. The compromise of any intermediate server
`can lead to security exposures beyond the boundary of
`the compromised realm[9].
`
`1081-6011/95 $04.00 6 ) 1995 IEEE
`
`224
`
`Authorized licensed use limited to: Stevens Institute of Technology. Downloaded on December 15,2023 at 19:22:20 UTC from IEEE Xplore. Restrictions apply.
`
`UNIFIED PATENTS EXHIBIT 1022
`UNIFIED PATENTS, LLC v. DYNAPASS IP HOLDINGS LLC
`IPR2023-00425
`Page 1 of 12
`
`

`

`Authentication in large distributed systems is mov-
`integration of
`ing
`towards
`the
`local
`network
`authentication servers with global directories (e.g., those
`based on the X.500 directory [28]) and open authentica-
`tion architectures (e.g., X.509 [29]) using public key
`cryptography [7,20,26,29]. Public key crytposystems like
`RSA [22] and the Digital Signature Standard (DSS) [6]
`have a private key that is kept secret and a public key that
`can be published to others.
`Global authentication architectures based on public
`key cryptography assume that named principals to be
`authenticated maintain the confidentiality of their private
`keys. Certificates using public key cryptography enable
`authentication information to be distributed using servers
`that need not he trusted on the authority of the certificate
`contents. Intermediaries, called certifiers or certification
`authorities (when authority is assumed by authenticating
`entities), create cryptographically protected statements
`Identification authorities, having
`called certificates.
`authority on identification of entities, issue identijicafion
`crrtijicafes. Identification certificates assert that a public
`key is associated with an entity having a unique name.
`Revocation authorities, having authority on the status of
`certificates, issue revocation certificates. Revocation (’er-
`tlficates assert the status of certificates previously issued.
`Revocation policies, which are typically included in
`authentication policies, represent the bounded delay
`before an authentication entity becomes current on the
`accuracy of authentication information. Authentication
`conforming to these policies is called recent-secure
`authentication. The entity or agent doing the authentica-
`tion is called the authenticating entiry.
`Propagation of certificates through servers, such as
`directory servers, can introduce delays. In this paper, we
`formalize data-origin authentication policies that enable
`authentication to be as strong as a ont-way authentication
`using timestamps or arbitrarily weaker.
`To better understand
`the protection offered by
`authentication, authorization, and revocation in distrib-
`uted systems, and to improve these systems, we present a
`general method for fonnally specifying and reasoning
`about distributed system with any desired degree of
`immediacy for revoking authentication. To effect revoca-
`tion, authenticating entities impose freshness constraints
`on statements made by trusted intermediaries. These con-
`straints are derived from initial policy assumptions and
`authentic statements made by trusted intermediaries. By
`adjusting freshness constraints the delay for certain revo-
`
`’ ’Time-stamped based authentication is vulnerable to clock synchroniza-
`
`tion failures and to inaccuracies in an authenticating entity’s knowledge
`of. certifier information caused by a wide time window.
`
`cation can be arbitrarily bounded. Though our techniques
`apply to authorization built on an authentication plat-
`form, the focus of this paper is authentication.
`The remainder of the paper is organized follows. In
`Section 2, an intuitive justification for the utility of recent-
`secure authentication is presented. In Section 3, the speci-
`fication language and axioms for reasoning about recent-
`secure authentication are presented. In Section 4, recent-
`secure authentication is defined and revocation mecha-
`nisms are discussed. In Section 5 , we present a technique
`for delegating revocation authority yet retaining both
`identification authority and authority for specifying
`recent-secure authentication policies. We explain how
`this technique enables the design of secure iind available
`revocation services. In Section 6, we illustrated our
`method by analyzing an authentication instance of an
`experimental authentication architecture. In ,Section 7 we
`present our conclusions of this paper.
`
`2. BACKGROUND
`
`Recent-secure authentication is based on the specifi-
`cation of freshness constraints on statements made both
`by trusted intermediaries (certifiers) and by principals
`that may be authenticated. These statements represent
`assertions whose authenticity can be protected using a
`variety of mechanisms ranging from public- or shared-
`key to physical protection. Freshness constraints, which
`restrict the useful age of statements, can come from ini-
`tial authentication assumptions and can also be derived
`from authentic statements which may themselves be sub-
`ject to freshness constraints.
`An important requirement of revocation in large dis-
`tributed systems is the fail-safe property. This means that
`revocation is resilient to unreliable communization. Revo-
`cation mechanisms not satisfying this property can be
`impeded by active attacks in which the adversary pre-
`vents the reception of revocation statements. Apparent
`countermeasures to these attacks may not be adequate.
`For example, consider the technique of cascaded delega-
`tion where a delegation certificate is treated as a
`delegation is passed to each new system [8] To terminate
`a delegation, a “tear down” order is passed down the
`chain. (This is analogous to the notificatioii mechanism
`discussed in Section 4.3). However, due to unreliable
`communication or a compromise of an intermediate sys-
`tem, the order may not fully propagate. Therefore, it was
`proposed that each intermediate delegate periodically
`authenticate delegates. However, periodic authentication
`of predecessor delegates can be vulnerable to attacks
`where the adversary steps down the chain blocking revo-
`cation statements until the particular link times out. The
`result is an additive effect on delaying revocation. Alter-
`
`225
`
`Authorized licensed use limited to: Stevens Institute of Technology. Downloaded on December 15,2023 at 19:22:20 UTC from IEEE Xplore. Restrictions apply.
`
`UNIFIED PATENTS EXHIBIT 1022
`UNIFIED PATENTS, LLC v. DYNAPASS IP HOLDINGS LLC
`IPR2023-00425
`Page 2 of 12
`
`

`

`natively, each node could authenticate every other node
`at the cost of nz messages where n is the number of
`nodes. The optimal design for balancing performance and
`security depends on ths protection of each system and
`communication between them.
`Performance optimizations and increased assurance
`can be realized if policies for querying entities could be
`fine-grained and the reasoning behind these policies
`could be formally analyzed. Recent-secure authentication
`is necessary both during initial authentication as well as
`during a session since revocation can occur at any time.
`Principals can be used as the basis for specifying
`freshness constraints and can be typed according to fresh-
`nesh classes. The freshness constraint associated with a
`principal type can depend on an identification authority's
`certificate issue policy since this policy specifies security-
`relevant information such as the randomness of keys, soft-
`ware and hardware protection for key management,
`identification, and authentication requirements for certifi-
`cate registration.
`Communication latency is an inherent property of
`distributed systems. Consequently, authenticating entities
`can not have perfect knowledge of authentication and
`authorization information and so failure can occur. The
`problem is compounded as systems grow in size. Addi-
`tionid certifiers represents more distributed knowledge.
`Our method makes precise what degree of protection is
`desired and obtained.
`By adjusting the recent-secure constraints the delay
`for revocation can be arbitrarily bounded.This is impor-
`tant since zero delays can not be achieved in large
`disti ibute systems due to communication latency.
`Given that obtaining consistent knowledge of authen-
`tication data may be difficult and cost prohibitive in
`practice, it is necessary to quantify levels of protection
`that can be obtained and to reason whether they have
`been obtained. The practical significance of the concept
`of recent-secure authentication is that it enables distrib-
`uted authenticating entities, on a per-transaction basis, to
`trade-off authentication costs against the levels protection
`Quantifiable authentication assurances are difficult to
`provide if information about intermediate system is
`incomplete. In spite of thi5 many systems operate with
`incomplete information. This requires the risk of opera[-
`ing such systems to be periodically reassessed. For
`exainple entire industries have been dependent on reas-
`sessing shifting risks We suggest that recent-secure
`authentication policies are an important variable for reas-
`sessling shifting risk in large distributed systems. For
`example, proposals have been made to assign financial
`liability attributes to certificate authority statements in
`
`financial systems based on shifting risk [2]. Our method
`suggests that recent-secure policies should be associated
`with statements of authentication liability.
`The concept of recent-secure authenticatiodauthori-
`zation is related in spirit to other systems concepts. In
`particular, it can be related to a hybrid optimistic/pessi-
`mistic method of concurrency control that allows for the
`selective application of the most efficient method charac-
`terized by the probability of conflict [12]. For example,
`small freshness intervals correspond to pessimistic meth-
`ods requiring more expensive mechanisms than those
`required by larger intervals.
`3. THEORY
`
`In this section, we present a theory for specifying
`temporal features of statements made by entities, and we
`present rules for reasoning about them. A primary pur-
`pose
`is to understand how
`to attain recent-secure
`imthentication rather than to specify implementation algo-
`rithms for maintaining recent-secure channels. Therefore,
`iln analysis instance does not carry additional constraints
`as extra baggage to the conclusion and the conclusion is
`only meaningful at the time of verification. Also, the the-
`ory does not reason about the liveliness properties of an
`architecture for attaining these properties. Nor do we
`describe algorithms for finding trustworthy certifiers
`19,271.
`Our work is inspired by recent literature on a theory
`of authentication in distributed systems [1,14]. This the-
`ory explains how one can reason about authority to
`deduce other principals that can speak for an entity. The
`theory has been useful for explaining general techniques
`of authentication in distributed systems including how
`one derives the adequacy of a key used to authenticate an
`entity. Reasoning about the freshness and temporal valid-
`ity of authentication statements is not addressed to any
`work to date. Where possible, we build on existing theory
`to realize its expressiveness for reasoning about general
`remote procedure calls, name lookup, groups, program
`loading, delegation, and access control. However, applica-
`tions of recent-secure authentication to these techniques
`is not described herein.
`We begin by briefly reviewing the theory of secure
`channels (we refer the reader to the literature for a more
`detailed description 1,141) and discuss assumption about
`time and ordering. Next, we discuss statements about
`time followed by some example interpretations. Finally,
`we present a formal description of the syntax, and axi-
`oms. A formal semantics, extension axioms, and
`theorems derived will be presented in a later paper.
`
`226
`
`Authorized licensed use limited to: Stevens Institute of Technology. Downloaded on December 15,2023 at 19:22:20 UTC from IEEE Xplore. Restrictions apply.
`
`UNIFIED PATENTS EXHIBIT 1022
`UNIFIED PATENTS, LLC v. DYNAPASS IP HOLDINGS LLC
`IPR2023-00425
`Page 3 of 12
`
`

`

`3.1 Principals, Statements, Time and Ordering
`
`PRINCIPALS
`All entities in our system are called principals. A dis-
`tinguished principal is the authenticating entity who
`authenticates a channel. Basic named principals are enti-
`ties that can not say things directly on a computer. For
`example, they can be people, groups, or roles. Channels
`or channel principals are principals that can say things
`directly. An VO port is an example of a channel that
`reports the receipt of a message. A key and cryptographic
`algorithm is an example of a channel that makes crypto-
`graphic statements. Cryptographic channels are of
`primary interest when communication transits untrusted
`domains and is subject to wiretapping.
`STATEMENTS
`If KBob and Bob are principals than,
`Ksoh Ij Bob
`is a ‘speaksfor’ relation. Suppose
`is a statement. ?he
`KBoh is a channel and Bob is a named principal, then the
`above statement let’s us deduce that the channel KBoh. rep-
`resents Bob.
`If IA is a principal and s is a statement then,
`IA says s
`is also a statement. If “IA says s”, we can proceed as
`though IA is willing to say s. It does not necessarily mean
`that IA had actually articulated the statement. For exam-
`ple, we may have derived this from our axioms. Also. a
`principal could be lying.
`CLOCKS AND ORDERING ASSUMPTIONS
`For acceptable performance, basic channel principals
`can have clocks that are loosely synchronized to an exter-
`nal time reference and the channel’s synchronization
`accuracy is known to other principals and the authenticat-
`ing entity. Loosely synchronized clocks are used to
`expire keys, and to age statements. The accuracy of clock
`synchronization constrain5 the granularity for aging state-
`ments and expiring keys. Granularity constraints on
`expiring keys i s not a practical problem in situations
`where sufficiently pessimistic assumptions can be made
`in assigning key lifetimes [25]. However, granularity is
`an issue for fail-safe revocation since the practical bound
`on revocation may need to be on the order of tens of min-
`ute$ or less. The reliance on clock synchronization for
`refreshing statements makes recent-secure authentication
`swceptible to vulnerabilities due
`to clock failures
`[4,10,16]. Therefore, the assumption of synchronized
`clocks must be carefully scrutinized.
`We assume statements from each channel principal
`can be ordered and missing statements can be detected.
`(In practice this requirement might be carefully relaxed.
`For example, if statements could be ordered and each
`
`statement provides a complete interpretation then inter-
`pretation of missing statements may be unnecessary.)
`Also, the order of statements from different sources can
`be established using clock synchronization and the exter-
`nal synchronization accuracies can be determined.
`
`3.2 Statements about Time
`
`SAYS WITH A TIME ATTRIBUTE
`A principal may assert a statement and a time attribute.
`For example,
`
`KIA says s at t.
`In the above statement, it is not necessarily a tact a princi-
`pal says s at time t . As mentioned before, a principal
`could be lying. However, our axioms capture the notion
`that if we trust a principal and are able to discern a state-
`ment made by it, then we also trust the facts concerning
`the statement time attribute. Not all “says” statements
`have time attributes. An example is the interpretation of
`the X.509 identification certificate [28].
`VALIDITY CONSTRAINTS ON ‘SPEAKS FOR’ RELATIONS
`Speaks for relations are given time conrtraints. We
`specify these constraints using the ‘notbefore’, and
`‘notafter’ suffixes. For example,
`KBob + Bobnotbefore t, notafter t2
`indicates that during the closed interval [t,, t2], KBob 3
`Bob.
`
`3.3 On Interpretation & Analysis
`
`For analysis, we need to first interpret individual
`messages (such as public key certificates) as statements
`in our formalism. The next step is to determine that we
`have an unambiguous interpretation.’ If so, we proceed
`with the analysis using the axioms in this paper.
`Below, we informally give examples of interpreting
`authentication message types (e.g., certificates) and for-
`malizing them as statements.
`IDENTIFICATION CERTIFICATES
`In practice, avi identification certificate (sometimes
`called a certificate) contains identifying information of an
`entity together with its associated keying material and
`possibly other information such as an expiration date.
`The identification certificate is cryptographic protected
`by using the key of an identification authority. The inter-
`pretation of a X 509 and Internet Society’s (X.509
`compliant) IPRA identification certificate [ 131 is repre-
`sented as:
`
`The method for detemiining a consistent interpretation for a given set
`of statements is not presented herein.
`
`227
`
`Authorized licensed use limited to: Stevens Institute of Technology. Downloaded on December 15,2023 at 19:22:20 UTC from IEEE Xplore. Restrictions apply.
`
`UNIFIED PATENTS EXHIBIT 1022
`UNIFIED PATENTS, LLC v. DYNAPASS IP HOLDINGS LLC
`IPR2023-00425
`Page 4 of 12
`
`

`

`KIA says
`
`+ IA/Bob notbefore f, notafter
`
`t 2 )
`In this statement, KIA, which is the identification
`relationship between
`authority’s key, asserts the
`and IA/Bob between the validity interval [f,, f z ] . Since a
`timestamp is not in the identification certificate, we can
`annotate the time. Consequently, from the statement
`alone, the authentication entity can not determine the
`recentness of the statement.
`TIME-STAMPED
`IDENl’lFlCATlON CERTIFICATE
`Where the identification authority can be adequately
`protected, architectures may use identification certificates
`as the primary basis for determining freshness. Since
`none of the current standards [2,13,29] specify a times-
`tamp within the identification certificate, we assume the
`X.509 certificate format with a timestamp and obtain:
`K, say. (K, 3 Bobnotbefor. rl aot8ft.r
`tz)
`at r3.
`RE VOCATION CERTIFICATE
`A certificate revocation list (CRL) or revocation cer-
`tificate indicates what certificates have changed
`in
`“status”. The interpretation of a revocation certificate typ-
`ically has the format of the time-stamped identification
`certificate. We summarize interpretations of revocation
`certificates as follows:
`“current”: The absence of a referenced identification
`certificate implies that it is cumnt at the time of the revo-
`certificate. Our interpretation asserts
`catlon
`the
`interpretation of the referenced identification certificate
`with the time of the revocation certificate.
`“revoked ”: indicates the referenced certificate is
`invalid or is about to be invalid. Our interpretation reas-
`serts the original statement specifying a ‘notafter’ time
`corresponding to the revocation date. If the timestamp is
`present we annotate the time of the statement.
`is
`indicates the certificate binding
`“extended”:
`extended to the new time. Our interpretation reasserts the
`original statement and the ‘notafter’ time is set for the
`new time. If the timestamp is present we annotate the
`time of the statement.
`“suspended”: indicates the certificate should be tem-
`porarily suspended (analogous to the certificate on hold
`option in [2]). Our interpretation consists of two state-
`ments: a statement indicating a ‘notafter’ time set sooner
`than the original certificate, and a new statement with a
`‘notbefore’ time set later. If the timestamp is present we
`annotate the time of the statement.
`
`3.4 Syntax and Axioms
`We now present the axioms of the paper, most are
`extensions of [1,14] and others are repeated for complete-
`s means that s is an axiom of the
`ness. The notation
`theory or is provable from the axioms. The symbol, ‘2’
`means implies, and ‘3’ is the ‘speaksfor’ relation
`represents the time
`between principals. The symbol f,,
`of verification.
`
`SYmM
`Formulas are defined inductively, as follows:
`a countable supply of primitive propositions pol p,, p2, ...
`are formulas;
`Ifs and s‘ are formulas then so are 1 s and s A s’ ;
`If A and B are principals expressions then the following
`are formulas:
`A e4 notbefore f l notafter r2 ;
`A says s at f ;
`STATEMENT AXIOMS
`Statements are inductively defined according to the
`following axioms.
`The axiom for statements are:
`(S l)If s is an instance of a propositional-logic tautology then
`I- s.
`(S2)If I- s and ( C s I) s‘) then I- s’ .
`(S3) C(A.aya(s3s‘)at
`r)~((Asaya vat f ) I A
`.ay# s‘ at r)).
`(S4)If I- s then I- A m y 8 s at rnow for every principal A.
`From (Sl)-(S4) we obtain the theorem:
`(s A s’ ) at t = (A says s at f A A says
`(S5) C A .ay.
`sat r)
`
`AXIOMS FOR PRlNC1PAL.S
`(Pl) I- A is associative, commutative, and idempotent.
`(P2) I- I is associative.
`(P3) I- I distributes over A in both arguments
`The time of a statement made by (A A N) is equiva-
`lent to both A and B saying it at the same time
`(P4) F (A A B ) says s at r 3 (A says s at t I A (B says
`sat f )
`B quoting A at time r has the definition:
`(P5) I- ( B I A) says s at t 3 B says ( A says s at f ) at f
`We introduce ,a new axiom, (P6), that ‘1 * II ows more
`restrictive a relations to be obtained from leas restrictive
`ones. It is used to normalize suffix constraints prior to
`applying other rules such as the transitivity of 3.
`(P6) I- ( A a B notbefore t, notafter I ! ) I> ( ( ( t , I
`t 3 ) ~ ( t 4 I tz)) 2 , 4 + B notbefore I] notafter t4)
`
`228
`
`Authorized licensed use limited to: Stevens Institute of Technology. Downloaded on December 15,2023 at 19:22:20 UTC from IEEE Xplore. Restrictions apply.
`
`UNIFIED PATENTS EXHIBIT 1022
`UNIFIED PATENTS, LLC v. DYNAPASS IP HOLDINGS LLC
`IPR2023-00425
`Page 5 of 12
`
`

`

`In (P7), the * relation allows us to remove a level of
`indirection. The constraint tl < t3 < t2, is meaningful if
`principals are trusted not to lie. For example, revocation
`authorities in the example in Section 6 iire trusted not to
`lie when specifying the time of revocation certificates.
`(W) I- (A~Bnotb~forer~notafter
`t z ) 2 ( ( ( A says
`s at t3) A (t, I tnmt3 I t2)) 2 (B says s at t3))
`The hand-off axiom allows principals to derive new
`facts:
`(P8) C (A says ( B + A notbef ore t, notaf tor r,)
`at f3) =I (B 3 A notbef ore t, notaf ter tz)
`REXENT4ECURE AUTHENTICA-
`4.
`TION AND MECHANISMS
`
`This section we explain how recenl-secure authenti-
`cation, and hence bounds on revocation, are specified as
`freshness constraints on statements made by trusted enti-
`ties. A discussion of recent-secure authentication in
`Kerberos is presented, and we briefly review techniques
`for revocations and discuss their relative merits.
`
`4.1 Policy Constraints of Authenticating Entities
`
`To effect revocation, authenticating entities are assumed
`to follow certain freshness policies. These policies can
`come from the authenticating entity’s participation in a
`distributed service. For example, a vender conducting
`electronic commerce on a public network authenticates
`customers according to the policies of organizations tak-
`ing financially liability for the transaction. Authenticating
`entities can also impose their own policies as necessary.
`Authenticating entities are given a set of‘ credentials
`or statements for channel authentication. They also begin
`with a set of freshness constraints that embody, in part,
`the revocation policies. Revocation policies are also
`embodied in freshness constraints recommended by inter-
`mediary certifiers. That is,
`-fa A d B S a l r f i e s b e s s const rain€ SA, at time
`t,, 1TA-B aotbef ore t where (trim - SA,,) I t and
`C j A d
`fnow
`Freshness constraints can be applied to 3 relations
`during interpretation by replacing existing less restrictive
`“notbefore” qualifiers with the more restrictive freshness
`constraints. For example, if the freshness constraint
`G c - ~ c - , , = 30 minutes is assumed by the authenticating
`entity, and we are given CA + CA/Bob, then we obtain:
`C M o b notbefore (t,,,, - 30 minutes).
`CA
`Channels obeying freshness constraints are called
`recent-secure channels andl are defined as follows:
`
`Defn A+B is recent-secure at time t,,, iff A a B can
`be deduced from given statements with freshness con-
`straints applied.
`It follows from our definitions that if freshness con-
`strains are associated with each trusted certifier whose
`statements may be used to establish a channel, then the
`delay for revocation can be bounded by the least restric-
`tive freshness constraint. Consequently, the choice of
`freshness constraints can arbitrarily bound the delay for
`revocation. Certifiers recommend freshness constraints
`typically by imposing “notafter” times in certificates.
`(However, in Section 5 we illustrate how freshness poli-
`cies can be promulgated in certificates.)
`
`4.2 Recent-Secure Authentication in Kerberos
`
`Kerberos is designed to enable application servers to
`impose freshness constraints on users who initially log in
`using shared keys. To do this, the time of initial log in
`“authtime”, is carried in a ticket that is presented to the
`application server. Application servers can choose to
`reject the credentials if the “authtime” is not recent even
`if the ticket is still within its valid lifetime.3
`A recent proposal calls for public key extensions for
`initial authentication [20]. With the exception of public-
`key authentication during initial log in, all protocols
`remain the same. The implication of recent-secure authen-
`tication is that application servers need to know that their
`recent-secure authentication requirements are satisfied.
`With the addition of public-key authentication to Ker-
`beros, the current “authtime” field may not be sufficient
`for application servers to determine if initial authentica-
`tion satisfies their authentication policies. The problem is
`complicated by the fact that recent-secure authentication
`policies may vary for each server, and possibly, each par-
`ticular type of transaction. To make Kerberos “recent-
`secure friendly”, one approach would be to rcrquire users
`to satisfy prescribed recent-secure authentication policies
`prior to obtaining a ticket. During the course of a session,
`the application server may require the user to satisfy new
`policies or simply maintain freshness policies during a
`long session (e.g., refresh stale certificates). A new ticket
`can be
`issued once recent-secure authentication is
`satisfied.
`
`4.3 General Revocation Mechanisms
`
`A revocation service should have the properties of
`being definite, available and recent, contained, bounded
`recovery, and adjustable, as noted in the introduction. A
`
`’ This example was pointed out to me by Clifford Neuman
`
`229
`
`Authorized licensed use limited to: Stevens Institute of Technology. Downloaded on December 15,2023 at 19:22:20 UTC from IEEE Xplore. Restrictions apply.
`
`UNIFIED PATENTS EXHIBIT 1022
`UNIFIED PATENTS, LLC v. DYNAPASS IP HOLDINGS LLC
`IPR2023-00425
`Page 6 of 12
`
`

`

`number of related techniques have been proposed for
`effecting revocation in distributed systems. We briefly
`review these techniques and discuss their relative merits
`for use in large distributed systems.
`CERTIFICATE CACHES WITH EXCEPTION NOTIFICATIONS
`Authenticating entities may cache certificates and
`notify caches when there is a change. This approach is
`not well suited to large distributed systems since the noti-
`fication mechanism is not fail-safe For example, an
`adversary could selectively block an exception notifica-
`tion. Also, it does not scale well if the destination caches
`need to be tracked. However, emergency notifications can
`augment a fail-safe scheme to possibly shorten revoca-
`tion delays (provided messages reach their destinations
`sooner than the time-out periods). A distributed multicast
`infrastructure could alleviate the load on servers for distri-
`bution of notifications.
`CERTIFICATES WITH EXPIRATION TIMES
`A common technique for bounding the delay of revo-
`times within
`cation
`is placing explicit expiration
`certificates. Provided a certifier has not been conipro-
`mised, statements using expiration times satisfy the fail-
`safe prope