Method and system for proactive password validation

• US 5,394,471 A
• Filed: 09/17/1993
• Issued: 02/28/1995
• Est. Priority Date: 09/17/1993
• Status: Expired due to Term

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Bell Atlantic Network Services, Inc. (Verizon Communications Inc.)
• Inventors: Ganesan, Ravi, Davies, Christopher I.
• Primary Examiner(s): Gregory, Bernarr E.
• Application Number:
  US08/121,852
• Time in Patent Office: 529 Days
• Field of Search: 380/1, 380/2, 380/4, 380/23-25, 380/49, 380/50
• US Class Current: 713/183
• CPC Class Codes: G06F 21/46 by designing passwords or checking the strength of passwords

Abstract

An improved method for password validation comprising the steps of identifying bad passwords having one or more characters; computing a frequency of occurrence of bad password characters; computing a probability of occurrence T of the bad password characters within the bad passwords based upon the computed frequency of occurrence; identifying a proposed password having one or more characters; and comparing the proposed password characters with the probability of occurrence T of the bad password characters. The method further comprises the steps of establishing a validation threshold and validating the proposed password based upon the correspondence between (i) a value, BAp, reflecting the relationship between the probability of occurrence T of bad password characters within bad passwords and the proposed password characters and (ii) an established validation threshold. A Markov model is use to compute the probability of occurrence. The present invention also includes an improved password validation system.

Claims

1. An improved method for password validation comprising the steps of:

(a) identifying bad passwords, wherein each said bad password is comprised of one or more characters;

(b) computing a frequency of occurrence of said bad password characters;

(c) computing a probability of occurrence T, within said bad passwords, of the bad password characters using the computed frequency of occurrence;

(d) identifying a validation password, wherein said validation password is comprised of one or more characters; and

(e) comparing said validation password characters with the probability of occurrence T of the bad password characters.

2. An improved method for password validation according to claim 1, further comprising the steps of (i) computing a first set of log likelihood functions 11f₁ for the bad password characters using the computed probability of occurrence T;

(ii) computing a mean μ and

standard deviation σ

for said first set of log likelihood functions 11f₁ ; and

(iii) computing a second set of log likelihood functions 11f₂ for the validation password characters using the computed probability of occurrence T;

wherein in the comparing step the probability of occurrence T of the bad password characters is represented by the mean μ and

the standard deviation σ and

the validation password characters are represented by said second set of log likelihood functions 11f₂.

3. An improved method for password validation according to claim 2, wherein said step of comparing is comprised of the steps of (i) computing BAp using the equation ##EQU6## where l-x is a numeric value related to the number of validation password characters;

(ii) establishing a validation threshold value; and

(iii) accepting or rejecting said validation password based upon the correspondence between BAp and the validation threshold value.

4. An improved method for password validation according to claim 3, wherein the validation threshold value is -2.6.

5. An improved method for password validation according to claim 3 further comprising the step of electronically storing the means μ

, the standard deviation σ

, the probability of occurrence T and the threshold valve.

6. An improved method for password validation according to claim 3, wherein the steps of computing the set of log likelihood functions 11f₂ and BAp and accepting or rejecting the validation password are performed in real time.

7. An improved method for password validation according to claim 1, wherein the step of computing the probability of occurrence T is performed using a Markov model comprised of a common alphabet plus selected other characters.

8. An improved method for password validation according to claim 7, wherein said Markov model is a second order model.

9. An improved method for password validation according to claim 7, wherein said common alphabet plus selected other characters is comprised of twenty-eight characters.

10. An improved method for password validation according to claim 1, wherein said bad password characters and said validation password characters are formed into trigrams.

11. An improved method for password validation according to claim 10, wherein said sets of log likelihood functions are computed using the equation ##EQU7## where 1-2 is a numeric value corresponding to the number of trigrams formed by the validation password characters and P_i, P_i+1 and P_i+2 represent the validation password characters forming a trigram.

12. An improved method for password validation according to claim 11, further comprising the step of adjusting the frequency of occurrence of certain of the bad password characters.

