(12) United States Patent
`Buffam.
`
`USOO6185316B1
`(10) Patent No.:
`US 6,185,316 B1
`(45) Date of Patent:
`Feb. 6, 2001
`
`(54) SELF-AUTHENTICATION APPARATUS AND
`METHOD
`
`(75) Inventor: William J. Buffam, West Chester, PA
`(US)
`
`(73) Assignee: Unisys Corporation, Blue Bell, PA
`(US)
`
`(*) Notice:
`
`Under 35 U.S.C. 154(b), the term of this
`patent shall be extended for 0 days.
`
`4,807,287
`4,838,644
`4.905,296
`
`2/1989 Tucker et al. .......................... 380/23
`6/1989 Ochoa et al. ................... 350/162.13
`2/1990 Nishihara ............................... 382/42
`(List continued on next page.)
`OTHER PUBLICATIONS
`Thomas Cousins, “Investigating A New Identification Tech
`nology,” Dec., 1995, p. 1-2.
`Simon Haykin, “Neural Networks, A Comprehensive Foun
`dation,” 1994, p. 363-394.
`
`(21) Appl. No.: 08/969,210
`(22) Filed:
`Nov. 12, 1997
`(51) Int. Cl." ....................................................... G06K 9/00
`(52) U.S. Cl. .......................... 382/115; 382/125; 382/100;
`713/186
`(58) Field of Search ................................. 178/89; 283/17,
`283/73; 382/115, 124, 125, 100, 232; 380/54,
`282, 55; 713/186; 340/825.33; 705/50,
`71
`
`Primary Examiner Bhavesh Mehta
`sailorney Agent, or Firm-Rocco L. Adornato; Mark
`(57)
`ABSTRACT
`An apparatus, method, and computer program for providing
`authenticating indicia and Verifying the image thereby. One
`particular embodiment is a biometric application Such as a
`fingerprint-based authentication System. The apparatus
`includes an image receiver for receiving the original image
`with true image point, a false image point generator provid
`ing false image points, and a transient template generator
`References Cited
`that selectively combines the true image points and the false
`U.S. PATENT DOCUMENTS
`image points. The apparatus can also constrain false image
`points to be non-coinciding plausible impostors of the true
`9/1960 Avakian et al. ....................... 380/54
`image points. The apparatus can include a claimant image
`5/1976 Uno et al. ......
`340/146.3 H
`receiver, a transient template receiver and a comparator for
`9/1976 Lynch et al. ......................... 235/156
`comparing the claimant image points with the template
`10/1976 Lippel, Jr. et al.
`... 340/5 H
`image points and producing an authentication signal. The
`2/1981. Szwarchier .....
`... 340/146.3 E
`method can employ a hashing technique to produce an
`3/1981 Todd ..........
`340/146.3 AO
`3/1982 Sternberg ...
`340/146.3 MA
`11/1983 Sternberg ............................... so encoding key from the non-coincident plausible impostor
`5/1984 Felix et al. ...
`364/513.5
`false image points, and preselected encryption techniques to
`9/1986 King ....................................... 382/32
`produce ciphertext from plaintext with the encoding key.
`1/1987 Taylor .................................... 382/31
`The method can include extracting claimant image points
`2/1987 Crimmins et al. ..................... 382/48
`from template image points and iteratively constructing
`3/1987 Nakashima et al. ................... 382/34
`candidate decoding keys from the post-extraction residual
`4/1987 Bedros et al. ......................... 382/30
`points. Authentication is indicated if the decoding key
`5/1987 Sternberg............................... 382/27
`Successfully produces a matching plaintext from the cipher
`10/1987 Rice .......
`... 128/664
`teXt.
`6/1988 Maeda .................................... 381/42
`9/1988 Itoh et al. .............................. 382/25
`1/1989 Goldman .............................. 235/380
`
`18 Claims, 12 Drawing Sheets
`
`(56)
`
`2,952.080
`3,959.771
`3.981,443
`3,984.804
`4,253,086
`4,259,661
`4,322,716
`4,414,685
`4,449,189
`4,612,666
`4,637,055
`4,644,858
`4,651,341
`4,658,428
`4,665.554
`4,699,149
`4,752,957
`4,769,850
`4,795,890
`
`Ya,
`
`is RECWER
`
`125
`
`tRUAA
`PONTs
`
`TRANSFORED
`TRUEDATA
`PONTs
`
`5
`
`FALSE IMAGE
`POINT
`GENERATOR
`
`28
`
`105
`
`AER
`
`110
`
`TRANSFORMER
`
`l
`Y
`
`20
`
`MASTER
`TEMPATE
`STORAG
`
`
`
`35
`
`DAPON
`CONDITIONER
`
`160
`
`NCRYPTE
`
`TRANSENT
`
`155
`
`TEPLATE
`
`
`
`IMAGE POINT
`cos
`
`IA1007
`
`Page 1 of 27
`
`

