Delegation of permissions in an electronic commerce system6523012Abstract An electronic commerce system includes a broker computer system having a database of scrip representing a form of currency, a vendor computer system having a database containing products which may be exchanged for the scrip, a consumer computer system with which a user may initiate transactions with the scrip, and an agent computer system to which the consumer can delegate rights to perform actions with the scrip. To delegate actions on scrip, the delegator provides the delegatee with a delegation having a list of the delegated actions. In addition, the delegator determines a delegation scrip secret (DSS) and a delegation pass phrase (DPP) and securely passes these to the delegatee. The delegatee uses the DSS to authenticate itself to servers accepting the scrip and uses the DPP to encrypt the DSS while the scrip is stored by the delegatee. To perform an action with delegated scrip, the delegatee sends a request for the action to a server. The request includes the action, the scrip, the delegation, and a request stamp (RS) calculated using the DSS. The server validates the request by recalculating the RS. When server provides the delegatee with new scrip having multiple delegations, the server encrypts the new DSS's for each delegation. The delegates uses the old DSS's to decrypt the DSS's for the new scrip. The delegatee stores the encrypted DSS for delegations for which the delegatee does not know the DSS. Claims We claim: Description BACKGROUND
MCS Table:
Partition Number Master Customer Secrets
P.sub.1 MCS.sub.1
P.sub.2 MCS.sub.2
P.sub.3 MCS.sub.3
Both the partition numbers and the MCS are preferably binary strings having lengths and values agreed to by the broker 111 and the vendor 121. When the consumer 131 buys scrip 400 from the broker 111 (or receives scrip from a vendor 121), the broker 111 generates the CS for the scrip 400 by determining the partition number from the Customer ID field 416 and looking up the corresponding MCS in the MCS table. Then, the broker 111 calculates the CS from a hash of the customer ID with the MCS as: CS=H(customer ID, MCS), where H( ) denotes the hash function. In one embodiment, the hash function used throughout the electronic commerce system is HMAC-MD5, described in H. Krawczyk, M. Bellare, R. Canetti, "HMAC: Keyed-Hashing for Message Authentication," RFC 2104, February 1997, and R. Rivest, "The MD5 Message Digest Algorithm," RFC 1321, April 1992, both of which are hereby incorporated by reference herein. However, any suitably secure one-way hash function can be substituted. If this is the first piece of scrip purchased by the consumer 131 from the broker 111, the CS is provided to the consumer 131 via a secure channel and the consumer 131 stores the CS in the wallet 221. A preferred secure channel is described in U.S. patent application Ser. No. 09/081,521, entitled METHOD FOR COMMUNICATING SECURE AND AUTHENTICATED TRANSACTIONS OVER AN NON-SECURE NETWORK SUBJECT TO EXPORT RESTRICTIONS, which was filed on May 19, 1998, and is hereby incorporated by reference herein. If the consumer 131 has already received a CS from the broker 111, the broker 111 uses the previously provided CS (the old CS, or OCS) to transmit a new CS (NCS) to the consumer 131 without requiring a secure channel. The broker 111 calculates the NCS using the Customer ID field 416 and the corresponding MCS in the MCS table in the same manner that the OCS was calculated. Then, the broker 111 calculates an encrypted NCS (ENCS) as follows: ENCS=NCS XOR H(nonce, OCS), where "XOR" is the exclusive-or function and a nonce is a random, guaranteed unique string of arbitrary length. The ENCS and the notice are passed to the consumer 131. When the consumer 131 receives the ENCS and nonce, the consumer 131 derives the NCS by performing the calculation: NCS=ENCS XOR H(nonce, OCS). The consumer 131 preferably stores the NCS with the corresponding scrip 400 in the wallet 221. Thus, the broker 111 communicates the value of the NCS to the consumer 131 without actually transmitting the NCS in the clear. The consumer 131 uses the CS to prove ownership of, i.e., possession of the right to spend, the scrip. In a preferred embodiment of the present invention, the consumer 131 requests product from the vendor 121 in the context of the World Wide Web. However, the present invention can be used for purchases in any electronic context. Accordingly, the request is preferably phrased as a uniform resource locator (URL) pointing to a location at a vendor-controlled domain. To spend scrip 400 for a product, the consumer 131 sends the vendor 121 a message in the form: scrip, request, H(scrip, request, CS), where scrip is the vendor scrip 400 issued to the consumer, the request is the URL specifying the requested product, and H(scrip, request, CS) is a hash of the scrip, request, and the CS. Thus, the consumer 131 sends the scrip in the clear (unencrypted). When the vendor 121 receives the scrip 400, the vendor 121 first validates the Stamp field 422 to ensure that the scrip 400 was not altered. Next, the vendor 121 validates that the consumer 131 possesses the correct CS. If the stamp field and CS validate, then the vendor 121 has a high degree of confidence that the scrip 400 was not altered and was received from someone knowing the CS. Once the vendor 121 has validated the scrip 400 and consumer 131, the vendor preferably provides the requested product to the consumer 131. Also, the vendor 121 may issue scrip to the consumer 131 as change by using the techniques described above. For normal purchases, as described above, the knowledge of secrets follows a defined trust relationship. It is acceptable for brokers 111 to know the customer secrets for vendor 121 scrip because the brokers 111 are trustworthy. Vendors 121 know the customer secrets for scrip the vendors validate or produce. Also, consumers 131 know the customer secrets for only the scrip they own. When a consumer 131 delegates a set of actions for a piece of scrip to an agent 151, the delegating consumer may not wish to give the agent 151 all the secrets for the scrip in order to maintain ultimate control of the scrip. Accordingly, the present invention allows the consumer 131 to delegate actions without providing "stronger" scrip secrets than are necessary for the agent 151 to perform the actions. In this description, a "delegation" is a set of delegated actions and, optionally, an expiration time for the delegation. A delegation is specific to a piece of scrip. Actions on scrip that may be delegated include: spend, refresh the expiration time, recover lost scrip, refund unused scrip, convert scrip to other currencies, subdivide scrip into multiple pieces, complain about problem purchase, and any other useful actions. The delegation allows the agent 151, or other delegatee, to perform the delegated actions in place of the delegator. A preferred embodiment of the present invention represents the set of actions in a delegation as a string listing the names of the delegated actions. The root delegation is defined as the full set of all actions with no expiration time. However, for efficiency and convenience, the root delegation is implicitly defined by the absence of any delegation, thereby removing the need to transmit a delegation in this case. In addition, certain actions are preferably included in every delegation--such as refreshing scrip before it expires. These actions are always allowed and cannot be removed from a delegation. Once again, implicitly including certain actions with delegations removes the need to explicitly list and transmit an action which is always present. An alternative embodiment of the present invention may use alternate syntax to express delegations. One alternative embodiment support revocations in addition to delegations. A revocation explicitly removes the right of the delegatee to perform an action. For example, a delegator can delegate the full set of actions to a delegatee along with one or more revocations of actions in the set. The delegatee would be able to perform all of the actions in the set except for the revoked actions. FIG. 5 is a diagram illustrating the transactions between a delegator 510 and a delegatee 512 according to a preferred embodiment of the present invention. In FIG. 5, the order of the illustrated transactions can vary depending on the implementation. Accordingly, the illustrated order should be considered as only one possible embodiment of the present invention. The delegator 510, may be, for example, a consumer 131, and the delegatee may be an agent 151. The delegator 510 may also be an agent 151 or some other form of delegatee with respect to another delegator higher up the delegation path. To delegate a specific set of actions for a piece of scrip 400 from the delegator 510 to the delegates 512, the delegator 510 transmits 520 the scrip 400 to the delegates 512. In addition, the delegator 510 transmits 522 the delegation for the piece of scrip to the delegatee 512. The delegation delegates a set of actions that can be performed by the delegator 510 to the delegatee 512. To delegate a specific set of actions in a delegation, the delegator 510 appends the names of the new sets of actions to the delegation owned by the delegator. So, if the set of actions owned by the delegator 510 is "X, Y, Z," and the delegator is delegating the actions "X, Z" to the delegatee 512, the delegator sends the delegation "X, Y, Z/X, Z" to the delegatee, where the "/" is the delimiter between the delegations. The delegator 510 also transmits 524 a delegation scrip secret (DSS) to the delegatee 512. Any secure mechanism can be used to transmit the DSS. Although not shown at this point in FIG. 5, the delegator 510 and delegatee 512 preferably establish a delegation pass phrase (DPP), and use the DPP to encrypt the DSS before it is transmitted. The delegatee 512 uses the DSS to validate that it has the right to perform the delegated actions on the scrip. The calculation of the DSS is defined as a recursive function: Let A, B, . . . , X, Y be sets of delegated actions, then: DSS(A/ . . . /X/Y)=H(A/ . . . /X/Y, DSS(A/ . . . /X)); DSS(A/ . . . /X)=H(A/ . . . /X, DSS(A/ . . . /W)); . . . DDS(A)=H(A, CS); DSS()=CS, where H(a, key) denotes the keyed hash function where "a" and "key" are any string or sequence of bits, and CS is the customer secret for the scrip. Thus, the DSS for the root delegation is the CS for the scrip. The DSS for a new delegation is the hash of the delegation using the DSS for the ancestor delegation as a key. As an example; suppose there are four possible actions on a piece of scrip: A, B, C, and D. The delegation for actions A, C, and D, and its DSS, is: ("A, C, D", DSS("A, C, D")), where "A, C, D" is a string containing the names of the actions in the delegation and DSS("A, C, D") is the DSS for the delegation. Fully expanded, the delegation and DSS for actions A, C, and D is: ("A, C, DD", H("A, C, D", CS)) The CS is used in the hash because the CS is the DSS for the previous (i.e., root) delegation. Since each piece of scrip has a different CS, the delegation is only effective for the single piece of scrip having this CS. To further sub-delegate actions A and D, the delegation and DSS is: (A, C, D/A, D", DSS("A, C, D/A, D")). Fully expanded, the sub-delegation for actions A and D and the DSS is: ("A, C, D/A, D", H ("A, C, D/A, D", DSS("A, C, D")))=("A, C, D/A, D", H("A, C, D/A, D", H("A, C, D", CS))). As described above, the sub-delegated actions are appended to the old delegated actions. The hash key is the DSS of the old delegation. The actions can be further sub-delegated. To sub-delegate the action D, the delegation and DSS is: ("A, C, D/A, D/D", H("A, C, D/A, D/D", DSS("A, C, D/A, D"))). If the path of delegations and sub-delegations is different, then the DSS for the delegation is different. For example, other delegations of action D and the associated DSS might be: ("D", DSS("D")); or ("B, C, D/D", DSS("B, C, D/D")). In each of these examples, the path of ancestor delegations that led to the delegation of D is different, thereby causing the delegation and DSS to be different. The delegator 510 and delegates 512 preferably store the scrip and any delegations of the scrip in a shared scrip file. The particulars of the scrip file are described in more detail below. The basic method for protecting stored scrip is described in U.S. patent application Ser. No. 09/273,240, entitled ENCRYPTING SECRETS IN A FILE FOR AN ELECTRONIC MICRO-COMMERCE SYSTEM, which was filed on Mar. 19, 1999, and is hereby incorporated by reference herein. In brief, application Ser. No. 09/273,240 describes a method and system for protecting scrip stored in a file with a pass phrase. The user of the scrip (e.g., the consumer) supplies a pass phrase. The customer secrets for the scrip in the file are encrypted using the formula: ECS=CS XOR H(nonce, pass phrase), where ECS is the encrypted CS. The ECS and the nonce are stored with each piece of scrip in the file. When the user provides the pass phrase, the hash is computed and XORed with the ECS to get the original CS. A preferred embodiment of the present invention encrypts the DSS for a piece of scrip and any sub-delegations of the scrip using similar techniques. Preferably, each delegatee 512 having a copy of the scrip should be able to decrypt its own delegation scrip secrets and any secrets that are derived from its delegations (i.e., from subsequent delegations made by the delegates 512). Each delegatee 512, however, should not be able to decrypt ancestor delegations or delegations that are not derived from the delegatee's delegation. The root delegator 510 is able to decrypt and encrypt every DSS. Accordingly, the delegator 510 preferably derives the pass phrase for delegations from the delegator's own pass phrase. According to this embodiment, the new delegated pass phrase (i.e., the delegatee's pass phrase) is calculated with a formula similar to the formula used to calculate the DSS. So: DPP("A, C, D/D")=H("A, C, D/D", DPP("A, C, D")), where DPP is the delegated pass phrase for the parent delegation. Accordingly, the new DPP is the hash of the new delegation using the delegator's pass phrase as the key. The pass phrase for the root delegation is preferably the pass phrase provided by the user. The DPP is preferably transmitted 526 to the delegatee 512 in a secure manner and the delegatee is responsible for remembering the pass phrase. For instance, the delegatee may store the DPP in an encrypted form and decrypt it as necessary. The delegator 510 does not have to remember the DPP because the DPP can be derived using the delegation and the delegator's own pass phrase. In an alternate embodiment, the pass phrase is chosen randomly and explicitly stored with the scrip. The delegatee 512 preferably uses the DPP to encrypt the DSS for its delegation by using the equation: EDSS=DSS XOR H(nonce, DPP), where EDSS is the encrypted DSS, DSS is the DSS for the scrip, and DPP is the DPP received from the delegator 510. The EDSS is stored with the nonce and delegation in the scrip file. Since the delegates 512 knows the DPP, and can read the nonce and EDSS from the file, the delegates 512 can easily decrypt the EDSS. FIG. 6 is a block diagram illustrating a scrip file 600 that is preferably held by the wallet 221 on a consumer computer system 130 or held in an agent computer system 150. The scrip file 600 contains one or more entries 610A, 610B, 610C, and each entry, such as entry 610A, holds a piece of scrip 400A. The scrip 400 has the fields illustrated in FIG. 4. In addition, each entry 610 holds an ECS 612A for the scrip and the nonce 614A used to encrypt the CS. Since the CS is the root delegation for the scrip 400A, the ECS 612A is also the EDSS for the root delegation. In addition, the entry 610 preferably holds a (delegation 616A, EDSS 618A, nonce 620A) triple for its own delegation and for each sub-delegation of the scrip 400A. FIG. 7 is a flowchart illustrating steps for using delegated scrip in the electronic commerce system 100. The agent 151 or another delegatee, requests 710 that an action be performed on the scrip 400 by another party, such as a broker 111 or a vendor 121. For example, the agent 151 may request that the broker 111 refresh scrip 400 that is about to expire. For convenience, the party receiving the request is referred to as a "server." Assume that the agent 151 has received a sub-delegation for an action D on a piece of scrip, scrip1 . Further assume that the total delegation path is "A, C, D/D". To request the action D on the scrip, scrip1, the agent 151 sends a message to the server including the action, the scrip, the delegation authorizing the action, and a request stamp (RS). Thus, the message in this example is: D, scrip1, "A, C, D/D", RS. The RS is preferably calculated as a hash of the action, scrip, and delegation concatenated together, with the DSS as a key. The RS in this example is: RS=H(D, scrip1, "A, C, D/D", DSS("A, C, D/D")). When multiple pieces of scrip are used in a single action, the key for the RS hash is preferably the hash of all of the delegated scrip secrets. The server receiving the request (e.g., a broker 111 or vendor 121) validates 712 the request by recalculating the RS. The server knows the CS for the scrip because the server either initially issued the scrip or shares data with the party that did. Accordingly, the server can calculate the DSS from the CS. In this example, the DSS is calculated as follows: DSS("A, C, D")=H("A, C, D", CS); DSS("A, C, D/D")=H("A, C, D/D", DSS("A, C, D")). Once the server has the DSS for the scrip, the server recalculates the RS: RS=H("A, C, C/D", scrip1, "A, C, D/D", DSS("A, C, D/D")). If the RS calculated by the server matches the RS provided by the agent 151, then the server knows that the agent knows the DSS and that action D has been delegated to the agent 151. Therefore, the server validates 712 the request. For almost all actions, the server replies 714 to the request with new scrip. The new scrip may be, for example, refreshed scrip having a later expiration date. When a server replies 714 to the request, the reply includes the delegation of the scrip, all ancestor delegations of the scrip, and a new DSS for each delegation. In other words, if the delegation for the request is "A, C, D/D", the reply includes the scrip and the specific DSS for each of the three delegations: "A, C, D/D"; "A, C, D"; and "" (the root delegation). The DSS for each of these delegations is returned securely as an EDSS using a New Delegated Scrip Secret (NDSS) function. The definition of NDSS includes dependencies on the specific pieces of incoming and outgoing scrip because there may be multiple pieces of scrip returned in one transaction and each has its own DSS. An EDSS is calculated as follows: EDSS=NDSS(delegation, incoming_scrip, outgoing_scrip, nonce)=H(nonce, DSS(delegation, incoming_scrip)) XOR DSS(delegation, outgoing_scrip), where incoming_scrip is the piece or pieces of scrip received from the agent 151, outgoing_scrip is a specific piece of scrip being returned by the server. and XOR is the exclusive-or operator. When multiple pieces of incoming scrip are used, the key for the NDSS hash is not the DSS from a single piece of scrip, but instead is the MD5 hash of the delegated scrip secrets from all of the pieces of scrip. For the example of FIG. 7, suppose that S1 is the incoming scrlp and S2 is the ougoing_scrip. Three delegations are returned giving the delegation string, the nonce used in the NDSS calculation, and the encoded delegation secret: EDSS_1 ("", nonce1, NDSS("", S1, S2, nonce1)); EDSS_2 ("A, C, D", nonce2, NDSS ("A, C, D", S1, S2, nonce2")); and EDSS_3=("A, C, D/D", nonce3, NDSS ("A, C, D/D", S1, S2, nonce3")), where EDSS_n are the returned encrypted delegations and nonce1, nonce2, and nonce3 are the nonces for the each delegation. Calculating the NDSS is relatively efficient. The first new delegation requires only three hashes and is calculated as: NDSS("", S1, S2, nonce1)=H(nonce1, DSS("", S1)) XOR DSS("", S2)=H(nonce 1, H("", CS1)) XOR H("", CS2), where CS1 is the CS for scrip1 and CS2 is the CS for scrip2. Once the root DSS functions for S1 and S2 are calculated, the second new delegation requires only three additional hashes: NDSS("A, C, D", S1, S2, nonce2)=H(nonce2, DSS("A, C, D", S1)) XOR DSS("A, C, D", S2)=H(nonce2, H("A, C, D", DSS("", S1))) XOR H("", DSS("A, C, D", S2)). Similarly, the final NDSS calculation also requires only three additional hashes. When the reply is received by the agent 151, the agent decodes 716 the EDSS to obtain the DSS for the new scrip. The agent 151 knows the scrip it used in the request, S1, and the delegation scrip secrets for its delegation and any of its sub-delegations. The reply returns the nonce, so the agent 151 can calculate: H(nonce, DSS(delegation, S1)). The agent 151 XORs this value with the EDSS value for its delegations. Since the two hash values cancel (because the values are equal and have been XOR'ed), the result of the XOR is the new DSS for the scrip. When the EDSS 618 is stored in the scrip file 600, the EDSS is said to be in "immediate" format--meaning it can be decrypted immediately by the agent 151. However, the agent 151 making the request is not able to decode the new delegation scrip secrets for the delegations of its ancestors on the delegation path because the agent does not know the original delegation scrip secrets for those delegations. For each of those delegations, the agent 151 stores the nonce, the EDSS, and the originating scrip in the scrip file 600 in place of the EDSS 618 value. An EDSS 618 represented in this manner is said to be in "deferred" format, since the decryption of the value is deferred to later. For efficiency, the originating scrip needs to be stored only once for multiple deferred EDSS values. When an ancestor of the delegatees 12 becomes active, it can then derive the deferred delegated scrip secrets. To do this deriving, the ancestor first decrypts the DSS for the old scrip, then it uses the old scrip's DSS to decode the new DSS. The ancestor can optionally decode only its own delegated scrip secrets or decode all of the deferred secrets for itself and any delegations derived from itself. If multiple pieces of scrip ate returned, the deferred secrets do not necessarily depend on a single piece of scrip but instead depend on all of the pieces of scrip that went into the action. Accordingly, the preferred deferred secret format gives all the scrip that it depends on and the scrip file preferably includes all of the scrip until the deferred secrets are decoded. If the delegatee 512 performs a series of actions between activations of its ancestor, then it preferably stores all of the scrip involved in the transactions in the scrip file 600. When an ancestor delegator (typically the consumer 131) is eventually activated, it preferably resolves all of the deferred DSS in the chain of derived scrip. Once all of the derived scrip is consumed, the originating scrip is preferably deleted. In an alternative embodiment of the present invention, the scrip represents an "authentication" value in a light-weight security system, rather than a monetary value in a commerce system. In this embodiment, the consumer 131 purchases authentication scrip by presenting authentication credentials to a broker 111. The broker 111 verifies the credentials and, if appropriate, issues the authentication scrip to the consumer 131. Once the consumer 131 has the authentication scrip, the consumer can use it to access restricted content held by a vendor 121 in the same way a consumer uses monetary scrip to purchase content. The price of accessing restricted content is possession of scrip allowing access. The consumer 131 can delegate the authentication scrip to a delegatee using the delegation tools described above. Different delegations of the scrip can allow access to different levels of restricted content. For example, assume content can have one of three increasing levels of security. Moreover, assume that content can only be accessed by a consumer 131 having a security clearance at least as high as the content. A consumer 131 having authentication scrip proving the highest security clearance (i.e., the root delegation) can access all of the content. By using the delegation tools described above, the consumer 131 can delegate lower levels of clearance to delegatees, thereby allowing the delegatees to access only certain content. Having described a preferred embodiment of the invention, it will now become apparent to those skilled in the art that other embodiments incorporating its concepts may be provided. It is felt therefore, that this invention should not be limited to the disclosed invention, but should be limited only by the spirit and scope of the appended claims.
|
Same subclass Same class Consider this |
||||||||||