Turtles All The Way Down:Research Challenges in User-Based Attestation∗Jonathan M. McCune Adrian Perrig Arvind Seshadri Leendert van DoornCMU/CyLab CMU/CyLab CMU/CyLab AMDA scientist once gave a public lecture describing howthe Earth orbits around the sun and how the sun, in turn,orbits around the center of a collection of stars called ourgalaxy.At the end of the lecture, a little old lady at the backof the room got up and said: “What you have told us isrubbish. The world is really a flat plate supported on theback of a giant tortoise.”The scientist gave a superior smile before replying,“What is the tortoise standing on?”“You’re very clever, young man, very clever,” said theold lady, “but it’s turtles all the way down!”AbstractCurrent trusted computing technologies allow comput-ing devices to verify each other, but in a networked world,there is no reason to trust one computing device any morethan another. Treating these devices as turtles, the userwho seeks a trustworthy system from which to verify oth-ers quickly realizes that it’s “turtles all the way down”because of the endless loop of trust dependencies. Weneed to provide the user with one initial turtle (the iTur-tle) which is axiomatically trustworthy, thereby breakingthe dependency loop. In this paper, we present some ofthe research challenges involved in designing and usingsuch an iTurtle.1 IntroductionInternet-connected computing devices feature complexsoftware stacks which are often riddled with remotely-exploitable software vulnerabilities. Attackers can exploit∗This research was supported in part by CyLab at Carnegie Mellonunder grant DAAD19-02-1-0389 from the Army Research Office, andgrant CCF-0424422 from the National Science Foundation, and equip-ment donations from AMD. The views and conclusions contained hereare those of the authors and should not be interpreted as necessarily rep-resenting the official policies or endorsements, either express or implied,of AMD, ARO, CMU, NSF, or the U.S. Government or any of its agen-cies.ComputingDeviceWhat code areyou running?Code ListUser?Bank(Verifier)Figure 1: Remote attestation does not create an authenticatedchannel between the verifier and the user. If verification fails,there is no way to inform the user. Thus, malware on the user’scomputing device can lie about verification results.these vulnerabilities to inject malware. The malware situ-ation is made worse by the feature creep in software andthe continuous introduction of new devices with vulnera-ble software on the Internet.In order to use their computing devices with confi-dence, users need to know if the software on their comput-ing devices is infected by malware. The Trusted Comput-ing Group (TCG) has proposed the mechanism of remoteattestation to achieve this goal [14]. Remote attestationenables a remote verifier to learn the configuration of thesoftware on any TCG-compliant computing device. Theverifier can compare this configuration to a known-goodconfiguration to detect deviations.The TCG’s remote attestation mechanism encountersat least three problems when we want to adapt it to user-based attestation. All three problems arise because theuser does not have an axiomatically trustworthy deviceto perform verification. (1) The chain of trust createdthrough the verification process does not propagate backto the user, because there is no authenticated channel be-tween the user and the verifier (see Figure 1). (2) In anetworked world, it is unclear to the user why the devicethat she uses as the verifier is any more trustworthy thanher other devices. (3) Platform and user privacy are issuesunder TCG attestation. We present scenarios which willillustrate the above problems.Security-Sensitive Interactive Transactions. Considera user who wants to perform online banking using hercomputer. If the bank’s server is TCG-aware and theuser’s computer is TCG-compliant, then the bank’s servercan request an attestation from the user’s computer to ver-ify that the user’s computer is running an approved soft-ware stack. If the server detects an unapproved softwarestack, then it can refuse service.The problem with the above scenario is that there isno way for the bank’s server to securely inform the userof the verification result (see Figure 1). If verification isunsuccessful, the user’s computer cannot be trusted to dis-play the correct result, since any notification mechanismthat displays the verification result on-screen is vulnera-ble to spoofing. Malware installed on the user’s computercould lie to the user that the attestation verified correctlyat the bank, display a fake login page, and capture theuser’s login credentials.There are two popularly suggested solutions to theproblem of establishing an authenticated channel betweenthe user and the bank: side-channels and trusted I/O.Automated side-channels use means of communicationother than the user’s computer to establish an authenti-cated channel. For instance, the bank’s computer can sendSMS messages or make telephone calls to convey the ver-ification result to the user. However, any unauthenticated,automated side-channel may facilitate automated attack.Using a side-channel that is not automated, such as hav-ing a customer service representative make a phone call,is also not an option since the attacker can pretend to be abank employee (a fact amply demonstrated by social en-gineering attacks). Besides, a non-automated side chan-nel makes the verification expensive and potentially errorprone by introducing additional human factors.Upcoming trusted computing technologies, such asAMD’s Presidio [1] and Intel’s Trusted Execution Tech-nology (TXT, formerly LaGrande) [5], which includehardware mechanisms for trusted I/O, do not solve theproblem of establishing an authenticated channel betweenthe user and the bank either. While they do include mech-anisms for establishing trusted channels between platformcomponents, they do not require any display to indicatethat the channel is present [8]. Even if, in the future, thesehardware technologies are extended to address this short-coming, legacy systems will remain a problem.The online banking example can be extended to anysecurity-sensitive interactive transaction, such as remotelogin or e-commerce. One may also wish to consider howthe problem presented in the above example can be ap-plied to the examples in Chapter 2 of Balacheff et al. [3].We believe that the best approach