`

`US 6,185.316 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`4,906,940
`3/1990 Greene et al. ......................... 382/16
`s: HAC: Eski t al.
`s:
`2-Y/ 2
`f
`urk et al. .....
`... 382/
`5,386,103
`1/1995 DeBan et al. ..
`... 235/379
`5,432,864
`7/1995 Lu et al. .....
`... 382/118
`5,457,747
`10/1995 Drexler et al.
`... 380/24
`5,469,512
`11/1995 Fujita et al. ...
`... 382/118
`5,505,494
`4/1996 Belluci et al. .
`... 283/75
`5,524,161
`6/1996 Omori et al. ........................ 382/125
`
`5,537,484
`5,550,928
`5,555,320
`5,566,246
`5,568,563
`5,568,568
`5,570.434
`5,574,573
`2- .
`.
`
`7/1996 Kobayashi ........................... 382/124
`8/1996 Lu et al. ..
`... 382/116
`9/1996 Irie et al. .
`382/225
`10/1996 Rao ...................................... 382/154
`10/1996 Tanaka et al. ....................... 382/144
`10/1996 Takizawa et al.
`382/220
`10/1996 Badique ...
`382/279
`11/1996 Ray et all
`358/452
`ay Clal. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`
`
`* cited by examiner
`
`IA1007
`
`Page 2 of 27
`
`

`

`U.S. Patent
`
`Feb. 6, 2001
`
`Sheet 1 of 12
`
`US 6,185,316 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`IA1007
`
`Page 3 of 27
`
`

`

`U.S. Patent
`
`Feb. 6, 2001
`
`Sheet 2 of 12
`
`US 6,185,316 B1
`
`Sa
`
`25
`
`SAVE IMAGE
`AS MASTER
`TEMPLATE
`
`30
`
`oil
`IMAGE
`
`GENERATE FALSE
`IMAGE POINTS
`
`CONVERT IMAGE
`TO TRUE IMAGE
`POINTS (TIPs)
`
`SELECT FALSE
`IMAGE POINTS
`(FIPs)
`
`35
`
`10
`
`15
`
`20
`
`40
`
`CREATE
`KEY
`
`42
`
`SELECT TRUE
`IMAGE POINTS
`
`45
`
`
`
`COMBINE FALSE
`IMAGE POINTS
`WITH TRUE
`MAGE POINTS
`
`50
`
`CREATE TRANSIENT
`TEMPLATE
`
`Figure 2
`
`IA1007
`
`Page 4 of 27
`
`

`

`U.S. Patent
`
`Feb. 6, 2001
`
`Sheet 3 of 12
`
`US 6,185,316 B1
`
`210
`
`205a
`
`QUADRANT
`
`
`
`--
`-
`
`2, 2.
`
`25N-- 200e
`
`QUA DRANTIV
`
`Figure 3A
`
`
`
`QUADRANT II
`
`QUADRANT
`
`-
`
`
`
`e
`
`
`
`Figure 3B
`
`2200
`235
`
`245
`
`QUADRANTIV
`
`IA1007
`
`Page 5 of 27
`
`

`

`US. Patent
`
`Feb. 6, 2001
`
`Sheet 4 0f 12
`
`US 6,185,316 B1
`
`mam
`
`com
`
`on.
`
`m4<_._.2mommo
`
`10.25.
`
`._.z<s=<._o
`
`mmo._.<m<n==oo
`
`
`5.0m...
`
`swim—oamgr..55..th
`
`._.zm=mz<m.r
`
`Eula—SE.
`
`
`
`mun—00mmEN
`
`NR
`
`._.zm_wz<m._.
`
`whims—E.
`
`mm>_m0mm
`
`EN
`
`momzmm8“
`
`mum:
`
`m._<_._.2mammu
`
`_________H|_h__
`
`Page 6 of 27
`
`oz
`
`mm>
`
`mozmmmnfim
`
`thaEMP
`
`mom
`
`v9:
`9...
`
`.—.z<s=<._o
`
`nmhomwmm
`
`hz<_2_<._o
`
`
`
`omb‘onm_._._.:<
`
`mom
`
`mmw<s=
`
`mom
`
`omm
`
`m.._.z<s=<._o
`
`mm2.035%
`
`mm“
`
`omm
`
`LAIOO7
`
`IA1007
`
`Page 6 of 27
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Feb. 6, 2001
`
`Sheet S of 12
`
`US 6,185,316 B1
`
`350
`
`380
`
`GENERATE
`FALSE IMAGE
`POINTS (FIPs)
`
`SELECT
`FIPS
`
`
`
`GENERATE
`KEY FROM
`FIPS
`
`GENERATE
`Wy
`
`
`
`
`
`
`
`
`
`PLAINTEXT
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`MASTER
`TEMPLATE
`DATABASE
`
`355
`
`360
`
`395
`
`400
`
`RECEIVE
`TRUE IMAGE
`POINTS (TIPs)
`
`SELECT
`TIPs
`
`TRANSFORM
`S
`
`INTERPOSE
`TIPS 8
`FIPSADD
`CPHER
`
`
`
`
`
`PROVIDE
`TRANSIENT
`TEMPLATE
`
`Figure 5
`
`IA1007
`
`Page 7 of 27
`
`

`

