Intercepting key sessions

[0001] This application claims priority under 35 U.S.C. §119(e) to U.S. Provisional Patent Application Ser. No. 61/607,681, filed on Mar. 7, 2012, the entire contents of which are hereby incorporated by reference.

[0002] In public-key cryptography, key agreement allows two parties to securely establish a shared secret key. Importantly, the parties are not required to have any shared information in advance of the key agreement protocol. Typically both parties have a certificate, issued by a mutually trusted party called a CA (a certificate authority). The certificate binds the identity of each party to their public key, to assure the other party that the correct public key is being used in the key agreement protocol. Traditionally, a public-key certificate for the party U consists of the CA's signature on U's public key, their identity, and some additional information. In an implicit certificate scheme, the certificate consists of a value, denoted P_U, that is jointly computed by the CA and U, along with some additional information, denoted I_U. The certificate is denoted cert_U=(P_U, I_U). The public key, denoted Q_U, can be derived by anyone from cert_U and the CA's public key, and public parameters. The security of the scheme ensures that only U will know the secret key associated with the public key derived from cert_U. Examples of traditional (explicit) certificates are X.509 certificates signed with, for example, Elliptic Curve Digital Signature Algorithm (ECDSA). An example of implicit certificate scheme is Elliptic Curve Qu-Vanstone (ECQV).

[0003] In some implementations, a method for providing a session key to a third party includes obtaining a private key associated with a public key certificate, and the session key for a communication session is based, at least in part, on the private key, an associated seed for a random number generator, and public keys assigned to a device participating in the communication session. The private key associated with the public key certificate is transmit, to an interception authority, and the interception authority is configured to grant the third party access to the private key and the associated seed to in response to a request from a third party authorized to access the communication session.

[0006] Like reference symbols in the various drawings indicate like elements.

[0007] The present disclosure is directed to a system and method for enabling lawful interception of communication sessions by escrowing information used to construct associated session keys. The escrowed information may include one or more private keys, one or more seeds for a pseudorandom generator (RNG), and/or other private information used to generate a session key. In general, lawful interception (e.g., allowing police to recover the session key) is a requirement for many telecommunications standards, such as 3rd Generation Partnership Project (3GPP). In some implementations, a key agreement protocol may involve an escrow system or trusted entities that support lawful interception by authorized parties. For example, the escrowed information may be distributed amongst two or more trusted entities, and, in order to decrypt communication sessions, the authorized party may generate the associated session key by combining the information stored at each of the trusted entities. By dividing the information among different entities, the potential for abuse may be eliminated, minimized or otherwise reduced. In order to receive the information, law enforcement may submit a request to each of the entities identifying the communication session and their basis for authorization.

[0008] As previously mentioned, lawful interception may allow a third party L to learn, construct or otherwise generate the session key shared between two parties U and V. L is typically a law-enforcement agency, who may intercept a session with appropriate authorization, such as a warrant. The phrase “intercept a session” may include L learning the session key for the session and/or decrypting the traffic. In some implementations, strong cryptography may be executed, but the disclosed key agreement protocol enables L a mechanism to compute the session key. Conventional systems typically use weak cryptography, which also allows interception by individuals without proper authorization. Interception in this disclosure may be undetectable by U and V, not impact performance, and may not depend on their participation. For these reasons, the disclosed systems may not escrow session keys for each communication session.

[0009] For example, L may not directly have access to session keys. Instead, U and V may escrow some private or secret information with one or more interception authorities (IAs). The IAs may be denoted as A₁, . . . , A_α, and for simplicity the current example has α=2. For each session intercept, L may contact A₁ and A₂, requesting access to session s. A session may be identified by a public identifier, denoted s. To give L access to s, IAs A₁ and A₂ may each respond with some secret information. L may then generate the session key for s using this information and decrypt the traffic. In some instances, L may only use secret information from one of U or V to intercept a session between them. In some implementations, none of the IAs can escrow sufficient information to learn any of the session keys individually. One or more of the participating IAs may be one or more Certificate Authorities (CAs). In some implementations, U and V may not perform additional security at the application layer such as by sending encrypted email or using an encrypted instant messaging service. In some implementations, the secret information provided to L may only allow a single session to be intercepted, so future and past communications of U and V may remain private, as do communications between U, V and other parties in other sessions. Limiting interception to a single session may be referred to as fine-grained access control. If both IAs participate, two independent checks of authorization may be provided. In addition, security may be maintained in the event of compromise of one of the IAs.

[0010] In some implementations, the key agreement protocol may be implemented based on ECQV. In these instances, an ECQV-escrow system may include a set of modifications to the conventional ECQV protocols. ECQV-escrow may proceed in a substantially identical manner to ECQV except certificate requests from users may be replaced by (0,O) (the trivial key pair, where the secret part of the request is the integer zero, and the public part is the zero (i.e., the identity element) of the elliptic curve group, which may also be referred to as the point at infinity), and the CA's response may be kept private. With ECQV-escrow, the CA may know the secret key corresponding to some, substantially all, or all issued certificates. In this implementation, ECQV-escrow certificates may be used. In addition, the issuing CA may be one of the IAs (e.g., A₁), and the certificate cert_U for the user U may be created by the CA. U's device may also contain a deterministic random number generator (RNG) that is seeded with the seed value seed_U. The second IA, A₂ may escrow seed_U.

