System and method for user authentication having clock synchronization

• US 5,887,065 A
• Filed: 10/02/1997
• Issued: 03/23/1999
• Est. Priority Date: 03/22/1996
• Status: Expired due to Term

• Current Assignee: Assa Abloy AB
• Original Assignee: ActivCard Co.
• Inventors: Audebert, Yves
• Primary Examiner(s): Buczinski, Stephen C.
• Application Number:
  US08/944,071
• Time in Patent Office: 537 Days
• Field of Search: 380/23, 380/25, 380/48, 380/49, 235/382
• US Class Current: 713/172
• CPC Class Codes: G06Q 20/341 Active cards, i.e. cards including their own processing means, e.g. including an IC or chip
• CPC Class Codes: G06Q 20/3674 involving authentication
• CPC Class Codes: G06Q 20/4097 using mutual authentication between devices and transaction partners
• CPC Class Codes: G07C 9/21 having a variable access code
• CPC Class Codes: G07C 9/215 the system having a variable access-code, e.g. varied as a function of time
• CPC Class Codes: G07F 7/1008 Active credit-cards provided with means to personalise their use, e.g. with PIN-introduction/comparison system
• CPC Class Codes: H04L 9/3228 One-time or temporary data, i.e. information which is sent for every authentication or authorization, e.g. one-time-password, one-time-token or one-time-key
• CPC Class Codes: H04L 9/3234 involving additional secure or trusted devices, e.g. TPM, smartcard, USB or software token network architectures or network communication protocols for supporting authentication of entities using an additional device in a packet data network H04L63/0853

Abstract

The system includes a first unit adapted to communicate with a second unit. The second unit grants conditional access to a function or service in accordance with an authentication operation. Both units are capable of running software for generating passwords by means of encryption of several dynamic variables as for example a time dependent variable and/or a variable representing the number of formulated authentication requests. The encryption may be performed using a dynamic key. In order to synchronize the values of the variables generated in concert but independently in the units, only some of the least significant digits of the variables are transferred from the card-like unit to the other unit, with the transfer being performed by adding the digits to the password. This synchronization information is combined with corresponding variables in the second unit and used to calculate therein a value which has to match with the password calculated in the second unit in order to gain access to the function or service. In a "virtual token" implementation, the first unit can be a smart card, which stores the dynamic key and the variable representing the number of formulated authentication requests and executes an encryption algorithm, a smart card reader and a personal computer. Either the smart card reader or the personal computer can generate the time dependent variable. In a "software token" implementation, the functions of the first unit are performed by a computer such as a personal computer, thus eliminating the need for a smart card or a smart card reader.

Claims

1. A system for authentication of individuals and/or messages, including at least one first unit personalized for an individual and at least one second verification unit capable of delivering an authentication function authenticating said individual and/or said messages,

(a) said first unit comprising:

first generating means for generating at least a first variable;

first calculating means for producing a first password as a function of at least said first variable;

transmission means for transmitting said first password to said second unit;

(b) said second unit comprising;

second generating means for, in response to an authentication request made by way of a specified one of said first units, generating at least a second variable assigned to this first unit;

second calculating means for producing a second password as a function of at least said second variable, said first and second variables being produced in concert, but independently in said first and second units;

means for comparing said first and second passwords;

delivering means for, in the event of a predetermined consistency of said passwords, delivering said authentication function;

said transmission means being configured so as to transmit with said first password n digits having the least significant weight of said first variable from said first unit to said second unit;

(c) said second unit further comprising;

j) substituting means for, based on the current value of said second variable, generating a substituted value wherein n digits having the least significant weight are replaced by said n digits having the least significant weight of said first variable, said second variable thereby comprising a replaced first group of n least significant digits and a second group of m highest significant digits;

jj) third calculating means for

k) retaining as second variable for the calculation of said second password said substituted variable, if said substituted variable and said current value of said second variable are consistent with at least a first predetermined condition,

kk) if said first predetermined condition is not satisfied, adjusting in said substituted value by one unit said second group of m highest significant digits, said adjusting being dependent from a second predetermined condition, said adjusting generating a substituted and adjusted variable, and

kkk) retaining as second variable for the calculation of said second password said substituted and adjusted variable.

