FR2808948A1 - SYSTEM AND METHOD FOR UNIQUE AUTHENTICATION OF EACH REPRODUCTION OF A GROUP OF ELECTRONIC DOCUMENTS - Google Patents

Abstract

The present invention uniquely authenticates each reproduction of a plurality of electronic documents forming a group. An electronic document, part of the group, becomes the bearer of an authentication code intended to protect the group. This authentication code is calculated from the concatenation of the set of electronic documents and a key. A random number is also generated for each reproduction of the file group. It is combined with the authentication code to mark the electronic document that has been selected as the bearer. Thus, the present invention introduces randomization into the insertion of the authentication code, so that with each reproduction of an identical group of data files, unique authentication data can be associated, merged and hidden in the information transmitted.

Description

TECHNICAL FIELD OF THE INVENTION

  The present invention relates to the field of document authentication, and applies more particularly to a system and method in which an electronic document belonging to a group of associated documents acts as the bearer of integrity information intended for uniquely authenticate

each reproduction of the group.

STATE OF THE ART

  The current environment of computer networks is characterized by an exponential growth in the circulation of electronic documents. These are simple text documents or text files, coded on p. ex. in ASCII (American Standard Code for Information Interchange), and more generally of data files such as those corresponding p. ex. coding of images according to the standard compression algorithm JPEG (Joint Picture Expert Group). However, these documents circulating on non-secure media, and in particular

  the Internet, their authentication is a serious problem.

  It should be possible for the recipient of a document to ascertain its origin in order to prevent anyone from impersonating someone else. Likewise, it should be possible to verify that a document has not been altered, accidentally or maliciously, along the way. For this, the standard solution - which is suitable for all forms of electronic documents since, whatever the method used to encode the information, the end result is a binary data file - consists in concatenating a message authentication code or MAC with electronic document files. A MAC is a code calculated with a unidirectional reducing calculation function from a coded binary file and which also depends on a key, p. ex. a secret key known only to the sender and the recipient so that

FR920000021

  -2 - that the latter can then verify, firstly that what he receives has been sent by the person with whom he shares the secret key and, secondly, that the document has not been altered. For example, the Secure Hash Algorithm or SHA specified by the National Institute of Standards and Technologies, NIST, FIPS PUB 180-1, "Secure Hash Standard", US Dpt of Commerce, May 93, generates a 160-bit code. It can be combined with a key, p. ex. using a mechanism called HMAC (KeyedHashing for Message Authentication) submitted to the RFC (Request For Comment) of the IETF (Internet Engineering Task Force) under number 2104. The HMAC is designed in such a way that it can be used with any iterative cryptographic calculation function, including SHA. Therefore a MAC can be appended to a document file so that everything can be checked by the recipient. Thus, this method supposes the addition of the control information to an existing file after the information to be transmitted has been coded. This method has the disadvantage of clearly separating the informational content of the file from its control mechanism. Consequently, the latter can be easily isolated and eliminated voluntarily with fraudulent intent, or accidentally because the intermediate equipment responsible for transmitting electronic documents is not designed to handle

  this additional piece of information.

  Another critical point of public communication networks such as the Internet is discretion and confidentiality. All information circulating between end users, whether text, images or combinations of the two, is not intended to be public. The standard answer to this problem is based on cryptography. In other words, the information files which must be kept secret are encrypted before being transmitted. The DES (Data Encryption Standard) is the standard encryption algorithm that has been used for two decades to encrypt and decrypt data files. It works on 64-bit data blocks, with a key

FR920000021

  -3 - symmetric secret shared between the users concerned. The DES algorithm is identical to the standard ANSI Data Encryption Algorithm (DEA) defined in