[0011] During key agreement, the ECMQV protocol may be used. An ECMQV session may be established with two public keys (per participant), typically called the long-term and ephemeral public key. The long-term public key may be the ECQV-escrow key (known to CA, who may act as A₁). The ephemeral key R_U may be generated with an RNG seeded by seed_U. Since A₂ knows seed_U, A₂ may compute the ephemeral secret key as well. The session identifier may be s=(cert_U, R_U, cert_V, R_V), which is typically communicated publicly by U and V during the ECMQV protocol.

[0012] Also, the protocol may have an increased number of IAs, (for example, by deriving the ephemeral secret from multiple RNG seeds and escrowing each with a different IA), or use only a single CA/IA, by having a single party implement both escrow functions. A non-interceptable session may be provided easily if desired, by choosing the ephemeral secret from another, non-escrowed seed (other steps may be unchanged). The session key may be provided in nearly real-time. Once s is known, the IAs may send L information used to reconstruct the session key. L may also be given the ability to intercept the next k sessions of party U, by receiving the information from CA, then receiving the next k ephemeral keys U will use from A₂.

[0013] Turning to an example system for executing one or more implementations of the present disclosure, FIG. 1 is a schematic diagram of an example data communication system 100 showing an example context where secured traffic can be intercepted by third parties. The illustrated system 100 is for example purposes only and other systems may be used to enable a third party to intercept communications without departing from the scope of the disclosure. For example, other systems may include two or more interception authorities (IAs) independent of certificate authority (CA). As illustrated, system 100 includes a CA server 102, an IA server 104, two terminals 106a and 106b, and a third party device 108 coupled through a data network 110. The data communication system 100 can include additional, fewer, or different components. For example, the data communication system 100 may include additional storage devices, additional servers (including additional CA servers and/or IA servers), additional terminals, and other features not shown in the figure.

[0014] At a high level, the CA server 102 is an electronic device that issues public key certificates (e.g., implicit certificate), escrows one or more private keys for other devices such as the terminals 106, and discloses the private keys to the third party device 108 when authorized. The IA server 102 is an electronic device that escrows secret information (e.g., private keys, seeds for random number generators) for other devices such as the terminals 106. The terminals 106 are electronic devices that are owned, operated or otherwise associated with a user and operable to at least establish communication sessions. The third party device 108 is an electronic device that are owned, operated or otherwise associated with an enterprise (e.g., law enforcement or government agency, medical agency) and may transmit, to the CA server 102 and the IA sever 104, requests for secret information of the terminal 106a or 106b based on an authorization (e.g., warrant). After receiving the secret information, the third party 108 may generate the session key and decrypt a communication session between terminals 106a and 106b. Turning to a high level description of operation, the CA server 102 may issue public key certificates to the IA server 104, the terminals 106, and the third-party server 108. Using the issued certificates, the terminals 106a and 106b may establish a secured communication. In connection with the communication session, the terminal 106a may transmit at least one of a private key to the CA server 102 or secret information to the IA server 104 such as, for example, a seed for a random number generator. The third-party device 108 may transmit a request for secret information to the CA server 102 and the IA server 104 that also includes information identifying an authorization. In response to at least the request, the CA server 102 and the IA server 104 may transmit the requested secret information to the third-party device 108. The third-party device 108 may generate the session key for the communication session between the terminals 106a and 106b using the received secret information and decrypt the communication session.

[0015] Turning to a more detailed description of the aspects of the system 100, the CA server 102 can include any software, hardware, and/or software configured to issue certificates and escrow private keys of different user devices such as terminals 106. For example, the CA server 102 may issue explicit or implicit certificates to the IA server 104, the terminals 106, and/or the third-party device 108. In some implementations, the CA server 102 may execute one or more of the following: receive requests for public key certificates via the network 110; generate public key certificates (e.g., explicit certificates, implicit certificates) in response to at least the requests; transmit the generated certificates to the requesting devices; establish secure communication sessions with devices in the network 110; escrow private keys or secret information for devices that were issued public key certificates; receive requests for private keys from third party devices 108; verify authorizations of the third-party devices 108; establish secured communication session with the third-party device 108; transmit a private key associated with the communication session identified in the request; and/or other operations. In some implementations, the requesting device may be a server (e.g., IA server), a terminal, a third-party device, or other computing device. In regards to secure communication sessions, different entities may establish secure communications using any of a number of processes. In some examples, seed escrow may always include a secure channel between the UE and the IA. In some examples, the certificate request from the UE to the CA may not include a secure channel but the response from the CA may include a secure channel as it may have the long-term private key (in the ECQV-escrow primitive). In summary, communication sessions may not always include secure channels, or secure channels may not be limited to specific mechanisms for establishing one (e.g., issued certificates) without departing from the scope of this disclosure. In short, the CA server 102 is a computing system that can perform operations of a certificate authority in a cryptography system. The CA server 102 is generally operable to receive, transmit, process, and store information associated with the cryptography system. Although FIG. 1 shows a single CA server 102, a certificate authority can be implemented using multiple certificate authority servers 104, including server clusters, as well as additional or different types of computing devices other than servers.

