United States Patent [19]
`Blakley, m et al.
`
`II 1111111111111
`
`US005677952A
`[11] Patent Number:
`[451 Date of Patent:
`
`5,677,952
`Oct. 14, 1997
`
`[54] MEmOD TO PROTECT INFORMATION ON
`A COMPUTER STORAGE DEVICE
`
`[75]
`
`Inventors: George R. Blakley, ill, Austin, Tex.;
`Phillip W. Rogaway, Davis, Calif.
`
`[73] Assignee: International Business Machines
`Corporation, Austin, Tex.
`
`3/1982 Best.
`4,319,079
`6/1986 Pickho1tz .
`4,593,353
`3/1988 Grynberg et al ..
`4,734,796
`4,888,798 1211989 Earnest .
`4,907,274
`3/1990 Nomura et al. ........................... 380/30
`3/1991 Merkle ...................................... 380137
`5,003,597
`5,212,729
`511993 Schafer.
`8/1993 Hane .
`5,239,581
`5,454,039
`9/1995 Coppersmith et al .................... 380/28
`
`[21] Appl. No.: 349,778
`
`[22] Filed:
`
`Dec. 6, 1994
`
`Primary Examiner-Bemarr E. Gregory
`Attorney, Agent, or Firm-Jeffrey S. LaBaw; David H.
`Judson
`
`Related U.S. Application Data
`
`[57]
`
`ABSTRACT
`
`[63] Continuation-in-part of Ser. No. 163,054, Dec. 6, 1993, Pat
`No. 5,454,039.
`Int. CL 6
`........................................................ H04L 9/00
`[51]
`[52] U.S. Cl ...................................... 380/4; 380/9; 380/28;
`380/46; 380/49
`[58] Field of Search ............................... 380/4, 9, 23, 25,
`380/46,49,50,28,30,37
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`2/1978 Ehrsam et al ..
`4,074,066
`4,238,854 12/1980 Ehrsam et al ..
`
`A method, using a secret key, to protect information in a
`storage disk of a computer, where the secret key is derived
`from a password entered into the computer by an authorized
`user. The method begins by applying a length-increasing
`pseudorandom function to the secret key and an index to
`generate a pseudorandom bit string having a length that is a
`function of the size of a sector of the storage disk. The sector
`is associated or otherwise identified by the index used by the
`pseudorandom function to generate the pseudorandom bit
`string. The pseudorandom bit string is then used to encrypt
`and decrypt data accesses to and from the sector.
`
`20 Claims, 3 Drawing Sheets
`
`OPERATING
`SYSTEM
`
`READ/
`WRITE OF
`SPECIFIED
`SECTORS
`
`vBO v7B
`USER
`
`LOGON
`UTILITY
`,
`PASSWORD
`KEY
`PROCESSING
`UTILITY
`
`1'--82
`
`..._
`
`TABLES
`
`8\6
`,..~--~--,
`I
`I -
`I
`®
`I
`L-------1
`~ ~'---76
`SYSTEM BUS
`
`DEV
`ICE
`
`DR IVER
`
`<
`
`~
`
`;s
`
`?6
`
`DISK
`CONTROLLER
`
`..
`
`PHYSICAL
`DISK
`
`"':>
`
`p
`
`NETAPP ET AL. EXHIBIT 1005
`Page 1 of 11
`
`