2. The system as claimed in claim 1 wherein said third calculating means further comprises:

means for implementing said first predetermined condition configured so as to determine if said substituted variable is higher than or equal to said current value of said second variable; and

means for implementing said second predetermined condition configured so as to increment by one unit said second group of m highest significant digits, if said substituted variable is strictly lower than said current value of said second variable, thereby generating a substituted and incremented value, and for retaining said substituted and incremented value as second variable.

3. The system as claimed in claim 1, wherein said third calculation means further comprises:

i) means for implementing said first predetermined condition configured so as to;

j) calculate a first difference between said current value of said second variable and said substituted variable,

jj) determine if said first difference is within a range the extent of which is at the most equal to the number of units having the highest weight p_n in said first group of n digits, as represented by the digit having the lowest weight p_n+1 in said group of m highest significant digits,

jjj) retaining as second variable said substituted variable if said difference is within said range, and

ii) means for implementing said second predetermined condition configured so as to;

k) adjust by one unit in a first direction said lowest weight p_n+1, if said difference is outside said range thereby generating a first substituted and adjusted variable,

kk) calculate a second difference between said current value of said second variable and said first substituted and adjusted variable,

kkk) determine if said second difference is within said range,

kkkk) retain as a second variable said first substituted and adjusted variable if said second difference is within said range,

kkkkk) adjust by one unit in a second direction opposed to said first direction said lowest digit p_n+1 if said second difference is outside said range thereby generating a second substituted and adjusted variable, and

kkkkkk) retaining as a second variable said second substituted and adjusted variable.

4. The system as claimed in claim 1, wherein said third calculating means further comprises:

i) means for defining a range of values the extent of which is at the most equal to a number of units having the highest weight p_n in said first group of n digits, as represented by the digit having the lowest weight p_n+1 in said group of m highest digits;

ii) means for generating first and second checking values, said checking values being respectively equal to the algebraic sum of said current value of said second variable and the lowest limit value of said range and said current value of said second variable and the highest limit of said range;

iii) means for implementing said first predetermined condition configured so as to;

j) determine if said substituted variable is between said first and second checking values;

jj) retain as a second variable said substituted variable if said substituted variable is between said first and second checking values;

said third calculating means further comprising;

iiii) means for implementing said second predetermined condition configured so as to;

k) adjust by one unit in a first direction said lowest weight pn+1, if said substituted value is outside said first and second checking values thereby generating a first substituted and adjusted variable,

kk) determine if said first substituted and adjusted variable is between said first and second checking values;

kkk) retain as a second variable said first substituted and adjusted variable if said first substituted and adjusted variable is between said first and second checking values;

kkkk) adjust by one unit in a second direction opposed to said first direction said lowest digit p_n+1 if said first substituted and adjusted variable is outside said first and second checking values thereby generating a second substituted and adjusted variable, and

kkkkk) retain as a second variable said second substituted and adjusted variable.

5. The system as claimed in claim 2, wherein said third calculating means further comprises means for subtracting said current value of said second variable from said substituted variable or, as the case may be, from said substituted and adjusted variable, thereby generating a difference value,

said second calculating means further comprising means for iteratively calculating said second password as many times as the value of said difference.

6. The system as claimed in claim 2 wherein said first generating means are configured so as to generate said first variable as a function of the number of authentication requests made by said at least one first unit, and wherein said second generating means are so configured as to generate said second variable as a function of the number of authentication request received by said second unit from said at least one unit.

7. The system as claimed in claim 1, wherein said first and second generating means are configured so as to generate respectively said first and second variables as first and second time dependent variables.

8. The system as claimed in claim 7, wherein each of said first and second generating means further comprises:

a base clock for supplying a basic clock signal composed of successive pulses having a predetermined frequency,

counter means for counting said pulses,

digit canceling means for canceling a predetermined number of the least significant digits from the contents of said counting means, thereby generating respectively in said at least one unit a first intermediate time value and in said second unit a second intermediate time value, whereby said first and second time dependent variables are generated respectively as functions of said first and second intermediate time values.

9. The system as claimed in claim 8, wherein each of said first and second generating means further comprises adjusting means for regulating said predetermined number of least significant digits to be canceled from the contents of said counting means.

