University of Pennsylvania
`ScholarlyCommons
`
`Technical Reports (CIS)
`
`Department of Computer & Information Science
`
`August 1997
`
`Automated Recovery in a Secure Bootstrap Process
`
`William A. Arbaugh
`University of Pennsylvania
`
`Angelos D. Keromytis
`University of Pennsylvania
`
`David J. Farber
`University of Pennsylvania
`
`Jonathan M. Smith
`University of Pennsylvania, jms@cis.upenn.edu
`
`Follow this and additional works at: http://repository.upenn.edu/cis_reports
`
`Recommended Citation
`Arbaugh, William A.; Keromytis, Angelos D.; Farber, David J.; and Smith, Jonathan M., "Automated Recovery in a Secure Bootstrap
`Process" (1997). Technical Reports (CIS). Paper 85.
`http://repository.upenn.edu/cis_reports/85
`
`University of Pennsylvania Department of Computer and Information Science Technical Report No. MS-CIS-97-13.
`
`This paper is posted at ScholarlyCommons. http://repository.upenn.edu/cis_reports/85
`For more information, please contact repository@pobox.upenn.edu.
`
`1
`
`EX 1006
`IPR of Pat. No. 6,892,304
`
`

`
`Automated Recovery in a Secure Bootstrap Process
`
`Abstract
`Integrity is rarely a valid presupposition in much systems architecture, yet it is necessary to make any security
`guarantees. To address this problem, we have designed a secure bootstrap process, AEGIS, which presumes a
`minimal amount of integrity, and which we have prototyped on the Intel x86 architecture. The basic principle
`is sequencing the bootstrap process as a chain of progressively higher levels of abstraction, and requiring each
`layer to check a digital signature of the next layer before control is passed to it. A major design decision is the
`consequence of a failed integrity check. A simplistic strategy is to simply halt the bootstrap process. However,
`as we show in this paper, the AEGIS bootstrap process can be augmented with automated recovery
`procedures which preserve the security properties of AEGIS under the additional assumption of the
`availability of a trusted repository. We describe a variety of means by which such a repository can be
`implemented, and focus our attention on a network accessible repository. The recovery process is easily
`generalized to applications other than AEGIS, such as standardized desktop management and secure
`automated recovery of network elements such as routers or "Active Network" elements.
`
`Comments
`University of Pennsylvania Department of Computer and Information Science Technical Report No. MS-
`CIS-97-13.
`
`This technical report is available at ScholarlyCommons: http://repository.upenn.edu/cis_reports/85
`
`2
`
`

