Method and system making it possible to test a cryptographic integrity of an error tolerant data item

• US 9,705,675 B2
• Filed: 12/22/2011
• Issued: 07/11/2017
• Est. Priority Date: 12/30/2010
• Status: Active Grant

• Current Assignee: Thales SA
• Original Assignee: Thales SA
• Inventors: Painchault, Philippe, Garrido, Eric, Marcello, Sandra
• Primary Examiner(s): Shaw, Yin-Chen
• Assistant Examiner(s): Amorin, Carlos
• Application Number:
  US13/977,554
• Publication Number:
  US 20140052987A1
• Time in Patent Office: 2,028 Days
• Field of Search: 713168
• CPC Class Codes: H04L 2209/26 Testing cryptographic entity, e.g. testing integrity of encryption key or encryption algorithm
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 9/06 the encryption apparatus using shift registers or memories for block-wise or stream coding, e.g. DES systems or RC4; Hash functions; Pseudorandom sequence generators
• CPC Class Codes: H04L 9/32 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
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC

Abstract

A method and system for testing the cryptographic integrity of data m comprises at least the following elements: a module transmitting a message M, said module comprising a memory for storing the parameters used to execute the steps of the method, such as the key, the public data, a transmission medium, a receiver module also comprising storage means for storing at least the same parameters as in transmission. The system may comprise storage means for storing confidential data such as the secret keys, a processor suitable for executing the steps.

Claims

1. A method for testing a cryptographic integrity of data represented by m, in a system comprising at least one cryptographic integrity testing processor, an emitter comprising a first memory configured to store a key, public data, and a medium for transmission, and a receiver comprising a second memory for storing a secret key, said method comprising, in combination, at least the following steps executed by the at least one cryptographic integrity testing processor:

a first step executed by the emitter during which a first secret key represented by Ksym is generated by executing the following sub-steps;

storing in the first memory a family, represented by F(GF(p), n, M, k, d), of linear or nonlinear system error-correcting codes over a corpus of p number of elements represented by GF(p), wherein the family of linear or nonlinear error-correcting codes are characterized by the following parameters;

a length represented by n, a cardinal represented by M, a dimension represented by k, and a distance represented by d,

randomly drawing a correcting code represented by C, from the family, F, represented by a function F(GF(p), n, k, d), wherein the correcting code has a correction capacity represented by t, and defining the first secret key, Ksym;

a second step executed at the emitter comprising the following sub-steps executed by the at least one cryptographic integrity testing processor;

coding said data, m, by using the correcting code, C, selected from the family, F(GF(p), n, M, k, d), stored in the first step,

computing, for a systematic code, a redundancy represented by r, and known as a message authentication code (MAC) to validate the cryptographic integrity of a message transmitted by the emitter and encrypting the redundancy using a second secret key Sk, which is a function of C, Ksym, and I, wherein the second secret key is stored in the second memory, wherein I is a non-zero integer less than the correction capacity, t, which represents the number of errors accepted in order to protect the redundancy, r, resulting in an encrypted redundancy represented by rp, wherein rp refers to a message authentication code with error correcting code (MACECC), wherein rp=SYM_ksym(r), wherein SYM is a symmetrical encryption block algorithm associated with the first secret key,

transmitting, using the emitter over a telecommunications system, a transmitted message (m|rp) to the receiver, wherein (m|rp) represents a concatenation of m and rp to form the transmitted message;

a third step executed by the receiver comprising receiving a received message (ma|ra) over the telecommunications system, wherein (ma|ra) representing the concatenation of the received message data ma and a received encrypted redundancy ra, and further comprising the following sub-steps executed by the at least one cryptographic integrity testing processor;

using a systematic code represented by the received message (ma|ra), as an input data for an integrity checking function, wherein the integrity checking function comprises;

reversing a redundancy confidentiality protection mechanism using an inverse of the symmetrical encryption algorithm SYM_ksym<sup>−

1</sup>(ra) associated with the first secret key,

applying a decoding function represented by D₁ associated with the chosen correcting code C wherein the decoding function takes as an input any received message data ma and produces as an output a word having a corrected code that is closest in terms of a Hamming distance, and wherein the decoding function D₁ is applied to a concatenation of the received message data with the inverse of the symmetrical encryption algorithm associated with the first secret key D₁(ma|SYM_ksym<sup>−

1</sup>(ra)),

determining whether the output, the word having the corrected code, of the decoding function of the receiver is valid, wherein the output of the decoding function is valid when the output of the decoding function equals mr, wherein mr=(D₁(ma|SYM_ksym<sup>−

1</sup>(ra)), ma), indicating that decoding is possible, and wherein the output of the decoding function is invalid when the word having the corrected code is determined to be not valid, indicating that decoding is not possible, the data of the received message are determined to be non-integral, indicating a spoofed message, and the data of the received message are not accepted by the receiver,