10. The system as claimed in claim 8, wherein said first and second generating means each further comprises:

means for adding a predetermined number of digits of zero value to said intermediate time values at the side of the highest weight thereof.

11. The system as claimed in claim 3, wherein said second unit further comprises:

storing means for storing the date of initialization of each of said first units,

means for, at the time an authentication request is formulated with said at least one first unit, comparing the time period elapsed between the date relevant for said at least one first unit and stored in said storing means and at least a predetermined time interval, and

means for increasing said range when said elapsed time interval exceeds said predetermined time interval.

12. The system as claimed in claim 4, wherein said second unit further comprises:

storing means for storing the date of initialization of each of said first units,

means for, at the time an authentication request is formulated on said at least one first unit, comparing the time period elapsed between the date relevant for said at least one first unit and stored in said storing means and at least a predetermined time interval, and

means for increasing said range of values when said elapsed time interval exceeds said predetermined time interval.

13. The system as claimed in claim 1, wherein said third calculating means further comprises:

means for, upon completion of each authentication request formulated with said at least one first unit, algebraically summing said current value of said second variable and said substituted variable or, as the case may be, said substituted and adjusted variable so as to generate an offset value,

means for storing said offset value as a current offset value pertaining to said at least one first unit, said second calculating means being so arranged as to, during at least a subsequent authentication request formulated with said at least one first unit calculate said substituted variable, or, as the case may be, said substituted and adjusted value, as a function of said current offset value.

14. The system as claimed in claim 13 wherein said third calculating means are so arranged as to adapt said first and second predetermined conditions as a function of said current offset value.

15. The system as claimed in claim 13, wherein said first and second generating means are configured so as to generate respectively said first and second variables as first and second time dependent variables,

said first and second generating means each further comprises:

a base clock for supplying a basic clock signal composed of successive pulses having a predetermined frequency,

counter means for counting said pulses, said first and second time dependent variables being generated respectively as functions of the contents of said counter means,

said storing means being so arranged as to store, for each of said second units a compensating value for compensating the contents of said counter means of said second unit against drift of the base clocks of said first and second units, respectively, and

said third calculating means further comprising means for generating said compensating value as a function of said time offset value.

16. The system as claimed in claim 15 wherein said third calculating means further comprises:

first determining means for determining the time interval between a current authentication request formulated by said at least one first unit and a subsequent authentication request formulated by said unit,

second determining means for determining the difference between said time offset value calculated upon completion of said current request and said time offset value calculated upon completion of said subsequent request,

means for refusing said subsequent authentication request when said difference between said time offset values exceeds a predetermined level as compared with said time interval as determined by said first determining means.

20. The system as claimed in claim 1, wherein said first encryption algorithm and said second encryption algorithm have a predetermined relationship with one another so as to produce said passwords having said predetermined consistency with one another.

22. The system as claimed in claim 1, wherein the first unit is a portable device comprising a source of electrical energy.

23. The system as claimed in claim 1, wherein the first unit is a portable device comprising a card.

24. The system as claimed in claim 1, wherein said first unit comprises:

a card reader; and

a card adapted for being read by said card reader.

25. The system as claimed in claim 24, wherein:

the first and second generating means generate the first and second variables, respectively, as first and second time-dependent variables;

the card comprises at least a first portion of the first calculating means, the first portion for producing the first password;

the first unit further comprises a processor in communication with the card, the processor comprising the first generating means for producing the first time-dependent variable; and

the first time-dependent variable is communicated to the at least first portion of the first calculating means in the card.

26. The system as claimed in claim 25, wherein the processor is disposed in the card reader.

27. The system as claimed in claim 25, wherein the first unit further comprises a computer and the processor is disposed in the computer.

28. The system as claimed in claim 25, wherein the first unit further comprises one of a personal digital assistant and a telephone device and the processor is disposed in said one of a personal digital assistant and said telephone device.

29. The system as claimed in claim 1, wherein the first unit is a computer programmed to function as the first generating means and the first calculating means.

17. A system for authentication of individuals and/or messages, including at least one first unit personalized for an individual and at least one second verification unit capable of delivering an authentication function authentifying said individual and/or said messages,

(a) said first unit comprising:

first generating means for generating at least first and second variables,

first calculating means for producing a first password as a function of at least said first and second variables;