`
`Automated Recovery in a Secure Bootstrap Process
`
`William A. Arbaugh
`Angelos D. Keromytis
`David J. Farber
`Jonathan M. Smith
`University of Pennsylvania
`Distributed Systems Laboratory
`Philadelphia, PA. 19104-6389
`@dsl.cis.upenn.edu
` waa, angelos, farber, jms
`MS-CS-97-13
`
`August 1, 1997
`
`Abstract
`
`Integrity is rarely a valid presupposition in many sys-
`tems architectures, yet it is necessary to make any security
`guarantees. To address this problem, we have designed a
`secure bootstrap process, AEGIS, which presumes a min-
`imal amount of integrity, and which we have prototyped
`on the Intel x86 architecture. The basic principle is se-
`quencing the bootstrap process as a chain of progressively
`higher levels of abstraction, and requiring each layer to
`check a digital signature of the next layer before con-
`trol is passed to it. A major design decision is the con-
`sequence of a failed integrity check. A simplistic strat-
`egy is to simply halt the bootstrap process. However, as
`we show in this paper, the AEGIS bootstrap process can
`be augmented with automated recovery procedures which
`preserve the security properties of AEGIS under the ad-
`ditional assumption of the availability of a trusted repos-
`itory. We describe a variety of means by which such a
`repository can be implemented, and focus our attention
`on a network-accessible repository. The recovery process
`
` Smith and Farber’s work is supported by DARPA under Contracts
`
`#DABT63-95-C-0073, #N66001-96-C-852, and #MDA972-95-1-0013
`with additional support from the Hewlett-Packard and Intel Corpora-
`tions.
`
`is easily generalized to applications other than AEGIS,
`such as standardized desktop management and secure au-
`tomated recovery of network elements such as routers or
`”Active Network” elements.
`
`1
`
`Introduction
`
`Systems are organized as layered levels of abstraction, in
`effect defining a series of virtual machines. Each virtual
`machine presumes the correctness (integrity) of whatever
`virtual or real machines underlie its own operation. With-
`out integrity, no system can be made secure, and con-
`versely, any system is only as secure as the foundation
`upon which it is built. Thus, without such a secure boot-
`strap the operating system kernel cannot be trusted since
`it is invoked by an untrusted process. We believe that
`designing trusted systems by explicitly trusting the boot
`components provides a false sense of security to the users
`of the operating system, and more important, is unneces-
`sary.
`We have previously reported[AFS97] the design and
`preliminary implementation results for AEGIS, a secure
`bootstrap process. AEGIS increases the security of the
`boot process by ensuring the integrity of bootstrap code.
`
`1
`
`3
`
`
`

`
`1 INTRODUCTION
`
`2
`
`It does this by constructing a chain of integrity checks, be-
`ginning at power-on and continuing until the final transfer
`of control from the bootstrap components to the operating
`system itself. The integrity checks compare a computed
`cryptographic hash value with a stored digital signature
`associated with each component.
`The AEGIS model relies explicitly on three assump-
`tions:
`
`1. The motherboard, processor, and a portion of the sys-
`tem ROM (BIOS) are not compromised, i.e., the ad-
`versary is unable or unwilling to replace the mother-
`board or BIOS.
`
`2. Existence of a cryptographic certificate authority in-
`frastructure to bind an identity with a public key, al-
`though no limits are placed on the type of infrastruc-
`ture.
`
`3. A trusted source exists for recovery purposes. This
`source may be a host on a network that is reachable
`through a secure communications protocol, or it may
`be a trusted ROM card located on the protected host.
`
`The AEGIS architecture, which we outline below in
`Section 2, includes a recovery mechanism for repairing
`integrity failures protecting against some classes of denial
`of service attacks. An added benefit of the recovery mech-
`anism is the potential for reducing the Total Cost Oper-
`ation (TCO) of a computer system by reducing trouble
`calls and down time associated with failures of the boot
`process.
`From the start, AEGIS has been targeted for commer-
`cial operating systems on commodity hardware, making it
`a practical “real-world” system. In AEGIS, the boot pro-
`cess is guaranteed to end up in a secure state, even in the
`event of integrity failures outside of a minimal section of
`trusted code.
`We define a guaranteed secure boot process in two
`parts. The first is that no code is executed unless it is
`either explicitly trusted or its integrity is verified prior to
`its use. The second is that when an integrity failure is
`detected a process can recover a suitable verified replace-
`ment module. This recovery process is the focus of the
`current paper.
`
`1.1 Responses to integrity failure
`
`When a system detects an integrity failure, one of three
`possible courses of action can be taken.
`The first is to continue normally, but issue a warning.
`Unfortunately, this may result in the execution or use of
`either a corrupt or malicious component.
`The second is to not use or execute the component. This
`approach is typically called fail secure, and creates a po-
`tential denial of service attack.
`The final approach is to recover and correct the incon-
`sistency from a trusted source before the use or execution
`of the component.
`The first two approaches are unacceptable when the
`systems are important network elements such as switches,
`intrusion detection monitors, or associated with electronic
`commerce, since they either make the component unavail-
`able for service, or its results untrustworthy.
`
`1.2 Goals
`
`There are six main goals of the AEGIS recovery protocol.
`
`1. Allow the AEGIS client and the trusted repository to
`mutually authenticate their identities with limited or
`no prior contact (mobility between domains).
`
`2. Prevent man in the middle attacks.
`
`3. Prevent replay attacks.
`
`4. Mitigate certain classes of denial of service attacks.
`
`5. Allow the participating parties to agree upon a shared
`secret in a secure manner in order to optimize future
`message authentication.
`
`6. Be as simple as possible: Complexity breeds design
`and implementation vulnerabilities.
`
`1.3 Outline of the Paper
`
`In Section 2, we make the goals of the AEGIS design ex-
`plicit. Sections 3, 4, and 5 form the core of the paper, giv-
`ing an overview of AEGIS, and the IBM PC boot process.
`Section 4 provides an introduction to the cryptographic
`and system tools needed to build a secure recovery pro-
`tocol, and describes such a protocol. Section 5 describes
`
`4
`
`

