WO2008119901A2

WO2008119901A2 - Method for the decryption of encrypted data using a cryptographic algorithm

Info

Publication number: WO2008119901A2
Application number: PCT/FR2008/050317
Authority: WO
Inventors: Olivier Billet; Gilles Macario-Rat
Original assignee: France Telecom
Priority date: 2007-02-28
Filing date: 2008-02-26
Publication date: 2008-10-09
Also published as: WO2008119901A3

Abstract

The invention relates to a method for the partial decryption of data, comprising: the decoding (32) of an encoded data set containing at least the payload, the non-determinable partial decryption (33) of the payload, the association (35) of the at least partially decrypted payload with supplementary data, and the encoding (36) of a data set containing the at least partially decrypted data and the associated supplementary data.

Description

Method for decrypting encrypted data with a cryptographic algorithm

The present invention relates to the field of protection of secret keys used in the decryption of data and in particular to the protection of these secret keys when they are used by a software ensuring the decryption of these data. More particularly, the invention makes it possible to keep secret keys secret when an attacker has access to all or part of the operation of the software ensuring the decryption of the data.

Software for decrypting digital data is, for example, acquired by a user subject to payment from a specific entity. This software includes portions of code for performing the steps of a decryption method. The decryption method comprises several partial decryption steps, each using an elementary function. In a variant, a partial decryption step uses several elementary functions. During a partial decryption step, the elementary function receives useful data input and outputs useful data at least partially decrypted. For this, some basic functions use part of a secret key. In order to improve the protection of the part of the secret key, it has been proposed to replace, in the software, the elementary function using this secret key part in the form of a correspondence table. A look-up table represents the set of input / output pairs of the elementary function used during a decryption part. The attacker is then able to observe only the useful data received and the useful data sent at the level of the elementary function. However, by observing this useful data received and this useful data sent, the attacker is able to find the relationship between these data. The analysis of this relation then allows him to reconstitute the part of the secret key used by the elementary function. A third party will eventually be able to decrypt the digital data without having to pay the payment to obtain the software that decrypts the data.

It was then proposed to make observable by an attacker only the coding of the useful data received at the input of the elementary function. This will hide this useful data to an attacker.

It has also been proposed, for the same purpose, to render observable only the coding of the at least partially decrypted useful data sent at the output of the elementary function. Despite this additional coding, it has been demonstrated in the document "Cryptanalysis of a White Box AES Implementation", by Olivier Billet,

Henri Gilbert, and Charaf Ech-Chatbi, that an attacker is able to find the part of the secret key used by the elementary function by determining and analyzing the relations between the coded useful data.

The present invention proposes a method of partial decryption of data comprising a decoding of a coded set of data said set comprising at least useful data, a non-determinable partial decryption of the useful data, an association of the useful data at least partially decrypted, with data additional, a coding of a data set including the at least partially decrypted payload data and associated additional data.

Thus, an attacker is not able to distinguish useful data from additional data when observing an encoded set.

An additional mechanism of masking the useful data vis-à-vis an attacker is thus added.

According to particular non-limiting embodiments, the method which is the subject of the invention has the additional characteristics taken separately or in combination, set out below:

The decoding of the coded data set, said coded set further comprising additional data associated with the payload, makes it possible to obtain said additional data associated with the payload, said additional data making it possible to calculate the additional data associated with the payload data. less partially deciphered.

Thus, being calculable from additional data, the additional data associated with the useful data at least partially decrypted can be used. They are exploitable to realize, once the useful data decrypted, a marking of this useful data.

A second object of the invention relates to a data decryption method, said data comprising a coded data set comprising useful data, characterized in that said method comprises the following steps of receiving at least a part of the coded set data, decoding of the at least part of the coded data set said at least a part of the coded set comprising at least a part of the useful data, of non-determinable partial decryption of the at least part of the useful data, of association of the at least part of the payload data at least partially decrypted with additional data, coding a set comprising the at least part of the at least partially decrypted payload data and the associated additional data, said set being a new part of the coded set of data if the at least part of the partially deciphered useful data is not fully decrypted, of transmitting the new part of the coded data set for decryption of the payload, decryption of data useful data from at least the new portion of the transmitted data encoded set.