ANSI X3.92-1981.

  Authentication of encrypted files is done exactly as for unencrypted files; in other words, a MAC is calculated and concatenated with what remains intrinsically a binary data file. Therefore, another disadvantage of calculating integrity information from the data is that this integrity information itself reveals information about the data from which it is calculated. Until the key is changed, the integrity information calculated from the data remains the same. Therefore, if an intrusive person notices that the MAC transmitted is the same, he can be certain that the encrypted message transmitted is also the same. In applications where pre-formatted files are repeatedly transmitted (eg, the same images or the same encoded music sequences), a simple frequency analysis applied to the intercepted MAC values can reveal a structure in the messages transmitted. Likewise, one or more encrypted files sent only once but to several destinations makes it possible to know which group has received the same information. This is why it would be interesting, firstly, to introduce a certain randomization in the process so that the MAC values vary constantly and, secondly, to make it possible to hide the MACs in the information transmitted in order to completely prevent an adversary to obtain information from the observation of the data transmitted. If this result could be obtained partially (randomization could be obtained in this way) by changing the codes, and more particularly the calculation key of the MAC, which should be different for each transmitted copy of one or more identical data files and / or for each destination, this would seriously penalize the key management system, since it would be necessary that

FR920000021

  -4 - the secret keys are first transmitted by a channel

  separate, which is a tedious task.

OBJECT OF THE INVENTION

  This is why the present invention has the general object of remedying the defects described above of

existing systems.

  The invention also aims to propose a method and a system introducing a certain randomization in the insertion of a MAC so that with each reproduction of the same group of data files can be associated data of unique authentication. The object of the invention is also to make it possible to merge and conceal the authentication data.

in the information transmitted.

  Finally, the object of the invention is also to be able to be implemented in a transparent manner, in particular without it being necessary to transmit more secret keys than is generally necessary for encryption and

authentication.

  The other objects, characteristics and advantages of the present invention will appear to specialists on examination

  the following description and accompanying drawings.

  It is understood that other advantages may be

incorporated.

FR920000021

-5 -

SUMMARY OF THE INVENTION

  A method and a system for uniquely authenticating each reproduction of a plurality of electronic documents forming a group are provided. The method first selects an electronic document from the group, which will become the bearer of an authentication code intended to protect the group. The electronic documents are concatenated, however using a canonical form of the selected electronic document, so that they can be checked later. Then, the authentication code is calculated from the concatenation of the group of electronic documents and a key. A random number is also generated for each reproduction of the file group. It is combined with the authentication code to mark the selected electronic document which acts as the bearer. A method for

  checking the authentication code is also proposed.

  Thus, the invention introduces a certain randomization in the insertion of an authentication code, so that each reproduction of an identical group of data files can be associated with unique authentication data. The invention also makes it possible to merge them and conceal them in the information transmitted.

FR920000021

-6 -

BRIEF DESCRIPTION OF THE FIGURES

  The present invention is fully described in the

  detailed description below with figures

  following: Figure 1 is a simple example of how

  the invention can be implemented.

  Figure 2 shows that more files can

be associated in a group.

  Figure 3 describes the general case where a set of

  files, including the bearer, are associated.

  Figure 4 is a detailed description of how

  the invention of which is implemented when the carrier is a

simple text file.

  Figure 5 shows the steps of the control method

according to the invention.

  FIG. 6 shows an example of an improved method for obtaining an authentication code according to the invention.

  DETAILED DESCRIPTION OF THE INVENTION

  Figure 1 shows how the invention can be optimally implemented using an example application. A first document, in this case a fingerprint image [100], is coded in the form of a formatted data file, p. eg, according to the standard image compression algorithm JPEG (Joint Photographic Experts Group), giving a data file [110] whose name will be, for example, fingerprint.jpg. A second document is associated with this image, for example a text [120] giving explanations on fingerprints. The text document is also encoded as a file,

  p. ex. a simple ASCII file "fingerprint.txt" [130].

  Then, the first document, the image of the fingerprint [100], can be protected by calculating [140] a MAC (Message Authentication Code) using the message of the file [110] and a key [115] as inputs, with any

