HK1117304A - Clone-resistant mutual authentication in a radio communication network - Google Patents

Description

Anti-clone mutual authentication in a radio communication network

Priority requirement

The present application claims the benefit of U.S. provisional application No.60/636906 filed on 12/17/2004, the entire disclosure of which is incorporated herein by reference.

Background

The invention relates to user authentication. More particularly, and without limitation, the present invention is directed to a method of preventing cloning of a Subscriber Identity Module (SIM) and enhancing protection against cloned SIMs in a cellular radio communication network or other services, utilizing SIM-based authentication.

In existing second generation (2G) and third generation (3G) standards, security is based on a shared secret key K stored in the authentication center (AuC) of the home operator and in the "identity module" of the user, such as the global system for mobile communications (GSM) Subscriber Identity Module (SIM), Universal Mobile Telephone Service (UMTS) SIM (i.e. USIM) or internet protocol multimedia subsystem (IMS) SIM (i.e. ISIM). The user is authenticated (and billed) according to his identity, the International Mobile Station Identifier (IMSI) and the challenge-response protocol in which the user proves that he knows the shared secret key K.

Fig. 1 is a message flow diagram illustrating the message flow in the existing authentication procedure described in detail in the third generation partnership project technical specification 3GPP TS33.102, v6.2.0, incorporated herein by reference. The entities involved are the USIM 1, a Visitor Location Register (VLR)2 acting as middleware and a home environment authentication center (HE/AuC)3 generating an authentication vector. In the following description, the VLR and HE/AuC are indicated with reference to the network. The mechanism used is based on a secret key K shared between the USIM and the HE/AuC. Each USIM is assigned a random unique K. To enable (mutual) authentication, the USIM and HE/AuC prove knowledge of the secret key to the other party.

The USIM 1 sends an authentication request 4 to the VLR 2 and includes an identifier, such as an IMSI, in the request. The VLR forwards the authentication request to HE/AuC 3. When the HE/AuC receives the authentication request, the HE/AuC updates the sequence number (SQN)_HE) Selecting a random value RAND, and selecting a random value from the pair K, RAND and SQN_HEAnd the message field (AMF) applies a function f1 to calculate a keyed Message Authentication Code (MAC). The expected response (XRES) is calculated using the operator defined function f2 and may be kept secret, but is certainly known to the USIM and HE/AuC. HE/AuC also calculates a keyed value Ck ═ f3(K, RAND); lk — f4(K, RAND); AK ═ f5(K, RAND); and an authentication message called AUTN-SQN XOR AK | | | AMF | | | MAC, which are all defined in 3GPP TS 33.102. At 5, the HE/AuC sends RAND, XRES, AUTN, Ck, and lk to the VLR. At 6, VLR sends RAND and contained SQN to USIM_HE(privacy protection), AMF and MAC messagesAUTN。

The USIM 1 checks the MAC, which verifies that the sending entity, i.e. the network, knows the shared key K. After this check, the USIM knows that the challenge is from its HE/AuC 3. Note however that this does not prove that the challenge is sent from the legitimate network to the USIM, since the RAND and AUTN messages may have been intercepted by a fraudulent entity and replayed later. To prevent such replay attacks, the USIM has the SQN value relative to itself_MSTo test SQN_HEThe freshness of (c). SQN present if USIM determines_HEIs out of order, it returns an error code and a message AUTS. AUTS comprises a sequence number retained by the USIM (SEQ ID NO)_MS) (security protection) and MAC. If SQN_HEIs up-to-date, it has not been used previously and since RAND is bound to the sequence number by the checked MAC, it indicates that RAND is also up-to-date. The USIM then calculates a response RES ═ f2(K, RAND) and returns RES to VLR 2 at 7. The VLR checks RES ═ XRES. If this check is successful, the user is considered authenticated and the keys Ck and lk can be used for data protection (confidentiality and integrity).

However, existing standards do not provide any way to detect clones that employ multiple copies of the same K/IMSI. Protection against "cloning" relies only on the assumed difficulty of reverse engineering identity modules, such as USIMs, or the difficulty of knowing the shared secret K. Note, however, that these assumptions may not be as difficult. First, since the shared key K is shared between the identity module and the HE/AuC, at some point K must be passed to the AuC. This transfer is a weakness where a hacker or dishonest insider may learn K. Second, if a hacker/insider compromises the HE/AuC, security fails altogether not only for a single target user, but more likely for all users associated with the HE/AuC. Third, certain AKA algorithms (e.g., COMP128 version of GSMAKA) are vulnerable and access to the SIM allows easy reverse engineering of K by observing the RAND/RES pair. Fourth, processes in the SIM manufacturing environment may exhibit a risk of "K leakage.

Observed network behavior suggests that existing standards do not provide any way to detect clones that use multiple copies of the same K/IMSI. The same USIM can be used simultaneously without problems or failures of any kind. Existing networks and USIMs are not able to detect clones programmed with the same K/IMSI.

What is needed in the art, therefore, is a solution for preventing cloning of SIMs, USIMs, and ISIMs and enhancing clone protection that overcomes the shortcomings of the prior art. The present invention provides such a solution.

Disclosure of Invention

