Classifications

• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
  • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
  • H04L9/0861—Generation of secret information including derivation or calculation of cryptographic keys or passwords
  • H04L9/0877—Generation of secret information including derivation or calculation of cryptographic keys or passwords using additional device, e.g. trusted platform module [TPM], smartcard, USB or hardware security module [HSM]
• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
  • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
  • H04L9/088—Usage controlling of secret information, e.g. techniques for restricting cryptographic keys to pre-authorized uses, different access levels, validity of crypto-period, different key- or password length, or different strong and weak cryptographic algorithms
• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
  • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
  • H04L9/3271—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using challenge-response
• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
  • H04L2209/08—Randomization, e.g. dummy operations or using noise
• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
  • H04L2209/80—Wireless

Definitions

• This invention relates to a method for protecting secret key cryptographic schemes and extends to a novel challenge-response authentication method for use in protecting devices used in secret key cryptographic schemes.
• a GSM telephone network requires the use of a challenge-response protocol to authenticate users on its network.
• SIM subscriber identification module
• Each SIM card is programmed to contain a unique random number called a secret key.
• Each SIM card is also programmed with an International Mobile Subscriber Identity (IMSI).
• IMSI International Mobile Subscriber Identity
• a network operator When a network operator wishes to authenticate a SIM, it will send a challenge to the SIM based on the SIM's IMSI.
• Each network operator uses a standard algorithm for the challenge-response method and the efficacy of the system relies largely on the strength of the algorithm.
• the network will, in most instances, have a database of suitable challenges and expected responses based on the SIM's IMSI.
• the network will thus select a suitable challenge and send it over the air to the SIM card.
• the SIM card will apply a cryptographic scheme, being a combination of cryptographic algorithm and secret key, to the challenge and produce a response.
• the SIM's computed response is then sent over the air to the network operator that issued the challenge. If the response agrees with the response expected by the network operator, the SIM has been authenticated.
• the algorithm used in such a system may be, and frequently is, public knowledge and thus it is obviously of critical importance that the secret key for a particular subscriber remains secret. It should be as difficult as possible to deduce the key even when a large number of challenges and corresponding responses may be examined.
• issuing challenges that are related in some way should not produce predictable responses, with a comparatively high probability. If one applies the same algorithm to two different challenges and the same response is generated to both (termed a collision) or if one can predict the outcome to a challenge that has been varied slightly on a previous challenge, then the algorithm is said to be cryptographically weak. In other words, an algorithm that (for most secret keys) produces responses that with comparatively high probability are related to changes in the challenge is not cryptographically safe.
• a series of similar challenges may produce like or predictable responses from which it is possible to work backwards, using the known algorithm, to deduce the secret key of an encoding device such as a SIM card.
• the COMP128-1 algorithm was shown to produce the same responses with high probability when the challenge was varied in respect of certain of the byte pairs in the challenge. It was possible to produce a collision with two different challenges and to work backwards to deduce a corresponding byte pair of the secret key. By repeating this process, it was found that all eight of the byte pairs in the COMP128-1 secret key eventually gave like answers to similar challenges. It was therefore possible to deduce the entire secret key.
• the SIM card can be cloned and fraudulent telephone charges can be billed to the user of the original SIM card.
• COMP128-1 is a widely fielded authentication scheme in GSM networks, some network operators are becoming worried about the risk posed by GSM-cloning worldwide.
• To implement a new algorithm on a network would involve the re-programming of every SIM card on that network and would therefore be a very expensive and inconvenient operation.
• To phase a new algorithm in over time would involve running two separate algorithms simultaneously and would also be inconvenient and costly to network operators.
• a 'strong key byte pair' shall mean a secret key value which makes up a secret that, when subjected to related challenges, is less likely to produce related responses than for a secret key made up from randomly selected secret key values.
• BGW-style challenge is a challenge as described in the Briceno, Goldberg and Wagner report.
• a method for protecting a secret key cryptographic scheme including the steps of: generating a set of strong key byte pairs for a given algorithm; selecting from the set a predetermined number of strong key byte pairs to at least partly form a secret key of predefined length; programming an encoding device with the secret key.
• a further feature of the invention provides for an algorithm to select the strong key byte pairs that comprise the secret key.
• Another feature of the invention provides for the secret key to be programmed into a SIM card operable on a GSM network.
• Still further features of the invention provide for the cryptographic scheme to be a GSM authentication scheme operating with the COMP128-1 algorithm and for the strong key byte pairs to be such that a collision is not produced at round 2 of the COMP128-1 algorithm application when a BGW-style challenge is used on the algorithm.
• the secret key (expressed in hexadecimal) to be formed using any one or more of the strong key byte pairs below:
• Still further features of the invention provide for the algorithm that forms the secret key for the COMP128-1 algorithm from the set of strong key byte pairs, expressed in pseudocode, to be: // K
• new byte[16]
• KiIJJ the MSB of k
• K ⁇ D+8] the LSB of k. ⁇
• Still further features of the invention provide for the algorithm used to select the strong key byte pairs that comprise the secret key to be programmed into a SIM card operable in a GSM telephone network.
• a further feature of the invention provides a challenge-response authentication method which includes applying an algorithm and a secret key comprising strong key byte pairs to a random challenge generated by a central network to produce a response at the central network and a response on a given encoding device and comparing the responses to authenticate a user.
• Further features of the method provide for the challenge to be generated by a GSM network operator and for the responses to the challenge to be generated by the GSM network operator and on a SIM card operable on a GSM network.
• a further feature of the method provides for the challenge to be generated by a GSM network operator operating with the COMP-128-1 algorithm.
• the secret key to be formed by the SIM card itself from a set of strong key byte pairs stored on the SIM card, and for the method to include the step of programming the SIM card with an algorithm used to form the secret key from the set of strong key byte pairs.
• Still further features of the method provide for the algorithm that forms the secret key for the COMP128-1 algorithm from the set of strong key byte pairs, expressed in pseudocode, to be: // K
• SIM card operable on a GSM network programmed with a secret key as defined above.
• a secret key comprising at least some strong key byte pairs
• the secret (expressed in hexadecimal) to be formed using any one or more of the strong key byte pairs below:
• [j] the MSB of k K
• [j+8] the LSB of k. ⁇
• a GSM network operated by a GSM network operator operating with the COMP-128-1 algorithm and using a challenge-response authentication method which includes applying an algorithm and a secret key comprising strong key byte pairs to a random challenge generated by a central network to produce a response at the central network and a response on a given encoding device and comparing the responses to authenticate a user.
• COMP128-1 One of the most widely used algorithms for mobile telephone networks is called the COMP128-1 algorithm.
• the algorithm uses a 16 byte secret key, which means the probability of determining the whole key by chance is 1 in 2 128 . This is called the key space.
• Such a vast key space effectively nullifies the possibility of revealing a secret key in a SIM card based on pure chance.
• SIM and in particular the secret key on that SIM and the known algorithm were subjected to a number of specially selected challenges to which they produced a response in each instance.
• SIM-cloning Due to weaknesses in the algorithm it was found that by varying certain pairs of bytes in a series of challenges, and only those bytes, the responses were found to be the same with comparatively high probability. Using the like responses and the known challenges it was possible to work backwards, using the known algorithm, to deduce which bytes in the secret key would give like responses. Each such collision revealed two bytes of the sixteen-byte key and with sufficient challenges it was found possible to reveal all sixteen bytes of the key. With the secret key revealed, a new SIM with the same secret key can be programmed and used. The charges for that new SIM will be billed to the account of the user of the original SIM. This is termed SIM-cloning or GSM-cloning.
• the COMP128-1 algorithm has 40 rounds of application. It has been found that a collision after round 40 is more than likely a result of a collision that occurred at round 2 in the algorithm when a pair of challenges of the form identified in the BGW report are used and which has been carried through the remaining rounds of application. Round 2 collisions are far more likely to occur than those in the subsequent rounds and, as such, the byte pairs are easier to reveal at this round than in subsequent rounds. To put this difference in perspective, one needs to issue approximately 23000 challenges to have a reasonable chance of witnessing a round 2 collision whereas approximately 260000 challenges are required to witness a round 3 collision with the same probability as for the round 2 collision. This simplifies the deduction of the secret key from the results of the application of the challenge to the algorithm and secret key.
• the strong key bytes for the COMP128-1 algorithm which in this case are in the form of strong key byte pairs (expressed in hexadecimal), were found to be the following: 000B 003F 005B 006D 0119 01A8 01F8 0293 031E 035A 036B 03BA
• the secret key for a SIM card in a system using the COMP128-1 algorithm is generated using only strong key byte pairs, it has been found that the possibility of deducing the secret key by selectively varying the challenge and analysing the results was significantly reduced.
• any algorithm which is susceptible to collisions not only the COMP128-1 algorithm and not only in a GSM environment, being used in a cryptographic scheme would benefit from the application of the invention.
• any encoding device may be used instead of a SIM card and the network operator can be replaced by a suitable central network capable of communicating with a particular encoding device on a public communication system.
• the collision can occur at any round of application of a given algorithm and thus the strong key byte pairs may be determined on the basis that they are not susceptible to collisions in that particular round of the attack.

Landscapes

• Engineering & Computer Science (AREA)
• Computer Security & Cryptography (AREA)
• Computer Networks & Wireless Communication (AREA)
• Signal Processing (AREA)
• Lock And Its Accessories (AREA)
• Storage Device Security (AREA)

Applications Claiming Priority (3)

Publications (2)

Family

ID=29401960

Family Applications (1)

Country Status (3)

Family Cites Families (7)

• 2003
  • 2003-04-29 AU AU2003223022A patent/AU2003223022A1/en not_active Abandoned
  • 2003-04-29 WO PCT/IB2003/001653 patent/WO2003094483A2/en not_active Ceased
  • 2003-04-29 EP EP03718989A patent/EP1504560A4/de not_active Withdrawn

Also Published As

Similar Documents

Legal Events