[0016] The CA server 102 generally includes a data processing apparatus, a data storage medium, and a data communication interface. For example, the CA server 102 may include a processor, a memory, an input/output controller, and/or other features. A memory can include, for example, a random access memory (RAM), a storage device (e.g., a writable read-only memory (ROM), etc.), a hard disk, a buffer memory, or another type of storage medium. The memory can store instructions (e.g., computer code) associated with computer applications, programs and computer program modules, and other resources. The processor can include any type of data processing apparatus, for example, a general purpose micro-processor, a specialized processor, a digital controller, or another type of device. An input/output controller can be coupled to input/output devices (e.g., a monitor, a keyboard, etc.) and to the data network 110. The input/output devices can receive and transmit data in analog or digital form over communication links such as a serial link, wireless link (e.g., infrared, radio frequency, etc.), parallel link, or another type of link.

[0017] The IA server 104 can include any hardware, software, and/or firmware that escrows secret information of the terminals 106 and provide the third-party device 108 with the secret information. For example, the IA server 104 may store a seed for a random number generator for the terminal 106 and transmit a private key based on the seed to the third-party device 108. In some implementations, the IA server 104 may execute one or more of the following: transmit a request for a public key certificate to the CA server 102; establish secure communication sessions with the terminal 106a or 106b; receive secret information (e.g., seed) from the terminal 106a or 106b; store the secret information received from the terminal 106; receive a request for the secret information from the third party device 108; generate a private key for the terminal 106 in response to at least the request; establish a secure communication session with the third party device 108; transmit to the third party device 108 the generated private key using a session key; and/or other operations. In regards to certification, the IA server 104 and the CA server 102 may cross certify each other. In some implementations, the IA server 104 may not directly transmit a generated private key to the third party device 108 but may compute a value based, at least in part, on the secret information. In these instances, the third party device 108 does not receive private keys from the CA sever 102 or the IA server 104, and, instead, the session key may be generated using the values.

[0018] The IA server 104 generally includes a data processing apparatus, a data storage medium, and a data communication interface. For example, the IA server 104 may include a processor, a memory, an input/output controller, and/or other features. A memory can include, for example, RAM, a storage device (e.g., a writable ROM), a hard disk, a buffer memory, or another type of storage medium. The memory can store instructions (e.g., computer code) associated with computer applications, programs and computer program modules, and other resources. The processor can include any type of data processing apparatus, for example, a general purpose micro-processor, a specialized processor, a digital controller, or another type of device. An input/output controller can be coupled to input/output devices (e.g., a monitor, a keyboard, etc.) and to the data network 110. The input/output devices can receive and transmit data in analog or digital form over communication links such as a serial link, wireless link (e.g., infrared, radio frequency, etc.), parallel link, or another type of link.

[0019] The terminals 106a and 106b may be any local or remote computing device operable to receive requests from the user via a user interface, such as a Graphical User Interface (GUI), a CLI (Command Line Interface), or any of numerous other user interfaces. Thus, where reference is made to a particular interface, it should be understood that any other user interface may be substituted in its place. In various implementations, each terminal 106 comprises an electronic computing device operable to receive, transmit, process and store any appropriate data associated with system 100. There may be any number of terminals 106 communicably coupled to the CA server 102. Further, “terminals 106” and “user” may be used interchangeably as appropriate without departing from the scope of this disclosure. As used in this disclosure, terminal 106 is intended to encompass a personal computer, touch screen terminal, workstation, network computer, kiosk, wireless data port, wireless or wireline phone, personal data assistant (PDA), smartphone, tablet computer, at least one processor within these or other devices, or any other suitable processing device. For example, terminal 106 may comprise a computer that includes an input device, such as a keypad, touch screen, mouse, or other device that can accept information, and an output device that conveys information associated with the operation of the CA server 102 or terminals 106, including digital data, visual information, or GUI. Both the input device and output device may include fixed or removable storage media such as a magnetic computer disk, CD-ROM, or other suitable media to both receive input from and provide output to users of terminals 106 through the display, such as a GUI.