In one aspect, the present invention is directed to a method of preventing unauthorized copying of an Identity Module (IM). The method includes internally generating at least a first key (K1) and a different second key (K2) in the IM, wherein the generating step includes ensuring that K1 cannot be derived from K2, and in some embodiments also ensuring that K2 cannot be derived from K1. The IM then exports K2 and the Identifier (ID) to the Authentication Server (AS) while keeping K1 secret internally in the IM. K1 and K2 may constitute a secret/public key pair for asymmetric cryptography, in which case the public key K2 is secret in the AS. The internal information in the IM used to generate K1 and K2 may be erased to ensure that K1 cannot be derived from K2 or that K2 cannot be derived from K1.

Since the keys K1 and K2 are different, tampering/intrusion into the AS does not disclose information from which K1 can be inferred, thus preventing cloning of the IM. Similarly, the delivery of K2 from IM to AS does not need to be greatly protected. It will be seen that the present invention is still able to maintain the signalling flow of existing authentication protocols, but employs asymmetric cryptography rather than symmetric cryptography in the processing. Various detailed embodiments employing different types of asymmetric cryptography (e.g., encryption, signatures, etc.) are described below. An embodiment in accordance with a hash chain is also described.

As described later, in another aspect, it is also explained how K1 is made unavailable to derive K2. This has the following effect: even if IM is compromised (in which case it would be possible to clone IM), it is still not possible to clone AS (i.e. make an AS interoperable with IM).

In the authentication phase of the present invention, the third party authenticates the IM. The authentication phase comprises the following steps: initiating authentication by providing information containing at least the ID from the IM to a third party; forwarding the information from the third party to the AS; retrieving, by the AS, the K2 from the ID received from the third party; and generating, by the AS, at least a first value (R) and a second value (X) at least according to K2. The authentication phase further comprises: returning R and X from AS to the third party; forwarding R from the third party to the IM; generating, by the IM, a Response (RES) based at least on K1 and R; returning the RES from the IM to the third party; and checking RES by a third party according to X.

In another aspect, the present invention is directed to copy protected IM. The IM includes: means for internally generating at least a first key (K1) and a second key (K2) in the IM, while ensuring that K1 cannot be derived from K2 and K2 cannot be derived from K1; and means for exporting the K2 and the Identifier (ID) from the IM to an Authentication Server (AS) while keeping the K1 secret internally in the IM. IM may be implemented in a terminal that contains an e-commerce application that performs payment in accordance with IM.

In yet another aspect, the present invention is directed to an authentication server for authenticating an access Identity Module (IM) while preventing unauthorized duplication of the access IM. The authentication server includes: means for receiving an access request from an access IM; means for generating a challenge using information stored in the authentication server but not in the access IM, wherein the information stored in the authentication server is insufficient to create an IM clone; and means for generating an expected response expected from the valid IM. The authentication server further comprises means for sending a challenge to the accessing IM, wherein the challenge changes for each access attempt.

In yet another aspect, the present invention is directed to a system for providing access to a network for a valid IM while preventing access to the network by unauthorized IM clones. The system includes an authentication server for receiving an access request from an accessing IM, generating a challenge using information stored in the authentication server but not in the accessing IM, generating an expected response expected from a valid IM, and sending the challenge to the accessing IM, wherein the challenge changes for each access attempt, and the information stored in or generated by the authentication server is insufficient to create an IM clone that can respond as a valid IM. The system further comprises: means in the accessing IM for receiving the challenge and preparing and sending a response based on information in the challenge and information stored in the accessing IM but not in the authentication server; and means for providing access to the network for the accessing IM only if the response prepared by the accessing IM is equal to the expected response generated by the authentication server.

The system may also include an intermediate node adapted to receive the challenge and the expected response from the authentication server, forward the challenge to the accessing IM, receive the response from the accessing IM, and determine whether the response prepared by the accessing IM is equal to the expected response generated by the authentication server.

In yet another aspect, the present invention is directed to a method for providing access to a network for a valid IM while preventing access to the network by an unauthorized IM clone, wherein an accessing IM sends an access request to an authentication server. The method comprises the following steps in an authentication server: selecting a random value y; using RAND as g^yCalculating a random value (RAND); calculated value R ═ g^xyWhere x is a Diffie-Hellman private key known to the accessing IM; computing a shared secret key (K) using K-KDF (R, …), wherein KDF is a key derivation function; update sequence number (SQN)_HE) (ii) a Calculating a keying Message Authentication Code (MAC) using MAC f1(K, RAND SQN AMF …); calculating an expected response (XRES) using XRES ═ f2(K, RAND); calculating Ck by using Ck ═ f3(K, RAND); calculate 1K using lk ═ f4(K, RAND); calculating AK by using AK f5(K, RAND); forming a message AUTN by using AUTN (equal to SQN) XOR AK (absolute AMF) MAC; and sending the RAND, XRES, AUTN, Ck, and lk to a Visitor Location Register (VLR) serving the visiting IM.