`U.S. Patent
`
`Feb. 6, 2001
`
`Sheet 6 of 12
`
`US 6,185,316 B1
`
`450
`
`465
`
`455
`
`RECEIVE
`CREDENTIALS
`
`
`
`RECEIVE
`CLAIMANT TRUE
`IMAGE POINTS (TIPs)
`
`EXTRACT
`TRANSIENT
`TEMPLATE
`
`
`
`460
`
`TRANSFORM
`RECEIVEDTIPs
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ANALYZEFIPs
`AND RESIDUAL
`DATAPOINTS
`
`
`
`IS
`CLAIMANT
`VALID
`
`AUTHENTICATE
`USERI
`GRANT ACCESS
`
`INVOKE
`PREDETERMINED
`RESPONSE
`
`Figure 6
`
`IA1007
`
`Page 8 of 27
`
`

`

`US. Patent
`
`Feb. 6, 2001
`
`Sheet 7 0f 12
`
`US 6,185,316 B1
`
`g
`
`E<3.26:n2sz
`
`._.z=.._n_m
`
`mOmzmm
`
`
`
`mOmzmw._<_h2mommoE
`
`moh<m<nzoo
`
`.Em:
`
`m._<:zm_nmmo
`
`
`
`<._.<o
`
`22.53am:
`
`Econ—wzgh
`
`mmprz
`
`whim—am:
`
`mm<m<._.<o
`
`
`
`mw<:n_._.zm=2._._omzm
`
`2.2296
`
`6".»m;g"gnu!mum:
`
`n/_\VEmsjomzu
`mmwo¢momw
`2225o;
`
`
`
`mm<_._n_zo_._.<o_n=mm_>
`
`cow
`
`Page 9 of 27
`
`LAIOO7
`
`IA1007
`
`Page 9 of 27
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Feb. 6, 2001
`
`Sheet 8 0f 12
`
`US 6,185,316 B1
`
`to.
`
`mmm\mom8..8m8m2m
`
`
`.F.,aE,
`
`
`
`Ehmmzn—Gwmm
`
`
`..<=zm.om=...o..5225:9...wmflhfim
`‘“Hm.
`
`.‘.3.smoumzfi:
`
`
`
`
`
`96.2322:86:32.3..flWm8m
`8mmmm
`
`”.22.onE.«.25.sz
`
`..>5.
`
`
`
`.3..
`
`
`
`
`
`mamoz<22.25sz>5...zm........om.zm
`
`C....cm...z.<..n.35.3@255mm<=mhzm—Ejomzm
`
`20.25
`
`on.m0.595
`
`N5motions
`
`hz<....<..ovi.‘K.m;4.580
`
`:8meO5.......u.33%“...9%
`
`
`mowzmm..<=zm.nm.mo8.93.:Eo:
`am5mgI5Es3.20:2“th
`
`
`
`083mg3was:>558...>5.
`
`
`
`
`
`mszzzoo...<u.$5.28I
`
`can
`
`Page 10 of 27
`
`LAIOO7
`
`IA1007
`
`Page 10 of 27
`
`
`
`

`

`U.S. Patent
`
`Feb. 6, 2001
`
`Sheet 9 of 12
`
`US 6,185,316 B1
`
`6 aun61-I
`
`IA1007
`
`Page 11 of 27
`
`

`