[0020] The third party device 108 can include any software, hardware and/or firmware configured to intercept a communication session between terminals 106a and 106b. As previously mentioned, the third-party device 108 may be owned, managed or otherwise associated with one or more third parties. The third party may include any suitable government and/or other agency that may monitor communications to provide one or more services. For example, the third party may be a government agency that is assigned to enforce laws, regulations, and/or orders passed by legislative process. For example, the third party may be a law enforcement agency that investigates suspected criminal activity. In some implementations, the third party device 108 may execute one or more of the following: request a public key certificate from the CA server 102; record a communication session between the terminals 106a and 106b; establish secure communication sessions with the CA server 102 and the IA server 104; transmit a request for secured information to the CA server 102 and the IA server 104; receive secret information from the CA server 102 and the IA server 104; generate a session key based, at least in part, on the received secret information; decrypt the recorded communication session using the computed session key; and/or others.

[0021] The third party device 108 generally includes a data processing apparatus, a data storage medium, and a data communication interface. For example, the third party device 108 may include a processor, a memory, an input/output controller, and/or other features. A memory can include, for example, RAM, a storage device (e.g., a writable ROM), a hard disk, a buffer memory, or another type of storage medium. The memory can store instructions (e.g., computer code) associated with computer applications, programs and computer program modules, and other resources. The processor can include any type of data processing apparatus, for example, a general purpose micro-processor, a specialized processor, a digital controller, or another type of device. An input/output controller can be coupled to input/output devices (e.g., a monitor, a keyboard, etc.) and to the data network 110. The input/output devices can receive and transmit data in analog or digital form over communication links such as a serial link, wireless link (e.g., infrared, radio frequency, etc.), parallel link, or another type of link.

[0022] Network 110 facilitates wireless or wireline communication between computer CA server 102, IA server 104, and any other local or remote computer, such as terminals 106. Indeed, while illustrated as single network 110, network 110 may be multiple networks without departing from the scope of this disclosure, so long as at least portion of network 110 may facilitate communications secret information. In other words, network 110 encompasses any internal and/or external network, networks, sub-network, or combination thereof operable to facilitate communications between various computing components in the system 100. Network 110 may communicate, for example, Internet Protocol (IP) packets, Frame Relay frames, Asynchronous Transfer Mode (ATM) cells, voice, video, data, and other suitable information between network addresses. Network 110 may include at least one local area network (LAN), radio access network (RAN), metropolitan area network (MAN), wide area networks (WAN), all or a portion of the global computer network known as the Internet, and/or any other communication system or systems at least one location.

[0023] In one aspect of operation, the CA server 102 may set up a key agreement scheme including defining, for example, key pairs, RNG, elliptic curve domain parameters, a hash function, and/or others. In response to requests for public key certificates, the CA server 102 may generate public key certificates associated with one or more private keys, and transmit the public key certificates to the IA server 104, the terminals 106, and the third-party device 108. In addition, the CA server 102 may escrow the private keys associated with the public key certificates of the terminals. In connection with receiving the certificate, the terminal 106a may generate a seed for a random number generator and generate a second private key by seeding the RNG with the seed. To establish a communication session with the terminal 106b, the terminal 106a may generate a session key based, at least in part, on the two private keys and the public keys of the terminal 106b. In some implementations, the session key may be based on three or more private keys without departing from the scope of the disclosure. The third party device 108 may record or otherwise store the communication session between the terminals 106. In order to decrypt the communication session, the third-party device 108 may transmit, to the CA server 102 and the IA server 104, a request for the private keys of the terminal 106a that identifies the communication session and the basis for authorization. In connection with verification of the authorization, the CA 102 may establish a secured communication session with the third-party device 108 using the public key certificate of the device 108 and transmit the private key to the third party device 108 using a session key. In addition, the IA 104 may generate a different private key by seeding an RNG using a seed, establish a secure communication with the third party device 108, and transmit the different private key to the third-party device 108 using a session key. After receiving the different private keys, the third-party device 108 may generate a session key for the communication session between the terminals 106 using the private keys of the terminal 106a and the public keys of the terminal 106b. The third-party device 108 decrypts the communication session using the generated session key.

[0024] FIGS. 2-5 are flowcharts illustrating example methods 200, 300, 400, and 500 for intercepting communication sessions based on an ECQV protocol. In particular, methods 200-500 describe operations of individual elements participating in interception of a communication sessions as followed: method 200 describes a user device; method 300 describes a certificate authority; method 400 describes an interception authority; and method 500 describes an authorized third party. These methods are for illustration purposes only and that the described or similar techniques may be performed at any appropriate time, including concurrently, individually, or in combination. In addition, many of the steps in these flowcharts may take place simultaneously and/or in different orders than as shown. Moreover, systems may use methods with additional steps, fewer steps, and/or different steps, so long as the methods remain appropriate.