VLR forwards RAND and SQN including privacy protection to visiting IM_HEMessage Field (AMF), and AUTN of MAC. The method then includes the following steps in accessing the IM: using R ═ RAND^xDetermination of R, thereinx is a Diffie-Hellman private key; calculating a shared secret key K KDF (R, …) using a key derivation function; calculating AK by using AK f5(K, RAND); extracting and verifying SQN_HEAMF and MAC; calculating a Response (RES) using RES ═ f2(K, RAND); and sending the RES to the VLR. The VLR then determines whether the RES received from the visiting IM is equal to the XRES received from the authentication server. The accessing IM is provided with access to the network only if the RES received from the accessing IM is equal to the XRES received from the authentication server.

In yet another aspect, the present invention is directed to a method for authenticating an accessing Identity Module (IM) while preventing unauthorized copying of the accessing IM in a network utilizing a signature scheme with message recovery. The public key U _ EK is generated internally in the access IM and registered on the Authentication Server (AS). When the accessing IM sends an access request to the AS including at least the IM identifier, the AS retrieves the public key U _ EK of the accessing IM. The AS preparation challenge CHAL, which contains at least one of a random value (RAND), a sequence number (SEQ) and additional DATA (DATA). The AS sends the challenge and the public key U _ EK of the accessing IM to the intermediate node, which forwards the challenge from the intermediate node to the accessing IM. The accessing IM then prepares the digital signature U _ SIGN (CHAL) of the challenge and sends the digital signature U _ SIGN (CHAL) to the intermediate node as a response RES to the challenge. The intermediate node verifies the response by determining whether the Challenge (CHAL) is equal to the public key U _ ek (res).

Drawings

In the following section, the invention will be described with reference to exemplary embodiments illustrated by the accompanying drawings, in which:

FIG. 1 (prior art) is a message flow diagram illustrating the flow of messages in a prior art third Generation partnership project (3GPP) authentication procedure;

FIG. 2 is a message flow diagram illustrating the flow of messages in a first embodiment of the invention;

FIG. 3 is a message flow diagram illustrating the flow of messages in one embodiment of the present invention employing a clear text interrogation system;

FIG. 4 is a message flow diagram illustrating the flow of messages in one embodiment of the invention employing an encrypted interrogation system;

FIG. 5 is a message flow diagram illustrating the flow of messages in an alternative embodiment of the present invention employing an encrypted interrogation system; and

fig. 6 is a message flow diagram illustrating the flow of messages in an alternative embodiment of the present invention employing a public key distribution system.

Detailed Description

The present invention employs an asymmetric cryptography system to prevent^*Cloning of SIMs (i.e., SIM, USIM, and ISIM) and enhancing protection against cloned Identity Modules (IMs). With the prior art arrangement (in)^*SIM and HE/AuC store the same information), the present invention stores and stores information in HE/AuC^*Information in the SIM is different and even if information in the HE/AuC leaks, it is not enough to clone^*And a SIM. In one embodiment of the present invention,^*the SIM internally generates its secret (private) public key pair and securely passes the public key to the HE/AuC. In another embodiment, the trusted third party generates a secret (private) public key pair. Trusted third party entering secret keys^*SIM and passes the public key to HE/AuC. Note that the system does not rely on shared keys as in the standard GSM/UMTS Authentication and Key Agreement (AKA) procedure.

The asymmetric scheme in the present invention may be based on public key encryption or on a Diffie-Hellman public key distribution system. In the first case, the secret key U _ SK is equal to the private key in the public key cryptosystem, and U _ PK represents the corresponding public key. In the second case, U _ SK represents the secret value (x) and U _ PK represents the corresponding public value g^x。

The invention is designed to prevent the lower part of the passing holeAttackers of information obtained in any of the three ways listed above^*And cloning SIM.

1. The information stored in the HLR/AuC is revealed to the attacker. This means that an attacker can generate a trusted challenge. However, it does not necessarily mean that an attacker may generate a cloned USIM.

2. The information stored in the VLR is revealed to the attacker. This should not enable an attacker to generate new valid challenges or give the correct response to saved challenges. The attacker should also not be able to derive the keys generated from the AKA procedure.

3. Information/parameters programmed into the USIM are revealed to the attacker. This should not enable an attacker to generate valid challenges. Note that information internally generated in the USIM is assumed not to be available to the attacker. Typically this is the private key in a public key system and if it is available, an attacker can obviously clone the USIM. However, in one embodiment, even if the private key becomes available, it still does not enable an attacker to issue valid authentication challenges, i.e. create a fake authentication server.

It is also assumed that the attacker can monitor all signaling between all involved entities until the moment the attack is performed.

The attacks considered by the present invention are standard attacks: (1) impersonating the user; (2) impersonating the system; (3) redirect attacks (i.e., redirecting authentication requests from one service to the USIM for another service); (4) replay attacks; (5) man-in-the-middle attacks to affect the key; and (6) deriving the key from the intercepted traffic and knowledge.