According to particular non-limiting embodiments, the second subject of the invention has the additional characteristics taken separately or in combination, set out below:

At least a portion of the step of decrypting the payload is done by successive iteration of the steps of receiving at least a part of the coded data set, decoding the at least part of the coded set of non-determinable partial decryption of the at least part of the useful data, encoding the set comprising the at least part of the at least partially decrypted useful data, transmission of the new part of the coded set of data. A third object of the invention relates to a computer program on a data medium and loadable in the internal memory of a computer, said program comprising portions of code for executing the steps of the method according to the second object of the invention. 'invention.

A fourth object of the invention relates to a device for partial decryption of data, said device comprising means for decoding a coded set of data, said set comprising at least useful data, means for non-determinable partial decryption of useful data, means for associating the useful data at least partly decrypted with additional data, coding means of a data set comprising the at least partially decrypted useful data and the associated additional data.

A fifth object of the invention relates to a data decryption module, said data comprising a coded data set comprising useful data, said module comprising at least one partial decryption device as described above.

The invention will be better understood and other features and advantages will appear on reading the description, given by way of example, this description with reference to the appended drawings showing:

In FIG. 1, a block diagram showing the transmission of a decryption software according to the invention; - In Fig.2, a decryption method according to the invention encrypted data; - In Fig.3, a decryption module according to the invention of encrypted data.

- In Fig.4, a terminal according to the invention for processing encrypted data; In FIG. 5, an encryption method according to the invention.

The invention is described below in a particular application to the protection of secret keys when used by a software or "software" ensuring the decryption of data. However, this invention also applies to secret key protection by any hardware or "hardware" ensuring the decryption of data.

FIG. 1 is a block diagram representing the transmission of encrypted data decryption software 1 by a terminal 10. This terminal 10 is intended to generate the decryption software and to transmit it to a terminal 12 intended to process encrypted data.

The decryption software 1 comprises portions of code for the execution of the steps of a method for decrypting the encrypted data 5. Part of these steps use all or part of a secret key 2. This secret key is transmitted with the decryption software 1.

In a variant, the secret key 2 and the software are transmitted independently. The decryption software 1 is distributed for example via a telecommunication network. Alternatively, software 1 is distributed by any other distribution channel as a data carrier distribution channel such as CDs. The encrypted data 5 is sent by a terminal 11 intended to broadcast encrypted data. The encrypted data 5 is obtained from plaintext data 4. The plaintext data 4 is for example audio data, alternatively this plaintext data is any other data such as video data. Note that the terminal 11 is, for example, an online music server, alternatively the terminal 11 is any other server as a video server on demand.

The terminal 11 sends the encrypted data on request (not shown) of the terminal 12. The request is for example a request for access to particular data. In a variant, the request is a request for access to a data distribution service. This service is, for example, limited in time.

If the user of the terminal 12 satisfies the conditions of the terminal 11 for access to the data in clear 4 it transmits the encrypted data 5. These conditions are, for example, authentication conditions. Alternatively, these conditions are all other conditions as a proof of payment.

Prior to the sending of the encrypted data 5, the terminal 11 sends a request (not shown) to the terminal 10. This request is intended to generate and transmit the decryption software 1 for the decryption of the encrypted data 5.

The software 1 is here represented as being sent on a distribution channel different from the channel for distributing the encrypted data 5. In a variant, these distribution channels are identical.

In addition, the terminal 10 for generating the decryption software 1 is shown as different from the terminal 11 for sending the encrypted data 5. Alternatively, the terminals 10 and 11 are merged. Moreover, the decryption software 1 is represented as being received by the terminal 12 at a different time from the encrypted data 5. In a variant, the decryption software 1 is received at the same time as the encrypted data 5. When the software 1 is received at the same time as the encrypted data 5, it is for example received associated with these encrypted data 5.

It should be noted that the data in clear 4 are encrypted to prevent, for example, an attacker

13 can not access this data by probing the distribution channels of this data. However, an attacker is able, in certain cases, to access all or part of the secret key 2 by observing the operation of the decryption software used.

The software 1, according to the invention, makes it possible to limit the consequences of this type of observation.

This software 1 thus comprises portions of code for the execution of the steps of a method of decryption of the encrypted data 5.