transmission means for transmitting said first password to said second unit;

(b) said second unit comprises;

second generating means for, in response to an authentication request made by way of a specified one of said first units, generating at least third and fourth variables assigned to this first unit;

second calculating means for producing a second password as a function of at least said third and fourth variables, said first and second variables and said third and fourth variables being respectively produced in concert, but independently in said first and second units;

means for comparing said first and second passwords;

delivering means for, in the event of a predetermined consistency of said passwords, deliver said authentication function;

said transmission means being configured so as to transmit with said first password n digits having the least significant weight of said first and second variables from said first unit to said second unit;

(c) said second unit further comprising;

j) substituting means for, based on the current value of said third and fourth variables respectively, generate first and second substituted values each wherein n digits having the least significant weight are replaced respectively by said n digits having the least significant weight of said first and second variables, said third and fourth variables thereby each comprising a replaced first group of n least significant digits and a second group of m highest significant digits;

jj) third calculating means for;

k) retaining respectively as third variable for the calculation of said second password said first substituted variable, if said first substituted variable and said current value of said third variable are consistent with at least a first predetermined condition,

kk) if said first predetermined condition is not satisfied, adjusting in said first substituted value by one unit said second group of m highest significant digits, said adjusting being dependent from a second predetermined condition, said adjusting generating a first substituted and adjusted variable, and

kkk) retaining as third variable for the calculation of said second password said first substituted and adjusted variable.

jjj) said third calculating means being also arranged so as to;

l) retain as fourth variable for the calculation of said second password said second substituted variable, if said second substituted variable and said current value of said fourth variable are consistent with at least a third predetermined condition,

ll) if said third predetermined condition is not satisfied, adjust in said second substituted value by one unit said second group of m highest significant digits, said adjusting being dependent from a fourth predetermined condition, said adjusting generating a second substituted and adjusted variable, and

lll) retain as fourth variable for the calculation of said second password said second substituted and adjusted variable.

18. The system as claimed in claim 17, wherein:

said first generating means are configured so as to generate said first variable as a function of the number of authentication requests made by said at least one first unit,

said second generating means are so configured as to generate said third variable as a function of the number of authentication request received by said second unit from said at least one first unit, and

said first and second generating means are configured so as to generate respectively said second and fourth variables as second and fourth time dependent variables.

19. The system as claimed in claim 18, wherein said first and second calculating means are so arranged as to calculate said encryption keys used in said at least one first unit and said second unit as dynamic variable encryption keys respectively as functions of said first and third variables.

21. The system as claimed in claim 17, wherein said first encryption algorithm and said second encryption algorithm have a predetermined relationship with one another so as to produce said passwords having said predetermined consistency with one another.

30. A method for authentication of at least one user or a message from said at least one user, said method comprising:

(a) generating at least a first variable;

(b) producing a first password as a function of at least said first variable;

(c) in response to an authentication request made by a specified one of said at least one user, generating at least a second variable assigned to this at least one user;

(d) producing a second password as a function of at least said second variable, said first and second variables being produced in concert, but independently in steps (a) and (c);

(e) comparing said first and second passwords;

(f) in the event of a predetermined consistency of said passwords, delivering said authentication function;

said first password being transmitted with n digits having the least significant weight of said first variable;

step (c) comprising;

(i) based on the current value of said second variable, generating a substituted value wherein n digits having the least significant weight are replaced by said n digits having the least significant weight of said first variable, said second variable thereby comprising a replaced first group of n least significant digits and a second group of m highest significant digits;

(ii) retaining as second variable for the calculation of said second password said substituted variable, if said substituted variable and said current value of said second variable are consistent with at least a first predetermined condition;

(iii) if said first predetermined condition is not satisfied, adjusting in said substituted value by one unit said second group of m highest significant digits, said adjusting being dependent from a second predetermined condition, said adjusting generating a substituted and adjusted variable; and

(iv) retaining as second variable for the calculation of said second password said substituted and adjusted variable.

31. The method as claimed in claim 30 wherein:

said first predetermined condition comprises determining if said substituted variable is higher than or equal to said current value of said second variable; and