Fig. 2 is a message flow diagram illustrating a first embodiment of the invention, such as USIM 11^*Flow of messages between the SIM, Visitor Location Register (VLR)12 and HE/AuC 13. The USIM knows the Secret Key (SK), and the HE/AuC knows the Public Key (PK) corresponding to SK. In one exemplary embodiment, an RSA public key system is employed, but it is readily appreciated that any public key system may be employed. Although RSA hasCertain special advantages (discussed later), however, the use of other systems, such as those based on elliptic curves, may also be beneficial from an efficiency/bandwidth perspective. The USIM sends an authentication request 14 to the VLR and includes an identifier, such as an IMSI, in the request. The VLR forwards the authentication request to the HE/AuC. When the HE/AuC receives the authentication request, the HE/AuC selects a random value R and computes RAND ═ E (PK, R), where E is RSA encryption. Alternatively, the HE/AuC may add redundancy/padding to R here, e.g., according to PKCS #1v1.5 or RSA-OAEP standards. The HE/AuC also computes the derived shared secret key K using K ═ KDF (R, …), which is a key derivation function (e.g., based on AES or HMAC). HE/AuC updates sequence number SQN_HEMAC is calculated using f1(K, RAND | | SQN | | | AMF …), XRES is calculated using f2(K, RAND), Ck is calculated using f3(K, RAND), lk is calculated using f4(K, RAND), AK is calculated using f5(K, RAND), and the construction message AUTN ═ SQN XOR | | AMF | | MAC is as described in 3GPP TS 33.102. At 15, the HE/AuC sends RAND, XRES, AUTN, Ck, and lk to the VLR. At 16, the VLR forwards the RAND and the contained SQN to the USIM_HE(privacy protection), AMF and AUTN of MAC.

Upon receiving the RAND and AUTN, the USIM 11 determines R ═ D (SK, RAND), where D is RSA decryption. If the HE/AuC adds redundancy/padding to R, the USIM checks here for redundancy/padding. The USIM also employs a key derivation function to compute a shared secret key K KDF (R, …). The USIM then proceeds as in 3GPP TS33.102 to prepare a response RES. At 17 the USIM sends RES to the VLR, which determines whether the RES received from the USIM is equal to the XRES received from the HE/AuC. If an RSA-based public key scheme is employed in which only the public key's modulus is stored in the USIM, but not the prime number that forms the public key, and in which the public key is erased after it has been distributed to the HE/AuC, the information in the USIM is insufficient to generate a valid challenge.

Thus, the present invention applies public key cryptography (or a hash chain, described below) to protect user authentication. The public key solution is consistent with the message exchange of the standard UMTS AKA procedure and employs the same confidence model, with slight modifications to the message format and processing. The hash chain solution may require a small amount of extra signaling, except in the ISIM case, where the solution only affects home network internal signaling.

Alternatively, the present invention may employ a plaintext challenge method instead of the encrypted challenge method described above. Both methods first assume that the USIM generates a private/public key pair (internal) and registers the public key with the HE/AuC in a secure manner. "secure" here means authenticated but not necessarily encrypted. USIM operations that cannot be cloned and enable attack detection will perform operations involving the private key in order to generate a digital signature, or to retrieve plaintext information. Clear text challenge also assumes that the USIM and HE/AuC share a secret, but alternatively this assumption may be replaced with the assumption that the HE/AuC has a private/public key.

By explicitly correlating AKA output with the IMSI of the USIM, the present invention adds an overall improvement to the standard UMTS AKA system and to the new AKA solution described below. This makes it impossible to program a USIM for standard UMTS AKA procedures with the key K of a given user and generate a correct response.

The present invention also relates the standard UMTS AKA output to the sequence number of the challenge. Including the serial number in the response calculation prevents the output parameter from being calculated from the previously used input parameter.

Clear text interrogation system

Fig. 3 is a message flow diagram illustrating the flow of messages between the USIM 11, VLR 12 and HE/AuC 13 in one embodiment of the present invention that employs a plaintext challenge system. In this embodiment, it is assumed that the USIM has already generated and registered its public key (U _ EK) on the HE/AuC. The USIM sends an authentication request 14 to the VLR and includes an identifier, such as an IMSI, in the request. The VLR forwards the authentication request to the HE/AuC. When the HE/AuC receives the authentication request, the HE/AuC retrieves the public key uek of the USIM and prepares a Challenge (CHAL). As in standard UMTS AKA, the HE/AuC maintains individual sequence counters for each USIM. Due to the fact that USIMs cannot be cloned, the generation of sequence numbers and SNAP used by USIMs can be adapted to system requirements and overall system solutions. The challenge comprises at least one of RAND and SEQ and possibly additional DATA (DATA). Preferably, RAND and SEQ are both part of a challenge, which preferably contains the service identifier in the DATA part. The service indicator makes it impossible to redirect a query from one service and use the result for another service.

The HE/AuC sends a Challenge (CHAL) to the VLR 12 at 18, along with the public key of the USIM (U _ EK), and the VLR 12 forwards the CHAL to the USIM at 19. The USIM prepares the digital signature U _ sign (CHAL) of the challenge and sends it as a Response (RES)20 to the VLR, which then verifies the signature by determining whether the Challenge (CHAL) is equal to the public key U _ ek (RES).

In the embodiment of fig. 3, a signature scheme employing message recovery is assumed. If a signature with an appendix is used, then verify CHAL? U _ ek (res) is given by hash (chal)? U _ EK (RES) replacement. To prevent denial of service attacks and to verify whether the challenge is from an authenticated source, the challenge and the user's public key may be integrity protected using a shared key MAC. The HHE/AuC may either digitally sign the challenge using a public/private key pair of all users or a USIM specific public/private key pair. In the latter case, the public key may be distributed to the USIM while the USIM registers its public key with the HE/AuC. By integrity protecting the challenge in this manner, an attacker cannot generate a valid challenge for all cases unless HE has the same knowledge as the HE/AuC. Thus, an attacker cannot send a challenge to block a valid sequence number.