when the word having the corrected code is determined to be valid, indicating that decoding is possible, further determining, by the receiver, whether d(h_n-k(D₁(ma|SYM_ksym<sup>−

1</sup>(ra)), ma)<

I+1, wherein the distance function d( ) is a distance in terms of the number of elements of GF(p) that are different, and h_n-k is the function which takes a character string as input and associates with the character string the first n−

k characters of the character string,

if d(h_n-k(D₁(ma|SYM_ksym<sup>−

1</sup>(ra)), ma)<

I+1 is satisfied, the data of the received message are determined to be integral and a response of the receiver is represented by a valid (OK) message, indicating that an effective useful message was received, the data of the received message are decoded, the data of the received message are accepted, and the data of the received message are retrieved by the at least one cryptographic integrity testing processor,

otherwise, if d(h_n-k(D₁(ma|SYM_ksym<sup>−

1</sup>(ra)), ma)<

I+1, is not satisfied, the data of the received message are determined to be non-integral, indicating a spoofed message, wherein the decoded data of the received message are rejected by the receiver.

2. The method as claimed in claim 1, wherein, in the case of a systematic code, the method comprises an encryption step encrypting all of the effective useful message, encrypting the redundancy r in transmission, and a decryption step decrypting said received message.

3. The method as claimed in claim 1, wherein the processed data are messages used in transmission systems.

4. The method as claimed in claim 1, wherein the redundancy r is protected using a block encryption or an XOR using a pseudo-random generator.

5. A system for testing a cryptographic integrity of data represented by m comprising at least the following elements:

an emitter transmitting a transmitted message over a telecommunications system, said emitter comprising a memory for parameters including a key, public data, and a transmission medium,

a receiver configured to receive a received message over the telecommunications system, the receiver comprising a first storage device for at least the same parameters as in transmission, a second storage device for storing a secret key, and

at least one cryptographic integrity testing processor configured to execute the following steps;

a first step executed by the emitter during which a first secret key represented by Ksym is generated by executing the following sub-steps;

storing in the memory a family, represented by F(GF(p), n, M, k, d), of linear or nonlinear system error-correcting codes over a corpus of p number of elements represented by GF(p), wherein the family of linear or nonlinear error-correcting codes are characterized by the following parameters;

a length represented by n, a cardinal represented by M, a dimension represented by k, and a distance represented by d,

randomly drawing a correcting code represented by C, from the family, F, represented by a function F(GF(p), n, k, d), has a correction capacity represented by t, and defining the first secret key, Ksym;

a second step executed at the emitter comprising the following sub-steps;

coding said data, m, by using the correcting code, C, selected from the family, F(GF(p), n, M, k, d), stored in the first step,

computing, for a systematic code, a redundancy represented by r, and known as a message authentication code (MAC) to validate the cryptographic integrity of the transmitted message transmitted by the emitter and encrypting the redundancy using a second secret key Sk, which is a function of C, Ksym, and I, wherein the second secret key is stored in the second storage device, wherein I is a non-zero integer less than the correction capacity, t, which represents the number of errors accepted in order to protect the redundancy, r, resulting in an encrypted redundancy represented by rp, wherein rp refers to a message authentication code with error correcting code (MACECC), wherein rp=SYM_ksym(r), wherein SYM is a symmetrical encryption block algorithm associated with the first secret key,

transmitting, using the emitter over a telecommunications system, a transmitted message (m|rp), wherein (m|rp) represents a concatenation of m and rp to form the transmitted message;

a third step executed by the receiver comprising receiving a received message (ma|ra) over the telecommunications system, wherein (ma/ra) representing the concatenation of the received message data ma and a received encrypted redundancy ra, and further comprising the following sub-steps executed by the at least one cryptographic integrity testing processor;

using a systematic code represented by the received message (ma|ra), as an input data for an integrity checking function, wherein the integrity checking function comprises;

reversing a reverse the redundancy confidentiality protection mechanism using an inverse of the symmetrical encryption algorithm SYM_ksym<sup>−

1</sup>(ra) associated with the first secret key,

applying a decoding function represented by D₁ associated with the chosen correcting code C, wherein the decoding function takes as an input any received message data ma and produces as an output a word having a corrected code that is closest in terms of a Hamming distance, and wherein the decoding function D₁ is a lied to a concatenation of the received message data with the inverse of the symmetrical encryption algorithm associated with the first secret key D₁(ma|SYM_ksym<sup>−

1</sup>(ra)),

determining whether the output, the word having the corrected code, of the decoding function of the receiver, is valid, wherein the output of the decoding function is valid when the output of the decoding function equals mr, wherein mr=(D₁(ma|SYM_ksym<sup>−

1</sup>(ra)), ma), indicating that decoding is possible, and

wherein the output of the decoding function is invalid when the word having the corrected code is determined to be not valid, indicating that decoding is not possible, the data of the received message are determined to be non-integral, indicating a spoofed message, and the data of the received message are not accepted by the receiver,

when the word having the corrected code is determined to be valid, indicating that decoding is possible, further determining, by the receiver, whether d(h_n-k(D₁(ma|SYM_ksym<sup>−

1</sup>(ra)), ma)<

I+1, wherein the distance function d( ) is a distance in terms of the number of elements of GF(p) that are different, and h_n-k is the function which takes a character string as input and associates with the character string the first n−

k characters of the character string,

if d(h_n-k(D₁(ma|SYM_ksym<sup>−

1</sup>(ra)), ma)<

I+1 is satisfied, the data of the received message are determined to be integral and a response of the receiver is represented by a valid (OK) message, indicating that an effective useful message was received, the data of the received message are decoded, the data of the received message are accepted by the receiver, and the data of the received message are retrieved by the at least one cryptographic integrity testing processor,

otherwise, if d(h_n-k(D₁(ma|SYM_ksym<sup>−

1</sup>(ra)), ma)<

I+1 is not satisfied, the data of the received message are determined to be non-integral, indicating a spoofed message, wherein the decoded data of the received message are rejected by the receiver.