`U.S. Patent
`
`Feb. 6, 2001
`
`Sheet 10 of 12
`
`US 6,185,316 B1
`
`710
`
`C BEGIN)
`
`715
`
`724
`
`SYNTHESIZE
`FALSE
`MINUTAE
`
`SELECT FALSE
`IMAGE POINTS
`
`
`
`
`
`
`
`
`
`
`
`
`
`HASHFALSE
`MINUTAETO
`GET KEY
`
`
`
`ENCRYPTPLAINTEXT
`PATTERN
`USING KEY
`
`
`
`718
`
`720
`
`722
`
`RECEIVE TRUE
`IMAGE POINTS
`
`SELECT TRUE
`IMAGE POINTS
`
`CONSTRUCT
`TRANSIENT
`TEMPLATE
`
`APPEND PLAINTEXT
`AND CIPHERTEXT
`TO TRANSIENT
`TEMPLATE
`
`
`
`735
`
`Figure 10
`
`IA1007
`
`Page 12 of 27
`
`

`

`U.S. Patent
`
`Feb. 6, 2001
`
`Sheet 11 of 12
`
`US 6,185,316 B1
`
`900
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`910
`
`915
`
`920
`
`925
`
`RECEIVE
`CREDENTIALS
`
`IDENTIFY CANDIDATE
`FALSE MINUTAE
`(FIPs)
`
`CONSTRUCT
`KEY FROM
`FIPS
`
`HASH
`CANDDATE
`KEY
`
`DECRYPT
`CPHERTEXT
`WITHKEY
`
`
`
`
`
`
`
`NO
`
`COMPARE
`DECRYPTED
`CPHERTEXT
`WITH PLAINTEXT
`
`935
`
`
`
`940
`
`INDICATE
`AUTHENTCATION
`
`INDICATE
`REJECTION
`
`945
`
`Figure 11
`
`IA1007
`
`Page 13 of 27
`
`

`

`U
`
`13,
`
`1
`
`
`
`
`
`
`
`N..&F.....NoumamdNFNF..o......e..8&8...8&8...eF..&8.FNoanF...8&8...FNmFeNFo....c....8&8...b.F..&B.FNoumFF...3&8...anF»FnFFo....ao8&8...8&8...8&8...FF..&nm.F
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`69F..&..F.FNoumFF...8&8...«NFFe"FmNFo........N..-&¢...N8&8.F
`
`
`
`
`
`
`
`
`
`tEaten—:8oa...»
`
`t._<._.o._.<&.._E:FFaFomenNFF.35°...3.35:on?n.325.32?
`
`
`
`
`
`
`aroma.5on.3...23.80.c.=33...JEER=8...8.3::3.5:....32.F...SN9.22.$3.582.
`na.33.32%:
`
`P#18853.5.....3“.>9..92...»o.2....2.22..mun58F3......Win
`
`
`
`
`S.HHHIiHHIHflI-flm—fl-H—H—iial
`
`ona
`
`
`
`F..&NN.F8&5...8&8...F..o........o..o8&8...8&8...
`
`
`
`
`
`
`
`F..&.....FNoumFF...N..&..F...N..o....o........8&8...8&8...
`
`
`
`
`
`
`
`F..&$.F8&5...2&8...nFF......eo....8&8...8&8...
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`13&8;NolmFF...No-8;98N88FNo«NaNF........8&3...N..&.....FWF..&.....FNam—FF...8&8...8..mFN8mFmN......o..3&865&2...2F..&F...F8&8...mvNFFF"NonF....o....F..&NN.F8&8.uN..&F...F.
`
`
`
`
`
`F..&N...NNolmFF...3&8.528aSN8S.FFnF........3&8.8&3...
`
`
`
`
`
`
`
`
`
`F..&8.NN..&F.....F..&NF.FmNFN2:NF.emFFm2eF......a3&9;8&3..N
`
`
`
`
`
`
`
`
`
`Sum—SNNolmFF...8&2;83NN..Fmm.3NmFNNoF........N..&8.N8&mF.F
`
`
`
`
`
`
`
`8&2:SF..&..N.NN..&F...F.:7ch;2....onN3.:3..SF8oN........N..&..N...8&86NoumFFéF..&8.FnumNFSee82FFmFmFF....FN....o..8&9."tSum—SNNolmFF...F..&F...FRan8...:8....NSF8NNF2a........8&3...N..&F...v8&8;m..8NoNFF«SN5..FNmmNFn........3&eN.F8&8...hF..&8.NN..&FF.v8&3;88..8::$88.:No»no..NeFo....8&3.F8&2.f2.-..chNam—F:F..&8.F38:FE...”..FN..FBFN5..BFF.”mFo....8&8.5&2...03.83NolmFF...F..&Fo.F85F2.8NmNNFm8NmNm«NFmNnF......8&2...F..&8.NHF..&Fm.N8&NF.N%Sum—RN
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`N..&FF.eF..&m...F”58FFNaae82:8F.”mFmSN8oFo....8&8.F.8&FN.NF..&mF.NN..&FF...F..&N...FFFSNN88F88F.38Na:SN5..Foa..8&8;8&8...HF..&NF.N
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`N..&FF...F..&8.N2.88..F888N88F9N8.”cNmFmuNF8FmNn........F&8.e1.,F..&N...nNam—F:Slum:F8838&FmeNNeNEmu...NNNmanFmNN..Naoo....F&N.....2&8...63&8...NF&8.FS5&8...N..&FF...Fo-an.NESFmN«N88N22:FNNFN252.:mmFNNN........F&am.F
`
`
`
`
`
`
`
`
`
`
`FF&R...UF..&FN....N..&FF...Fo&..N.N38::SFN...‘vaNFFRSN83.8..2:NFN..o..8&2...FF&N.....
`
`
`
`
`
`8&2...N..&FF...F..&FF.NnnmnenF:8anHanaFanFF8.”8FwFFoFN......8&8.NFF&mF.F
`
`
`
`
`
`
`
`5&5...N..&F...eF..&..F.N888RF8NF8888F=an8m:2«FN......8&8.....F&Nn...
`
`
`
`3&8.NN..&FF...3&8.:53...N88FFmoN88~anNF.”onaF....o8&2:8&8;
`
`
`
`
`
`
`
`
`
`F..&n...NNam—FE.F..&8.F88....83.28.888..BF3..E.FFF......8&oF.F8&58
`
`
`
`
`
`
`
`
`
`
`
`5&8...Nam—FF...F..&8.N88888.:Some”EFF8mNsaw8NFF......8&8...oF&um.F
`
`
`
`
`
`
`
`
`
`
`
`
`
`%3&3...N..&F...F.FolmNmN35......8&FFNFSNmNaFoFeNFF88FFoNNaNo....FF&N...NNF&..F.F
`
`
`
`
`
`Bll6NF959".
`
`
`
`Page 14 of 27
`
`LAIOO7
`
`IA1007
`
`Page 14 of 27
`
`
`
`