The shared key may also be used to derive shared keys, such as Ck and lk, as in a standard UMTS AKA system. In this derived embodiment, the key preferably depends on the complete challenge and not just the RAND part. This ensures that the key will also depend on the sequence number and DATA part. If the terminal or USIM can verify, for example, that the service descriptor in the data part is correct, the redirection attack is blocked. Note that the derived shared key must be sent from the HE/AuC to the VLR.

The method of hiding the sequence numbers provided by the standard UMTS AKA system is also applicable to this solution.

Note also that if the shared key in the USIM is compromised, the attacker can generate a valid challenge because the public key of the USIM must be considered publicly known because it is sent in clear text to the VLR. This is not the case if the challenge is signed with the HE/AuC private key. The attacker may also be able to "intercept" the connection in this case after the actual USIM has been authenticated, since the attacker may be able to derive the same session key. To prevent this, the key should be derivable only with a secret (non-shared) key in the USIM. This may be accomplished by having the HE/AuC send a "key seed" to the USIM, encrypted by the USIM's public key as performed in the encrypted challenge solution described previously.

Alternate encrypted interrogation system

Fig. 4 is a message flow diagram illustrating the flow of messages between the USIM 11, VLR 12 and HE/AuC 13 in an alternative embodiment of the present invention that employs an encrypted interrogation system. There are two main differences between this embodiment and the encrypted challenge embodiment described above. First, in this embodiment, integrity protection is provided by having the USIM and HE/AuC share a secret key. Second, in this embodiment, the USIM public key is made available to the VLR. In this embodiment, it is assumed that the USIM has generated and registered its public key (U _ EK) on the HE/AuC. As described above, the HE/AuC may alternatively digitally sign the challenge with a public/private key pair.

The USIM sends an authentication request 14 to the VLR and includes an identifier, such as an IMSI, in the request. The VLR forwards the authentication request to the HE/AuC. When the HE/AuC receives the authentication request, the HE/AuC retrieves the public key U _ EK of the USIM and prepares and encrypts a challenge (E _ CHAL). The HE/AuC sends the E _ CHAL and public key (U _ EK) and MAC of the USIM to the VLR 12 at 21, and the VLR 12 forwards the E _ CHAL and MAC to the USIM at 22. Note that the step of delivering the public key U EK to the VLR is a second major difference from the encrypted challenge embodiment described previously. The USIM modifies the encrypted challenge E _ CHAL by applying a publicly known function HR. The USIM digitally signs the result and at 23 the signature is sent as a Response (RES) to the VLR. The VLR knows the HR function and the public key of the USIM so that it can verify the received signature.

The shared key may be derived from the challenge by applying a hash (prg) function to the plaintext challenge CHAL D. Also here, the derived shared key has to be sent from the HE/AuC to the VLR.

Note also that if the shared key in the USIM is compromised, the attacker can also generate valid challenges in this case. This is not the case if the challenge is signed with the HE/AuC private key, and the AKA key may be derived from the clear text challenge.

Fig. 5 is a message flow diagram illustrating the flow of messages between the USIM 11, VLR 12 and HE/AuC 13 in a third alternative embodiment of the present invention that employs an encrypted interrogation system. In this embodiment, the public key of the USIM is not sent to the VLR as in the previous embodiment. The USIM sends an authentication request 14 to the VLR and includes an identifier, such as an IMSI, in the request. The VLR forwards the authentication request to the HE/AuC. When the HE/AuC receives the authentication request, the HE/AuC retrieves the public key U _ EK of the USIM and prepares and encrypts a challenge (E _ CHAL). The HE/AuC also derives the S _ KEY to be shared with the VLR 12. The HE/AuC sends the E _ CHAL and expected response (XRES), S _ KEY, and MAC to the VLR 12 at 24, and the VLR 12 forwards the E _ CHAL and MAC to the USIM at 25. The USIM provisioning Response (RES) serves as HASH of the plaintext challenge CHAL _ D or Pseudo Random Generator (PRG), HA (CHAL _ D). At 26, RES is sent to the VLR, which determines whether the RES received from the USIM is equal to the XRES received from the HE/AuC.

In order to preserve the feature that the information held by the VLR is not sufficient to generate a valid response to a challenge, masking techniques are applied. The same type of masking technique may be used to correlate the derived shared key with the response generated by the USIM. This method is also applicable to both solutions described above.

Note also that there is no shared key in this embodiment. If an RSA-based public key scheme is employed in which only the public key's modulus is stored in the USIM but not the prime number that forms the public key, and in which the public key is erased after it has been distributed to the HE/AuC, the information in the USIM is insufficient to generate a valid challenge.

Hash chain based solution

The benefits of the hash-based solution are efficiency, but the signaling and maintenance are slightly more complex. The principle of digital signatures is that the signer reveals a value that only the signer can produce, but anyone can verify the correctness. The same result can in principle be achieved with a one-way hash function. Starting with an easy-to-calculate but hard-to-reverse function h, the "signer" a chooses a random x and publishes y (═ h (x)) as the "public key". Then, signer A reveals x, and anyone can apply h and verify that the value is correct. To be able to "sign" more than once, chains can be used