FR920000021

  -.7- which method known in the current state of the art, to obtain a unique code or MAC [145], ie a binary vector made of 1 and 0. Then, the MAC, instead of d be attached to the fingerprint file, is used, with a random number [160], to mark [170] transparently and uniquely the text file [130] that accompanies the image, as explained in the following figures, in order to fulfill the objectives of the invention which are to randomize and conceal the authentication data. Consequently, the second document acts as a carrier [150] for the authentication data. Figure 2 specifically illustrates that more than two documents may be involved. For example, a photo of the person [205] whose fingerprint is shown [200] can also be associated, so that a MAC is calculated [240] from the concatenated graphic files [210 and 211] and then merged in the text file [230] so that the two can be authenticated together by decoding the marked accompanying text [250], upon receipt of the three associated files [210, 211

and 250].

  FIG. 3 illustrates another general use case of the invention in which the MAC [345] is not calculated only from several files, p. ex. the files [310 and 311] of the two images [300, 305], but also includes the text document file itself [320] which is ultimately used to transport [350] the authentication data, so that the three elements form a group [313] which can be authenticated as a whole. Since, in this case, the bearer of the authentication data is concatenated [314] in order to participate in the calculation [340] of the MAC, it is implicitly assumed that there may exist something such as a canonical form of the file of text that acts as a carrier [330] from which an identical file [312] (canonical.txt) can be generated so that the calculations performed during generation and control can

FR920000021

  -8 - actually coincide. In this particular example, the carrier being the text file [330], the aforementioned modifications that can be made transparently to the text document must consist of changing, in some way, the number of blanks between the words (like , eg, [331]) of the text. However, this should not affect readability. Then, the canonical form of the text on which all the parties involved must agree and from which the calculation of the MAC must begin, can consist in removing all the blanks between the words or in leaving a predefined fixed number of these blanks, for example a blank space between each word as is customary in a text document. Thus, the canonical form is, in this particular case, a form of text which can be obtained identically by the sender and by the recipient, without taking into account that the text has been marked (by the insertion of blanks additional), in order to

  allow authentication of the group of files transmitted.

  Finally, as in the examples of FIGS. 1 and 2, the MAC is used, with a random number [360], to mark in a transparent manner [370] the text file [130] which acts as a carrier [350] for the authentication data. FIG. 4 describes the method of the invention to allow the integration into the carrier file of the authentication data so that the information is randomized and concealed. Although, in this example, this preferred version of the invention uses a text file as the carrier for the authentication data, it should be obvious to specialists that, without betraying the spirit of the invention, it could be applied in different ways whether or not involving a text file. The implementation of the invention supposes that there is a kind of neutral element in the carrier file which does not alter its meaning or its functioning even if it is isolated or reproduced more than is strictly necessary . According to this definition, white (x'40 'for an ASCII file, displayed

FR920000021

  -9 - here in the form of an insertion sign ^ [480]) is the neutral element for a text document since the insertion of more blanks than is necessary, ie more 'white, does not affect readability. Likewise, since there is at least one blank space between each word, there are many opportunities to merge, in the form of additional blank spaces between words, the authentication data, provided that the text understands

enough words.

  Next, the invention supposes that the MAC [400] (calculated according to any standard or personalized method known in the current state of the art) is used here to divide the text into two sets of words. For that, it is enough to create a first set [410] with the words whose position corresponds to 1 [412] of the binary vector MAC. The second, complementary set [420] corresponds

  to 0 [422]. In the description of FIG. 4, we admit,

  for the sake of simplicity, that the length of the binary vector MAC corresponds to the number of words in the text [430] although this is rarely the case. However, if the text includes more words, which is generally the case, all parties involved must agree on the party to be selected so that coding and control are done in the same way. The simplest method is to select a sufficient number of words in the text, starting at the beginning, corresponding to the length of the MAC binary vector, but there are many other possibilities, such as selecting the words from the end. , which avoids choosing other more sophisticated methods such as selecting subgroups of words on which we must agree a priori. It is also assumed that the number of words in the shortest carrier text is sufficient to correspond to the length of the binary vector resulting from the selected MAC function. In other words, depending on the level of protection that it is desired to obtain in a given application of the invention, the binary vector MAC will have different lengths (eg, a 160-bit computer code is produced with SHA ). So the