Fig. 2 presents the steps of such a data decryption method 5. These data 5 comprise a coded set π (F (x), r) of data. This set comprises useful data F (x) which are the encrypted data in encrypted form. The coded set also includes additional data r associated with the payload F (x).

It will be noted that the data decryption method notably includes the steps 31, 32, 33, 35, 36, 37, 38 of a partial data decryption method.

The data decryption method thus comprises a reception 31 of at least a part πO (FO (x), rO) of the coded data set. Only part of the encoded set is received. The The size of this part is ideally chosen to allow a compromise between the security of the decryption and the processing time of this decryption. Part πO (FO (x), rO) of the coded set is for example of the order of 8 bits.

As a variant, the entire coded set of data π (F (x), r) is received in step 31.

The method also comprises a decoding step 32 of the at least one part πO (FO (x), rO) of the coded data set. It will be noted that said at least part of the coded set includes at least one FO (x) portion of the payload and additional data rO.

The portion FO (x) of the payload is partially decrypted in step 33 to obtain a portion of the payload at least partially decrypted Fl (x).

This portion of at least partially decrypted useful data is then associated with step 34 with additional data ri. By associating the part of the useful data at least partially decrypted with additional data is meant a concatenation of the different data.

The additional data ri have been previously generated in step 34. The additional data ri have, for example, been generated randomly. Thus, the set comprising the part of the useful data at least partially decrypted F (x) and the additional data ri then takes a random value.

As a variant, the additional data ri are calculated from the supplementary data rO. These additional data have in a particular embodiment also in addition to a random component. Note that the size of the additional data ri is identical to the size of the useful data at least partially decrypted Fl (x).

As a variant, the size of the additional data ri is different from the size of the useful data at least partially decrypted F1 (x).

It should also be noted that the additional data is independent of the useful data.

Step 36 makes it possible to code the set comprising the at least part of the at least partially decrypted useful data Fl (x) and the associated additional data ri. It is thus constituted a coded set ni (Fl (x), ri), this coded set ni (Fl (x), ri) constituting a new part of the set encoded π (F (x), r) if the part useful data is not completely deciphered.

Step 37 comprises transmitting the portion of the encoded set of data n1 (F1 (x), r1) for deciphering the payload F (x).

Step 38 then comprises a decryption step in order to complete the deciphering of the useful data F (x). Indeed, step 33 allows only partial decryption of a portion FO (x) of the payload. By partial decryption, it is understood that the portion of the useful data FO (x) is not fully decrypted. It is necessary then that the parts of the useful data undergo several stages of partial decryption. For this purpose, part of step 38 is done by successive iteration of steps 31, 32, 33, 35, 36, 37 on the partially decrypted portions of the payload.

Alternatively, the entire step 38 is by successive iteration of the steps 31, 32, 33, 35, 36, 37. It should be noted that the part n1 (F1 (x), ri) of the coded data set transmitted in step 37 can be received in its entirety during the next reception step 31. Alternatively, it is only part of the ni (F1 (x), ri) portion of the encoded set that is received.

In another variant, the part n1 (F1 (x), ri) of the coded set is combined with another part of the coded set, prior to a reception step 31.

It will also be noted that when two partial data decryption methods follow each other, the coding function used in step 36 of the first method is related to the decoding function used in step 32 of the second method. These two functions are for example the opposite of each other.

Thus, step 38 makes it possible to obtain decrypted useful data x or data in clear 6. Step 38 also makes it possible to obtain additional data rn associated with the deciphered payload x.

Note that in the case where the additional data ri are determined from the additional data r0, it is possible to choose the additional data r in order to obtain additional data rn desired. The final additional data can then be used, for example, as a tagging of the decrypted useful data x. Marking is in the form of data intended to provide complementary information to data in the clear such as the name of a work or its author. Marking also makes it possible to incorporate security data. As a variant, the data x is not the data in the clear 6. A transformation of the data x is then necessary to obtain these data in clear 6.

In a particular embodiment, this transformation involves the additional data rn.

It will be noted that step 33 allows only a partial decryption of a part of the useful data because this step uses only part of the elementary functions of the algorithm used for the decryption of the data.

