Process and authentication device for secured authentication between two terminals6055638Abstract Process and device for secured authentication of the transmission of data between two terminals includes a secured authentication process for the communication between a user's station and a server station, through a communication network, the user's station bring the content of an authentication device depending on information coming from a server station, in which a link is established between the user's station and the server station, a server code is chosen at random at the level of the server station, representative data of the server code are transmitted in a first server-to-user direction, thanks to those data, a corresponding user's code is recognized in the content of the authentication device, the recognized user's code is transmitted in a second user-to-server direction, the user's code is compared with the server code, and the authentication is validated if the user's code is identical to the server code. Claims We claim: Description BACKGROUND OF THE INVENTION
______________________________________
SERVER/U.sub.1
INTERNET
to U.sub.n NETWORK PC/U.sub.i
______________________________________
MS/U.sub.1 <-------->
MU/U.sub.1 <= U.sub.1
MS/U.sub.2 <-------->
MU/U.sub.2 <= U.sub.2
. . . . . .
MS/U.sub.n <-------->
MU/U.sub.n <= U.sub.n
.O slashed. U.sub.2
.O slashed.
______________________________________
With: MS/Ui=server matrix of the user i; MU/Ui=user matrix of the user i, or floppy disk matrix. First, a safe and logical authentication can be provided by the seizure of a password. In that case, during his access to the server, the customer seizes, on one hand, his ID, which is in general in the form of figures-letters code, in order to let his identity be known and recognized, and, on the other hand, a password. In fact, when the user or the customer is accredited for the connexion to a server, the authority, that is to say, the bank for example, gives an ID to the user who chooses his password. Those two elements make if possible to initiate a transaction. The process according to the invention, in fact, definitively validates the transaction. To this effect, logical authentication is doubled with physical authentication. Thus, when a link between the customer and the server is established through logical authentication, we will proceed with a second authentication, the information from that second authentication being conceived in such a way as to prevent "piracy". In addition, the user possesses the floppy disk 3, 31/2 inches format. Today, almost every single Personal Computer existing on the market is equipped with floppy disk drive of that format. The second authentication or physical authentication is accomplished in the following way: For each authorized user Ui, a server matrix MS/Ui is created by a pseudo-random function F1 that fills in the matrix cells of dimension d, and this, by means 4 of pseudo-random creation of a matrix located in server 2. The matrix that can be used in the application of the process, is of dimension 2 and comprises 255 lines and 255 columns, which corresponds to 65 025 cells. For each cell of the matrix (line x, column y), in order to fill in this server matrix MS/Ui, the pseudo-random function F1 chooses "at random" a sign among 62, for example: [0, 1, . . . , 9, a, b, . . . , z, A, B, . . . , Z]. Of course, the choice of signs could be extended to most of the ASCII codes, and even to other types of signs. Thus, all the authorized users have available their personal matrices which are very different from one another. In accordance with a first embodiment, the server matrix S/Ui is identical to the MU/Ui user's matrix. Thus, the server matrix MS/Ui, created by the server 2 for the user Ui, is copied or duplicated on floppy disk 3 of that user, through duplication means 5 located in the server 2 and linked to means 4 and that particular floppy disk 3 is transmitted to the user in question, through a transmission means not shown such as for example by postmail. Each attempt at connection to the server 2 corresponds to a transaction ti'. After a conventional logical authentication step (ID and password transmitted via the network), the authorized user Ui is subjected, from the server 2, to a challenge-response procedure in order to authentify his identity, in compliance to the process according to the invention. Let us take, in order to simplify, a server matrix with three lines and three columns:
______________________________________
a x 2
f 8 t
r q s
______________________________________
At each transaction, means 6 located in the server 2 generate, according to a pseudo-random function F2, two couples of co-ordinates (lines, columns). These couples are sent to the terminal PC/Ui of the user Ui, ia the network, through first emission-reception means 7 located in the server 2: this is the challenge. In the server matrix MS/Ui, the content of these co-ordinates represents the server code CS. The user receives the information via second emission-reception means 9 and is then invited to place his personal floppy disk 3 in a drive 8 of his terminal PC/Ui. Let us take for example the co-ordinates (1, 1) and (3, 2). Thus, F2ti'(M)=(1, 1), (3, 2)=1132. In the example in consideration, the diagram is as follows:
______________________________________
INTERNET NETWORK
Challenge = 1132
MS/U.sub.i MU/U.sub.i
______________________________________
a x 2 => a x s
f 8 t f 8 t
r q s <= r q s
response = aq
______________________________________
A function V makes it possible to read the value corresponding to those couple of co-ordinates. This function V is applied, through means 6, on the server matrix MS/Ui present on the server 2 in order to obtain, on the one hand, the server code CS and, through drive 8, on the user's matrix present on floppy disk 3, in order to obtain a user's code CU on the other hand. Thus, we obtain, for user Ui: CS=V(MS/Ui, F2ti')=a, q=aq, and CU=V(MU/Ui, F2ti')=a, q=aq The user's code CU obtained with floppy disk 3 is sent, through second emission-reception means 9, to the server 2 via the network: this is the response. The server 2 compares the two codes CU and CS through comparison means 10: if they are identical, that is to say that V(MS/Ui, F2ti')=V(MU/Ui, F2ti'), then validation means 11 validate the authentication of the user and the connection to the server 2 is authorized for that user; if they are different, that is to say that V(MS/Ui, F2ti').noteq.V(MU/Ui, F2ti'), then the authorized user is not authentified and the connection to the server 2 is refused. At each new transaction, the server 2 proposes a new challenge to the authentication device. It is perfectly understood that the information transmitted in the first server-to-user direction is different in nature from the information transmitted in the second user-to-server direction, which prevents a third party from establishing a correlation or a logical link between those two types of information. That being said, the invention is applied to any data group containing specific signs at specific addresses. To increase security in case of a robbery, which was not noticed, of the authentication device 3, the process according to the invention also associates an almost impregnable code to the authentication device 3. This code is also called shift code CD. After the creation of the server matrix MS/Ui in the server by creation means 4, the server matrix MS/Ui is in fact not memorized identically on the authentication device 3. Thus, shift means 12 located in the server 2 apply a shift function to the server matrix MS/Ui to generate a new so-called shifted matrix MD/Ui which is duplicated on the floppy disk in order to form a new user's matrix: D(F3, MS/Ui)=MD/Ui=MU/Ui where F3 is a pseudo-random function generating shift codes for each matrix and thus for each user. Each shift code CD is transmitted to the user in question by second transmission means 13 distinct from the first transmission means, and will have to be seized by the user at each transaction by input means 14 located in the terminal. Thus, the user's code CU will be made up of the content of the user's matrix MU/Ui corresponding to the co-ordinates transmitted (challenge) to which the shifted function D has been applied. According to a first embodiment, the shifted function D is such that at all the line co-ordinates of the matrix, a first number u is added, given by the pseudo-random function F3 (for example +1) and that at all the column co-ordinates of the matrix, a second number v is added by the pseudo-random function F3 (for example +2). The shift code is then made up of the first and second numbers uv. Of course, this shift is accomplished modulo the number of n lines of the matrix and modulo the number of m columns. In the example that follows, let us take 12 as the shift code which consists in adding 1 to the lines and 2 to the columns. From our starting example, we obtain:
______________________________________
MS/U.sub.i MD/U.sub.i = MU/U.sub.i
______________________________________
a x 2 D (line +1, column +2)
q s r
f 8 t or D.sub.12 x 2 a
r q s => 8 t f
______________________________________
Let us take our transaction t.sub.i ' again. Without the seizure of the shift code uv on the terminal, the user's code CU is erroneous.
______________________________________
MS/U.sub.i MU/U.sub.i or MD/U.sub.i
______________________________________
a x 2 1132 q s r
f 8 t => x 2 a
r q s <= 8 t f
qt
______________________________________
Because: V(MS/Ui, 1132)=aq and V(MD/Ui, 1132)=qt aq.noteq.qt The connection is refused. By seizing, on the terminal, the right shift code which is applied to the co-ordinates of the challenge, the user's code obtained is correct.
______________________________________
MS/U.sub.i MU/U.sub.i or MD/U.sub.i
______________________________________
a x 2 1132 q s r
f 8 t 1132 corrected by shift code gives 2311
x 2 a
r q s <= 8 t f
aq
______________________________________
Because: V(MS/Ui, 1132)=aq and V(MD/Ui, D12(1132))=V(MD/Ui, 2311)=aq aq=aq The connection is authorized. Thus, generally, we obtain: V(MS/Ui, F2ti')=V'MD/Ui, Duv(F2ti')) On the contrary, any seizure of erroneous shift code Du'v' with (u', v').noteq.(u, v) will result in an incorrect user's code such as: V(MS/Ui, F2ti').noteq.V(MU/Ui, Du'v'(F2ti')) In addition, it can be forecasted that, whatever shift code CD may be seized by the user on the authentication device 3, this is accepted by the reading program. Thus, there is no good or bad shift code CD that a "cracker" could try to "break". Of course, this shift code CD is not present in any form on the authentication device 3, never transits on the communication network, and is not explicitly present on the server 2. Thus, it is almost impregnable. In the embodiment previously described, the shift function used D+u+v is very simple. It is thus possible to establish the link between the server matrix MS/Ui and the user's matrix MU/Ui if the user's matrix MU/Ui is known and if we assist in a few transactions in clear which each time inform us on: F2ti'(M) and V(MU/Ui, Duv(F2ti')) That is to say, in the example, (1, 1) (3, 2) where "1132" gives "aq" taking into account u and v. In that case and in the light of a few transactions, it is possible to deduce u and v from it and consequently, to discover the shift code's value CD. Yet, this necessitates four preliminary conditions: 1. To physically steal the user's floppy disk 3. 2. To duplicate this floppy disk 3 or to read and rewrite the user's matrix present on this floppy disk 3. 3. To give back the floppy disk to the user without him noticing the theft. 4. To assist in a certain number of ti' transactions after the theft. And this, even more so since floppy disk 3 can be protected against copying, duplication and decompilation for example by the COPY CONTROL.COPYRGT. process, world leader in its category. The possibility thus becomes very slight but it exists. Thus explaining the possibility to resort to a second embodiment that uses a shift function D' much more complex than D. If it is considered that the shift code CD comprises a series of s signs which have values defined by a shift function D', the shift function successively consists in: applying a shift on all the lines of the server matrix, column by column, in order to obtain an intermediate shifted matrix; and applying this shift on all the columns of intermediate shifted matrix, line after line, in order to obtain the final shifted matrix; the shift consisting in applying the respective value of the first symbol of the shift code respectively to the first to last (s) line or column of the matrix and to reiterate this application for the following n-s lines or m-s columns up to respectively n or m. Let us take for example a shift code made up of five signs, namely f, r, 1, 2, C, the pre-determined coded function being the known ASCII conversion. In this case, the value corresponding to f is 102, the value corresponding to r is 114, the value corresponding to 1 is 49, the value corresponding to 2 is 50 and the value corresponding to r is 67. Consequently, first of all, the shift function D' consists in applying on the first column C1 of the server matrix a shift of +102; on the second column C2 of the matrix, a shift of +114; on the third column C3 of the matrix, a shift of +49; on the fourth column C4 of the matrix, a shift of +50; on the fifth column C5 of the matrix, a shift of +67; and to reiterate this operation for the C6 until C10, C11 until C15, until the last column Cm of the matrix. If the function D' is represented in the form of a diagram, the following result is obtained:
__________________________________________________________________________
Shift code f r 1 2 C f r 1 2 C f . .
.
ASCII value
102
114
49 50 67 102
114
49 50 67 102 . . .
Applied shift
+102
+114
+49
+50
+67
+102
+114
+49
+50
+67
+102
. . .
N.sup.o of the related column
1 2 3 4 5 6 7 8 9 10 11 . .
. .
All the coordinates of
the lines of this column
__________________________________________________________________________
Second of all, this same type of shift is applied on the intermediate shifted matrix but this time, on all the column co-ordinates, line by line, in order to obtain the definite shifted matrix. The following diagram gives the result which was obtained:
__________________________________________________________________________
N.sup.o of the line of N
N.sup.o of the line of N
On line shift
Applied
N.sup.o of the line of the
initial matrix for
initial matrix for
code shift
resulting matrix
the column 1
the column 2
. . .
__________________________________________________________________________
f +102
1 154 142
r +114
2 155 143
1 +49
3 156 144
2 +50
4 157 145
C +67
5 158 146
f +102
6 159 147
. . . . . .
. . . . . . . . .
__________________________________________________________________________
The value X=154 is found according to the equation X+114=255+1. The value X=142 is found according to the equation X+114=255+1, etc. . . . Of course, the bigger the shift code, the more difficult the link between the server matrix MS/Ui and the user's matrix will be to establish. Consequently, the bigger the shift code, the more likely the possibility of discovering this shift code starting from the user's matrix and a certain number of transaction results is close to zero. To conclude, the necessary conditions for a pirate to be connected on the server by usurping the identity of an authorized user are so disproportionate that the risk is close to zero. Thus, there is an authentication of the authorized users by authentication thanks to an individual physical device: without additional equipment for the terminal, with a physical support whose unitary cost is much lower than any other equivalent system. The bigger the shift code, the safer it is. But also, the more difficult it is to memorize for the user. This implies either a constraint of use for the user (one more code to memorize), or the writing of this code, which makes it easy to discover by a third party. This is the actual problem of symmetrical and asymmetrical encoding keys which are much too long. In the previously described examples, the authorized user receives his floppy disk by postmail during its registration at the server, and then by another separate postmail, his associated shift code created by the server. A variant embodiment consists in requesting each authorized user to choose his own shift code. This code is transmitted by the user to the server by the second transmission means 13 such as for example by postmail or telephone or any other type of transmission. It is then applied to shift the user's matrix, which will be duplicated. This code can correspond for example to any text of from 7 to 20 signs. A correspondence table established once and for all, gives the numerical shift to apply according to each sign. Let us take for example the correspondence table:
__________________________________________________________________________
Sign 0 1
. . . 9
a b . . . z
A B . . . Z
e e a . . .
Shift (+)
1 2
. . . 10
11
12
. . . 36
37
38
. . . 62
63
64
65
. . . 73
__________________________________________________________________________
The following shift is obtained for example for the code "Fort Knox":
______________________________________
Sign F o r t K n o x
Shift (+)
42 35 28 30 73 47 24 25 34
______________________________________
The user's matrix is thus shifted compared to the server's matrix following the shift function D'.sub.Fort Knox and this user will be invited, at each transaction, to seize his own shift code ("Fort Knox") necessary to obtain the connection to the server. This variant of the shift code solves in practice the problem of too long keys impossible to memorize. The primary function of the process according to the invention is the authentication. Yet it is possible to use this process for electronic signature by applying the property of encoding starting from a matrix. In that case, two users Ui and Uj are linked to server 2 which performs the role of an intermediary. The message to encode is cut up sign by sign. Each sign to be encoded is the subject of a query on the server's matrix which gives all the couples of co-ordinates (line-column) corresponding to that sign, the equivalent in the previous examples of more than 1000 possible couples per sign with a matrix of 65025 cells. Then, a pseudo-random function F4 chooses "at random" a couple among those 1000 and so on for each sign of the plain text. The result obtained, is an encoded message represented by a series of signs which correspond to the couples of co-ordinates which were selected. Since there are 1000 possibilities for each sign, the same plain text will thus be encoded differently each time, which renders impossible the cryptanalysis by letter frequency. The user must enter his shift code prior to this process. If, for example, Paul (Ui) wants to sign a document sent to Valerie (Uj) and that Valerie wants to be certain that the document is really signed by Paul, and Paul must not be able to deny his signature, the steps will be as follows: Paul encodes his name with his matrix and his shift code: MU/Uj (shift code), "Paul")=4 couples of co-ordinates (line, column)=S/Ui=signature code. This signature code S/Ui (by MU/Ui) is sent to the server with the name of the addressee Uj. The server authenticates the transmitter Ui with the process according to the invention and then decodes the signature of ui with his server's matrix MU/Ui. It obtains "Paul": this is the second verification of the transmitter. The server then uses the server's matrix of the addressee Uj, MS/Uj, to encode "Paul" (without the shift code known only to Valerie): MS/Uj ("Paul")=4 couples of co-ordinates (line-column)=S'Ui. This signature code S'/Ui (by MS/Uj) is sent to the addressee Uj. The server authenticates Uj with a process according to the invention. Then Uj decodes the signature of Ui with the user's matrix MU/Uj and its shift code: he obtains "Paul". Valerie is thus certain of Paul's signature and Paul cannot deny his signature. This electronic signature necessitates from the transmitter and from the addressee the use of their own authentication device 3 and the seizure of their own shift code. However the server does not have knowledge of these shift codes during the transaction, which makes it a perfectly neutral intermediary. In accordance with another embodiment, for exploitation reasons and in particular to limit the storage space of the matrix on the server as on the physical device of the user (when it is not a floppy disk), it may be interesting to use smaller matrices with fewer cells. In that case, the security of the process is diminished compared to a direct attack by a reading in clear of the transactions on the network, by reconstitution of the matrix. In that case, the process according to the invention forecasts that after each validated link, the data groups are modified simultaneously, by modification means 15 and 16, according to a predetermined function known to the server and the terminal, and depending on the addresses used during the previous transaction. This principle consists in fact in regenerating, as they are used, the server matrix MS/Ui and the user's matrix MU/Ui at the level of their respective cells revealed during the transactions. Let us take an example of a diagram of regeneration peculiar to the two matrices of the user Ui called GR/Ui:
__________________________________________________________________________
Initial sign
0 1 2 3 4 6 6 7 8 9 a b c . . .
Y Z
Substitution sign
t 4 c M L d z q O f i o G 7 W
__________________________________________________________________________
The line of substitution signs is created by a random shuffle to change the previous order for the 62 signs from 0 to Z. A specific regeneration diagram (GR/Ui) is attributed to each couple of matrices (MS and MU) for each user. Each diagram corresponds to some extent to the "genetic code" for that couple of matrices. At each transaction, for example 5 couples of co-ordinates of the matrix and their 5 corresponding values are used. After having sent the user's code from the user's terminal towards the server, the 5 signs of the user's code used are replaced by the corresponding substitution values (according to the diagram) once the connection has been validated by the server. Thus, the logical reconstitution of the server matrix by direct reading on the network is impossible because each cell used is modified as and, when needed in accordance with a regeneration diagram kept secret and that never transits on the network. Consequently, a matrix with its associated regeneration diagram can have a size largely smaller than M(255,255)=65025 cells while keeping the same level of security. Another solution consists in that after each link or validated transaction: the addresses used or the content of the addresses used on the data-server group are written, by inscription means 17, as being unusable; the addresses or the content of the addresses used on the data-user group are modified at random by modification means 18 located in the terminal. This is the equivalent of regenerating, as they are used, the server matrix MS/Ui and the user's matrix MU/Ui to the level of their respective cells which are revealed during the transactions, but, this time, without using a regeneration diagram as in the previous case. On the server, all the used cells of the server matrix MS/Ui are made blank, so that they may not be used again during a subsequent transaction. On the floppy disk, a pseudo-random function F5 replaces the signs of the used cells on MU/Ui after each valid connection with other signs chosen at random. These signs cannot be subsequently called since the corresponding co-ordinates were rendered unusable on the server matrix MS/Ui. When the cracker tries to find the shift code again starting from his data base constituted by the "challenge-response" of the previous transactions and of the stolen floppy disk's user's matrix MU/Ui, his program is biased due to the absence of correspondence between the cells due to their random replacement. The connection to the server immediately after the theft of the floppy disk, without having assisted in clear in legitimate transactions, is thus impossible, because the shift code CD cannot be found again. In addition, it is not necessary to keep, in the server station, the shifted matrix and/or the shift code. This shift principle can also be forecasted, for example, at the level of the server station in order to reinforce the security of the server. To this effect, certain groups of server matrices present on the server station can be periodically shifted and thus become dependent before their reading of the seizure of a daily code effected by the administrator of the server. This precaution renders even more random the outside analysis of the figures and codes that transit through communication networks. Of course, this daily code could be definite and/or memorized on a device independent of the server. In the previous description, the example considered, to simplify the explanation, used matrices. However, the process according to the invention can be applied to any other type of data group containing specific signs at specific addresses. In that case, the challenge, such as it has been previously defined, is made up of the data-server group and the code server is made up of the content of the data-server group at these addresses. Similarly, the user's code is made up of the content of the data-user group at the addresses transmitted during the challenge. To improve the security of the transaction, even more the data-server group can comprise: a first data-server subsystem that serves to determine the starting address and the size of the second data-server subsystem, and a complementary code CC, a second data-server subsystem containing specific signs at specific addresses. In that case, before duplicating the overall data-server group, the first subsystem is shifted according to the previously mentioned shift code CD, and the second data-server subsystem is shifted according to another code C made up of the shift code CD completed by complementary code CC, the complementary code being memorized at least in part in the server. The data-server group thus shifted is then duplicated on the authentication device and the authentication device and the shift code are transmitted to the user separately. The user does not know the complementary code. After having established a link between the terminal and the server, three numbers are generated at random, namely: a first number representative of the size of the second data subsystem, a second number representative of the starting address of the second data-server subsystem, and a third number called "aggregate" representative of the complementary code CC. Nevertheless, the way in which the size and the address are interpreted as well as the complementary code in the first and second representative numbers, cannot be determined by an outside person. Then, during the transaction, when the user has entered his shift code, the user's code is read in the terminal according to the first, second and third representative numbers. To this effect, functions that are adapted to re-establish the relations between the first, second and third representative numbers and their content, are memorized either in the terminal or in the authentication device. Thus, the data that are transmitted through the network, if they are intercepted, can not be interpreted by "cracking". In accordance with an example, the embodiment described previously will comprise the following steps: the server determines at random the size of the second data subsystem which is going to be used for the transaction, and the address of this second subsystem, by searching in the first data subsystem, the addresses of the first subsystem are sought for which will subsequently permit the terminal to determine the size and the starting address of the second data subsystem, the server multiplies the size of the second data subsystem thus obtained by a random number, thus obtaining a very high value (multiple rotation), the server chooses aleatorily a temporary shift of the second data subsystem, the server creates a number (called aggregate) made up of the addition of the multiple rotation's value, the temporary shift and of the complementary shift, in a first server-to-user direction, the starting address of the second data subsystem, the addresses representative of the size of the second data subsystem used for the transaction, as well as the addresses representative of parts of the second data subsystem (challenge) and the aggregate, are transmitted. In the terminal: the user seizes his shift code CD; the terminal determines the size of the second data subsystem used and the starting address thanks to the first data subsystem; the terminal divides the aggregate by the size of the second data subsystem, obtaining a shift complement. This complement is composed of the temporary shift and of the complementary code; the final shift is calculated by adding the complementary code and the shift code; the transmitted displacements are applied; once the sought after value has been found (user's code), a value transformation rule can be applied taking into account the application of the shift code; the user's code or response to the challenge is transmitted in a second user-to-server direction, that is to say the values found at the spot of the transmitted displacements. In the server: the shift is calculated by adding the complementary code CC and the temporary shift in order to give the final shift; the displacements transmitted to obtain the code server are applied; the result is compared with the user's code sent; and the authentication is confirmed or infirmed and the response is sent to the user.
|
Same subclass Same class Consider this |
||||||||||