`

`1
`SELF-AUTHENTICATION APPARATUS AND
`METHOD
`
`FIELD OF THE INVENTION
`The invention herein relates to a verification System and,
`in particular, to an apparatus and method for providing
`Self-authentication of an image, and a computer program
`therefor.
`
`BACKGROUND OF THE INVENTION
`AS the trend toward computer networking continues, the
`ability to verify the identity of system users with a high
`degree of accuracy becomes more important. Adequately
`Secure Systems deter, prevent, or detect unauthorized
`disclosure, modification, or use of information. Systems
`which cannot differentiate between requests for service by
`legitimate users and unauthorized acceSS attempts are Vul
`nerable to a variety of attackS.
`In the past, it was relatively easy to protect computer
`Systems because they were typically installed in a central
`ized computing facility. Because the terminals used to acceSS
`the computer usually were in the Same building, only those
`perSons having physical access to the building would be able
`to use the terminals. However, as networked IT systems
`proliferate, this level of physical access control becoming
`much leSS feasible. The design of open computing Systems
`permits access to more Systems, thereby allowing access to
`legitimate users and intruders, alike.
`Among the popular methods used by IT System intruders
`C.
`Password cracking
`Exploiting known Security weaknesses
`Network spoofing
`“Social engineering
`Masquerade
`Replay
`Repudiation
`Interception of data
`Manipulation of messages
`One of the most common techniques used to gain unau
`thorized System acceSS involves password cracking and the
`exploitation of known Security weaknesses. Password crack
`ing is a technique used to Surreptitiously gain System acceSS
`by using another user's account, often because the other user
`Selected a weak password, for example, one easily guessed,
`based on knowledge of the user (e.g. wife's maiden name)
`a password that is Susceptible to dictionary attacks (i.e., a
`brute-force guessing of passwords using a dictionary as the
`Source of guesses). Unauthorized System access can be
`gained through the exploitation of known Security
`weaknesses, Such as System configuration errors, and Secu
`rity bugs.
`In network Spoofing, a System presents itself to the
`network as though it were a different System, for example,
`by presenting the other System's address as its own. In
`“Social engineering, an intruder may call a System operator,
`pretending to be Some authority figure, and demand that a
`password be changed to allow them access.
`Masquerade refers to users representing themselves as
`other users. Replay of data can be accomplished by record
`ing the authentication data and playing it back at the whim
`of the intruder. If a user denies Sending (or receiving) a
`communication, the communication has been repudiated.
`Passive eavesdropping on communications is a simple, but
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,185,316 B1
`
`2
`effective, form of data interception. Messages can be
`manipulated through unauthorized insertions, deletions, or
`modifications to messages. Clearly, Some techniques, when
`implemented, can be indistinguishable from others, but the
`effect of these methods is undeniable-compromised com
`puter Security.
`Users may be able to acceSS network-connected comput
`erS from any physical location on the network, indeed from
`anywhere around the World, and the logical connection
`which Supports a Session between the user and a given
`computer may travel through many communications
`circuits, each Subject to intrusion by the above methods. The
`increasing level of interconnection between computer Sys
`tems has made it possible to distribute and process infor
`mation far more easily than in the past. However, it has also
`become Significantly more difficult to identify System users
`based on physical location, because the pathway between a
`user and the computing resources accessed by that user may
`be impossible to trace. One key proceSS in determining the
`identity of a user, or claimant, is that of authentication.
`Authentication is the verification of the true identity of a
`user. It is of Such fundamental importance in IT Systems that
`the DoD Computer Security Center standard, “Department
`of Defense Trusted Computer System Evaluation Criteria”
`(CSC-STD-001-83, August 1983) states: “Without
`authentication, user identification has no credibility. Without
`a credible identity (no) Security policies can be properly
`invoked because there is no assurance that proper authori
`Zations can be made.” Authentication, then, is essential to
`the proper use of IT Systems handling Sensitive data.
`The three generally-accepted categories of methods for
`authenticating a user's identity are based on: (1) Something
`the user knows, such as a password; (2) Something the user
`possesses, Such as an authentication token; or (3) Some
`physical characteristic of the user, Such as a fingerprint or
`Voice pattern. Collectively, these are called credentials.
`Authentication Systems can be hardware, Software, or pro
`cedural mechanisms that enable a user to obtain access to
`computing resources. At the Simplest level, the System
`administrator who adds new user accounts to the System is
`part of the System authentication mechanism. More Sophis
`ticated Solutions can use fingerprint readers or retinal Scan
`ners to establish a potential user's identity. Without estab
`lishing and proving a user's identity prior to establishing a
`Session, an IT System is Vulnerable to any Sort of attack.
`Traditionally, users have been individually supplied with
`a Secret password, which they must Submit when requesting
`access to a particular System. The majority of computer
`Systems in use today rely Solely on passwords for authen
`tication. The primary advantage of password-only authenti
`cation is that it can be implemented entirely in Software, thus
`avoiding the cost of Special purpose authentication hard
`ware. However, password-only Systems have a number of
`disadvantages in practice which restrict their use to appli
`cations with minimal Security requirements, or situations
`where password management can be strictly controlled.
`Suitable Secret information often cannot easily be remem
`bered by a human. It may consist, for example, of from 56
`to 1024 bits, or an even longer length, of randomly generated
`material.
`A password is a Sequence of characters obtained by a
`Selection or generation process from a set of acceptable
`passwords. A good password System has a very large Set of
`acceptable passwords in order to prevent an unauthorized
`person (or intruder) from determining a valid password in
`Some way other than learning it from an authorized perSon
`(i.e., owner). The set of acceptable passwords should be
`
`IA1007
`
`Page 15 of 27
`
`

`

`US 6,185,316 B1
`
`15
`
`35
`
`40
`
`25
`
`3
`large enough to assure protection against Searching and
`testing threats to the password, commensurate with the value
`of the data or resources that are being protected. The Set of
`acceptable passwords must be Such that it can be specified
`easily, that acceptable passwords can be generated or
`Selected easily, that a valid password can be remembered,
`can be Stored reasonably, and can be entered easily.
`Broadly Stated, the Security provided by a password
`depends on its composition, its length, and its protection
`from disclosure and Substitution during Storage and trans
`mission. Composition is defined as the Set of characters
`which may comprise a valid password. The composition of
`a password depends in part on the device from which the
`password is going to be entered.
`Length is closely associated with composition in assess
`ing the potential Security of a password System against an
`intruder willing to try exhaustively all possible passwords.
`The length of a password provides bounds on the potential
`Security of a System. The potential number of valid pass
`words is proportional to the number of characters in the
`acceptable composition Set, raised to the power of the length
`of the password. The potential number of passwords in a
`credentialing Scheme with a composition of 10 digits and a
`length of exactly 4 provides for 10 or 10,000 possible
`passwords, ignoring any other limiting factors.
`Increasing these parameters would be expected to have a
`positive effect on the overall Security of the System because
`exhaustive attacks become more difficult. Other factors,
`though, cannot be ignored in practical password Systems.
`For example, entering a password into an automated authen
`tication System in a Secure manner can be a difficult task. An
`interested observer can detect part or all of a password while
`the user is entering the password. Computer keyboards are
`the typical entry device, and are not particularly Suited for
`password entry. A user that is not a trained typist often enters
`the password slowly, with one finger, allowing a greater
`degree of observation. Long, random passwords can be more
`difficult to remember, be entered more slowly and visibly,
`and may be more Subject to error when being entered.
`Paradoxically, a long, random password thus may be more
`Vulnerable to observation than a short, easily-entered pass
`word.
`Whether passwords are distributed electronically, in hard
`copy form, or through other means, the distribution proceSS
`also is Subject to attack or Subversion, and be impotent
`against disclosure. Sealed envelopes with tamper-evident
`features can be used for distribution of hardcopy passwords.
`If an unauthorized party intercepts a tamper-evident enve
`lope and opens it to read the password, the envelope cannot
`be resealed and Sent to the intended recipient without
`evidence of tampering. This approach relies on the System
`users to recognize and report Suspected disclosure of hard
`copy passwords. If a password is compromised in this
`fashion, there may be a short period of time before the
`legitimate user detects and reports the compromise.
`The effectiveness of passwords often is questioned, pri
`marily because they can be easily forgotten, lost, or given to
`55
`another perSon. A user who allows his account to be com
`promised increases the chances of compromising other
`accounts or resources. In Some circumstances, passwords are
`shared as “community' passwords among members of an
`organization because maintaining password integrity is con
`sidered as a nuisance that is ineffective and SubServient to
`the organization's primary mission (e.g., health care,
`banking, law enforcement). Despite the heightened aware
`neSS of the need for tighter controls on access to computer
`Systems, it is not unusual for one to find a password written
`on note paper and taped to a heavily-used monitor in public
`VeW.
`
`45
`
`50
`
`60
`
`65
`
`4
`In these situations, the composition, length, and manner
`of distribution of the passwords are meaningless. However,
`passwords can provide reasonable deterrence to unautho
`rized access if properly handled by people authorized to use
`them and if properly Stored and processed in the password
`Verification System. Token-based credentials can be as Sus
`ceptible to attack as password Systems: tokens (e.g., ID
`cards) can be lost, Stolen, or counterfeited. The bearer of a
`compromised token can be just as indistinguishable to an IT
`System as the bearer of a pilfered password.
`Authentication Systems are useful in commercial and
`government environments in a myriad of applications. The
`Strength of an authentication System should be chosen to
`provide a degree of assurance appropriate for the Security
`requirements of the application and environment in which
`the System is to be used and the Security Services provided
`by the System. The central design objective of an authenti
`cation System is to protect against adversaries mounting
`cost-effective attacks on Sensitive data, that is, an effective
`Security System design makes the cost of an attempted attack
`greater than the expected payoff.
`AS used herein, the concept of identity Verification is
`described primarily with respect to human users but could be
`applied to other types of users as warranted by the applica
`tion and with Suitable modifications known to skilled arti
`SS.
`Reliable authentication mechanisms are critical to the
`Security of any automated information System. If the identity
`of legitimate users can be verified with an acceptable degree
`of accuracy, those attempting to gain access without proper
`authorization can be denied permission to use the System.
`When a legitimate user's identity is verified, access control
`techniques are applied to mediate that users acceSS to
`System resources. If a computer System cannot verify the
`identity of users and other computers, the System will not be
`able to protect itself against unauthorized access.
`Networking not only makes it more difficult to identify
`System users, it also increases the opportunities for unau
`thorized parties to intercept authentication data passing
`through the network during the course of a legitimate
`Session between a user and a remote host computer. User
`passwords are Sometimes transmitted through a network in
`plaintext form. If an attacker is able to monitor the user's
`Session, the attacker may be able to record the user's
`password or other critical authentication data. This would
`allow the attacker to masquerade as a valid user by initiating
`a login on the remote host and Submitting the user's authen
`tication data when the host requests it.
`Some Systems apply a cryptographic algorithm to
`Scramble (encrypt) passwords before they are transmitted, So
`that the plaintext password is not exposed. However, an
`attacker may still be able to record the encrypted password,
`and gain access to the host computer by Submitting the
`encrypted value. In either case, the host computer will be
`unable to distinguish between the attacker and a valid user,
`and will grant access to the attacker. This "replay attack can
`be defeated by using a random challenge/response mecha
`nism in which a variable parameter (typically time-varying)
`is integrated into the encrypted password and an attempted
`replay of the “Stale' password reveals the attacker, thus
`permitting the System to preserve its integrity. Obviously,
`the Security of a replay-prevention technique hinges on the
`generation of random challenges which have a low prob
`ability of being repeated.
`Furthermore, an IT System typically Stores passwords for
`use in the authentication process. When a user attempts to
`login to the System, the user will Submit a password which
`
`IA1007
`
`Page 16 of 27
`
`

`

`US 6,185,316 B1
`
`15
`
`25
`
`S
`must be compared to the Stored password, or Some one-way
`mapping thereof, which the System knows to be valid for
`that user. Protection can be provided for passwords by
`Storing them in a physically Separate area which can only be
`accessed by authorized System components. Stored pass
`words may also be protected by encryption or through the
`application of a one-way mapping function before Storage.
`The aforementioned shortcomings of existing authentica
`tion Schemes are magnified when human users are required
`to acceSS multiple Services on multiple hosts. Separate
`authentication events may be required for each Service a user
`wishes to access, particularly if these Services are resident on
`Separate host machines. Users might, for example, be
`required to provide a separate password for each Service. In
`Some cases, Services or host computers may even use
`different authentication techniques which would, for
`example, force users to memorize passwords for Some
`Services and carry tokens or provide biometric Scans for
`others. This situation quickly becomes an unreasonable
`burden for users, and can lead to, or exacerbate, poor
`Security practices.
`To address the problems described above, login authen
`tication Schemes have been developed that only require
`users to authenticate once during a Session. These
`approaches are commonly referred to as unitary login, or
`Single Sign-on. Unitary login is generally a two-step process,
`in which the user first authenticates to a user using, for
`example, a password, token, or biometric Sample. The
`principal may be the user's WorkStation, a physical authen
`tication token, or Some other device. Then, as the user
`requests access to various Services, the principal is respon
`Sible for authenticating the user to each Service.
`Conceptually, the principal acts as a proxy for the user in
`conveying the original authentication event, and automates
`Subsequent authentications with little or no intervention
`from the user. These Subsequent authentications are usually
`based on Strong cryptographic protocols which are Secure
`acroSS communications networks. Both the principal and the
`Verifying entity of the Service accessed by the user must
`understand, and adhere to, the pre-arranged authentication
`protocol. Also, it is preferred that the principal be respon
`Sible for determining the point at which a given user's
`current authentication terminates. This termination point is
`often tied to the end of a user's login Session.
`Authentication based on public key cryptography may
`have an advantage over other authentication Schemes
`because no Secret information has to be shared by the entities
`involved in the exchange. A user presenting for authentica
`tion can use a private key to digitally sign a random number
`challenge issued by the verifying entity. This random num
`50
`ber is desired to be a time-variant parameter which is unique
`to the authentication eXchange. If the Verifier can Success
`fully verify the Signed response using the user's public key,
`then the user has been Successfully authenticated.
`The foregoing interactive eXchange is Sometimes referred
`to as a “Zero-knowledge proof in which knowledge of the
`private is proved without divulging the actual key. That is,
`the prover convinces the verifier of a Statement (with high
`probability) without revealing any information about how to
`go about proving that Statement.
`Because a given user's private key does not need to be
`shared with other parties, there is a Strong association
`between the user's identity and possession of the private key.
`Digital Signatures can be used for authentication as follows:
`when a host system wishes to verify the identity of a user
`who is in possession of a particular private key, the host
`System can challenge the user with an electronic message.
`
`6
`The user would sign this message with the private key and
`return the Signature to the host System. The host can then
`Verify the Signature, and thus the identity of the user, with
`the user's public key. Because only one Specific user pos
`SeSSes a particular private key, a Signature generated by this
`key is Strong proof of the user's identity.
`These cryptographic methods are referred to as "asym
`metric' or “two-key' methods, because they rely on two
`different keys to perform cryptographic processing of data.
`The requisite keys are generated and used in pairs consisting
`of private and public key components. Because there is no
`longer a Single Secret key shared by a pair of users, and each
`user has his own key material, public-key techniques differ
`from conventional Systems. Furthermore, the key material of
`each user is divided into two portions, a private component
`and a public component. The public component generates a
`public transformation E, and the private component gener
`ates a private transformation D.
`The public key becomes in effect part of the user's
`identity, and should be made as well known as necessary,
`like a phone number. Conversely, the private key should be
`known only to the user, because it can be used to prove
`ownership of the public key and thus the user's identity. A
`desirable property of public key Systems is that it essentially
`computationally infeasible to derive a user's private key
`from the corresponding public key, So free distribution of the
`public key theoretically poses no threat to the Secrecy of the
`private key. The private key can be used to create a digital
`Signature which is unique to the Signer, which Signature is
`infeasible to forge and can be verified electronically.
`Also, public key cryptography makes it possible to place
`the authentication information under the direct control of the
`System user. For access control, this is especially helpful
`because Secret authentication information need not be dis
`tributed throughout the System.
`However, the Security of authentication protocols ba