The cryptographic algorithm is, for example, the AES algorithm for Advanced Encryption Standard. Alternatively, the algorithm is any other symmetric or asymmetric cryptographic algorithm. This AES algorithm thus takes, as input, blocks of encrypted data 5. These blocks are, for example, blocks of size 128 bits or 16 bytes. In a variant, these blocks are of any other size. The bytes then undergo different operations. In a first step, the bytes are permuted in a previously defined manner. This operation is called byte substitution or ByteSub transformation. The bytes are then placed in a matrix of 4 * 4 elements. The lines of this matrix are then rotated to the right. The increment for the rotation varies according to the line number. This operation is called line shift or shift row transformations. A linear operation is then applied to the matrix. This operation consists of a binary multiplication of each element of the matrix with polynomials coming from an auxiliary matrix. This multiplication is subject to special rules according to the Galois group or finite body. The linear operation thus guarantees better bit diffusion. This operation is called Column Mix or MixColumn transformation. Finally, an XOR between the matrix and another matrix makes it possible to obtain an intermediate matrix. This operation is called addition of floor keys or round key addition.

The different operations are chained to form a turn.

All these operations can be represented in the form of elementary functions allowing partial decryption of the at least part of the useful data. Thus the deciphering of the useful data amounts to the successive application of the different elementary functions on the parts of the useful data. The elementary functions are, for example, XORs or S boxes.

It will be noted that these elementary functions use partial decryptions of all or part of the decryption key 2 present in the decryption module. In a variant, some of the elementary functions do not use all or part of the key. The partial decryption step that these functions perform simply makes it possible to transform the portion of the useful data into a form that can be used for another partial decryption step.

It will also be noted that the coding or decoding functions are different from the elementary functions. In fact, unlike the latter, they do not represent operations of a decryption algorithm. In addition, the encoding / decoding functions apply to a set of data. The basic functions apply only to the parts of the useful data. In addition, these coding / decoding functions are used to prevent an attacker from can dissociate useful data at least partially decrypted additional data.

As already mentioned above, the partial decryption step 33 is not determinable with respect to an attacker. This step is not determinable because it is considered that it is not possible for an attacker to observe the received useful data FO (x) and the payload data Fl (x) at the level of the elementary function used during this procedure. partial decryption step. To make the decryption step 33 non-determinable, it is, for example, suitably chosen the decoding function used in step 32 and the coding function used in step 36. These functions are chosen in such a way that the composition of this decoding function with the elementary function and with this coding function does not allow the observation of the data circulating between the various means 41, 42, 43, 44, 45, 46, 47. The partial decryption device 40 is then seen by an attacker as a black box.

In another variant, the partial decryption step 33 is made non-determinable with respect to an attacker in that the composition of the decoding function with the elementary function and with the coding function is represented in the form of a decoder. a correspondence table. This table includes all the input / output pairs of this composition previously calculated. It will thus be noted that the correspondence table performs the equivalent of the decoding steps 32, partial decryption 33, association 35, and coding 36. By the use of this table, it is not possible to attacker to specifically observe the received useful data FO (x) and the payload data Fl (x) at the elementary function used during this partial decryption step. The partial decryption device 40 present in the form of a table is then seen by an attacker as a black box. Note also that during the preliminary creation of this correspondence table, the decoding steps 32, partial decryption 33, association 35, and coding 36 are implemented.

Fig. 3 presents a data decryption module 50. These data comprise a coded set of data π (F (x), r) having useful data F (x) and additional data r. In practice, the decryption module 50 consists of a computer system in which a computer program loadable in the internal memory of this system is executed for the implementation of the decryption method. This program comprises, in fact, portions of code for the execution of steps 31, 32, 33, 35, 36, 37, 38 of this decryption method.

The module includes a partial data decryption device 40 and a data decryption device 48.

The partial decryption device comprises means 41 for receiving at least a portion of the coded data set πO (FO (x), rO).

The part of the coded set of data πO (FO (x), rO) comes directly from the coded set of data π (F (x), r).

Alternatively, the portion of the encoded data set is from prior decryption.

The partial decryption device also includes decoding means 42 for the at least part of the coded data set. This at at least part of the set has a part FO (x) of the payload and additional data rO.

The at least one portion FO (x) of the payload is then decrypted at least in part by partial decryption means 43.

Association means 45 associates the at least part of the useful data at least partially decrypted Fl (x), with additional data ri. This additional data is generated previously by generation means 44.