`
`2 AEGISARCHITECTURE
`
`3
`
`the details of adding the recovery protocol to existing Dy-
`namic Host Configuration Protocol (DHCP), and Trivial
`File Transfer Protocol (TFTP) implementations and pro-
`vides performance information. We discuss the system
`status and our next steps in section 6, and conclude the
`paper in section 7.
`
`2 AEGIS Architecture
`
`2.1 Overview
`
`To have a practical impact, AEGIS must be able to work
`with commodity hardware with minimal changes (ideally
`none) to the existing architecture. The IBM PC archi-
`tecture was selected as our prototype platform because
`of its large user community and the availability of the
`source code for several operating systems. We also use
`the FreeBSD operating system, but the AEGIS architec-
`ture is not limited to any specific operating system. Port-
`ing to a new operating system only requires a few minor
`changes to the boot block code so that the kernel can be
`verified prior to passing control to it. Since the verifica-
`tion code is contained in the BIOS, the changes will not
`substantially increase the size of the boot loader, nor the
`boot block.
`AEGIS modifies the boot process shown in figure 1 so
`that all executable code, except for a very small section
`of trusted code, is verified prior to execution by using a
`digital signature. This is accomplished through modifi-
`cations and additions to the BIOS. The BIOS contains the
`verification code, and public key certificate(s). In essence,
`the trusted software serves as the root of an authentication
`chain that extends to the operating system and potentially
`beyond to application software [PG89] [GDM89] [Mic].
`In the AEGIS boot process, either the operating system
`kernel is started, or a recovery process is entered to repair
`any integrity failure detected. Once the repair is com-
`pleted, the system is restarted to ensure that the system
`boots. This entire process occurs without user interven-
`tion.
`In addition to ensuring that the system boots in a se-
`cure manner, AEGIS can also be used to maintain the
`hardware and software configuration of a machine. Since
`AEGIS maintains a copy of the signature for each expan-
`
`sion card1, any additional expansion cards will fail the in-
`tegrity test. Similarly, a new operating system cannot be
`started since the boot block would change, and the new
`boot block would fail the integrity test.
`
`2.2 AEGIS Boot Process
`
`Every computer with the IBM PC architecture follows ap-
`proximately the same boot process. We have divided this
`process into four levels of abstraction (see figure 1), which
`correspond to phases of the bootstrap operation. The first
`phase is the Power on Self Test or POST [Ltd91]. POST
`is invoked in one of four ways:
`
`1. Applying power to the computer automatically in-
`vokes POST causing the processor to jump to the en-
`try point indicated by the processor reset vector.
`
`2. Hardware reset also causes the processor to jump to
`the entry point indicated by the processor reset vec-
`tor.
`
`3. Warm boot (ctrl-alt-del under DOS) invokes POST
`without testing or initializing the upper 64K of sys-
`tem memory.
`
`4. Software programs, if permitted by the operating
`system, can jump to the processor reset vector.
`
`In each of the cases above, a sequence of tests are con-
`ducted. All of these tests, except for the initial processor
`self test, are under the control of the system BIOS.
`Once the BIOS has performed all of its power on tests,
`it begins searching for expansion card ROMs which are
`identified in memory by a specific signature. Once a valid
`ROM signature is found by the BIOS, control is immedi-
`ately passed to it. When the ROM completes its execu-
`tion, control is returned to the BIOS.
`The final step of the POST process calls the BIOS op-
`erating system bootstrap interrupt (Int 19h). The boot-
`strap code first finds a bootable disk by searching the
`disk search order defined in the CMOS. Once it finds a
`bootable disk, it loads the primary boot block into mem-
`ory and passes control to it. The code contained in the
`boot block proceeds to load the operating system, or a
`
`1Ideally, the signature would be embedded in the firmware of the
`ROM.
`
`5
`
`

`
`2 AEGISARCHITECTURE
`
`4
`
`secondary boot block depending on the operating sys-
`tem [Gri93] [Eli96] or boot loader [Alm96].
`Ideally, the boot process would proceed in a series of
`levels with each level passing control to the next until
`the operating system kernel is running. Unfortunately, the
`IBM architecture uses a “star like” model which is shown
`in figure 1.
`
`Operating System
`
`Level 4
`
`Boot Block
`
`Expansion ROMs
`
`Level 3
`Expansion ROMs
`
`Level 2
`
`Level 1
`
`System BIOS
`
`Initiate POST
`
`Figure 1: IBM PC boot process
`
`2.2.1 A Layered Boot Process
`
`We have divided the boot process into several levels to
`simplify and organize the AEGIS BIOS modifications, as
`shown in figure 2. Each increasing level adds functional-
`ity to the system, providing correspondingly higher lev-
`els of abstraction. The lowest level is Level 0. Level 0
`contains the small section of trusted software, digital sig-
`natures, public key certificates, and recovery code. The
`integrity of this level is assumed to be valid. We do, how-
`ever, perform an initial checksum test to identify PROM
`failures. The first level contains the remainder of the usual
`BIOS code, and the CMOS. The second level contains
`all of the expansion cards and their associated ROMs, if
`any. The third level contains the operating system boot
`block(s). These are resident on the bootable device and
`
`are responsible for loading the operating system kernel.
`The fourth level contains the operating system, and the
`fifth and final level contains user level programs and any
`network hosts.
`The transition between levels in a traditional boot pro-
`cess is accomplished with a jump or a call instruction
`without any attempt at verifying the integrity of the next
`level. AEGIS, on the other hand, uses public key cryptog-
`raphy and cryptographic hashes to protect the transition
`from each lower level to the next higher one, and its re-
`covery process ensures the integrity of the next level in the
`event of failures. The pseudo code for the action taken at
`each level,
`, before transition to level
`is:
`
` 
`if (IntegrityValid(L+1))) {
`GOTO(L+1);
`} else {
`GOTO(Recovery);
`
`}.
`
`2.2.2 AEGIS BIOS Modifications
`
`AEGIS modifies the boot process shown in figure 1 by
`dividing the BIOS into two logical sections. The first sec-
`tion contains the bare essentials needed for integrity veri-
`fication and recovery. It comprises the “trusted software”.
`The second section contains the remainder of the BIOS
`and the CMOS.
`The first section executes and performs the standard
`checksum calculation over its address space to protect
`against ROM failures. Following successful completion
`of the checksum, the cryptographic hash of the second
`section is computed and verified against a stored signa-
`ture. If the signature is valid, control is passed to the sec-
`ond section, i.e., Level 1.
`The second section proceeds normally with one
`change. Prior to executing an expansion ROM, a cryp-
`tographic hash is computed and verified against a stored
`digital signature for the expansion code. If the signature
`is valid, then control is passed to the expansion ROM.
`Once the verification of each expansion ROM is complete
`(Level 2), the BIOS passes control to the operating sys-
`tem bootstrap code. The bootstrap code was previously
`verified as part of section 2 of the BIOS, and thus no fur-
`ther verification is required. The bootstrap code finds the
`bootable device and verifies the boot block.
`
`6
`
`
`