[0025] When describing the methods 200-500, an example interception process may identify parties as followed: CA for the certificate authority and for the first interception authority (A₁); A₂ for the second interception authority; U and V for the parties with certificates who will securely communicate; and L for an authority (such as law enforcement) intercepting a communication session. Referring to FIG. 2, method 200 begins a step 202 where a request is transmitted to the CA for an implicit certificate, and, at step 204, an implicit certificate is received. In the example, U may contact the CA who responds on a secure channel with cert_U=P_U|I_U and the secret key sk_U, using the ECQV-escrow primitive described above. At step 206, a seed for a RNG is generated. U may generate a seed seed_U at random for the RNG and Q_U may denote the public key derived from cert_U. Next, at step 208, the ephemeral key is generated by seeding the RNG with the seed seed_U. In the example, U may generate an ephemeral key pair (r₀, R₀), where r₀ is the first value generated by the RNG seeded with seed_U and R₀=r₀G where G is a point that generates the elliptic curve group. An authentication request is transmitted to the IA at step 210, and the IA is authenticated based on an implicit certificate of the IA at step 212. As for the example, U contacts A₂ and performs an ECMQV key establishment, mutually authenticated by cert_U and cert_A2. U's ephemeral key is R₀. A first session key is generated using the private keys and the public keys of the IA at step 214, and the seed is transmitted to the IA using the session key at step 216. Returning to the example, once the session is established, U may securely transmit seed_U to A₂. In connection with a communication session, public keys of a different terminal are identified at step 218, and, at step 220, a second session key is generated for the communication session with the other terminal. As for the example, U may generate the ephemeral keypair (r_U, R_U), and V generates the ephemeral keypair (r_V, R_V). U and V use the ECMQV primitive with the public key pairs (R_U, Q_U) and (R_V, Q_V), corresponding secret keys (r_U, sk_U) and (r_V, sky). The shared key is k_UV and the session ID is s=(cert_U, R_U, cert_V, R_V). Additional information (such as a timestamp) may be included in s, provided U and V exchange this information during key agreement.

[0026] Referring to FIG. 3, method 300 begins at step 302 where an ECQV scheme is generated including identifying an RNG. As for the example, the CA may set up the ECQV scheme (which includes generating a key pair, and choosing elliptic curve domain parameters, and a hash function) and may perform the following additional steps. The CA may also select an RNG that U and V use for key agreement. Next, at step 304, an implicit certificate is issued to an interception authority identifying it as an interception authority. Returning to the example, A₂ is issued an implicit certificate that indicates its status as interception authority (this certificate may be issued by the CA or another party). At step 306, a request for an implicit certificate is received from a terminal, and an implicit certificate is generated at step 308 using the ECQV-escrow primitive described above. The long-term private key associated with the implicit certificate is escrowed at step 310, and the implicit key and the long-term private key are transmitted to the terminal at step 312. In the example, CA, on a secure channel, transmits, to U, cert_U=P_U|I_U and the private key sk_U. A request for the long-term private key of a terminal is received from an authorized party at step 314. Again in the example, CA receives, from L, (s, U) and information identifying authorization for L. In some implementations, L may only send s because s includes certU which, in turn, includes U's identity. A secured communication session is established with the third party using a session key at step 318, and the long-term private key of the terminal is transmitted to the third party at step 320. In the example, if L is authorized for s, CA responds with sk_U.

[0027] Referring to FIG. 4, method 400 begins at step 402 where an implicit certificate is received from the certificate authority. In the example, A₂ is issued an implicit certificate that indicates its status as interception authority (this certificate may be issued by the CA or another party). At step 404, a lookup-table database is initialized. As for the example, A₂ initializes a lookup-table database D (we write D[key]=value). An authentication request is received from a terminal at step 406, and the terminal is authenticated at step 408 using the implicit certificate of the terminal. Again in the example, U contacts A₂ and performs an ECMQV key establishment, mutually authenticated by cert_U and cert_A2. Next, at step 410, the seed is received from the terminal, and, at step 412, the seed is escrowed. Returning to the example, U's ephemeral key is R₀, and, once the session is established, A₂ securely receives seed_U. A₂ then checks whether R₀ is correctly formed from seed_U, and aborts if not. In some implementations, A₂ may notify CA that U has completed the escrow step and the CA may revoke cert_U if U does perform the escrow step with A₂ within a certain amount of time. In some implementations, the seed escrow step may be done before the device is deployed to U (for example, by the manufacturer). In these instances, the procedure above may not be executed or may be used for special circumstances where U's device generates seed_U, for example, to replace an exposed seed or to periodically refresh the seed. A₂ sets D[cert_U]=seed_U, and responds success to U. A request for the ephemeral private key of the terminal is received at step 414. As for the example, A₂ receives, from L, (s, U) and information identifying authorization. In some implementations, L may only send s because s includes cert_U which, in turn, includes U's identity. At step 416, a secure communication session is established with third party using a session key, and, at step 418, the seed associated with the terminal is identified. The ephemeral key is generated by seeding the RNG with the identified seed at step 420, and the ephemeral key is securely transmitted to the third party using a session key at step 422. In the example, A₂ retrieves seed_U=D[cert_U], then computes r_U such that r_U=log(R_U), (where the logarithm is to base G) and sends r_U to L. A₂ may recover r_U by computing r₀, r₁, . . . and checking whether r_iG=R_U.

