United States Patent
`Abadi et al.
`
`[191
`
`US006141760A
`Patent Number:
`Date of Patent:
`
`[111
`[451
`
`6,141,760
`Oct. 31, 2000
`
`[541
`
`[751
`
`SYSTEM AND METHOD FOR GENERATING
`UNI UE PASSWORDS
`Q
`Inventors: Martin Abadi, Palo Alto; Krishna
`Bharat, Santa Clara; Johannes Marais,
`Mountain View, an of Calif
`
`Assignee: Compaq Computer Corporation,
`Houston, Tex'
`
`A l. N .: 08 962 505
`pp
`0
`/
`’
`Filed:
`Oct. 31, 1997
`Int C17
`
`H04L 9/00
`
`OTHER PUBLICATIONS
`
`.
`Hensley et al.; Proposal for an Open Pro?ling Standard;
`located @ WWW-12W3~Org/TR/NOTE_OPS_Frame'
`work'html; downloaded OCP 1997'
`Hensley et al.; Implementation of OPS Over HTTP; located
`@ WWW.W3.org/TR/NOTE—OPS—OverHTTP.html; doWn
`loaded 091- 1997
`Hensley et al.; Standard Practices for OPS Systems; located
`@WWW.W3 .org/TR/NOTE—OPS—StandardPractices.html;
`downloaded Oct. 1997.
`Hoff et al.; The HTTP Distribution and Replication Protocol;
`located @ WWW.W3.org/TR/NOTE—drp—19970825.html;
`downloaded Oct. 1997.
`
`US. Cl. ........................................... .. 713/202; 713/184
`Field of Search ................................... .. 713/200, 201,
`713/202, 183, 184; 707/9; 380/23, 25; 709/229;
`
`Primary Examiner—R0bert W. Beausoliel, Jr.
`Assistant Examiner—sc0tt T- Baderman
`Attorney, Agent, or Firm—F9nWiCk & West LLP
`
`References Cited
`U S PATENT DOCUMENTS
`'
`'
`9/1994 Blandford ............................... .. 380/25
`5,347,579
`5,684,951 11/ 1997 Goldman et al-
`395/ 188-01
`577197941
`2/1998 swl? Ft a1~ - - - - - -
`- - - ~~ 380/25
`2’812’819
`9/1998 Rodwm et a1‘ "
`395/5500
`{222L333
`grliigor'r'l'g """"" "
`364/468:15
`5’847’957 12/1998 Cohen et
`.. 395/187.01
`5,892,905
`4/1999 Brandt et a1. .
`713/202
`6,006,333 12/1999 Nielsen ...... ..
`6,079,021
`6/2000 Abadi et a1. .......................... .. 713/202
`
`A computerized method is provided for generating pass
`Words for passWord controlled access points. Provided are a
`master passWord, an access passWord, and a user name. The
`master passWord, the service name, and the user name are
`combined using an irreversible function to generate a unique
`passWord. The function can be a one-Way hash function. The
`combining can be performed by a broWser of a client
`computer. A similar combining can also be used to generate
`a user name from the master passWord and the user’s real
`name
`
`20 Claims, 2 Drawing Sheets
`
`(2 O1
`master_password
`
`real
`name
`
`20 4
`
`220 202
`
`service_name
`
`passwords
`
`( 200
`
`203
`
`.
`
`user_name
`
`Page 1
`
`

`
`U.S. Patent
`
`0a. 31, 2000
`
`Sheet 1 of2
`
`6,141,760
`
`ON_
`
`ON_
`
`mm>mmw
`
`ON.
`
`
`
`HZ_On_ wwmOO<
`
`NN_ / U
`
`On
`
`6595
`
`mw>>
`
`Ewzo <0:
`
`
`
`(1/ .v:
`
`\O:
`
`Page 2
`
`

`
`U.S. Patent
`
`0a. 31, 2000
`
`Sheet 2 of2
`
`6,141,760
`
`oEmclEw:
`
`MON
`
`mEmcImEEmm
`
`6%
`
`OEGC
`
`O_N m
`
`oom
`
`N
`
`222523
`
`Page 3
`
`

`
`1
`SYSTEM AND METHOD FOR GENERATING
`UNIQUE PASSWORDS
`FIELD INVENTION
`This invention relates generally to computer systems, and
`more particularly to passwords used to gain access to
`computer system services and data records stored by com
`puter systems.
`BACKGROUND OF THE INVENTION
`
`It is common to use passWords to alloW users to access
`computer systems and data records. More recently, many
`services provided via the World-Wide-Web (the Web) also
`authenticate access With passWords. The use of passWords
`for access protection is so pervasive that it is not unusual for
`a user to have to remember a large number of different
`passWords.
`Because of the large number of passWords that one might
`need to have, many users choose memorable passWords,
`Which are easy to guess. A sophisticated imposter using
`automated schemes can easily “try” millions of common
`passWord variations in a matter of minutes. Because users
`often use the same passWord for many services, if the user’s
`passWord for a particular service is disclosed, then the
`passWord could be used to access other accounts. In
`particular, the oWners or administrators of one service could
`use the user’s passWord to access the user’s other accounts.
`In addition, for services that are accessed by many users,
`user names based on common names, e.g., “johnsmith,” are
`quickly used up.
`The problems With passWords are Well knoWn, and there
`have been a number of proposed replacements for
`passWords, in particular, schemes based on sophisticated
`cryptographic techniques or biometric identi?cation, see
`Schneier, “Applied Cryptography.” In some cases, these
`approaches can provide adequate security at the expense of
`requiring fundamental changes in hoW authentication sys
`tems operate.
`Currently, an “Open Pro?ling Speci?cation” is being
`considered by the Platform for Privacy Preferences (P3)
`project of the W3C. This speci?cation may eventually
`provide a solution to the problem of passWord authentication
`on the Web, although the present efforts of the Open
`Pro?ling Work concentrate on the exchange of user prefer
`ences betWeen broWser and server computers.
`One could use Open Pro?ling for managing user
`passWords, and protecting the passWords from access by
`inappropriate servers. In all cases, Open Pro?ling requires
`aWareness and cooperation by broWsers and servers, so it
`cannot be used With current softWare. Moreover, Open
`Pro?ling requires access to a user-speci?c pro?le, Which
`users Will need to either fetch from a server or carry With
`them. Fetching over a netWork may not alWays be quick or
`possible, e.g., the pro?le may be behind a ?reWall or the
`netWork may be partitioned. Carrying the pro?le may be
`inconvenient or unsafe, since it may require use of ?oppy
`disks, smart-cards, or other auxiliary hardWare.
`Therefore, it is desired to provide a scheme in Which the
`user is not required to remember many different passWords.
`
`1O
`
`15
`
`25
`
`35
`
`45
`
`55
`
`SUMMARY OF THE INVENTION
`A computeriZed method is provided for generating pass
`Words for passWord controlled access points. Provided are a
`master passWord, a service name, and a user name. The
`master passWord, the service name, and the user name are
`combined using an irreversible function to generate a unique
`passWord.
`
`65
`
`6,141,760
`
`2
`The function is a one-Way hash function, e.g., the input
`cannot be determined from the output. The combining can
`be performed by a broWser of a client computer. As an
`advantage the technique is easy to use, and the service name
`does not need to be kept secret. In addition, the method
`provides for a Way to automatically generating unique user
`names. This is useful in the case of users With common
`“real” names.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagram of distributed computer system
`100 providing services accessible using passWords accord
`ing to the invention; and
`FIG. 2 is How diagram of a preferred embodiment for
`generating passWords.
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`
`System OvervieW
`FIG. 1 shoWs a distributed computer system 100 provid
`ing services accessible using passWords generated according
`to the invention. The system 100 includes client computers
`110 connected to server computers 120 via a communica
`tions netWork 130.
`The client computers 110 can be lap-tops, personal
`computers, Work-stations, or the like. The clients 110 gen
`erally include input and output (I/O) devices, for example, a
`mouse 111, a keyboard 112, and a monitor 113. The I/O
`devices alloW users of the clients 110 to execute applications
`under the control of operating system softWare, for example,
`Microsoft WindoWs, or Unix. One of the applications can be
`a Web broWser 114 such as the Netscape Navigator, or the
`Microsoft Explorer.
`The netWork 130 can be the Internet supporting an
`application communications interface, for example, the
`World Wide Web (Web) 131.
`The server computers 120 are usually larger computer
`systems characteriZed by providing services 121 and infor
`mational databases 122 accessible by many client computers
`all over the World.
`System Operation
`A typical user of the system 100 Will provide a passWord
`to enable the operation of the client 110, additional pass
`Words may be required to activate and access privileged
`softWare and applications of the client 110. Use of the
`netWork 130 may require yet another set of passWords.
`Access to the servers 120 and its services 121 and informa
`tion 122 may be protected by a ?nal layer of passWords. In
`a typical day, the user may need to remember doZens of
`passWords that get authenticated by passWord controlled
`access points. This is a burden, particularly When more
`sophisticated authentication processes require a long
`sequence of nonsense characters.
`In order to lessen the burden of remembering a large
`number of passWords for different access points, and also to
`improve the security of passWords, the system 100 is
`enhanced as folloWs.
`The Web broWser 114, Which has become a primary Web
`access tool, is provided With an extension 115, described in
`further detail beloW, Which implements aspects of the inven
`tion.
`PassWords Generation
`As shoWn in FIG. 2, passWords 200 are constructed as
`folloWs.
`Each user chooses a ?rst string as a master13passWord
`201. This is the only passWord the user must remember.
`For any service, hardWare or data structure that requires
`a passWord 200, generally “passWord controlled access
`
`Page 4
`
`

`
`3
`points,” second strings 202 form serviceinames 202.
`Serviceinames 202 need not be kept secret, and may be
`easy to remember and to guess.
`In one implementation, each serviceiname 202 can be
`manually generated by the user. Alternatively, the service
`name may be automatically generated by the client or the
`access point, e.g., the server, from the domain name of the
`service, or data structure. Other possible serviceinames 202
`could be the IP address of the passWord controlled access
`point, or the title of its entrance Web page. In a simplest
`implementation, any speci?c passWord protected access
`point can provide the same serviceiname to each user.
`The string 202 is expressed in a canonical form to
`compensate for minor variations in the spelling of the
`service name as entered by the user. The canonical form can
`be obtained by ignoring all punctuation and spaces, con
`verting uppercase characters to loWercase, and omitting
`common Words such as ‘The,’ ‘in,’ ‘and,’ etc. For example,
`the user may take “The NY. Times” as the serviceiname
`202 for accessing the NeW York Times on-line edition
`service. In canonical form, “The NY. Times” becomes
`“nytimes.”
`In addition, a third string, the user name 203, is associated
`With each user. As an advantage, it is possible to generate
`unique user names for users With common “real” names,
`such as John Smith. This is described in greater detail beloW.
`An operation
`210 combines, for any particular user,
`the strings 201—203 to generate passWords 200. The opera
`tion 210 has the property that it is hard to invert, and that it
`maps different inputs to different outputs. That is, the
`likelihood that combinations of different input strings pro
`duce the same output string is minimal. The operation 210
`can be implemented as part of the broWser extension 115 of
`FIG. 1.
`The method for generating unique userinames 203 can
`proceed as folloWs. The user supplies his masteripasssWord
`201 (e.g., sdtTg2;WqZ:r#), and his or her real name 204 (e.g.,
`John Smith). Afunction 220 is applied. This function applies
`a one-Way hash-function on the real name 204 and the
`master passWord to compute a unique string Which is
`appended to the user’s initials, (e.g., “js”) to give a unique
`useriname 203, e.g., js4546Q. This function can be like the
`function 210 above although it operates on different strings.
`This method for generating unique userinames is optional,
`user-names can be generated by other methods, or the real
`names can be used.
`The extension 115 can be started When the broWser 114 is
`initialiZed, or the extension may be doWnloaded, on demand,
`via the Web. The extension can be implemented in the
`J avaScript language, for example. When the extension 115
`is started, the user only needs to provide the masteri
`passWord 201 and his or her common name.
`As described above, each passWord controlled access
`point has an associated serviceiname 202. Therefore, When
`the user needs a passWord for a particular service, the
`broWser extension must receive the corresponding servicei
`name 202. The broWser extension 115 then determines the
`correct passWord by applying the operation F 210 on the
`masteripassWord, the serviceiname, and the useriname.
`The result is the user’s passWord 200 for the access point and
`user in question. The user can enter the generated passWord
`using easy cut-and-paste operations, or the broWser exten
`sion 114 could directly submit the passWord.
`Because the passWord is generated from the master pass
`Word 201 and the user name, it is generally immune to
`so-called “dictionary attacks”.
`The present invention enhances security and convenience.
`It alloWs users to remember only a single master passWord,
`
`15
`
`3O
`
`35
`
`55
`
`6,141,760
`
`4
`and avoids the dangers of using the same passWord for many
`different controlled access points. In addition, the invention
`alloWs users to use the same user name across services, and
`avoids having to remember complicated user names.
`Furthermore, the invention discourages users to expose
`passWords, e.g., by Writing them doWn. An important aspect
`of this invention is that it can be integrated into current
`softWare for Web broWsing. It does not require any changes
`in the concept of passWord, or any changes in server
`softWare.
`It is understood that the above-described embodiments are
`simply illustrative of the principles of the invention. Various
`other modi?cations and changes may be made by those
`skilled in the art Which Will embody the principles of the
`invention and fall Within the spirit and scope thereof.
`What is claimed is:
`1. A computeriZed method for generating passWords for
`passWord controlled access points, comprising the steps of:
`receiving a master passWord, a service name, and a user
`name; and
`generating a unique passWord at a local terminal by
`combining the master passWord, the service name, and
`the user name.
`2. The method of claim 1 Wherein the generating step uses
`an irreversible function.
`3. The method of claim 2 Wherein the function is a ?rst
`one-Way hash function.
`4. The method of claim 1 Wherein the combining step is
`performed by a broWser of a client computer.
`5. The method of claim 1 Wherein the generating step is
`performed by an applet of a client computer.
`6. The method of claim 1 Wherein the service name is
`expressed in canonical form.
`7. The method of claim 1 Wherein the user name is derived
`by combining the master passWord and a real name of a user.
`8. The method of claim 7 Wherein the generating step uses
`a second one-Way hash function.
`9. The method of claim 1 further comprising the steps of:
`maintaining a plurality of service names Within the local
`computer, each service name corresponding to one of
`the passWord controlled access points; and
`retrieving at least one service name for use in generating
`the unique passWord.
`10. The method of claim 9 Wherein the plurality of service
`names are automatically created by the local terminal.
`11. The method of claim 9 Wherein the plurality of service
`names are created by a user.
`12. A computer apparatus for generating passWords com
`prising:
`a local computer;
`a receiving module adapted to receive a master
`passWord, a service name and a user name;
`a generation module adapted to generate a unique
`passWord at the local computer by combining the
`master passWord, the service name, and the user
`name.
`13. The computer apparatus of claim 12 Wherein the
`generation module is adapted to implement an irreversible
`function adapted to generate the unique passWord by com
`bining the master passWord, the service name, and the user
`name.
`14. The computer apparatus of claim 12 further compris
`ing a broWser applet Within the local computer, said broWser
`applet adapted to generate the unique passWord by combin
`ing the master passWord, the service name and the user
`name.
`
`Page 5
`
`

`
`6,141,760
`
`5
`15. The computer apparatus of claim 12 wherein the
`generation module is adapted to implement a plurality of
`irreversible functions adapted to generate the unique pass
`Word by combining the master passWord, the service name
`and the user name.
`16. The computer apparatus of claim 12 further compris
`ing a storage module adapted to store a plurality of service
`names Within the local computer.
`17. A computer program product comprising:
`a computer usable medium having computer readable
`code embodied therein for causing the generation of a
`unique passWord, the computer program product
`including:
`computer readable program code devices con?gured to
`cause a local computer to effect the reception of a
`master passWord, a service name and a user name;
`computer readable program code devices con?gured to
`cause the local computer to effect the generation of
`the unique passWord at the local computer by com
`bining the master passWord, the service name, and
`the user name.
`
`10
`
`15
`
`6
`18. The computer program product of claim 17 further
`including a computer readable program code device con?g
`ured to cause the local computer to effect the storage of a
`plurality of service names and a computer readable program
`code device con?gured to retrieve at least one of the service
`names for use in the generation of the unique passWord.
`19. The computer program product of claim 17 further
`including a computer readable program code device con?g
`ured to use an irreversible function to generate the unique
`passWord from the combination of the user name, the service
`name and the master passWord.
`20. The computer program product of claim 17 further
`including a computer readable program code device con?g
`ured to use a broWser applet contained Within the local
`computer to generate the unique passWord from the combi
`nation of the user name, the service name and the master
`passWord.
`
`Page 6