Coding means 46 encode the set comprising the at least part of the at least partially decrypted useful data Fl (x) and the associated additional data ri. This coded set constitutes a part of the coded set of data π (F (x), r).

The partial decryption device also comprises means for the transmission 47 of the set comprising the at least part of the at least partially decrypted useful data Fl (x) and the associated additional data ri, to the data decryption device 48 The data decryption device 48 comprises, for its part, at least one partial decryption device comprising, in particular, reception means 41, decoding means 42, partial decryption means 43, association means 45, coding means 46.

In a variant, the decryption device 48 comprises any other means for decrypting the data.

The decryption device makes it possible to obtain at the output of the decryption module the decrypted useful data x or data in clear 6. As a variant, the data x are not the data in clear 6. A transformation of the data x is then necessary to obtain these data in clear 6. It will be noted that the decryption module 50 is seen by an attacker as a white box in which it is possible to observe the data flowing between the partial decryption device 40 and the decryption device 48. However, the attacker observes only the coding of a set comprising at least partially decrypted useful data associated with data. additional. It is not able to distinguish the useful data at least partly decrypted from the additional data.

Fig.4 shows a terminal 12 for processing encrypted data. The terminal 12 thus comprises means 51 for receiving a coded set of data π (F (x), r), transmission means 52 of the coded data set to a module 50 for decrypting the data.

Transmission means 57 allow the transmission of the decrypted useful data x to the means of use 58 of this decrypted user data.

Fig. 5 presents a method of data encryption. This method comprises a step of encrypting useful data x. This useful data is for example the data 4.

The method also includes a step of associating the encrypted user data F (x) with additional data r. This additional data was previously generated. A coding step 62 makes it possible to encode a data set comprising the encrypted useful data F (x) and the associated additional data r. It should be noted that the coding function is chosen in such a way that the decoding of the data set in a decryption module 50 is facilitated.

As a variant, the encryption of the useful data comprises encryption, association, coding and useful data part steps.

Claims

claims

A method of partial decryption of data, characterized in that said method comprises: decoding (32) a coded data set said set comprising at least useful data; partial decryption (33) of the useful data; an association (35) of the payload data at least partially decrypted with additional data; an encoding (36) of a data set comprising the at least partially decrypted payload and associated additional data.

2. Partial decryption method according to claim 1, characterized in that the decoding

(32) of the coded data set, said coded set further comprising additional data associated with the payload, provides said additional data associated with the payload, said additional data for calculating the additional data associated with the payload at least partially deciphered.

3. A data decryption method, said data comprising a coded set of data (π (F (x), r)) comprising useful data F (x), characterized in that said method comprises the following steps: receiving at least a portion (πO (FO (x), rθ)) of the encoded data set; - 32) a decoding of the at least a part of the coded data set said at least a part of the coded set having at least a portion (FO (x)) of the payload; - 33) a non-determinable partial decryption of the at least one part (FO (x)) of the payload data;

- 35) an association of the at least part of the useful data at least partly decrypted

(Fl (x)) with additional data (ri); - 36) a coding of a set comprising the at least part of the at least partially decrypted payload (Fl (x)) and the associated additional data (ri), said set being a new part of the coded set of data (π (F (x), r)) if the at least part of the useful data at least partially decrypted is not completely deciphered;

37) transmitting the new portion (ni (F1 (x), ri) of the encoded data set for decryption of the payload data;

38) a decryption (38) of the useful data from at least the new part (ni (F1 (x), ri)) of the transmitted data coded set.

4. Decryption method according to the preceding claim characterized in that at least a portion of step 38 is by successive iteration of steps 31, 32, 33, 35, 36, 37.

A computer program on a data carrier and loadable in the internal memory of a computer, said program comprising portions of code for performing the steps of the method according to any of claims 3 to 4.

6. Device for partial decryption of data characterized in that said device comprises:

means for decoding (42) a coded set of data said set comprising at least useful data; means for partial decryption (43) of non-determinable useful data;

means for associating (45) useful data at least partly decrypted with additional data;

coding means (46) for a set of data comprising at least partially decrypted useful data and associated additional data.

Data decryption module, said data comprising an encoded data set comprising useful data, characterized in that the module comprises at least one partial data deciphering device according to claim 6.