[0028] Referring to FIG. 5, method 500 begins at step 502 where a request for an implicit certificate is transmitted to the CA. At step 504, an implicit certificate including a long-term private key is received. A communication session for interception is identified at step 506, and the communication session is stored at step 508. Returning to the example, L may record the session between U and V. At step 510, a request for the long-term private key is transmitted to the CA, and a request for the ephemeral private key is transmitted to the IA. In the example, to intercept s for user U and recover k_UV, L sends (s, U) (and its authorization) to CA and A₂. In some implementations, L may only send s because s includes cert_U which, in turn, includes U's identity. At step 512, the long-term private key and the ephemeral private key are received from the CA and IA, respectively. As for the example, if L is authorized for s, CA responds with sk_U and A₂ responds with r_U. Next, at step 514, the session key for the communication session is generated using the received private keys and the public keys of the different terminal. In the example, L has (sk_U, r_U), (R_U, Q_U), (R_V, Q_V), which is used to recover k_UV by performing U's actions in the ECMQV primitive. The communication session is decrypted using the recovered session key at step 516. The described interception protocol is for illustration purposes and other implementations may be executed for the interception protocol without departing form the scope of the disclosure. In some implementations, L may censor R_V and cert_V from the request, in order to protect V's identity from CA and A₂. In some implementations, L may submit cert_U and a number of sessions k starting at counter C. The CA's response may be the same, but A₂ may respond with r_j for j=C, C+1, . . . , C+k. These implementations may be useful if L intends to intercept U's communication over an extended period of time, since it may not include interaction with CA and A₂ for each interception. In some implementations, A₂ may have an estimate of the number (or the exact number) of sessions that U has initiated, allowing him to compute r_U more efficiently. For example, if the estimated number (or exact number) is greater the number n, then r_n+1 may be computed, skipping computations for r₀, . . . , r_n, to determine whether r_UG=R.

[0029] In addition to the variations in the protocol discussed above, the key agreement may include alternative or additional variations. In some implementations, the key agreement may include an alternative randomness generation. In this variant, the random values may be computed as r_i←Fseed_U (time_U), where F is a pseudorandom function keyed by the value seed_U (an example choice of F is HMAC), and time_U is a timestamp chosen by U. Both U and V may include the timestamps in their ECMQV messages, and these values may be included in the SharedInfo parameter of the protocol In some implementations, the SharedInfo parameter may require that the user device (i) have a reliable clock (or access to a network time service, like on the cellular network), and (ii) implement the seed update step.

[0030] In some key agreement operations, entities U and V may establish keying data using the elliptic curve MQV scheme. For clarity, only U's use of the operation may described. Entity V's use of the operation may be analogous, but with the roles of U and V reversed. Entity U may establish keying data with V using the keys and parameters established during the setup procedure and the key deployment procedure as follows:

[0031] Input: The input to the key agreement operation may be:

[0032] 1. An integer keydatalen which is the number of octets of keying data required.

[0033] 2. (Optional) An octet string SharedInfo which consists of some data shared by U and V. This octet string may be included and may contain information identifying the entities U and V.

[0034] Output: An octet string K which is the keying data of length keydatalen octets, or “invalid”.

[0035] Actions: Establish keying data as follows:

[0036] 1. Use an elliptic curve MQV primitive to derive a shared secret field element z ε F_q from U's key pairs (d_1,U, Q_1,U) and (d_2,U, Q_2,U) established during the key deployment procedure and V's public keys Q_{1, V} and Q_2,V obtained during the key deployment procedure. If the MQV primitive outputs “invalid”, output “invalid” and stop.

[0037] 2. Convert z ε F_q to an octet string Z using a conversion routine.

[0038] 3. Use the key derivation function KDF established during the setup procedure to generate keying data K of length keydatalen octets from Z and [SharedInfo]. If the key derivation function outputs “invalid”, output “invalid” and stop.

[0039] 4. Output K.

[0040] When L makes a request to A₂ to intercept (s, U), it may also provide time_U, so that A₂ may quickly compute r_U as Fseed_U (time_U).

[0041] In another variation, an alternative interception may be executed. In this variant, L may not be given sk_U by CA, but L may still compute k_UV. The variant does include CA learning R_V and may not enable L to request intercept information for k future sessions in advance (as described in the second option to the intercept protocol above). This may be possible based on the following observation. In ECMQV, the point P from which k_UV is derived, can be written as
P=P₁+P₂
where
P₁=h(R_U*sk_U)(R_V+R_VQ_V), and
P₂=hr_U(R_V+R_V*Q_V)
and h is the cofactor of the elliptic curve, and notation Z* denotes an integer derived from the point Z. For example, a suitable key derivation function is applied to Z and some additional information such as, for example, the identifiers of the participants, timestamps, and the messages exchanged during the key agreement protocol. Since A₂ knows r_U, it may compute P₂. Since CA knows sk_U, it may compute P₁. L sends (s, U) to CA and A₂ and receives P₁ and P₂. In some implementations, L may only send s because s includes cert_U which, in turn, includes U's identity. L may then compute the ECMQV output point P and derive k_UV from it. In these implementations, L may not learn sk_U.