X_0＝random，

X_j＝h(X_(j-1))，j＝1，2，…

The problem is that such a chain has a limited length anyway and can use up the value X. However, in the case of USIMs, there is usually a defined maximum number of allowed authentications (around 20000 + 50000) and therefore the chain can always be made sufficiently long. Alternatively, there are methods to "boot" a new chain from an old chain. This is done by having the second to last value of the first hash chain used as a message integrity key, which protects the last value of the second hash chain.

Thus, the USIM generates the hash chain { X _ j } as signer a above, and the last "anchor" value X _ N is registered in the AuC. To reduce storage requirements, the USIM may, for example, store only every nth value and derive intermediate values as needed. In principle, at each authentication, the USIM reveals the "next" X _ j (which is the previous X value in the chain). However, this has some synchronization problems, since the home network needs to know how many authentications have occurred in order to provide the correct X value. This is not necessarily easy, as the home network may have difficulty in "tracking" the roaming user.

One solution is to let the USIM "report home" via the VLR at least at given intervals. The AuC stores (j, X _ j) as the most recently reported hash chain value. (alternatively, N and SQN may be used to derive j, see below, since j will correspond to N and SQN by j ═ N-SQN. The home network always knows what SQN is used in conjunction with a particular challenge-response (AKA vector). Thus, whenever the VLR reports a particular xj, the AuC may update its value accordingly. Next, when the VLR requests the AKA parameter, the AuC looks up the most recent (j, X _ j) value. The AuC generates an AKA vector and includes X _ j and an integer T SQN-j. This value T is the number of times the VLR needs to apply h to the X _ k value revealed by the USIM in order to obtain X _ j.

It should be noted that the VLR may order more than one AKA vector immediately and store them for later use. For example, assume the VLR orders M > 1 vectors. A "malicious" VLR may then take the last of these vectors (rather than the first as normally expected) and send to the USIM. When the USIM reveals the corresponding X _ n, if the VLR also has access to K, it will be able to generate a cloned USIM that is good for M consecutive authentications. Generally, this caveat exists if one can compromise both the VLR and USIM (to get K). In the IP Multimedia Subsystem (IMS), authentication takes place in the home network. Therefore, the solution is better suited there (at ISIM) because the "report home" function is basically already in place.

Diffie-Hellman based solution

Fig. 6 is a message flow diagram illustrating the flow of messages between the USIM 11, VLR 12 and HE/AuC 13 in one embodiment of the present invention that employs a public key distribution system rather than public key encryption. The solution can be illustrated using the standard Diffie-Hellman method. The USIM knows the Diffie-Hellman secret key (x), and the HE/AuC knows the Diffie-Hellman public key (g)^x). Note that g^xCan be easily calculated from x, but the reverseIt is considered computationally infeasible. The USIM sends an authentication request 14 to the VLR and includes an identifier, such as an IMSI, in the request. The VLR forwards the authentication request to the HE/AuC. When the HE/AuC receives the authentication request, the HE/AuC selects a random value y and calculates RAND g^y. HE/AuC then bases on public key g^xTo calculate the value R ═ g^xyWhere the value x is the Diffie-Hellman private key. The HE/AuC also computes a shared secret key K using K ═ KDF (R, …), which is a key derivation function. HE/AuC updates sequence number SQN_HEMAC is calculated using f1(K, RAND | | SQN | | | AMF …), XRES is calculated using f2(K, RAND), Ck is calculated using f3(K, RAND), lk is calculated using f4(K, RAND), AK is calculated using f5(K, RAND), and the construction message AUTN ═ SQN XOR | | AMF | | MAC is as described in 3GPP TS 33.102. At 27, the HE/AuC sends RAND, XRES, AUTN, Ck, and lk to the VLR. At 28, the VLR forwards the RAND and the contained SQN to the USIM 11_HE(privacy protection), AMF and AUTN of MAC.

Upon receiving the RAND and AUTN, the USIM 11 determines R ═ RAND^xWhere x is the Diffie-Hellman private key. This step can be expressed as: d (SK, RAND) ═ D (x, RAND) ═ RAND^x。

The USIM also employs a key derivation function to compute a shared secret key K KDF (R, …). The USIM then proceeds as in 3GPP TS33.102 to prepare a response RES. At 29 the USIM sends RES to the VLR, which determines whether the RES received from the USIM is equal to the XRES received from the HE/AuC.

In one embodiment, in the case of a public key or Diffie-Hellman, the secret information is stored in the IM and is cryptographically protected so that it can only be used by initializing the IM, e.g., by entering the appropriate initialization information. The secret information may include a secret key, a public key, or both. Appropriate initialization information may be used to initiate generation of the secret information and, for example, output a public key that is further exported to the AuC. This initialization information is not known to the ordinary user and therefore the public key is not known to the ordinary user. Other suitable initialization information may be used when a user performs authentication that requires the use of a private key. The use of a previously created private key is enabled by applying appropriate initialization information, or the information initiates the re-creation of a key from a pre-stored seed. In the latter case, it should be noted that no keys are available on the mobile device before the initialization information is applied. Electronic circuits implementing these features are disclosed in international patent application PCT/SE03/01660, incorporated herein by reference.

