New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

CS 5788

by: Mrs. Carolyne Abbott
Mrs. Carolyne Abbott
GPA 3.71


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 10 page Class Notes was uploaded by Mrs. Carolyne Abbott on Monday September 21, 2015. The Class Notes belongs to CS 5788 at University of Virginia taught by Staff in Fall. Since its upload, it has received 7 views. For similar materials see /class/209686/cs-5788-university-of-virginia in ComputerScienence at University of Virginia.

Similar to CS 5788 at UVA

Popular in ComputerScienence


Reviews for CS 5788


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/21/15
The Eternity Service Ross J Anderson Cambridge University Computer Laboratory Pembroke Street Cambridge CB2 3QG Email rossandersonclcamacuk Abstract The Internet was designed to provide a communications chan nel that is as resistant to denial of service attacks as human ingenuity can make it In this note we propose the construction of a storage medium with similar properties The basic idea is to use redundancy and scat tering techniques to replicate data across a large set of machines such as the Internet and add anonymity mechanisms to drive up the cost of selective service denial attacks The detailed design of this service is an interesting scienti c problem and is not merely academic the service may be vital in safeguarding individual rights against new threats posed by the spread of electronic publishing 1 The Gutenberg Inheritance In medieval times knowledge was guarded for the power it gave The Bible was controlled by the church as well as being encoded in Latin bibles were often kept chained up Secular knowledge was also guarded jealously with medieval craft guilds using oaths of secrecy to restrict competition Even w en information leaked it usually did not spread far enough to have a signi cant effect For example Wycliffe translated the Bible into English in 138071 but the Lollard movement he started was suppressed along with the Peasants7 Revolt But the development of moveable type printing by Johannes Gens eisch zur Laden zum Gutenberg during the latter half of the fteenth century changed the game completely When Tyndale translated the New Testament in 152475 the means were now available to spread the word so quickly that the princes and bishops could not suppress it They had him executed but too late by then some 50000 copies had been printed These books were one of the sparks that led to the Reformation Just as publication of the Bible challenged the abuses that had accreted over centuries of religious monopoly so the spread of technical knowhow destroyed the guilds Reformation and a growing competitive artisan class led to the scien ti c and industrial revolutions which have given us a better standard of living than even princes and bishops enjoyed in earlier centuries Conversely the soci eties that managed to control information to some extent became uncompetitive and with the collapse of the Soviet empire democratic liberal capitalism seems nally to have won the argument But what has this got to do with a cryptology conference Quite simply the advance of electronic publishing has placed at risk our inheritance from Guten ergi Just as advancing technology in the fteenth century made it very much harder to control information so the advances of the late twentieth are making it very much easier This was made clear by recent court action involving the Church of Scientology one of whose former adherents had published some ma terial which the organisation would prefer to have kept secret This apparently included some of the organisations scripturel that is only made available to members who have advanced to a certain level in the organisation Since Gutenberg the publication of such a trade secret would have been irreversible and its former owners would have had to cope as best they could However the publication was in electronic form so the scientologists got court orders in an action for copyright infringement and raided the primary site in the USA in August 1995 They then went to Amsterdam where they raided an Internet service provider in September and led for siezure of all its assets on the grounds that their copyright information had appeared on a subscriber7s home page Their next move was to raid an anonymous remailer in Finland to nd out the identity of one of its users The saga continues The parallel with earlier religious history is instructive The Bible came into the public domain because once it had been printed and distributed the sheer number of dispersed copies made it impossible for the bishops and judges and princes to gather them up for burning However now that publishing has come to mean placing a copies of an elec tronic document on a few servers worldwide the owners of these servers can be coerced into removing it It is irrelevant whether the coercion comes from wealthy litigants exploiting the legal process or from political rulers conspiring to control t e ow ofi easi The net effect is the erosion of our inheritance from Guten berg printing is disinventedl and electronics document can be depublishedli This should concern everyone who values the bene ts that have owed from half a millenium of printing publication and progress So how can we protect the Gutenberg Inheritance Put into the language of computer science is there any way in which we can assure the availability of data when the threat model includes not just Murphyls ferrite beetles the NSA and the Russian air force but Her Majesty7s judges 2 Preventing Service Denial This problem is merely an extreme case of a more general one namely how we can assure the availability of computerised services This problem is one of the traditional goals of computer security the others being to assure the con dentiality and integrity of the information being processed Yet there is a strange mismatch between research and reality The great ma jority of respectable computer security papers are on con dentiality and almost all the rest on integrity there are almost none of any weight on availability But availability is the most important of the three computer security goalsr Outside the military intelligence and diplomatic communities almost nothing is spent on con dentiality and the typical information systems department in civil government or industry might spend 2 of its budget on integrity in the form of audit trails and internal auditors However 2040 of the budget will be spent on availability in the form of offsite data backup and spare processing capacity There are many kinds of record that we may need to protect from acciden tal or deliberate destructionr Preventing the powerful from rewriting history or simply suppressing embarrassing facts is just one of our goals lllegal immigrants might wish to destroy government records of births and deathslg real estate own ers might attack pollution registries clinicians may try to cover up malpractice by shredding medical casenotes Ald95 fraudsters may accidentallyl destroy accounting information and at a more mundane level many computer security systems become vulnerable if audit trails or certi cate revocation lists can be destroyed There is also the problem of how to ensure the longevity of digital doc umentsr Computer media rapidly become obsolete and the survival of many important public records has come under threat when the media on which they were recorded could no longer be read or the software needed to interpret them could no longer be run Rot95lr For all these reasons we believe that there is a need for a le store with a very high degree of persistence in the face of all kinds of errors accidents and denial of service attac sf 3 Previous Work Many papers purport to show that the average rm could not survive long for without its computers and that only 20740 of rms have properly tested dis aster recovery plans The authors of such papers conclude that the average rm will not survive when a disaster strikes and that company directors are thus being negligent for not spending more money on disaster recovery services The more honest of these papers are presented as marketing brochures for disaster recovery services IBMQS but many have the appearance of academic papers They are given the lie by incidents such as the Bishopsgate bomb in London where hundreds of rms had systems destroyedr Some banks lost access to their data for days as both their production and backup sites were within the 800 yard police exclusion zone Won94lr Yet we have no report of any rm s going out of business as a result A more recent IRA bomb in London s dockland area con rmed the pattern it also destroyed a number of computer installations yet companies bought new hardware and recovered their operations within a ew days Bur96lr 1 The population of California is said to have increased signi cantly after re destroyed San Francisco s birth records in the wake of the great earthquake So we can ignore most of the existing literature on availability and indeed we have to look rather hard for respectable papers on the subject One of the few of which we are aware Nee94 suggests that availability has to do with anonymity 7 anonymous signalling prevents denial of service attacks being selectiver That insight came from studying burglar alarm systems and it also makes sense in our publication scenario if the physical location of the worldwide web site cannot be located then t e rich man7s lawyers will have nowhere to execute their seizure order But how could an anonymous publication service be realised in practice 4 The Eternity Service We draw our main inspiration from the Internet which was originally conceived to provide a communications capability that would survive a global thermonu clear warr Is it possible to build a le store which would be similarly resilient against even the most extreme threat scenarios Firstly let us sketch a high level functional speci cation for such a store which we will call the Eternity Serv1ce72r 41 What it does The Eternity Service will be simple to user Say you want to store a 1MB le for 50 years there will be a tariff of say 9995 You upload a digital coin for this together with the le no proof of identity or other formality is needed After a while you get an ack and for the next 50 years your le will be there for anyone to get by anonymous le transfer Copies of the le will be stored on a number of servers round the world Like the Internet this service will depend on the cooperation of a large number of systems whose only common element will be a protocol there will be no head of ce which could be coerced or corrupted and the diversity of ownership and implementation will provide resilience against both error and attac r The net effect will be that your le once posted on the eternity service cannot be deleted As you cannot delete it yourself you cannot be forced to delete it either by abuse of process or by a gun at your wife s hea r External attacks will be made expensive by arranging things so that a le will survive the physical destruction of most of the participating le servers as well as a malicious conspiracy by the system administrators of quite a few of themr If the servers are dispersed in many jurisdictions with the service perhaps even becoming an integral part of the Internet then a successful attack could be very expensive indeed 7 hopefully beyond even the resources of governments 2 In The City and the Stars Arthur C Clarke relates that the machinery of the City of Diaspar was protected from wear and tear by eternity Circuits but he omits the engineering detai s The detailed design will utilise the well known principles of fragmentation redundancy and scattering But before we start to consider the details let us rst consider the threat model 42 The threat model Perhaps the most high level threat is that governments might ban the service out right Might this be done by all governments or at least by enough to marginalise the service The political arguments are quite predictablel Governments will object that child pornographers Anabaptists and Persian spies will use the service while libertarians will point out that the enemies of the state also use telephones faxes email video and every other medium ever invented Software publishers will be afraid that a pirate will Eternally publish their latest release and ask for an es crow7 facility that lets a judge have offending matter destroyed libertarians will object that no judge today can destroy the information contained in a personal advertisement published in The Times7 at the cost of a few pounds But law tends to lag technology by a decade or more it is be hard to get all governments to agree on anything and some countries such as the USA have free speech enshrined in their constitutionsl So an effective worldwide ban is unlikely There might always be local bans lsraeli agents might put up a le containing derogatory statements about the Prophet Mohammed and thus get eternity servers banned in much of the Muslim world If it led to a rejection of the Internet this might provide an effective attack on Muslim countries7 ability to develop but it would not be an effective attack on the Eternity Service itself any more than the Australian government7s ban on sex newsgroups has any effect on the US campuses where many of the more outre postings originatel Most nonlegislative global attacks can be blocked by technical means Net work ooding can never be completely ruled out but can be made very expensive and unreliable by providing many access points ensuring that the location of individual les remains a secret and integrating the service with the Internet So in what follows we will focus on the mechanisms necessary to prevent selective service denials at ner levels of granularityl We will imagine that an ignorant or corrupt judge has issued an injunction that a given le be deleted and we wish the design of our system to frustrate the plaintiffs solicitors in their efforts to seize it We will also imagine that a military intelligence agency or criminal organistion is prepared to use bribery intimidation kidnapping and murder in order to remove a le our system should resist them too The basic idea will be to explore the tradeoffs between redundancy and anonymityl 43 A simple design The simplest design for an eternity service is to mimic the printed book One might pay 100 servers worldwide to retain a copy of the le remember the names of a randomly selected 10 of them to audit their performance and thus enforce the contract and destroy the record of the other 90 Then even if the user is compelled by authority to erase the le and to hand over the list of ten servers where copies are held and these servers are also compelled to destroy it there will still be ninety surviving copies scattered at unknown locations round the world As soon as the user escapes from the jurisdiction of the court and wishes to recover his le he sends out a broadcast message requesting copies The servers on receiving this send him a copy via a chain of anonymous remailersi Even if the protection mechanisms are simple the use of a large number of servers in a great many jurisdictions will give a high degree of resilience 44 The perjury trap Signi cant improvements might be obtained by intelligent optimisation of the legal environment For example server should not delete eternity les without manual approval from a security of cer whose logon procedure should require him to declare under oath that he is a free agent while the logon banner states that access is only authorised under conditions of free wi Thus in order to log on under duress he would have to commit perjury and in the UK at least contravene the Computer Misuse Act as well Courts in most countries will not compel people to commit perjury or other criminal offences We refer to this protection measure as a perjury trapli It might be useful in other applications as well ranging from root logon to general systems to the passphrases used to unlock decryption and signature keys in electronic mail encryption software like PC 45 Using tamperproof hardware Using a perjury trap may block coercion of the abuseofprocess kind in many countries but we must still consider more traditional kinds of coercion such as kidnapping extortion and briberyi In order to protect the owner of the le from such direct coercion we have the rule that not even the owner may delete a le once postedi However the coercer may turn his attention to the system administrators and we need to protect them too This can best be done if we arrange things so that no identi able group of people 7 including system administrators 7 can delete any identi able le in the systemi The simplest approach is to encapsulate the trusted computing base in tamper resistant hardware such as the security modules used by banks to protect the personal identi cation numbers used by their customers in autoteller machines JDKJrQlli Of course such systems are not infallible many of them have failed as a result of design errors and operational blunders And94 and even if keys are kept in specially hardened silicon chips there are still many ways for a wealthy opponent to attack them BFL93i However given wide dispersal as one of our protection mechanisms it may be too expensive for an opponent to obtain and break a quorum of tamper resistant devices within a short time window and so the combination of tamper resistance with careful protocol design may be sufficient In that case the Eternity Service could be constructed as follows Each hardware security server will control a number of le servers When a le is rst loaded on to the system it will be passed to the local security server which will share it with a number of security servers in other jurisdictions These will each send an encrypted copy to a le server in yet another jurisdiction When a client requests a le that is not in the local cache the request will go to the local security server which will contact remote ones chosen at random until one with a copy under its control is located This copy will then be decrypted encrypted under the requester7s public key and shipped to himi Communications will be anonymised to prevent an attacker using traf c anal ysis to link encrypted and plaintext lesi Suitable mechanisms include mixnets networks of anonymous remailers ChaSl and rings Cha88li The former are suitable for sending the le to the user and the latter for communications be tween security servers even traf c analysis should not yield useful information about which le server contains a copy of which le and this may be facilitated by traf c padding VN94li Note that the existence of secure hardware allows us to substantially reduce the number of copies of each le that have to be kept It is sufficient that the attacker can no longer locate all copies of the le he wishes to destroy Anonymity enables us to reduce diversity just as in the burglar alarm example referred to above 46 Mathematics or metal Relying on hardware tamper resistance may be undesirablei Firstly it is relative and erodes over time secondly export controls would slow down the spread of the system and thirdly special purpose lowvolume hardware can be expen sive Now it is often the case that security properties can be provided using mathematics rather than metali Can we use mathematics to build the eternity service Protecting the location of le copies means that location information must be inaccessible to every individual user and indeed to every coercible subset of users Our goal here is to use techniques such as threshold decryption and Byzantine fault tolerance as implemented in Rampart Rei94li Byzantine fault tolerance means for example that with seven copies of the data we can resist a conspiracy of any two bad sysadmins or the accidental destruction of four systems and still make a complete recovery Using Byzantine mechanisms alone incomplete recovery would be possible after the destruction of up to six systems but then there would be no guarantee of integrity as such a recovery7 could be made by a bad sysadmin from bogus a There are some interesting interactions with cryptographyi If all les are signed using a system key then a full recovery can still be made so long as there is just one surviving true copy of the le in the system and the public key is not subverted Of course it is rare to get something for nothing and we must then make it hard to compromise the signing key and feasible to recover from such a compromise We will need to provide for inservice upgrades of the cryptographic mech anisms progress in both cryptanalysis and computer engineering may force the adoption of new signature schemes or of longer keylengths for existing ones We will also need to recover from the compromise of any key in the systemi Users may also want to use cryptography to add privacy properties to their les In order to prevent a number of attacks such as selective service denial at retrieve time and complications such as resilient management of authen tication the eternity service will not identify users Thus it cannot provide con dentiality it wil e up to users to encrypt data if they wish and are able Of course many users will select encryption schemes which are weak or which become vulnerable over time and it may be hoped that this will make govern ments less illdisposed towards the service 4 7 Indexing The systems directory will also have to be a le in it If users are left to remember le names then the opponent can deny service by taking out an injunction preventing the people who know the name from revealing it The directory should probably contain not just the les logical name the one which relevant security servers would understand but also some further labels such as a plaintext name or a keyword list in order to allow retrieval by people who have not been able to retain machine readable information The current directory might be cached locally along with the most popular les in the beginning at least the eternity service may be delivered by local gateway serversi lnjunctions may occasionally be purchased against these servers just as some university sites censor newsgroups in the altsex namespace however users should still be able to ftp their data from overseas gatewaysi Ultimately we will aim for a seamless integration with the rest of the Internet 4 8 Payment The eternity service may have to be commercialised more quickly than the rest of the Internet as storage costs money paid locally while most academic network costs are paid centrallyi Here we can adapt digital cash to generate an electronic annuity7 which follows the data around Provided the mechanics can be got right the economics will get better all the time for the leserver owners 7 the cost of disk space keeps dropping geo metrically but they keep on getting their 1 per MB per year or whatever for their old les This will motivate server owners to guard their les well and to copy them to new media when current technology becomes obsoletei But the con dentiality properties needed for electronic annuities are not at all straightforward For example we may want banks to underwrite them but we do not want the opponents lawyers enjoining the bankers Thus the annuity will probably need to be doubly anonymous both for the client visavis the bank and for the bank visavis the network How do we square this with audit and accountability and with preventing money laundering What if our bent judge orders all banks to delay payment by long enough for the nancier of an allegedly libellous le to be ushed out These requirements do not seem to have been tackled yet by digital cash researchersi Another problem will arise once the service becomes pro tablei Presumably there will be a market in revenuegenerating Eternity servers so that a leserver owner who wishes to cash in and retire can sell his revenue generating les to the highest bidder The obvious risk is that a wealthy opponent might buy up enough servers to have a signi cant chance of obtaining all the copies of a target le The secondary risk is that a single network service provider might acquire enough market share to penetrate the anonymity of communications and track down the copies How can these risks be controlled One might try to certify server owners but any central body responsible for certifying this site is not an NSA site7 could be bought or coerced while if the certi cation were distributed among many individuals few of them would have the resources to investigate wouldbe server owners thoroughlyi An alternative could be to leave the security policy to the user who uploads the le she could say something like I want seven copies of my le to be moved randomly around the following fty sites7i The problem here is how we prevent policy erosion as sites are replaced over time At a more mundane level we need mechanisms to stop a le server owner cheating by claiming annuity payments on a le without keeping a copy all the time After all he could just download the le from the Eternity Service itself whenever he needs to demonstrate possessioni This provides yet another reason why les must be encrypted with keys the server owners do not know then the annuity payment server can pose a challenge such as calculate a MAC on your le using the following key7 to check that the annuitant really has kept all the data that he is being paid to keep 49 Time One of the complications is that we need to be able to trust the time other wise the opponent might manipulate the network time protocol to say that the date is now 2500AD and bring about general le deletioni Does this bring the Network Time Protocol and thus the Global Positioning System and thus the US Department of Defense within the security perimeter or do we create our own secure time service The mechanics of such a service have been discussed in other contexts but there is as yet no really secure clock on the Internet A dependable time service could bene t other applications such as currency exchange transactions that are conducted in a merchantls premises while the bank is of ine Meanwhile we must plan to rely on wide dispersal plus some extra rules such as assets may not be deleted unless the sysadmin con rms the date7 the date for deletion purposes may never exceed the creation date of the system software by ve years7 and no le may be deleted until all annuity payments for it have been receivedli 5 Conclusion The eternity service that we have proposed in outline here may be important in guaranteeing individual liberties against the abuses ofpowerr It is also interesting from the scienti c point of view and the purpose ofthis paper has been to present it to the cryptology and computer security communities as an interesting problem that merits further study Building the eternity service will force us to clarify a number of points such as the nature of secure time the limits to resilience of distributed authentication services and the writeonce indexing of large databases The project should also broaden our understanding of anonymity It appears for example that the dif culty of scaling anonymous communications is an essential feature rather than a nuisance if there were just one channel the judge could have it cut or oodedr Perhaps the most interesting aspect of the service is that it might teach us a lot about availabilityr Just as our appreciation of con dentiality was developed by working out the second and thirdorder effects of the Bell LaPadula policy model Am094 and authenticity came to be understood as a result of analysing the defects in cryptographic protocols AN95 so the Eternity Service provides a setting in which availability services must be provided despite the most extreme opponents imaginabler Acknowledgements Some of these ideas have been sharpened in discussions with Roger Needham David Wheeler Matt Blaze Mike Reiter Bruce Schneier Birgit P tzmann Peter Ryan and Rajashekhar Kailar and I am grateful to the Isaac Newton Institute for hospitality while this paper was being written References Ald95 Nurse sacked for altering records after baby s death K Alderson The imes 29 November 95 p 6


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Allison Fischer University of Alabama

"I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.