[0042] In another variation, the interception may operate with SEC 4 (Standards for efficient cryptography, SEC 4: Elliptic Curve Cryptography) compliant CAs. While the techniques previously described may execute specialized behavior from the CA, this solution may operate with standard (i.e., SEC 4 compliant) ECQV CAs. In these implementations, the user may obtain an ECQV certificate from a SEC 4 compliant CA and then simply sends its private key to another interception authority, A₃ (encrypted under A₃'s public key). A₃ may be the same party as the CA or may be a separate entity.

[0043] The described implementations may be extended to cover situations where L intends to intercept a session for which s is unknown but U and V are identified as the parties communicating. Since CA knows cert_U and cert_V, and thus Q_U and Q_V, the challenge may be to determine R_U and R_V such that the resulting k_UV is correct. Without additional information, given that U has participated in at most I_U sessions and V has participated in at most I_V sessions, A₂ may have to try I_U I_V pairs (r_U, r_V) in order to find k_UV used in s. If the service provider has an estimate of the number of sessions U and/or V have established, this information may be used to guide the search. Similarly, the number of potential k_UV to try may be smaller if the time stamping variant is used, provided the timestamps have low resolution, and L can reasonably estimate when the session was initiated. Implementing this feature may require that the user device (i) have a reliable clock (or access to a network time service, like on the cellular network), and (ii) implement the seed update step.

[0044] Testing whether a potential key k_UV is used in s is also an issue. Assuming that the plaintexts are drawn from a low-entropy distribution, decrypting a portion of the ciphertext and checking for redundancy may be possible, depending on the mode. It may also be possible to attempt to verify a MAC of the ciphertext (again, depending on the mode). Most authenticated encryption methods should enable confirmation whether a partial decryption is successful.

[0045] A low-tech solution to intercept an existing session is to have the service provider interrupt it (e.g., drop the connection), forcing the devices to re-establish a new session, so that L may observe the initial handshake. This may however, cause U and/or V to suspect that the resumed session is being intercepted.

[0046] As discussed above, it may be desirable for L to be able to intercept all or substantially all of U's sessions over specified period of time. For example, L may be given a warrant to intercept all of U's communications during one month. Interception windows may be implemented by rotating the seed used to generate the ephemeral key r_U. A master seed s₀ is used with an RNG to generate sub-seeds: s₁ during time period t₁, s₂ for time period t₂, and so on.

[0047] Revealing s_i allows L to compute all of the ephemeral secrets used during time period i, but since the pseudorandom generator is backtracking resistant (a standard security property of RNGs), L cannot compute s₀ from S_i. Since the RNG is also unpredictable, computing S_i+1 from s_i is also intractable.

[0048] Implementing this feature requires that the user device (i) have a reliable clock (or access to a network time service, like on the cellular network), and (ii) implement the seed update step.

[0049] In general, the disclosed implementations can escrow two or more keys (or information allowing the two or more keys to be recovered), then use a key agreement protocol to compute a session key that uses both the escrowed keys or the information allowing the two keys to be recovered. A number of generalizations are possible. In some instances, the information escrowed may be a combination of keys, or seeds from which keys may be generated. In some instances, an Menezes-Qu-Vanstone (MQV) agreement protocol may be replaced with the Diffie-Hellman key agreement protocol, in any of possible combination of key types: (static, static), (static, ephemeral), or (ephemeral, ephemeral). In some instances, more than two keys may be used (and also escrowed) if variants of the MQV and DH key agreement protocols are used. An example of such an MQV variant that uses three keys simple replaces one of the key pairs (x, xG) by the combination of two others, i.e., the key pair (x₁+x₂, x₁G+x₂G) formed from the two others (x₁, x₁G) and (x₂, x₂G). In some instances, the ECQV-escrow method of certifying users' keypairs may be replaced with a standard explicit certificate scheme, such as X.509 certificates created with the ECDSA signature scheme, where the CA chooses the key pair of the user.

[0050] A number of embodiments of the invention have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the invention. Accordingly, other embodiments are within the scope of the following claims.

[0051] In some implementations, a method for providing a session key to a third party includes generating a public key certificate corresponding to a private key. The private key associated with the implicit certificate is stored. A session key for a communication session between a first device and a second device is based, at least in part, on the private key, an associated seed for a random number generator, and public keys assigned to the second device.

[0052] Various implementations may include one or more of the following. A seed associated with the first device is obtained, and the seed associated with the first device is stored. The seed for the random number generator is received. The seed for the random number generator is received from at least one of the first device or a manufacturer of the first device. A request for the implicit certificate is received from the first device, and the public key certificate is generated based, at least in part, on the request. A request for information associated with the first device is received from a third party, and the session key between the first device and the second device is determined using the requested information. When the private key comprises a long-term private key, an ephemeral private key is generated based, at least in part, on the associated seed, and the long-term private key and the ephemeral private key is transmitted to the third party. Information identifying different seeds for different time periods is received, and the associated seed is determined based, at least in part, on the information identifying the different seeds for the different time periods. When the private key comprises a first private key, a random number generator dependent on time and a current time are identified, and a second private key is determined based, at least in part, on the a time-dependent random number generator, the current time, and the associated seed. When a second value is calculated by interception authority different from the certificate authority based, at least in part, on the associated seed, the session key determined based, at least in part, on the first value and the second value, a first value is calculated based, at least in part, on the private key, and the first value is transmitted to the third party. The public key certificate is based, at least in part, on an Elliptic Curve Qu-Vanstone (ECQV) certificate protocol.

[0053] In some implementations, a certification authority includes memory and one or more processors. The memory is configured to store private keys associated with public key certificates. The one or more processors is configured to generate a public key certificate corresponding to a private key and store the private key associated with the implicit certificate. A session key for a communication session between a first device and a second device is based, at least in part, on the private key, an associated seed for a random number generator, and public keys assigned to the second device.

[0054] Various implementations may include one or more of the following. The processors are further operable to obtain a seed associated with the first device and store the seed associated with the first device. The processors are further operable to receive the seed for the random number generator. The seed for the random number generator is received from at least one of the first device or a manufacturer of the first device. The processors are further operable to receive a request for the public key certificate from the first device and generate the public key certificate based, at least in part, on the request. The processors are further operable to receive, from a third party, a request for information associated with the first device, and the session key between the first device and the second device is determined using the requested information. When the private key comprises a long-term private key, the processors are further operable to generate an ephemeral private key based, at least in part, on the associated seed and transmit the long-term private key and the ephemeral private key to the third party. The processors are further operable to receive information identifying different seeds for different time periods and determine the associated seed based, at least in part, on the information identifying the different seeds for the different time periods. When the private key comprises a first private key, the processors are further operable to identify a random number generator dependent on time, identify a current time, and determine a second private key based, at least in part, on the a time-dependent random number generator, the current time, and the associated seed. When a second value is calculated by an interception authority different from the certificate authority based, at least in part, on the associated seed, the key session determined based, at least in part, on the first value and the second value, the processors are further operable to calculate a first value based, at least in part, on the private key, and transmit the first value to the third party. The public key certificate is based, at least in part, on an Elliptic Curve Qu-Vanstone (ECQV) certificate protocol.

[0055] In some implementations, a method for providing a session key to a third party includes receiving information identifying a seed for a random number generator associated with a first device. The seed associated with the first device is stored. A session key for a communication session between the first device and a second device is based, at least in part, on a private key associated with a public key certificate, the seed for the random number generator, and public keys assigned to the second device.

[0056] Various implementations may include one or more of the following. The seed for the random number generator is received from at least one of the first device or a manufacturer of the first device. A request for information associated with the first user equipment is received from a third party, and the session key between the first device and the second device is determined using the requested information. When the private key comprises a long-term private key, an ephemeral private key is generated based, at least in part, on the associated seed, and the ephemeral private key is transmitted to the third party. Information identifying different seeds for different time periods is received, and the associated seed is determined based, at least in part, on the information identifying the different seeds for the different time periods. When the private key comprises a first private key, a random number generator dependent on time and a current time is identified, and a second private key is determined based, at least in part, on the time-dependent random number generator, the current time, and the associated seed. A first value is calculated based, at least in part, on the private key, a second value is calculated based, at least in part, on the associated seed, the session key is calculated based, at least in part, on the first value and the second value, and the session key is transmitted to the third party.

[0057] In some implementations, an interception authority includes memory and one or more processors. The memory is configured to store private keys associated with public key certificates. The one or more processors are configured to receive information identifying a seed for a random number generator associated with a first device and store the seed associated with the first device. A session key for a communication session between the first device and a second device is based, at least in part, on a private key associated with a public key certificate, the seed for the random number generator, and public keys assigned to the second device.

[0058] Various implementations may include one or more of the following. The seed for the random number generator is received from at least one of the first device or a manufacturer of the first device. The processors are further operable to receive, from a third party, a request for information associated with the first device, and the session key between the first device and the second device is determined using the requested information. When the private key comprises a long-term private key, the processors are further operable to generate an ephemeral private key based, at least in part, on the associated seed and transmit the ephemeral private key to the third party. The processors are further operable to receive information identifying different seeds for different time periods and determine the associated seed based, at least in part, on the information identifying the different seeds for the different time periods. When the private key comprises a first private key, the processors are further operable to identify a random number generator dependent on time, identify a current time, and determine a second private key based, at least in part, on the a time-dependent random number generator, the current time, and the associated seed. The processors are further operable to calculate a first value based, at least in part, on the private key, calculate a second value based, at least in part, on the associated seed, calculate the key session based, at least in part, on the first value and the second value, and transmit the key session to the third party.