`
`2 AEGISARCHITECTURE
`
`5
`
`Assuming that the boot block is verified successfully,
`control is passed to it (Level 3). If a secondary boot block
`is required, then it is verified by the primary block before
`passing control to it. Finally, the kernel is verified by the
`last boot block in the chain before passing control to it
`(Level 4).
`Any integrity failures identified in the above process
`are recovered through a trusted repository.
`
`2.3 Integrity Policy
`
`Formalizing the discussion in Section 1.1, the AEGIS in-
`tegrity policy prevents the execution of a component if
`its integrity can not be validated. There are three reasons
`why the integrity of a component could become invalid.
`The first is the integrity of the component could change
`because of some hardware or software malfunction, or
`it could change because of some malicious act. Finally,
`the component’s certificate timestamp may no longer be
`valid. In each case, the client MUST attempt to recover
`from a trusted repository. Should a trusted repository be
`unavailable after several attempts, then the client’s fur-
`ther action depends on the security policy of the user. For
`instance, a user may choose to continue operation in a
`limited manner, or they may choose to halt operations al-
`together.
`The AEGIS Integrity Policy can be represented by the
`following pseudo code:
`
`StartOver:
`if (ComponentCertificateValid) {
`if (ComponentIntegrityValid) {
`continue;
`} elseif (Recover(Component)) {
`continue;
`} else {
`User_Policy();
`
`}
`} else if (Recover(Certificate)) {
`goto StartOver;
`} else {
`UserPolicy();
`
`}
`
`}
`
`2.4 Trusted Repository
`
`The trusted repository can either be an expansion ROM
`board that contains verified copies of the required soft-
`ware, or it can be a network host.
`If the repository is
`a ROM board, then simple memory copies can repair or
`shadow failures. If the repository is a network host, then
`a protocol with strong authentication is required
`In the case of a network host, the detection of an in-
`tegrity failure causes the system to boot into a recovery
`kernel contained on the network card ROM. The recovery
`kernel contacts a “trusted” host through the secure pro-
`tocol described in this paper to recover a signed copy of
`the failed component. The failed component is then shad-
`owed or repaired, and the system is restarted (warm boot).
`The resultant AEGIS boot process is shown in fig-
`ure 2. Note that when the boot process enters the recov-
`ery procedure it becomes isomorphic to a secure network
`boot. We leverage this fact by adding authentication to the
`well known network protocols supporting the boot pro-
`cess DHCP[Dro97], and TFTP[Fin84] and using them as
`our recovery protocol.
`
`Network Host
`
`User Programs
`
`Operating System
`
`Boot Block
`
`Expansion ROMs
`
`AEGIS ROM
`
`BIOS Section 2
`
`BIOS Section 1
`
`Initiate POST
`
`Level 0
`
`Level 5
`
`Level 4
`
`Level 3
`
`Level 2
`
`Level 1
`
`Legend
`Control Transition
`Recovery Transition
`
`Figure 2: AEGIS boot control flow
`
`7
`
`

