EP1504560A2 - Procede de protection de codes cryptographiques a cle secrete - Google Patents

Procede de protection de codes cryptographiques a cle secrete

Info

Publication number
EP1504560A2
EP1504560A2 EP03718989A EP03718989A EP1504560A2 EP 1504560 A2 EP1504560 A2 EP 1504560A2 EP 03718989 A EP03718989 A EP 03718989A EP 03718989 A EP03718989 A EP 03718989A EP 1504560 A2 EP1504560 A2 EP 1504560A2
Authority
EP
European Patent Office
Prior art keywords
algorithm
key
secret key
strong
byte pairs
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Withdrawn
Application number
EP03718989A
Other languages
German (de)
English (en)
Other versions
EP1504560A4 (fr
Inventor
Carl Alko Meijer
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Individual
Original Assignee
Individual
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Individual filed Critical Individual
Publication of EP1504560A2 publication Critical patent/EP1504560A2/fr
Publication of EP1504560A4 publication Critical patent/EP1504560A4/fr
Withdrawn legal-status Critical Current

Links

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)

Abstract

L'invention concerne un procédé de protection d'un code cryptographique à clé, dont les étapes consistent à générer un ensemble de paires d'octets de clé solides pour un algorithme donné, à sélectionner dans cet ensemble un nombre prédéterminé de paires d'octets de clé solides afin de former au moins partiellement à une clé secrète d'une longueur prédéfinie, et à programmer un dispositif de codage avec cette clé secrète. L'invention concerne également la programmation de cette clé secrète sur une carte SIM fonctionnant dans un réseau de téléphonie mobile (GSM).
EP03718989A 2002-04-30 2003-04-29 Procede de protection de codes cryptographiques a cle secrete Withdrawn EP1504560A4 (fr)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
ZA200201944 2002-04-30
ZA200201944 2002-04-30
PCT/IB2003/001653 WO2003094483A2 (fr) 2002-04-30 2003-04-29 Procede de protection de codes cryptographiques a cle secrete

Publications (2)

Publication Number Publication Date
EP1504560A2 true EP1504560A2 (fr) 2005-02-09
EP1504560A4 EP1504560A4 (fr) 2007-11-28

Family

ID=29401960

Family Applications (1)

Application Number Title Priority Date Filing Date
EP03718989A Withdrawn EP1504560A4 (fr) 2002-04-30 2003-04-29 Procede de protection de codes cryptographiques a cle secrete

Country Status (3)

Country Link
EP (1) EP1504560A4 (fr)
AU (1) AU2003223022A1 (fr)
WO (1) WO2003094483A2 (fr)

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4605820A (en) * 1983-11-10 1986-08-12 Visa U.S.A. Inc. Key management system for on-line communication
US5003596A (en) * 1989-08-17 1991-03-26 Cryptech, Inc. Method of cryptographically transforming electronic digital data from one form to another
US6075859A (en) * 1997-03-11 2000-06-13 Qualcomm Incorporated Method and apparatus for encrypting data in a wireless communication system
FR2766317B1 (fr) * 1997-07-15 1999-09-24 Alsthom Cge Alcatel Dispositif pour relier un commutateur telephonique a un reseau telephonique fixe via une pluralite de terminaux radiotelephoniques fixes d'un reseau radiotelephonique
DE19820422A1 (de) * 1998-05-07 1999-11-11 Giesecke & Devrient Gmbh Verfahren zur Authentisierung einer Chipkarte innerhalb eines Nachrichtenübertragungs-Netzwerks
US6338140B1 (en) * 1998-07-27 2002-01-08 Iridium Llc Method and system for validating subscriber identities in a communications network
WO2001069838A2 (fr) * 2000-03-15 2001-09-20 Nokia Corporation Procede et dispositif associe pour produire des cles de securite dans un systeme de communication

Also Published As

Publication number Publication date
EP1504560A4 (fr) 2007-11-28
AU2003223022A1 (en) 2003-11-17
AU2003223022A8 (en) 2003-11-17
WO2003094483A3 (fr) 2004-01-29
WO2003094483A2 (fr) 2003-11-13

Similar Documents

Publication Publication Date Title
US10164954B2 (en) Method to manage a one time password key
Gueron et al. GCM-SIV: full nonce misuse-resistant authenticated encryption at under one cycle per byte
KR101095239B1 (ko) 보안 통신
US7937593B2 (en) Storage device content authentication
JP7362676B2 (ja) データの暗号化および完全性のためのデバイス
JP4298010B2 (ja) データシーケンスの暗号化または解読方法
ES2343491T3 (es) Procedimiento y aparato para encriptar señales para su transmision.
US20050071655A1 (en) Permutation of opcode values for application program obfuscation
US20040234074A1 (en) Generation of a mathematically constrained key using a one-way function
CN111526007B (zh) 一种随机数生成方法及系统
US20060002550A1 (en) Method and system for generation of cryptographic keys and the like
US20250331573A1 (en) Aerosol-generating device with encrypted data management
CN117294431A (zh) 一种密钥生成方法、装置、设备及介质
JP3204317B2 (ja) 電子入札システム
WO2003094483A2 (fr) Procede de protection de codes cryptographiques a cle secrete
CN117221878B (zh) 一种基于无线网络设备的信息安全管控方法及装置
JPH1117673A (ja) 共通鍵暗号通信方法及びその通信ネットワーク
WO2021100386A1 (fr) Procédé de codage avec mélange de texte de données de communication
ZA200409196B (en) Method for protecting secret key cryptographic schemes.
JP6365076B2 (ja) データ変換装置
US8457309B2 (en) Private key compression
JP6617375B2 (ja) データ変換装置
Wray COMP128: A birthday surprise
JP2005003745A (ja) 乱数生成装置とその方法、プログラム、および暗号処理装置
CN114342315A (zh) 网络中多个实体之间的对称密钥生成、认证和通信

Legal Events

Date Code Title Description
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

17P Request for examination filed

Effective date: 20041126

AK Designated contracting states

Kind code of ref document: A2

Designated state(s): AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IT LI LU MC NL PT RO SE SI SK TR

AX Request for extension of the european patent

Extension state: AL LT LV MK

A4 Supplementary search report drawn up and despatched

Effective date: 20071030

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE APPLICATION IS DEEMED TO BE WITHDRAWN

18D Application deemed to be withdrawn

Effective date: 20071126