Those skilled in the art will appreciate that the inventive concepts described herein are susceptible to modification and variation in a wide variety of applications. Accordingly, the scope of patented subject matter should not be limited to any of the specific exemplary teachings discussed above, but is instead defined by the following claims.

Claims (24)

1. A method of preventing unauthorized copying of an Identity Module (IM), the method comprising:

internally generating at least a first key (K1) and a different second key (K2) in the IM, wherein the generating step includes ensuring that K1 cannot be derived from K2 and K2 cannot be derived from K1; and

k2 and an Identifier (ID) are exported from the IM to an Authentication Server (AS) while K1 is kept secret internally in the IM.

2. The method of claim 1, wherein K1 and K2 constitute a secret/public key pair for asymmetric cryptography, and the method further comprises keeping the public key K2 secret in the AS.

3. The method of claim 2 wherein the step of ensuring that K2 cannot be derived from K1 includes erasing internal information in the IM used to generate K1 and K2.

4. The method of claim 1, wherein the deriving step includes initializing the IM to receive K2 at an output for derivation to the AS while keeping K1 secret internally in the IM.

5. The method of claim 4, wherein the initializing step comprises applying an initialization code to an input port of the IM.

6. The method of claim 1, further comprising an authentication phase, wherein a third party authenticates the IM, the authentication phase comprising:

providing information from the IM to a third party initiating authentication, the information including at least the ID;

forwarding said information from the third party to said AS;

retrieving, by the AS, the K2 from the ID received from a third party;

generating, by the AS, at least a first value (R) and a second value (X) according to at least K2;

returning R and X from the AS to the third party;

forwarding R from a third party to said IM;

generating, by the IM, a Response (RES) based at least on K1 and R;

returning RES from the IM to the third party; and

the RES is verified by a third party according to X.

7. The method of claim 6, wherein:

the step of generating R comprises encrypting a value V with K2, wherein V contains information for deriving X;

said step of generating the RES comprises decrypting R and checking information derived from the decryption of R; and

the step of checking RES by the third party against X is a comparison that RES equals X.

8. The method of claim 1, wherein K1 is a first secret for a public key exchange system and K2 is a corresponding public parameter.

9. A copy resistant Identity Module (IM), comprising:

means for internally generating at least a first key (K1) and a second key (K2) in the IM, while ensuring that K1 cannot be derived from K2 and K2 cannot be derived from K1; and

means for exporting K2 and an Identifier (ID) from the IM to an Authentication Server (AS) while keeping K1 secret internally in the IM.

10. The identity module of claim 9 wherein the IM is implemented in a terminal containing an e-commerce application that performs payment in accordance with the IM.

11. An authentication server for authenticating an accessing Identity Module (IM) while preventing unauthorized duplication of the accessing IM, the authentication server comprising:

means for receiving an access request from the access IM;

means for generating a challenge using information stored in the authentication server but not in the access IM, wherein the information stored in the authentication server is insufficient to generate an IM clone that can respond as a valid IM;

means for generating an expected response expected from the valid IM; and

means for sending the query to the accessing IM, wherein the query changes for each access attempt.

12. A system for providing a valid Identity Module (IM) access to a network while preventing access to the network by an unauthorized IM clone, the system comprising:

an authentication server for receiving an access request from an accessing IM, generating a challenge using information stored in the authentication server but not in the accessing IM, generating an expected response expected from a valid IM, and sending the challenge to the accessing IM, wherein the challenge changes for each access attempt, and the information stored in or generated by the authentication server is insufficient to create an IM clone that can respond as a valid IM;

means in said accessing IM for receiving said challenge and preparing and sending a response based on information in said challenge and information in said accessing IM but not stored in said authentication server; and

means for providing the accessing IM with access to a network only if the response prepared by the accessing IM is equal to the expected response generated by the authentication server.

13. The system of claim 12 wherein the accessing IM further comprises means for determining whether the sequence number received from the authentication server is up to date.

14. The system of claim 12, further comprising an intermediate node adapted to receive the challenge and an expected response from the authentication server, forward the challenge to the accessing IM, receive the response from the accessing IM, and determine whether the response prepared by the accessing IM is equal to the expected response generated by the authentication server.

15. A method of providing a valid Identity Module (IM) access to a network while preventing access to the network by an unauthorized IM clone, wherein an accessing IM sends an access request to an authentication server, the method comprising:

in the authentication server:

selecting a random value y;

using RAND as g^yCalculating a random value (RAND);

calculated value R ═ g^xyWhere x is a Diffie-Hellman private key known to the accessing IM, and g^xIs known to the authentication server;

calculating a shared secret key (K) using K ═ KDF (R.), wherein KDF is a key derivation function;

transmitting the RAND and expected response (XRES) to an intermediate node; and

forwarding said RAND from said intermediate node to said accessing IM; and

in the access IM:

using R ═ RAND^xTo determine R, where x is a Diffie-Hellman private key;

calculating the shared secret key K ═ KDF (R.) using the key derivation function;

calculating a Response (RES) using RES ═ f2(K, RAND); and