`
`3 AEGISNETWORKRECOVERYPROTOCOL
`
`6
`
`3 AEGIS Network Recovery Proto-
`col
`
`The AEGIS network recovery protocol combines proto-
`cols and algorithms from networking and cryptography
`to ensure the security of the protocol. This section first
`provides an introduction to the material needed to fully
`understand the recovery protocol. We then describe the
`protocol and provide examples of its use.
`
`((cert (issuer (hash-of-key (hash sha1
`cakey)))
`(subject (hash-of-key (hash sha1
`keyholderkey)))
`(tag (client))
`(not-before 03/29/97-0000)
`(not-after 03/29/98-0000))
`(signature (hash sha1 hashbytes)
`(hash-of-key (hash sha1 cakey))
`(sigbytes)))
`
`3.1 Certificates
`
`The usual purpose of a certificate with respect to public
`key cryptography is to bind a public key with an identity.
`While this binding is essential for strong authentication,
`it severely limits the potential of certificates, e.g. anony-
`mous transactions. The most widely used certificate stan-
`dard, the X.509[Com89] and its variants, provide only this
`binding. The X.509 standard, also, suffers from other se-
`rious problems in addition to its limited use. The most
`significant is ambiguity in the parsing of compliant cer-
`tificates because of its use of the Basic Encoding Rules
`(BER)[Com88]. The encoding rules also require a great
`deal of space to implement, and the encoded certificates
`are usually large.
`Because of the limits and problems with the X.509
`certificate standard, we use a subset of the proposed
`SDSI/SPKI 2.0 certificate structure[EFRT97][Ell97] in-
`stead. The SDSI/SPKI format does not suffer from the
`same problems as X.509, and it offers additional func-
`tionality.
`
`3.1.1 SDSI/SPKI Lite
`
`Since the SDSI/SPKI standard is still under development,
`we have chosen to support the small subset of SDSI/SPKI
`needed for AEGIS. We call this subset SDSI/SPKI Lite.
`SDSI/SPKI provides for functionality beyond the sim-
`ple binding of an identity with a public key. Identity based
`certificates require the existence of an Access Control List
`(ACL) which describe the access rights of an entity. Main-
`taining such lists in a distributed environment is a com-
`plex and difficult task. In contrast, SDSI/SPKI provides
`for the notion of a capability [Lev84].
`In a capability
`based model, the certificate itself carries the authoriza-
`tions of the holder eliminating the need for an identity
`
`Figure 3: AEGIS Authorization Certificate
`
`infrastructure and access control lists. In AEGIS, we use
`two capabilities: SERVER, and CLIENT with the obvious
`meanings.
`In AEGIS we only use three types of certificates. The
`first is an authorization certificate. This certificate, signed
`by a trusted third party or certificate authority, grants to
`the keyholder (the machine that holds the private key)
`the capability to generate the second type of certificate-
`an authentication certificate. The authentication certifi-
`cate demonstrates that the client or server actually hold
`the private key corresponding to the public key identified
`in the authentication certificate. The nonce field is used
`along with a corresponding nonce in the server authenti-
`cation certificate to ensure that the authentication proto-
`col is “Fail Stop”[GS95] detecting and preventing active
`attacks such as a man–in–the–middle. The msg-hash field
`ensures that the entire message containing the certificates
`has not been modified. Using the msg-hash in the authen-
`tication certificate eliminates a signature and verification
`operation since the entire message no longer needs to be
`signed. The additional server fields are used to pass op-
`tional Diffie-Helman parameters to the client so that these
`parameters need not be global values. While clients are
`free to set the validity period of the authentication certifi-
`cate to whatever they desire, we expect that clients will
`keep the period short. Examples of these certificates are
`shown in figures 3 , 4, and 5. The third and final certifi-
`cate format is the component signature certificate shown
`in figure 6. This certificate is either embedded in a com-
`ponent or stored in a table. It is used with the AEGIS boot
`process described earlier in this paper.
`
`8
`
`

`
`3 AEGISNETWORKRECOVERYPROTOCOL
`
`7
`
`((cert (issuer (hash-of-key (hash sha1
`clientkey)))
`(subject (hash-of-key (hash sha1
`clientkey)))
`(tag (client (cnonce cbytes)
`(msg-hash
`(hash sha1 hbytes))))
`(not-before 09/01/97-0000)
`(not-after 09/01/97-0000))
`(signature (hash sha1 hashbytes)
`(public-key dsa-sha1 clientkey)
`(sigbytes)))
`
`Figure 4: AEGIS Client Authentication Certificate
`
`((cert (issuer (hash-of-key (hash sha1
`serverkey)))
`(subject (hash-of-key (hash sha1
`serverkey)))
`(tag (server (dh-g gbytes)
`(dh-p pbytes)
`(dh-Y ybytes)
`(msg-hash
`(hash sha1 hbytes))
`(cnonce cbytes)
`(snonce sbytes)))
`(not-before 09/01/97-0900)
`(not-after 09/01/97-0900))
`(signature
`(hash sha1 hashbytes)
`(public-key dsa-sha1 serverkey)
`(sigbytes)))
`
`Figure 5: AEGIS Server Authentication Certificate
`
`((cert (issuer (hash-of-key (hash sha1
`approverkey)))
`(subject (hash sha1
`hashbytes))
`(not-before 09/01/97-0000)
`(not-after 09/05/97-0000))
`(signature (hash sha1
`hashbytes)
`(public-key dsa-sha1
`approverkey)
`(sigbytes)))
`
`Figure 6: AEGIS Component Certificate
`
`3.1.2 Certificate Revocation Lists
`
`Requiring each client to maintain a Certificate Revocation
`List (CRL) places a significant burden on the non-volatile
`storage of the client. Rather than use CRLs, we choose
`instead to keep the validity period of certificates short as
`in the SDSI/SPKI model and require the client to update
`the certificates when they expire. This serves two pur-
`poses beyond the ability to handle key revocation. First,
`we eliminate the storage requirements for CRLs. Second,
`we can potentially reduce the amount of system mainte-
`nance required of the client. Since the client must connect
`to the server on a regular basis to update the component
`certificates, the server can, at the same time, update the
`actual component as well if a new version is available.
`
`3.2 Diffie Hellman Key Agreement
`
`The Diffie Hellman Key Agreement (DH) [DH76] per-
`mits two parties to establish a shared secret between them.
`Unfortunately, the algorithm as originally proposed is sus-
`ceptible to a man-in-the-middle attack. The attack can be
`defeated, however, by combining DH with a public key al-
`gorithm such as DSA as proposed in the Station to Station
`Protocol[DvOW92].
`The algorithm is based on the difficulty of calculat-
`ing discrete logarithms in a finite field. Each participant
`agrees to two primes,
`and
`, such that
`is primitive
`. These values do not need to be protected in or-
` 
`der to ensure the strength of the system, and therefore can
`be public values. Each participant then generates a large
`
`9
`
`
`
`
`

`
`3 AEGISNETWORKRECOVERYPROTOCOL
`
`8
`
`random integer. Bob generates
`
`as his large random in-
`. He then sends
`teger and computes   
`
`to Alice. Alice generates

as her large random integer
`and computes  
`
`to Bob.
`. She then sends
`Bob and Alice can now each compute a shared secret, 
`,
`by computing    
`
`and    
`
`, re-
`
`spectively.
`
`3.3 Digital Signature Standard
`
`The Digital Signature Standard (DSS) includes a digital
`signature algorithm (DSA) [oS94] and a cryptographic
`hash algorithm (SHA1) [oS95]. DSA produces a 320 bit
`signature using the following parameters:
`
`, between 512 and 1024 bits in length. The
`A prime,
`size of the prime must also be a multiple of 64.
`
`A 160 bit prime factor,
`
`, of
`
`.
`
` 
`and 
`  "!$#&%  
`
`is greater than 1.
`
`, where
`such that
`
`, where
`
`is less than
`
`.
`
`is less than
`
` '
`
`, where
`
`

   (
`
`
`.
`
`are public. The private key is
`
`, and
`,
`The parameters
`.
`, and the public key is
`A signature of a message,
`, is computed in the fol-
`lowing manner. The signer generates a random number,
`, that is less than
`. They then compute
`. The
`, and
`, each 160 bits in length, comprise the sig-
`and
`values
`nature. The receiver verifies the signature by computing:
`
`
`
`* + -,   /. 
`0 1 2+    +436587 + )9. :-*;.".< (
`=
`
`>  1    
`=?  @+A36587 + )9.B > .C 
`=?/D @+ *EB > .F 
`=G 9+"+ (H;IJBK

HMLN.F (
` /.O 
`0
`
`.
`
`The signature is verified by comparing G and * . If they are
`
`equal, then the signature is valid.
`
`3.4 SHA1 Message Authentication Code
`
`,
`Message Authentication Codes (MAC) utilize a secret,
`shared between the communicating parties and a message
`digest. We use the Secure Hash Algorithm (SHA1), and
`the HMAC described in RFC 2104[KBC97]. The MAC is
`defined as:
`
`XOR QP -R 3J587 + 
`36587 + 
`S QP -R )9.T.
`where )
`is the message or datagram, QP 
`64 bytes each with the value 0x5c, and S QP 
`
`XOR
`
`is an array of
`is an array
`of sixty four bytes each with the value 0x36.
`is zero
`padded to sixty four bytes. The result of this MAC is the
`160-bit SHA1 digest.
`
`,
`
`3.5 DHCP
`
`The DHCP protocol[Dro97] provides clients the ability to
`configure their networking and host specific parameters
`dynamically during the boot process. The typical param-
`eters are the IP addresses of the client, gateways, and DNS
`server. DHCP, however, supports up to 255 configuration
`parameters, or options. Currently approximately one hun-
`dred options are defined for DHCP [AD97]. One of these
`options is an authentication option which is described in
`Section 4.1.
`The format of a DHCP message is shown in fig-
`ure 7[Dro97]. The first field in the DHCP message is the
`opcode. The opcode can have one of two values, 1 for
`a BOOTREQUEST message, and 2 for a BOOTREPLY
`message. The next field, htype, is the hardware address
`type defined by the “Assigned Numbers” RFC[RP94], and
`hlen indicates the length of the hardware address. hops is
`set to zero by the client and used by BOOTP relay agents
`to determine if they should forward the message. xid is a
`random number chosen by the client. Its use is to permit
`the client and the server to associate messages between
`each other. secs is set by the client to the number of sec-
`onds elapsed since the start address acquisition process.
`Currently, only the leftmost bit of the flags field is used
`to help solve an IP multicast problem. The remaining bits
`must be zero. ciaddr is the client address if the client
`knows it already, yiaddr is “your” address set by the server
`if the client did not know (or had a bad one) its address.
`giaddr is the relay agent address. chaddr is the client’s
`hardware address. sname is an optional null terminated
`
`10
`
`
`
`
`
`
`
`
`
`

`
`
`
`
`

`)
`
`
`*
`1
`
`
`

`
`3 AEGISNETWORKRECOVERYPROTOCOL
`
`9
`
`24
`
`31
`
`Client
`
`Server
`
`0
`
`8
`
`OPCODE
`
`HTYPE
`
`16
`
`XID
`
`HLEN
`
`HOPS
`
`Time
`
`DISCOVER
`
`OFFER
`
`OFFER
`
`REQUEST
`
`ACK
`
`SECS
`
`FLAGS
`
`Client IP Address
`
`Your (Client) IP Address
`
`IP Address of Next Server in Bootstrap
`
`Relay Agent IP Address
`
`Client Hardware Address (16 bytes)
`
`Optional Server Name (64 bytes)
`
`Figure 8: Initial DHCP Message Exchange
`
`cation of a bootstrap program to support diskless clients.
`After the client receives the IP address of the boot server
`and the name of the bootstrap program, the client uses
`TFTP[Sol92] to contact the server and transfer the file.
`
`Boot File Name (128 bytes)
`
`3.6 TFTP
`
`Options (variable)
`
`Figure 7: DHCP Message Format
`
`string containing the server’s name. file is the name of
`the boot file. In AEGIS, this is the name of the compo-
`nent to recover. Finally, options is a variable length field
`containing any options associated with the message.
`The initial message exchange between the client and
`the server is shown in figure 8. The client begins the pro-
`cess by sending a DHCPDISCOVER message as a broad-
`cast message on its local area network. The broadcast
`message may or may not be forwarded beyond the LAN
`depending on the existence of relay agents at the gate-
`ways. Any or all DHCP servers respond with a DHCPOF-
`FER message. The client selects one of the DHCPOFFER
`messages and responds to that server with a DHCPRE-
`QUEST message, and the server acknowledges it with a
`DHCPACK.
`In addition to providing networking and host specific
`parameters, DHCP can provide the name and server lo-
`
`TFTP was designed to be simple and small to fit in a ROM
`on a diskless client. Because of this, TFTP uses UDP
`rather than TCP with no authentication included in the
`protocol. TFTP does, however, have an option capabil-
`ity [MH95] similar to DHCP.
`TFTP has five unique messages that are identified by a
`two byte opcode value at the beginning of the packet. The
`Read Request (RRQ) and the Write Request (WRQ) pack-
`ets, opcodes 1 and 2 respectively, share the same format,
`see figure 12. The Data (DATA) packet contains three
`fields. The first field is the two byte opcode, 3 for DATA.
`Following the opcode is a two byte field containing the
`block number of the data, beginning at 1 and increasing.
`The third and final field of the packet contains the actual
`block of data transferred. Typically, the block size is 512
`bytes. However, the size can be increased through the use
`of the TFTP options. Should the block be smaller than
`the blocksize, this identifies the packet as the final DATA
`packet. Each DATA packet is acknowledged by a four
`byte ACK packet, opcode 4, containing the opcode and
`the acknowledged block number. The final packet, op-
`code 5, is the ERROR packet with three fiel