`
`U.S. Patent
`
`Oct. 14, 1997
`
`Sheet 1 of 3
`
`5,677,952
`
`20
`~
`
`. FIG. 1
`
`SYSTEM
`
`61
`
`OPERATING vso B
`l
`PRESENTATION
`MANAGER 1'-62
`
`RAM
`34
`
`~2
`MICRO-
`PROCESSOR
`
`1
`
`5~
`1/0
`CONT.
`
`)3
`
`ROM
`
`1
`
`?6
`
`DIGITAL
`SIGNAL
`PROCESSOR
`
`~
`
`11
`
`35
`;
`MEMORY
`MANAGEMENT
`
`1
`
`:l
`
`MOUSE
`CONTROLLER
`_f
`I
`
`?~
`
`VIDEO
`CONTROLLER
`
`2
`
`AUDIO
`CONTROLLER
`
`•
`
`GRAPHIC
`DISPLAY
`
`2~
`25A../ SPEAKER
`
`:ZB
`
`SPEAK.£R
`
`KEYBOARD
`
`MOUSE
`
`2;
`
`2~
`FIG. 2
`
`)1
`4~
`CD
`
`~ ROM
`
`3~
`HARD
`DISK
`
`FLOPPY
`DISK
`
`)B
`KEYBOARD
`CONTROLLER
`1
`
`NETAPP ET AL. EXHIBIT 1005
`Page 2 of 11
`
`

`
`U.S. Patent
`
`Oct. 14, 1997
`
`Sheet 2 of 3
`
`5,677,952
`
`OPERATING
`SYSTEM
`
`LOGON
`UTILITY
`
`/80 v78
`USER
`
`READ/
`WRITE OF
`SPECIFIED
`SECTORS
`
`PASSWORD
`
`KEY
`PROCESSING
`UTILITY
`
`"-82
`
`DEV
`ICE
`DR IVER
`
`A
`
`<: -
`
`)6
`PHYSICAL
`DISK
`
`DISK
`CONTROLLER
`
`f---1.---
`
`1 ~
`
`8p
`
`,:~ __ ._ __ ,
`I
`I
`®
`I
`I
`L------~
`
`TABLES
`
`)5
`
`~
`
`~'--76
`
`SYSTEM BUS
`
`FIG. 3
`
`FIG. 4
`
`NETAPP ET AL. EXHIBIT 1005
`Page 3 of 11
`
`

`
`U.S. Patent
`
`Oct. 14, 1997
`
`Sheet 3 of 3
`
`5,677,952
`
`APPLICATION
`
`t
`
`USER
`
`vBD
`
`LOGON
`UTILITY
`
`PASSWORD
`KEY
`PROCESSING
`UTILITY
`
`"-82
`
`(T,R,S)
`
`FILE
`EM
`SYST
`(LOCA
`L
`
`MACHI NE)
`
`FILE
`SYSTE
`M
`OR
`(LOCAL
`REMOT E)
`
`< ....
`
`INTERFACE
`
`FILE SYSTEM
`Bp
`r':J.. _____ ,
`I
`I
`®
`I
`I
`L------..J
`~ "'--88
`FILE SYSTEM
`INTERFACE
`(BOTTOM)
`
`~92
`
`Fl LE SERVER INTERFACE
`
`i'-90
`
`;s
`?6
`DISK M- PHYSICAL
`DISK
`CONTROLLER
`
`DEVICE DRIVER
`
`SYSTEM BUS
`
`FIG. 5
`
`~ ...
`
`NETAPP ET AL. EXHIBIT 1005
`Page 4 of 11
`
`

`
`5,677,952
`
`1
`METHOD TO PROTECT INFORMATION ON
`A COMPUTER STORAGE DEVICE
`
`This application is a continuation-in-part of prior appli(cid:173)
`cation Ser. No. 08/163,054, filed Dec. 6, 1993, and assigned
`to the assignee of this application, now U.S. Pat. No.
`5.454.039.
`
`TECHNICAL FIELD
`
`The present invention relates generally to computer data
`security and more particularly to a method to protect against
`unauthorized disclosure of information stored on a mass
`storage device of a computer.
`
`BACKGROUND OF THE INVENTION
`
`2
`computer may change his or her password yet still access the
`computer's storage device in a secure manner.
`It is yet a further object of the invention to describe a
`novel computer that incotporates the techniques for securing
`s sensitive information stored therein.
`These and other objects of the invention are provided in
`a method, using a secret key, to protect information in a
`storage disk of a computer. where the secret key is derived
`from a password entered into the computer by an authorized
`10 user. The method begins by applying a length-increasing
`pseudorandom function to the secret key and an index to
`generate a pseudorandom bit string having a length that is
`the size of a sector of the storage disk. The sector is
`associated or otherwise identified by the index used by the
`pseudorandom function to generate the pseudorandom bit
`15 string. The pseudorandom bit string is then used to encrypt
`and decrypt data accesses to and from the sector. Thus, all
`sensitive information is stored on the storage device in
`ciphertext. The ciphertext is decrypted by the pseudorandom
`bit string when the disk is read. Information to be stored in
`20 a sector is encrypted by the pseudorandom string before it is
`written to the disk.
`Preferably, the secret key is only maintained in the
`computer's volatile memory to thereby enable the autho(cid:173)
`rized user to encrypt and decrypt data accesses from the
`sector during authorized use of the computer. However.
`when the particular computing session is ended (e.g., when
`the authorized user turns the computer off or logs off) or
`interrupted (e.g .• when the authorized user locks up the
`computer or ceases to interact with the computer for a
`30 predetermined timeout period), the secret key is erased from
`the computer's volatile memory to prevent unauthorized
`access to and disclosure of information in the sector.
`In one preferred embodiment, the secret key is prepro(cid:173)
`cessed by transforming it into one or more tables of pseu-
`35 dorandom numbers. Preprocessing the secret key in this
`manner facilitates the generation of the pseudorandom bit
`string by the pseudorandom function once the particular
`index (i.e., the disk sector identification) is identified. The
`tables of pseudorandom numbers provide an efficient rep(cid:173)
`resentation of the secret key to decrease the time necessary
`40 to generate the particular pseudorandom bit string associated
`with the sector.
`According to another feature of the invention, a computer
`having a storage device is provided with a routine for
`processing a password to generate a secret key. A pseudo(cid:173)
`random function uses the secret key and an index to generate
`a pseudorandom bit string whose length is a function of the
`size of a particular disk sector identified by the index. Data
`accesses to and from the disk sector and encrypted and
`decrypted using the bit string.
`The preferred method may be implemented on a program
`storage device (e.g., a floppy diskette) that is readable by a
`processor and that tangibly embodies a program of instruc(cid:173)
`tions executable by the processor to perform the method.
`The foregoing has outlined some of the more pertinent
`objects of the present invention. These objects should be
`construed to be merely illustrative of some of the more
`prominent features and applications of the invention. Many
`other beneficial results can be attained by applying the
`disclosed invention in a different manner or modifying the
`invention as will be described. Accordingly. other objects
`and a fuller understanding of the invention may be had by
`referring to the following Detailed Description of the pre(cid:173)
`ferred embodiment.
`
`The shrinking of computing resources has led to a new
`and dangerous mass security threat. Information stored in a
`computer's mass storage device (e.g., a hard disk) can be
`stolen by theft of the computer itself. The theft of smaller
`computers such as "portables" is a particularly urgent prob(cid:173)
`lem that has not been adequately addressed. Whether the
`portable computer is stolen for the sensitive data stored
`therein or for the hardware is often unclear from the cir(cid:173)
`cumstances of the theft itself; typically, however. the owner 25
`must assume that the data will be compromised.
`There are other known threats to sensitive information
`stored in a computer. Under many operating systems there is
`no access control or user authentication. For example. under
`the DOS or OS/2 operating systems as well as With other
`machines with access control, a so-called "lunchtime" attack
`can be quite effective. In this scenario, the adversary sneaks
`into an insecure or unattended area and copies information
`off the computer's hard disk. The owner, of course. may
`never know that the information has been stolen.
`There is therefore a long felt need in the computer
`industry for methods to protect information on a computer
`storage device against unauthorized disclosure when the
`computer is stolen or temporarily commandeered by unau(cid:173)
`thorized individuals.
`
`BRIEF SUMMARY OF THE INVENTION
`
`45
`
`It is a principal object of the invention to protect the
`confidentiality of information stored on a storage device of
`.
`l
`th
`.
`
`if th e computer 1s sto en or o erw1se
`a computer. even
`accessed without the owner's consent or knowledge.
`It is a further object of the invention to allow any
`computer (including, without limitation, personal
`computers. portable computers, pen-based computers and 50
`handheld personal data assistants or "PDA's") to secure
`information stored therein such that there is little or no user
`visibility of the security, no special security features are
`required of the underlying hardware or operating system,
`and there is little performance impact on the operation of the 55
`device.
`It is still a further object of the invention to secure and
`protect information on a storage device of a computer using
`a cryptographic transformation that operates efficiently in
`software and that is optimized to known high speed micro- 60
`processors. The cryptographic transformation is used to
`encrypt and decrypt data accesses to and from the comput(cid:173)
`er's storage device.
`It is another object of the invention to describe a method
`for securing information on a portable computer that is 65
`shared by a number of authorized users. each obtaining
`access with his own password. Each authorized user of the
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`For a more complete understanding of the present inven(cid:173)
`tion and the advantages thereof. reference should be made to
`
`NETAPP ET AL. EXHIBIT 1005
`Page 5 of 11
`
`

`
`5,677,952
`
`3
`the following Detailed Description taken in connection with
`the accompanying drawings in which:
`FIG. 1 illustrates a computer comprising a system unit, a
`keyboard. a mouse and a display, for use in implementing
`the method to protect information according to the present 5
`invention;
`FIG. 2 is an architectural block diagram of the computer
`illustrated in FIG. 1;
`FIG. 3 illustrates a portion of the computer of FIG. 1
`showing a length-increasing pseudorandom function sup- 10
`ported in the device driver to facilitate disk encryption;
`FIG. 4 illustrates a preferred process for generating a
`pseudorandom bit string; and
`FIG. 5 illustrates a portion of the computer of FIG. 1 15
`showing a length-increasing pseudorandom function sup(cid:173)
`ported in the device driver to facilitate file encryption.
`
`DEfAll..ED DESCRIPITON
`According to the present invention, a software product is
`provided that works under any operating system (including,
`without limitation, DOS. OS/2, and AIX) to protect all
`confidential information on a computer disk or other storage
`media during those periods in which the machine is not in
`use. The invention protects against thieves, lunchtime
`attacks and other invasions of privacy. The invention is
`useful on so-called ''portables" (i.e., laptop, notebook and
`subnotebook computers), desktop machines (i.e., personal
`computers or workstations), pen-based machines, other
`handheld computers including personal data assistants
`("PDA's"), smartcards and the like. As used herein, "com(cid:173)
`puter" in intended to have the broadest possible interpreta(cid:173)
`tion.
`According to the invention, all sensitive information on
`the computer's storage device is stored in ciphertext using a
`secret key such that if the storage device or the computer
`itself is stolen or improperly accessed, the thief cannot make
`use of the information. The information obtained from each
`read of the storage device is decrypted, and the information
`obtained from each write is encrypted. Preferably, the req- 40
`uisite secret key is not present on the storage device; rather,
`it resides in memory when the machine is in use, and it
`resides nowhere in the computing system when the machine
`is not in use.
`More specifically, securing the computer's sensitive infor(cid:173)
`mation and data is achieved by using a cryptographic object,
`called a "length-increasing pseudorandom function," which
`is a function of the secret key and an index that determines
`where in the storage device the particular data is stored. The
`result of that evaluation is a pseudorandom bit string that so
`will have a length equal to the area of the storage device in
`which the data will be stored. If the storage device is a hard
`disk drive, the area is a "sector." Data to be stored in the
`sector is then encrypted with the pseudorandom bit string
`(typically by XORing the bit string with the plaintext) to 55
`derive the ciphertext, which is then stored.
`By way of brief background, a computer for use in
`supporting the invention tool is shown in FIG. 1. The
`computer 20 comprises a system unit 21, a keyboard 22, a
`mouse 23 and a display 24. The screen Ui of display device 60
`24 is used to present a graphical user interface (GUI). The
`graphical user interface supported by the operating system
`allows the user to use a point and shoot method of input, i.e ..
`by moving the mouse pointer 25 to an icon representing a
`data object at a particular location on the screen 26 and 65
`pressing on the mouse buttons to perform a user command
`or selection.
`
`4
`FIG. 2 shows a block diagram of the components of the
`personal computer shown in FIG. 1. The system unit 21
`includes a system bus or plurality of system buses 31 to
`which various components are coupled and by which com-
`munication between the various components is accom(cid:173)
`plished. The microprocessor 32 is connected to the system
`bus 31 and is supported by read only memory (ROM) 33 and
`random access memory (RAM) 34 also connected to system
`bus 31. A microprocessor in the ffiM PS/2 series of com-
`puters is one of the Intel family of microprocessors includ(cid:173)
`ing the 386 or 486 microprocessors. Other microprocessors
`included, but not limited to, Motorola's family of micro-
`processors such as the 68000, 68020 or the 68030 micro(cid:173)
`processors and various RISC microprocessors such as the
`PowerPCTM microprocessor manufactured by IBM, and oth(cid:173)
`ers made by Hewlett Packard, Sun, Intel, Motorola and
`others may be used in the specific computer.
`The ROM 33 contains among other code the Basic
`Input-Output system (BIOS) which controls basic hardware
`20 operations such as the interaction and the disk drives and the
`keyboard. The RAM 34 is the main memory into which the
`operating system and application programs are loaded. The
`memory management chip 35 is connected to the system bus
`31 and controls direct memory access operations including,
`25 passing data between the RAM 34 and hard disk drive 36
`and floppy disk drive 37. The CD ROM 42. also coupled to
`the system bus 31, is used to store a large amount of data,
`e.g., a multimedia program or large database.
`Also connected to this system bus 31 are various J/0
`30 controllers: the keyboard controller 38, the mouse controller
`39, the video controller 40, and the audio controller 41. The
`keyboard controller 38 provides the hardware interface for
`the keyboard 22, the mouse controller 39 provides the
`hardware interface for the mouse 23, the video controller 40
`35 is the hardware interface for the display 24, and the audio
`controller 41 is the hardware interface for the speakers 25a
`and 25b. An J/0 controller 50 such as a Token Ring Adapter
`enables communication over the local area network 56 to
`other similarly configured data processing systems.
`One of the preferred implementations of the present
`invention is as a set of instructions in a code module resident
`in the random access memory 34. Until required by the
`computer system, the set of instructions may be stored in
`another computer memory, for example, in the hard disk
`45 drive 36. or in a removable memory such as an optical disk
`for eventual use in the CD ROM 42 or a in a floppy disk for
`eventual use in the floppy disk drive 37. As shown in FIG.
`2, the operating system 60 and the presentation manager 62
`are resident in RAM 34.
`According to the invention, the contents of the data
`storage device (such as hard disk drive 36) are protected
`from unauthorized disclosure of its information through the
`use of a pseudorandom function keyed using a user-derived
`secret and evaluated at the position of a data block within the
`data storage device in order to determine a mask which is
`XORed or otherwise combined with the data stored at that
`location. Generally, the invention envisions the use of a
`length-preserving cipher where the ciphertext depends not
`only on the plaintext (i.e., the data to be secured) and the key
`but also on the plaintext's position or index; namely
`(plaintext, f_,,..r~re, (index)). Thus, for example, one might
`use the cipher block chaining of a block cipher, with the
`initialization vector thereof specifying the sector position. A
`stream cipher of similar structure and function is thus useful
`in the present invention.
`In one embodiment, the invention is a device driver that
`transparently encrypts and decrypts all accesses to and from
`
`NETAPP ET AL. EXHIBIT 1005
`Page 6 of 11
`
`

`
`5,677,952
`
`5
`the disk 36. In this application, the secret key is a bit string
`that is derived from a password P u that a user u enters when
`he or she turns his machine on. As an example, one might
`select a=SHA(p")$1(,., with K,. being a 160-bit string asso(cid:173)
`ciated to user u and stored on the machine's disk. "SHA" 5
`refers to the Secure Hash Algorithm described in National
`Institute of Standards. "Secure Hash Standard," Federal
`Information Processing Standards Publication 180, which is
`incorporated herein by reference. When the operating sys(cid:173)
`tem tries to read the i-th sector from the hard disk. the data 10
`there (i.e., a string x) is read and then decrypted by XOR-ing
`it with a length-increasing pseudorandom function fa evalu(cid:173)
`ated at "i" (i.e., the sector number). As many bits of the
`pseudorandom function are used as a sector is long.
`Similarly, when the operating system tries to write the i-th 15
`sector, the data to be written is first encrypted by XOR-ing
`with fa(i). In the event that there is more than one disk whose
`contents are to be encrypted, indices are selected for each
`disk such that no two sectors receive the same index.
`F1G. 3 illustrates a portion of the computer of FlG. 1 20
`showing the pseudorandom function supported in a device
`driver to facilitate such disk encryption. As used herein, the
`term "device driver" also includes terminate and stay(cid:173)
`resident programs. In this example, the computer supports
`the device driver 76 that intercepts read or write calls 25
`directed to a mass storage device, in this case the hard disk
`36 of the computer of F1G. 2. The read/write calls are
`communicated to the device driver 76 from the operating
`system 78. The operating system supports a login utility 80
`that receives the password P u that the user enters when he 30
`turns the computer on. The login utility hands off the
`password to the key processing utility 82 that generates an
`efficient representation of the secret key to enable
`computationally-fast generation of a pseudorandom bit
`string that is used to secure the information intended for or 35
`retreived from the sector. In one embodiment, the efficient
`representation is one or more tables of pseudorandom num(cid:173)
`bers that are then are supplied to the pseudorandom function
`84. Function 84 then encrypts the disk data via the encryp(cid:173)
`tion function 86, usually an XOR.
`The particular details of the preferred embodiment can
`now be described in greater detail. When the user installs the
`product, it queries him for a password P u and possibly a user
`name and other usercheck data. Information dependent on
`the user password is then combined with (non-secret) infor- 45
`mation (e.g., a mask associated to the user and an instance
`identification for the product) to determine a secret key, a,
`for the user. More particularly, the mask may depend on a
`value identification (ID) stored on the machine's disk (in the
`clear), where the ID is unique to each machine and may be so
`a random number or a device serial number. The mask may
`depend on information stored (in the clear) on the disk and
`that is associated to the particular user. Or the mask may
`depend on user-associated check information used in such a
`way that the mask will evaluate to "invalid" if the entered 55
`password does not recover the correct key. The secret key
`can also be generated using a slow-to-compute function.
`Such processing insures that an attacker cannot assemble a
`generally-useful dictionary of secret keys corresponding to
`commonly-selected passwords.
`The secret key a is processed by the computing system to
`convert it into an efficient representation of a cipher spe(cid:173)
`cialized to a, namely fa. The cipher fa is a "length-increasing
`pseudorandom function" that takes a relatively short index i
`and maps it into a long sequence of bytes, as many bytes as 65
`there are bytes in one sector of the disk 36. A one-way
`function of the secret key a is installed on the mass storage
`
`6
`device to allow the key processing unit to distinguish correct
`and incorrect passwords. However, preferably the password
`itself is not saved after installation.
`Each sector in the range over which the user wishes to
`have information information kept private is then subjected
`to the following processing. When the string x at position i
`of the disk is read, the value fa(i) is computed by the
`computing system. These steps may be carried out concur(cid:173)
`rently. A value y is computed by XORing or otherwise
`combining x and foCi). The value y replaces the previous
`value x for the contents of the sector. This completes the
`installation of the program.
`Later, when the user performs a machine logon or other(cid:173)
`wise initiates a session with the machine, the following
`processing takes place. The authorized user first enters a
`password, and possibly a user name and other data. Again,
`this information, possibly combined with other (non-secret)
`information stored in the computing system, determines the
`secret key. The secret key is then subjected to processing in
`the computing system to convert it into an efficient repre(cid:173)
`sentation of a cipher specialized to a, namely fa. The
`password is verified by checking a one-way function of "a"
`against information stored in the computing device. If the
`password is incorrect, logon is denied; otherwise, logon is
`accepted. This completes the logon operation.
`As noted above, at some time after logon and in response
`to a read command, the operating system will attempt to read
`the i-th sector from the disk. where information has been
`stored in encrypted form. When this occurs, the software
`computes fa(i), which can be done quickly because the secret
`key has already been preprocessed into an efficient repre(cid:173)
`sentation of fa. The underlying hardware then retrieves the
`contents of the i-sector of the disk. namely "ciphertext" y.
`This operation may be concurrent with the fa(i) computa(cid:173)
`tion. The value y returned as a result of the read is XORed
`with fa(i) to determine the "plaintext" x. Or, the ciphertext
`and fa(i) may be combined in some other way to determine
`X.
`
`At some point in time after logon and in response to a
`40 write command, the operating system will attempt to write
`the contents of the i-th sector from the disk, where infor(cid:173)
`mation for this sector is to be stored in encrypted form.
`When this occurs, the software computes fa(i), and then
`computes the ciphertext y which is the XOR of x and fa(i).
`Or these strings are otherwise combined to determine the
`ciphertext. The computing system then writes the string y to
`the position at i.
`The efficient representation of fa, the function that pro(cid:173)
`duces pseudorandom bit string for each sector index, and
`any other information (e.g., the secret key) useful in encrypt(cid:173)
`ing and decrypting disk accesses, is preferably stored in
`volatile memory when the machine is in use under the
`contrOl of an authorized user. When the authorized user logs
`off, powers off, locks the computer, or when a predetermined
`timeout occurs (e.g., a time period during which no user
`interaction with the machine has occurred), the efficient
`representation of fa and such other information. is erased.
`In a preferred embodiment, the inventive scheme is
`implemented as low-level software and, as noted above, may
`60 be a device driver or terminate-stay-resident program. On a
`machine like an ffiM PS/1 or PS/2. which use the BIOS
`(Basic Input Output System) for low-level disk operations,
`the software can be latched into the interrupt chain and
`associated with the interrupts that are used to gain read and
`write access to the hard disk.
`If desired, the encrypting software is located in a device
`driver and encryption occurs on specified partitions; ele-
`
`NETAPP ET AL. EXHIBIT 1005
`Page 7 of 11
`
`

`
`5,677,952
`
`8
`preferred, the length-increasing pseduorandom function is
`appropriate to any general purpose 32-bit processor.
`As noted above. the pseudorandom function is a crypto(cid:173)
`graphic "object" that preferably maps a relatively short (e.g.,
`5 32 bits) index "i" and a secret key a to an pseudorandom bit
`sequence fa(i). For f to be called a pseudorandom function,
`it must be impossible for the attacker, who does not know
`"a," to distinguish fa(i) from a random function of i. To
`create the "efficient representation" of the secret key. the key
`is preprocessed into a table of pseudorandom values. The
`index (i.e., the sector identification) and a set of values from
`a table is then used to generate initial values for a plurality
`of registers. Using a predetermined mixing function, the
`initial values of some of the registers are then modified in
`part by taking a current value of a register and replacing the
`15 current value with a function of the current value and a value
`retrieved from the table, the latter value being determined by
`portions of one or more other registers. After modifying the
`registers in this fashion, their resulting values are masked
`using other pseudorandom values derived from the tables
`20 and a predetermined masking function. The masked register
`values are then concatenated into the pseudorandom bit
`string to complete an iteration. Subsequent iterations are
`performed to grow the pseudorandom bit string to a desired
`length, in this case, the length of the disk sector.
`With particular reference now to FIG. 4, a process flow
`~
`diagram. as described in Ser. No. 081163.054. filed Dec. 6.
`1993, now U.S. Pat. No. 5.454,039. is shown detailing a
`method for mapping a 32-bit index ''n" to an L-bit string
`y=SEALa(n) under the control of a set of tables T, R and S
`30 generated from a key "a." The method begins by prepro(cid:173)
`cessing the key "a" into preferably three (3) tables T. R and
`S. This step is effected using a Make Table procedure 10
`which receives as an input the key "a." In this particular
`example, the key is a 160-bit string that. in conjunction with
`a function G described below, is used to define the three
`35 tables.
`The pseudorandom values in the tables are specified using
`any one or more algorithms known in the art. The particular
`algorithm used is not critical and it is envisioned that any
`secure pseudorandom generator is useful for this purpose.
`The pseudorandom generator thus may be derived from a
`secure hash algorith.m. a block cipher, a stream cipher. and
`so on. For example, the algorithm used to generate the tables
`could be based on DES, MD5, the Secure Hash Algorithm
`(SHA) or even a combination of any of the above. According
`to the illustrative embodiment, the function G is descnbed in
`National Institute of Standards, "Digital Signature
`Standard," Federal Information Processing Standards Pub(cid:173)
`lication XX Draft-February 1993, which is incotpOrated
`herein by reference.
`With the ke~ "a" being a 160-bit string and i being an
`integer, O~i<2 2
`, Gii) is a 160-bit value. To construct the
`tables, G is re-iodexed by the Make Table procedure 10 to
`construct a function whose images are 32-bit words instead
`of 160-bit ones. The function r is defined by ra(i)=Hiimods
`where H;0 H;1H;2H;3 H;4=Gad..i!5.b. Thus a table ofr-values
`is a table for G-values read left-to-right. top-to-bottom. The
`Make Tables procedure 10 then preferably defines the tables
`as follows:
`
`55
`
`7
`ments of the operating system that load before the device
`driver reside in a non-encrypted partition. In another
`embodiment, the boot sector of the machine is modified and
`all sectors. except the boot sector and the sectors containing
`the algorithm itself, are encrypted.
`Preferably. it is desired that an authorized user have the
`ability to change his or her password, but that the high(cid:173)
`overhead operation of encrypting the entire disk should be
`performed only at install time and not during password
`change. This is achieved as follows. During installation as 10
`described above. a strong password or a sequence of unpre(cid:173)
`dictable bits is determined. This password or these bits
`determine the secret key a that is used to encrypt the disk
`according to the function fa.
`When the user u types a password which leads to key a.,.
`the record (u, a .. G:)a) is stored on the disk. When the user u
`presents his password at some later time, a., is determined
`and XORed with the value a,.. G:)a stored on disk to recover
`a. which is then used to encrypt and decrypt the disk. If the
`user wishes to change his password from p., to p.,', where p,..
`maps to key a,.. and p.,' maps to key a,..', all that needs to be
`done is to replace the record (u, a,. $a) by (u, (a., G:)a)ffi(a,.
`ffia,.')). Thereafter, the routine recovers a from a,.' and (u,
`a..'ffia) in the same way as it recovers a from a,.. and (u. a,..
`~
`Similar processing can be used to allow multiple users to
`share the computer, and each user can separately change his
`or her password. When multiple users share the computer, it
`is not always necessary to have a user specify his identity u
`at logon time. Rather, at logon, each record (u, a,. $a) can
`be tried and, if any record yields a.key a that recovers the
`disk contents, the user is allowed on end the function fa is
`appropriately constructed.
`Nontrivial password processing (the function from the
`password P .. that u types to a..) is useful in protecting the
`encryption against brute force attacks, e.g., an attacker who
`steals the computer and then has the time to test millions of
`passwords. One useful approach to frustrate such an attack
`is to apply to the password p., a slow-to-compute one-way 40
`function. The resulting data string is then used to create the
`secret key. Although such an approach does not materially
`impact operating efficiency from the user'