sending the RES to the intermediate node;

determining, by the intermediate node, whether the RES received from the accessing IM is equal to the XRES received from the authentication server; and

providing access to a network for the accessing IM only if the RES received from the accessing IM is equal to the XRES received from the authentication server.

16. The method of claim 15, further comprising:

in the authentication server:

update sequence number (SQN)_HE)；

Calculating a keyed Message Authentication Code (MAC) using the MAC f1(K, RAND SQN amf);

calculating an XRES using the XRES ═ f2(K, RAND);

calculating a key Ck using Ck ═ f3(K, RAND);

calculating a key lk by using lk ═ f4(K, RAND);

calculating AK by using AK f5(K, RAND);

constructing an authentication message AUTN by using AUTN (SQN) XOR AK (II) AMF (II) MAC; and

sending the AUTN, the RAND, and the XRES to the intermediate node;

in the intermediate node:

forwarding the AUTN and the RAND to the access IM; and

in the access IM:

calculating AK by using AK f5(K, RAND); and

extracting and verifying the SQN from the AUTN_HEAMF and MAC.

17. A method of authenticating an accessing Identity Module (IM) while preventing unauthorized copying of the accessing IM, the method comprising:

internally generating at least a first key (K1) and a different second key (K2) in the accessing IM; and

exporting K2 and an Identifier (ID) from the accessing IM to an Authentication Server (AS) while keeping K1 secret internally in the accessing IM;

sending information containing at least the ID from the accessing IM to a third party;

forwarding said information from the third party to said AS;

retrieving, by the AS, the K2 from the ID received from a third party;

selecting, by the AS, a random number R;

generating, by the AS, at least one value (RAND) based at least on the number R;

generating, by the AS, a key K at least according to the number R;

generating, by the AS, a value (X) from at least the value (RAND) and the key K;

returning the values RAND and X from the AS to a third party;

forwarding said value RAND from a third party to said accessing IM;

receiving, by a third party, a response RES from the accessing IM; and

the RES is verified by a third party according to X.

18. The method of claim 17, further comprising, prior to the step of receiving the RES from the accessing IM, the steps of:

calculating, by said accessing IM, said random number R at least from said key K1 and said value (RAND);

calculating, by the accessing IM, the key K at least from the value R; and

calculating, by the accessing IM, the response RES at least from the key K and the value RAND.

19. The method of claim 18, wherein:

the access IM uses R1 ═ RAND^K1To calculate a value R1;

the access IM calculates the key K using K KDF (R1.); and

the access IM calculates the response RES using RES ═ f2(K, RAND).

20. The method of claim 17, further comprising determining, by the AS, a random number R1 ═ using the random number R (K2)^R；

Wherein the AS is according to RAND-g^RGenerating the value RAND;

wherein the AS generates the key K using K ═ KDF (R1.), wherein KDF is a key derivation function; and

wherein the AS generates the value X using X ═ f2(K, RAND) employing a function f 2.

21. A method of authenticating an accessing Identity Module (IM) while preventing unauthorized copying of the accessing IM in a network utilizing a signature scheme with message recovery, the method comprising:

generating a public key U _ EK internally in the access IM;

registering the public key U _ EK on an Authentication Server (AS);

sending an access request from the access IM to the AS, the access request including at least an identifier for the access IM;

retrieving, by the AS, a public key U _ EK of the accessing IM;

preparing, by the AS, a challenge CHAL, the challenge comprising at least one of a random value (RAND), a sequence number (SEQ), and additional DATA (DATA);

sending the challenge and a public key U _ EK of the access IM from the AS to an intermediate node;

forwarding said query from said intermediate node to said accessing IM;

preparing, by the accessing IM, a digital signature U _ sign (chal) of the challenge;

sending said digital signature U _ SIGN (CHAL) from said accessing IM to said intermediate node as a response RES to said challenge; and

verifying, by said intermediate node, said response by determining whether said Challenge (CHAL) is equal to said public key U _ EK (RES).

22. The method of claim 21, wherein said Challenge (CHAL) comprises RAND and SEQ.

23. The method of claim 22, wherein said Challenge (CHAL) further comprises said DATA portion, wherein said DATA portion comprises a service identifier.

24. A method of authenticating an accessing Identity Module (IM) while preventing unauthorized copying of the accessing IM in a network utilizing a signed with an appendix, the method comprising:

generating a public key U _ EK internally in the access IM;

registering the public key U _ EK on an Authentication Server (AS);

sending an access request from the access IM to the AS, the access request including at least an identifier for the access IM;

retrieving, by the AS, a public key U _ EK of the accessing IM;

preparing, by the AS, a challenge CHAL, the challenge comprising at least one of a random value (RAND), a sequence number (SEQ), and additional DATA (DATA);

sending the challenge and a public key U _ EK of the access IM from the AS to an intermediate node;

forwarding said query from said intermediate node to said accessing IM;

preparing, by the accessing IM, a digital signature U _ SIGN (hash (chal)) of the challenge;

sending said digital signature U _ SIGN (hash (chal)) from said access IM to said intermediate node as a response RES to said challenge; and

verifying, by the intermediate node, the response by determining whether a hash of the Challenge (CHAL) is equal to the public key U _ EK (RES).