FR920000021

- 10 -

  carrier text must have at least the corresponding number of words (more exactly, there must be a sufficient number of intervals between words, the last word of the text being generally excluded [431]) to allow the use of the binary vector MAC full. Otherwise, if the MAC cannot be fully used because the carrier text is too

  short, the level of protection is reduced accordingly.

  Then, the first set of words [410], with the blanks following them, is marked by the insertion of a random number (RN) of additional blanks. The exact method for achieving this is beyond the scope of the present invention. For the sake of clarity, it is assumed in this illustration of the invention that a simple method is applied. In this case, RN is generated by any suitable random number generator [445], known or adapted from the current state of the art, in the form of a first binary vector Pi [440], which can enter

  p. ex. in the smaller of the two sets of words.

  Then an additional blank is inserted for each corresponding interval, p. eg, to a 1 in Pi [442]. We can envisage more sophisticated methods and numerous variants to obtain and insert a random combination of additional blanks, but that would not change the object of the invention, which, rather than inserting the MAC directly into the carrier text, use it to divide it and insert a random number of extra blanks.

  Finally, the second set of words is also marked.

  From Pi [440], a transformation function T [450] is applied to obtain a second combination P2 = T (P1) [460] which must be able to enter the second set of words. Like Pi, P2 is used to insert additional blanks in the second set, p. ex. [462]. Again, the type of transformation function T to be used to obtain P2 from P1 is beyond the scope of the invention. Many equivalent methods are possible. The simplest is to simply reuse Pi as is to insert it into the second set. A more transformation method

FR920000021

- he -

  elaborate consists in calculating RN so that P2 = H (P1).

  H can be any suitable calculation function. In this case, P2 [460] is just the bit-to-bit complement of Pi. The last operation consists in gathering [470] the two sets resulting from the combination of 1 and 0 of the MAC

  [400] to obtain the carrier [475].

  FIG. 5 describes an example of the decoding method according to the invention, the carrier being a simple text document in which additional blanks have been

  inserted. Description begins when MAC is recalculated

  [500] as shown in Figures 1, 2 and 3. The operations shown in this figure are performed in a similar manner to what was shown in Figure 4. Next, with the binary vector MAC, the text is divided into first and second sets of words. A combination of additional blanks is extracted [520 and 530] from each of the two sets. On the combination extracted from the first set is applied [540] the same transformation function as that used for coding. Finally, if the combination of additional blanks in the second set matches [551] to the transformed combination in the first set when compared [550], the files are recognized as authentic. If the comparison fails [552], it must be admitted that one or more

  several files in the file group have been used.

  FIG. 6 gives more details on what the combination of the MAC should be for an optimal implementation of the invention. Although the invention does not require any assumption as to how to calculate the MAC, the following restrictions should nevertheless be mentioned. Whichever method is actually used to calculate it, account must be taken of the case where the MAC would have very few bits at 1 or very few bits at 0, although the probability of obtaining such a ratio between the 0 and the 1 is weak, even very weak. So suppose for a moment, p. e.g. a MAC of

  128 bits includes 127 bits at 1 and only one bit at 0.

  Concretely, this would result in 127 bits of random data which could be coded in the first

FR920000021

- 12 -

  set of words (such as [410] in Figure 4) of the split text, and only 1 bit of transformed random data that could be encoded in the second set (such as [420]), which would therefore include a single word in this extreme example. In this case, an opponent wishing to substitute another text for the actual text would have a probability of 1/2 of successfully passing the verification check. Similarly, with a split of 126 and 2, we would have a probability of 1/4 of successfully passing the verification check, etc. Consequently, the optimal situation is that where the MAC has the same number of 1 and 0, namely 64 ones and 64 zeros in this example o the MAC has 128 bits. This gives a minimum probability of 1 / (2 ** 64). Therefore, one may possibly wish to favor a method of MAC generation which

  guarantees a prescribed number of bits at 0 and bits at 1.

  Among the many possibilities, a trivial method is to have a recursive procedure where the MAC is calculated using the input data [600], a key [610] and a counter [620]. The generated MAC [630] is tested [640] to see if the number of bits at 0 and bits at 1 satisfies the imposed condition, and, if this is the case, the MAC is accepted and used [650]. Otherwise, the value of counter [620] is increased [660] and a new MAC is calculated, this procedure continuing until an acceptable MAC is found. The sender and the recipient using the same procedure to generate MACs and the first acceptable MAC

  being taken, they are guaranteed to use the same MAC value.