13. An improved method for password validation according to claim 12, wherein the step of adjusting the frequency of occurrence includes setting to zero each frequency of occurrence having a value equal to 1.

14. An improved method for password validation according to claim 13, wherein the step of adjusting the frequency of occurrence further includes the adjustment of each frequency of occurrence having a value of less than or equal to five.

15. An improved method for password validation according to claim 14, wherein the step of adjusting each frequency of occurrence with a value of less than or equal to five is performed using the equation ##EQU8## where f[i,j,k] is the frequency of occurrence of a trigram of the bad password characters and R is an array representing how often a particular one of the bad password characters occurs.

16. An improved password validation system comprising:

(a) means for accessing a data base of bad passwords, wherein each said bad password is comprised of one or more characters;

(b) means for computing a frequency of occurrence of said bad password characters;

(c) means for computing a probability of occurrence T, within said bad passwords, of the bad password characters using the computed frequency of occurrence;

(d) means for inputting a validation password to the system, wherein said validation password is comprised of one or more characters; and

(e) comparitor means for comparing said validation password characters with the probability of occurrence T of the bad password characters.

17. An improved password validation system according to claim 16, further comprising (i) means for computing a first set of log likelihood functions 11f₁ for the bad password characters using the computed probability of occurrence T;

(ii) means for computing a mean μ and

standard deviation σ

for said first set of log likelihood functions 11f₁ ; and

(iii) means for computing a second set of log likelihood functions 11f₂ for the validation password characters using the computed probability of occurrence T;

wherein the comparitor means utilizes the mean μ and

the standard deviation σ

to represent the probability of occurrence T of the bad password characters, and the second set of log likelihood functions 11f₂ to represent the validation password characters.

18. An improved password validation system according to claim 17, wherein said comparitor means is comprised of (i) means for computing BAp which implements the equation ##EQU9## where l-x is a numeric value related to the number of validation password characters;

(ii) means for accessing a validation threshold value; and

(iii) means for accepting or rejecting said validation password based upon the correspondence between BAp and the validation threshold value.

19. An improved password validation system according to claim 18, wherein the validation threshold value is -2.6.

20. An improved password validation system according to claim 18, wherein, the validation password characters are in the form of trigrams and said means for computing sets of log likelihood functions implements the equation ##EQU10## where 1-2 is a numeric value corresponding to the number of trigrams formed by the validation password characters and P_i, P_i+1 and P_i+2 represent the validation password characters forming a trigram.

21. An improved password validation system according to claim 20, further comprising means for adjusting the frequency of occurrence of certain of the bad password characters.

22. An improved password validation system according to claim 21, wherein the means for adjusting the frequency of occurrence sets to zero each frequency of occurrence having a value equal to 1.

23. An improved password validation system according to claim 22, wherein the means for adjusting the frequency of occurrence further adjusts each frequency of occurrence having a value of less than or equal to five.

24. An improved password validation according to claim 23, wherein the means for adjusting each frequency of occurrence with a value of less than or equal to five implements the equation ##EQU11## where f[i,j,k] is the frequency of occurrence of a trigram of the bad password characters and R is an array representing how often a particular one of the bad password characters occurs.

25. An improved password validation system according to claim 18, wherein the means for computing the set of log likelihood functions 11f₂ and BAp and the means for accepting or rejecting the validation password perform on-line and in real time.

26. An improved password validation system according to claim 25, further comprising means for electronically storing the mean μ

, the standard deviation σ

, the probability of occurrence T and the validation threshold valve.

27. An improved password validation system according to claim 26, wherein said electronic storage means resides in a central server.

28. An improved password validation system according to claim 27, wherein said server is part of a local or wide area network.

29. An improved password validation system according to claim 18, wherein said means for computing the set of log likelihood functions 11f₂ and BAp and said means for accepting or rejecting the validation password are part of a central security processor.

30. An improved password validation system according to claim 16, wherein the means for computing the probability of occurrence T utilizes a Markov model comprised of a common alphabet plus selected other characters.

31. An improved password validation system according to claim 30, wherein said Markov model is a second order model.

32. An improved password validation system according to claim 30, wherein said common alphabet plus selected other characters is comprised of twenty-eight characters.