second predetermined condition comprises incrementing by one unit said second group of m highest significant digits, if said substituted variable is strictly lower than said current value of said second variable, thereby generating a substituted and incremented value, and retaining said substituted and incremented value as second variable.

32. The system as claimed in claim 30, wherein:

said first predetermined condition comprising;

(i) calculating a first difference between said current value of said second variable and said substituted variable,

(ii) determining if said first difference is within a range the extent of which is at the most equal to the number of units having the highest weight p_n in said first group of n digits, as represented by the digit having the lowest weight p_n+1 in said group of m highest significant digits; and

(iii) retaining as second variable said substituted variable if said difference is within said range, and

said second predetermined condition comprises;

(i) adjusting by one unit in a first direction said lowest weight p_n+1, if said difference is outside said range thereby generating a first substituted and adjusted variable,

(ii) calculating a second difference between said current value of said second variable and said first substituted and adjusted variable,

(iii) determining if said second difference is within said range,

(iv) retaining as a second variable said first substituted and adjusted variable if said second difference is within said range,

(v) adjusting by one unit in a second direction opposed to said first direction said lowest digit p_n+1 if said second difference is outside said range thereby generating a second substituted and adjusted variable, and

(vi) retaining as a second variable said second substituted and adjusted variable.

33. The method as claimed in claim 30, wherein:

a range of values is defined, the extent of which is at the most equal to a number of units having the highest weight p_n in said first group of n digits, as represented by the digit having the lowest weight p_n+1 in said group of m highest digits;

first and second checking values, said checking values are generated, being respectively equal to the algebraic sum of said current value of said second variable and the lowest limit value of said range and said current value of said second variable and the highest limit of said range;

said first predetermined condition comprises;

(i) determining if said substituted variable is between said first and second checking values;

(ii) retaining as a second variable said substituted variable if said substituted variable is between said first and second checking values;

said second predetermined condition comprises;

(i) adjusting by one unit in a first direction said lowest weight p_n+1, if said substituted value is outside said first and second checking values thereby generating a first substituted and adjusted variable,

(ii) determining if said first substituted and adjusted variable is between said first and second checking values;

(iii) retaining as a second variable said first substituted and adjusted variable if said first substituted and adjusted variable is between said first and second checking values;

(iv) adjusting by one unit in a second direction opposed to said first direction said lowest digit p_n+1, if said first substituted and adjusted variable is outside said first and second checking values thereby generating a second substituted and adjusted variable, and

(v) retaining as a second variable said second substituted and adjusted variable.

34. The method as claimed in claim 31, wherein:

step (c) further comprises subtracting said current value of said second variable from said substituted variable or, as the case may be, from said substituted and adjusted variable, thereby generating a difference value; and

step (d) comprises iteratively calculating said second password as many times as the value of said difference.

35. The method as claimed in claim 31 wherein step (a) comprises generating said first variable as a function of the number of authentication requests made by said at least one first unit, and wherein step (c) comprises generating said second variable as a function of the number of authentication request received by said second unit from said at least one unit.

36. The method as claimed in claim 30, wherein steps (a) and (c) comprise generating respectively said first and second variables as first and second time dependent variables.

37. The method as claimed in claim 36, wherein each of steps (a) and (c) further comprises:

supplying a basic clock signal composed of successive pulses having a predetermined frequency,

counter means for counting said pulses to obtain a count, and

canceling a predetermined number of the least significant digits from the count, thereby generating respectively a first intermediate time value and a second intermediate time value, whereby said first and second time dependent variables are generated respectively as functions of said first and second intermediate time values.

38. The method as claimed in claim 37, wherein each of steps (a) and (c) further comprises regulating said predetermined number of least significant digits to be canceled from the count.

39. The method as claimed in claim 37, wherein each of steps (a) and (c) further comprises:

adding a predetermined number of digits of zero value to said intermediate time values at the side of the highest weight thereof.

40. The method as claimed in claim 32, further comprising:

storing the date of initialization of each of said at least one user;

at the time an authentication request is formulated from said at least one user, comparing the time period elapsed between the date relevant for said at least one user and at least a predetermined time interval; and

increasing said range when said elapsed time interval exceeds said predetermined time interval.

41. The method as claimed in claim 33, further comprising:

storing the date of initialization of each of said at least one user;