FR920000021

- 13 -

Claims (11)

  1) A method for uniquely authenticating each reproduction of a plurality of electronic documents [310, 311 and 330], said plurality of electronic documents forming a group [313], said method comprising the following steps: selection of a electronic document [330] in said group [313], which will become the bearer [350] of an authentication code [345] intended to protect said group, concatenation [314] of said plurality of electronic documents, said concatenation step comprising the following step: use of a canonical form [312] of said selected electronic document [330], calculation [340] of said authentication code [345] from said concatenated set of electronic documents [314] and a key [315], generation of a random number [360], and combination of said random number and said authentication code to mark [370] said selected electronic document [330], in order to obtain ledi t carrier [350].   2) The method described in claim 1, said concatenation step excluding said electronic document selected [230].   3) The method described according to any one of   previous claims, said concatenation step   being replaced by the step of taking charge of only one electronic document [110]. FR920000021 - 14 -   4) The method described in any one of   previous claims the combining step   comprising the following steps: dividing said selected electronic document [430] into a first set [410] and a second set [420] based on said authentication code [400], using said random number [440] to mark [442 ] said first set, transforming [450] of said random number, using said transformed random number [460] to mark said second set, and gathering [470] of said first set [410] and said second set [420] based on said code authentication [400], in order to obtain said carrier [475].   ) The method described in any of   previous claims, said electronic document   selected being a simple text document [430] and said first set [410] and said second set [420] being   sets of words from said simple text document.   6) The method described in any of   previous claims said simple text document   [430] being marked by the insertion of additional blanks [442] and [462].   7) The method described in any one of   previous claims, the step of using said   canonical form of said simple text document comprising the following step: extraction of all the blanks of the words, except for one, from said simple text document,   in order to obtain said canonical form. FR920000021 - 15 -   8) The method described in any of   previous claims, said authentication code   [400], said random number [440] and said transformed random number [460] being binary vectors which can be of a size suitable for said selected electronic document [430], said first set [410] and said second set [420].   9. The method described in any of   previous claims, said dividing step   comprising the following steps: forming said first set with the words of said selected electronic document corresponding to the ones of said authentication code [412], and forming said second set with the words of said selected electronic document corresponding to zeros   said authentication code [422].   ) The method described in any of   previous claims, said calculation step being   replaced by the following steps: calculation [605] of said authentication code [630] from said concatenated group of electronic documents [600], said key [610] and a counter [620], and test [640] the density of some of said authentication code; if the test fails: incrementation [660] of said counter, and resumption of the calculation step; if the test succeeds: validation [650] of said authentication code, and exit from said calculation step. FR920000021 - 16 -   11) The method described in any of   previous claims, said transformation step   comprising one or more of the following steps: re-calculation from said random number, re-use of said random number, inverting said random number.   12) A method for controlling said authentication code comprising the following steps: obtaining [500] of said authentication code, dividing [510] of said carrier into a said first set and a said second set, extraction [520] from a first combination of said first set, transforming [540] of said first combination, extracting [530] a second combination from said second set, and comparing [550] of said first transformed combination and said second combination; if they match [551]: validation of the check, if they do not match [552]: invalidation of the control.   13) A system, and in particular a system for uniquely authenticating each reproduction of a group of electronic documents, comprising means suitable for implementing the method described in one   any of the preceding claims.   14) A computer-readable medium comprising the instructions of a program executable by said computer, said program implementing the method   according to any one of claims 1 to 12. FR920000021