at the time an authentication request is formulated by said at least one user, comparing the time period elapsed between the date relevant for said at least one user and at least a predetermined time interval; and

increasing said range of values when said elapsed time interval exceeds said predetermined time interval.

42. The method as claimed in claim 30, further comprising:

upon completion of each authentication request formulated by said at least one user, algebraically summing said current value of said second variable and said substituted variable or, as the case may be, said substituted and adjusted variable so as to generate an offset value;

storing said offset value as a current offset value pertaining to said at least user; and

said during at least a subsequent authentication request formulated by said at least one user calculating said substituted variable, or, as the case may be, said substituted and adjusted value, as a function of said current offset value.

43. The method as claimed in claim 42, wherein said first and second predetermined conditions are adapted as a function of said current offset value.

44. The method as claimed in claim 42, wherein said first and second variables are generated as first and second time dependent variables,

each of steps (a) and (c) further comprises:

supplying a basic clock signal composed of successive pulses having a predetermined frequency;

counting said pulses to obtain a count, said first and second time dependent variables being generated respectively as functions of count;

storing a compensating value for compensating the count in step (c) drift of the basic clock signals of steps (a) and (c) respectively; and

generating said compensating value as a function of said time offset value.

45. The method as claimed in claim 44, further comprising:

determining the time interval between a current authentication request formulated by said at least one user and a subsequent authentication request formulated by said user,

determining the difference between said time offset value calculated upon completion of said current request and said time offset value calculated upon completion of said subsequent request; and

refusing said subsequent authentication request when said difference between said time offset values exceeds a predetermined level as compared with said time interval.

49. The method as claimed in claim 30, wherein said first encryption algorithm and said second encryption algorithm have a predetermined relationship with one another so as to produce said passwords having said predetermined consistency with one another.

46. A method for authentication of a least one user or a message from said at least one user, said method comprising:

(a) generating at least first and second variables;

(b) producing a first password as a function of at least said first and second variables;

(c) in response to an authentication request made by a specified one of said at least one user, generating at least third and fourth variables assigned to this at least one user;

(d) producing a second password as a function of at least said third and fourth variables, said first and second variables and said third and fourth variables being respectively produced in concert, but independently in steps (a) and (c);

(e) comparing said first and second passwords;

(f) in the event of a predetermined consistency of said passwords, delivering said authentication function;

said first password being transmitted with n digits having the least significant weight of said first and second variables;

step (c) comprising;

(i) based on the current value of said third and fourth variables respectively, generating first and second substituted values each wherein n digits having the least significant weight are replaced respectively by said n digits having the least significant weight of said first and second variables, said third and fourth variables thereby each comprising a replaced first group of n least significant digits and a second group of m highest significant digits;

(ii) retaining respectively as the third variable for the calculation of said second password said first substituted variable, if said first substituted variable and said current value of said third variable are consistent with at least a first predetermined condition;

(iii) if said first predetermined condition is not satisfied, adjusting in said first substituted value by one unit said second group of m highest significant digits, said adjusting being dependent from a second predetermined condition, said adjusting generating a first substituted and adjusted variable;

(iv) retaining as the third variable for the calculation of said second password said first substituted and adjusted variable;

(v) retaining as the fourth variable for the calculation of said second password said second substituted variable, if said second substituted variable and said current value of said fourth variable are consistent with at least a third predetermined condition;

(vi) if said third predetermined condition is not satisfied, adjusting in said second substituted value by one unit said second group of m highest significant digits, said adjusting being dependent from a fourth predetermined condition, said adjusting generating a second substituted and adjusted variable; and

(vii) retaining as the fourth variable for the calculation of said second password said second substituted and adjusted variable.

47. The method as claimed in claim 46, further comprising:

said first generating means are configured so as to generating said first variable as a function of the number of authentication requests made by said at least one user;

generating said third variable as a function of the number of authentication request received by said second unit from said at least one user; and

generating respectively said second and fourth variables as second and fourth time dependent variables.

48. The method as claimed in claim 47, wherein said encryption keys as dynamic variable encryption keys respectively as functions of said first and third variables.

50. The method as claimed in claim 46, wherein said first encryption algorithm and said second encryption algorithm have a predetermined relationship with one another so as to produce said passwords having said predetermined consistency with one another.