Abstract. The Internet was designed to provide a communications chan-nel that is as resistant to denial of service attacks as human ingenuity canmake it. In this note, we propose the construction of a storage mediumwith similar properties. The basic idea is to use redundancy and scat-tering techniques to replicate data across a large set of machines (suchas the Internet), and add anonymity mechanisms to drive up the costof selective service denial attacks. The detailed design of this service isan interesting scienti c problem, and is not merely academic: the servicemay be vital in safeguarding individual rights against new threats posedby the spread of electronic publishing.
1 The Gutenberg InheritanceIn medieval times, knowledge was guarded for the power it gave. The Bible wascontrolled by the church: as well as being encoded in Latin, bibles were often keptchained up. Secular knowledge was also guarded jealously, with medieval craftguilds using oaths of secrecy to restrict competition.
bibles
Bible
Luther Bible, 1534Even when informationleaked, it usually did not spread far enough to have a signi cant e ect. Forexample, Wycli e translated the Bible into English in 1380{1, but the Lollardmovement he started was suppressed along with the Peasants' Revolt.
But the development of moveable type printing by Johannes Gensfleisch zurLaden zum Gutenberg during the latter half of the fteenth century changedthe game completely. When Tyndale translated the New Testament in 1524{5,the means were now available to spread the word so quickly that the princesand bishops could not suppress it. They had him executed, but too late; by thensome 50,000 copies had been printed. These books were one of the sparks thatled to the Reformation.
Just as publication of the Bible challenged the abuses that had accreted overcenturies of religious monopoly, so the spread of technical know-how destroyedthe 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 livingthan 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 seemsnally 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 ourinheritance from Gutenberg.
Just as advancing technology in the fteenth century made it very muchharder to control information, so the advances of the late twentieth are makingit 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 apparentlyincluded some of the organisation's `scripture' that is only made available tomembers who have advanced to a certain level in the organisation.
Since Gutenberg, the publication of such a trade secret would have beenirreversible and its former owners would have had to cope as best they could.
However, the publication was in electronic form, so the scientologists got courtorders in an action for copyright infringement and raided the primary site inthe USA in August 1995. They then went to Amsterdam where they raided anInternet service provider in September, and led for siezure of all its assets onthe grounds that their copyright information had appeared on a subscriber'shome page. Their next move was to raid an anonymous remailer in Finland tond out the identity of one of its users. The saga continues.
The parallel with earlier religious history is instructive. The Bible came intothe public domain because once it had been printed and distributed, the sheernumber of dispersed copies made it impossible for the bishops and judges andprinces 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 becoerced into removing it. It is irrelevant whether the coercion comes from wealthylitigants exploiting the legal process, or from political rulers conspiring to controlthe flow of ideas. The net e ect is the erosion of our inheritance from Guten-berg: printing is `disinvented' and electronics document can be `de-published'.
This should concern everyone who values the bene ts that have flowed from halfa 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 canassure the availability of data when the threat model includes not just Murphy'sferrite beetles, the NSA and the Russian air force, but Her Majesty's judges?2 PreventingServiceDenialThis problem is merely an extreme case of a more general one, namely howwe can assure the availability of computerised services. This problem is oneof the traditional goals of computer security, the others being to assure thecon 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 almostall the rest on integrity; there are almost none of any weight on availability.
But availability is the most important of the three computer security goals.
Outside the military, intelligence and diplomatic communities, almost nothingis spent on con dentiality; and the typical information systems department incivil government or industry might spend 2% of its budget on integrity, in theform of audit trails and internal auditors. However 20-40% of the budget willbe spent on availability, in the form of o site data backup and spare processingcapacity.
There are many kinds of record that we may need to protect from acciden-tal or deliberate destruction. Preventing the powerful from rewriting history orsimply suppressing embarrassing facts is just one of our goals. Illegal immigrantsmight wish to destroy government records of births and deaths1; real estate own-ers might attack pollution registries; clinicians may try to cover up malpracticeby shredding medical casenotes [Ald95]; fraudsters may `accidentally' destroyaccounting information; and at a more mundane level, many computer securitysystems become vulnerable if audit trails or certi cate revocation lists can bedestroyed.
There is also the problem of how to ensure the longevity of digital doc-uments. Computer media rapidly become obsolete, and the survival of manyimportant public records has come under threat when the media on which theywere recorded could no longer be read, or the software needed to interpret themcould no longer be run [Rot95].
For all these reasons, we believe that there is a need for a le store with avery high degree of persistence in the face of all kinds of errors, accidents anddenial of service attacks.
3 Previous WorkMany papers purport to show that the average rm could not survive long forwithout its computers, and that only 20{40% of rms have properly tested dis-aster recovery plans. The authors of such papers conclude that the average rmwill not survive when a disaster strikes, and that company directors are thusbeing negligent for not spending more money on disaster recovery services. Themore honest of these papers are presented as marketing brochures for disasterrecovery services [IBM93], but many have the appearance of academic papers.
They are given the lie by incidents such as the Bishopsgate bomb in Londonwhere hundreds of rms had systems destroyed. Some banks lost access to theirdata for days, as both their production and backup sites were within the 800yard police exclusion zone [Won94]. Yet we have no report of any rm's goingout of business as a result. A more recent IRA bomb in London's dockland areacon rmed the pattern: it also destroyed a number of computer installations, yetcompanies bought new hardware and recovered their operations within a fewdays [Bur96].
1 The population of California is said to have increased signi cantly after re destroyedSan Francisco's birth records in the wake of the great earthquake.
So we can ignore most of the existing literature on availability, and indeed wehave to look rather hard for respectable papers on the subject. One of the few ofwhich we are aware [Nee94] suggests that availability has to do with anonymity| anonymous signalling prevents denial of service attacks being selective. Thatinsight came from studying burglar alarm systems, and it also makes sense in ourpublication scenario; if the physical location of the worldwide web site cannot belocated, then the rich man's lawyers will have nowhere to execute their seizureorder. But how could an anonymous publication service be realised in practice?4 The Eternity ServiceWe draw our main inspiration from the Internet, which was originally conceivedto provide a communications capability that would survive a global thermonu-clear war. Is it possible to build a le store which would be similarly resilientagainst 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 Service'2.
4.1 What it doesThe Eternity Service will be simple to use. Say you want to store a 1MB le for50 years; there will be a tari of (say) $99.95. You upload a digital coin for this,together with the le; no proof of identity or other formality is needed. After awhile you get an ack, and for the next 50 years your le will be there for anyoneto get by anonymous le transfer.
Copies of the le will be stored on a number of servers round the world. Likethe Internet, this service will depend on the cooperation of a large number ofsystems whose only common element will be a protocol; there will be no heado ce which could be coerced or corrupted, and the diversity of ownership andimplementation will provide resilience against both error and attack.
The net e ect will be that your le, once posted on the eternity service,cannot be deleted. As you cannot delete it yourself, you cannot be forced todelete it, either by abuse of process or by a gun at your wife's head.
External attacks will be made expensive by arranging things so that a lewill survive the physical destruction of most of the participating le servers, aswell as a malicious conspiracy by the system administrators of quite a few ofthem. If the servers are dispersed in many jurisdictions, with the service perhapseven becoming an integral part of the Internet, then a successful attack could bevery expensive indeed | hopefully beyond even the resources of governments.
2 In `The City and the Stars', Arthur C Clarke relates that the machinery of the cityof Diaspar was protected from wear and tear by `eternity circuits'; but he omits theengineering details.
The detailed design will utilise the well known principles of fragmentation,redundancy and scattering. But before we start to consider the details, let usrst consider the threat model.
4.2 The threat modelPerhaps 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 marginalisethe service?The political arguments are quite predictable. Governments will object thatchild pornographers, Anabaptists and Persian spies will use the service, whilelibertarians will point out that the enemies of the state also use telephones, faxes,email, video and every other medium ever invented. Software publishers will beafraid that a pirate will Eternally publish their latest release, and ask for an `es-crow' facility that lets a judge have o ending matter destroyed; libertarians willobject that no judge today can destroy the information contained in a personaladvertisement published in `The Times' at the cost of a few pounds.
But law tends to lag technology by a decade or more; it is be hard to getall governments to agree on anything; and some countries, such as the USA,have free speech enshrined in their constitutions. So an e ective worldwide banis unlikely. There might always be local bans: Israeli agents might put up a lecontaining derogatory statements about the Prophet Mohammed, and thus geteternity servers banned in much of the Muslim world. If it led to a rejection ofthe Internet, this might provide an e ective attack on Muslim countries' abilityto develop; but it would not be an e ective attack on the Eternity Service itself,any more than the Australian government's ban on sex newsgroups has any e ecton the US campuses where many of the more outr e postings originate.
Most non-legislative global attacks can be blocked by technical means. Net-work flooding can never be completely ruled out, but can be made very expensiveand unreliable by providing many access points, ensuring that the location ofindividual les remains a secret and integrating the service with the Internet.
So in what follows, we will focus on the mechanisms necessary to preventselective service denials at ner levels of granularity. We will imagine that anignorant or corrupt judge has issued an injunction that a given le be deleted,and we wish the design of our system to frustrate the plainti 's solicitors intheir e orts to seize it. We will also imagine that a military intelligence agencyor criminal organistion is prepared to use bribery, intimidation, kidnapping andmurder in order to remove a le; our system should resist them too. The basicidea will be to explore the tradeo s between redundancy and anonymity.
4.3 A simple designThe simplest design for an eternity service is to mimic the printed book. Onemight pay 100 servers worldwide to retain a copy of the le, remember the namesof a randomly selected 10 of them (to audit their performance and thus enforcethe contract), and destroy the record of the other 90.
Then even if the user is compelled by authority to erase the le and tohand over the list of ten servers where copies are held, and these servers arealso compelled to destroy it, there will still be ninety surviving copies scatteredat unknown locations round the world. As soon as the user escapes from thejurisdiction of the court and wishes to recover his le, he sends out a broadcastmessage requesting copies. The servers on receiving this send him a copy via achain of anonymous remailers.
Even if the protection mechanisms are simple, the use of a large number ofservers in a great many jurisdictions will give a high degree of resilience.
4.4 The perjury trapSigni cant improvements might be obtained by intelligent optimisation of thelegal environment. For example, server should not delete eternity les withoutmanual approval from a security o cer, whose logon procedure should requirehim to declare under oath that he is a free agent, while the logon banner statesthat access is only authorised under conditions of free will.
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 mostcountries will not compel people to commit perjury or other criminal o ences.
We refer to this protection measure as a `perjury trap'. It might be usefulin other applications as well, ranging from root logon to general systems tothe passphrases used to unlock decryption and signature keys in electronic mailencryption software like PGP.
4.5 Using tamper-proof hardwareUsing a perjury trap may block coercion of the abuse-of-process kind in manycountries, but we must still consider more traditional kinds of coercion such askidnapping, extortion and bribery.
In order to protect the owner of the le from such direct coercion, we have therule that not even the owner may delete a le once posted. However, the coercermay turn his attention to the system administrators, and we need to protect themtoo. This can best be done if we arrange things so that no identi able group ofpeople | including system administrators | can delete any identi able le inthe system.
The simplest approach is to encapsulate the trusted computing base in tamper-resistant hardware, such as the security modules used by banks to protect thepersonal identi cation numbers used by their customers in autoteller machines[JDK+91]. Of course, such systems are not infallible; many of them have failedas a result of design errors and operational blunders [And94], and even if keys arekept in specially hardened silicon chips there are still many ways for a wealthyopponent to attack them [BFL+93].
However, given wide dispersal as one of our protection mechanisms, it may betoo expensive for an opponent to obtain and break a quorum of tamper resistantdevices within a short time window, and so the combination of tamper resistancewith careful protocol design may be su cient. In that case, the Eternity Servicecould be constructed as follows.
Each hardware security server will control a number of le servers. When ale is rst loaded on to the system, it will be passed to the local security serverwhich will share it with a number of security servers in other jurisdictions. Thesewill 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 goto the local security server which will contact remote ones chosen at random untilone with a copy under its control is located. This copy will then be decrypted,encrypted under the requester's public key and shipped to him.
Communications will be anonymised to prevent an attacker using tra c anal-ysis to link encrypted and plaintext les. Suitable mechanisms include mix-nets(networks of anonymous remailers) [Cha81] and rings [Cha88]. The former aresuitable for sending the le to the user, and the latter for communications be-tween security servers; even tra c analysis should not yield useful informationabout which le server contains a copy of which le, and this may be facilitatedby tra c padding [VN94].
Note that the existence of secure hardware allows us to substantially reducethe number of copies of each le that have to be kept. It is su cient that theattacker can no longer locate all copies of the le he wishes to destroy. Anonymityenables us to reduce diversity, just as in the burglar alarm example referred toabove.
4.6 Mathematics or metal?Relying on hardware tamper resistance may be undesirable. Firstly, it is relative,and erodes over time; secondly, export controls would slow down the spread ofthe system; and, thirdly, special purpose low-volume hardware can be expen-sive. Now it is often the case that security properties can be provided usingmathematics rather than metal. Can we use mathematics to build the eternityservice?Protecting the location of le copies means that location information mustbe inaccessible to every individual user, and indeed to every coercible subsetof users. Our goal here is to use techniques such as threshold decryption andByzantine fault tolerance, as implemented in Rampart [Rei94].
Byzantine fault tolerance means, for example, that with seven copies of thedata we can resist a conspiracy of any two bad sysadmins, or the accidentaldestruction of four systems, and still make a complete recovery. Using Byzantinemechanisms alone, incomplete recovery would be possible after the destructionof up to six systems, but then there would be no guarantee of integrity (as sucha `recovery' could be made by a bad sysadmin from bogus data).
There are some interesting interactions with cryptography. If all les aresigned using a system key, then a full recovery can still be made so long as thereis just one surviving true copy of the le in the system, and the public key isnot subverted. Of course, it is rare to get something for nothing, and we mustthen make it hard to compromise the signing key (and feasible to recover fromsuch a compromise).
We will need to provide for in-service upgrades of the cryptographic mech-anisms: progress in both cryptanalysis and computer engineering may force theadoption of new signature schemes, or of longer keylengths for existing ones. Wewill also need to recover from the compromise of any key in the system.
Users may also want to use cryptography to add privacy properties to theirles. In order to prevent a number of attacks (such as selective service denialat retrieve time) and complications (such as resilient management of authen-tication), the eternity service will not identify users. Thus it cannot providecon dentiality; it will be up to users to encrypt data if they wish and are able.
Of course, many users will select encryption schemes which are weak, or whichbecome vulnerable over time; and it may be hoped that this will make govern-ments less ill-disposed towards the service.
4.7 IndexingThe system's directory will also have to be a le in it. If users are left to rememberle names, then the opponent can deny service by taking out an injunctionpreventing the people who know the name from revealing it.
The directory should probably contain not just the le's logical name (theone which relevant security servers would understand), but also some furtherlabels such as a plaintext name or a keyword list, in order to allow retrieval bypeople who have not been able to retain machine readable information.
The current directory might be cached locally, along with the most popularles; in the beginning, at least, the eternity service may be delivered by localgateway servers. Injunctions may occasionally be purchased against these servers,just as some university sites censor newsgroups in the alt.sex.* namespace;however, users should still be able to ftp their data from overseas gateways.
Ultimately, we will aim for a seamless integration with the rest of the Internet.
4.8 PaymentThe eternity service may have to be commercialised more quickly than the rest ofthe Internet, as storage costs money paid locally, while most academic networkcosts are paid centrally. Here we can adapt digital cash to generate an `electronicannuity' which follows the data around.
Provided the mechanics can be got right, the economics will get better allthe time for the leserver owners | the cost of disk space keeps dropping geo-metrically, but they keep on getting their $1 per MB per year (or whatever) fortheir old les. This will motivate server owners to guard their les well, and tocopy them to new media when current technology becomes obsolete.
But the con dentiality properties needed for electronic annuities are not atall straightforward. For example, we may want banks to underwrite them, butwe do not want the opponent's lawyers enjoining the bankers. Thus the annuitywill probably need to be doubly anonymous, both for the client vis- a-vis thebank and for the bank vis- a-vis the network. How do we square this with auditand accountability, and with preventing money laundering? What if our bentjudge orders all banks to delay payment by long enough for the nancier of anallegedly libellous le to be flushed out? These requirements do not seem to havebeen tackled yet by digital cash researchers.
Another problem will arise once the service becomes pro table. Presumablythere will be a market in revenue-generating Eternity servers, so that a leserverowner who wishes to cash in and retire can sell his revenue generating les tothe highest bidder. The obvious risk is that a wealthy opponent might buy upenough servers to have a signi cant chance of obtaining all the copies of a targetle. The secondary risk is that a single network service provider might acquireenough market share to penetrate the anonymity of communications and trackdown 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 site'could be bought or coerced, while if the certi cation were distributed amongmany individuals, few of them would have the resources to investigate would-beserver owners thoroughly. An alternative could be to leave the security policy tothe user who uploads the le: she could say something like, `I want seven copiesof my le to be moved randomly around the following fty sites'. The problemhere 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 ownercheating by claiming annuity payments on a le without keeping a copy all thetime. After all, he could just download the le from the Eternity Service itselfwhenever he needs to demonstrate possession. This provides yet another reasonwhy les must be encrypted with keys the server owners do not know; then theannuity payment server can pose a challenge such as `calculate a MAC on yourle using the following key' to check that the annuitant really has kept all thedata that he is being paid to keep.
4.9 TimeOne 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 thedate is now 2500AD and bring about general le deletion. Does this bring theNetwork Time Protocol (and thus the Global Positioning System and thus theUS Department of Defense) within the security perimeter, or do we create ourown secure time service? The mechanics of such a service have been discussedin 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 currencyexchange transactions that are conducted in a merchant's premises while thebank is o ine. Meanwhile, we must plan to rely on wide dispersal, plus someextra rules such as `assets may not be deleted unless the sysadmin con rms thedate', `the date for deletion purposes may never exceed the creation date ofthe system software by ve years', and `no le may be deleted until all annuitypayments for it have been received'.
5 ConclusionThe eternity service that we have proposed in outline here may be important inguaranteeing individual liberties against the abuses of power. It is also interestingfrom the scienti c point of view, and the purpose of this paper has been to presentit to the cryptology and computer security communities as an interesting problemthat merits further study.
Building the eternity service will force us to clarify a number of points such asthe nature of secure time, the limits to resilience of distributed authenticationservices, and the write-once indexing of large databases. The project shouldalso broaden our understanding of anonymity. It appears, for example, that thedi culty of scaling anonymous communications is an essential feature ratherthan a nuisance; if there were just one channel, the judge could have it cut orflooded.
Perhaps the most interesting aspect of the service is that it might teach us alot about availability. Just as our appreciation of con dentiality was developedby working out the second- and third-order e ects of the Bell LaPadula policymodel [Amo94], and authenticity came to be understood as a result of analysingthe defects in cryptographic protocols [AN95], so the Eternity Service provides asetting in which availability services must be provided despite the most extremeopponents imaginable.
AcknowledgementsSome 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 NewtonInstitute for hospitality while this paper was being written.
References[Ald95] \Nurse sacked for altering records after baby's death", K Alderson, TheTimes 29 November 95 p 6[Amo94] `Fundamentals of Computer Security Technology', E Amoroso, Prentice Hall1994[And94] \Why Cryptosystems Fail" in Communications of the ACM vol 37 no 11(November 1994) pp 32{40[AN95] RJ Anderson, RM Needham, \Programming Satan's Computer", in `Com-puter Science Today | Recent Trends and Developments', J van Leeuven(ed.), Springer Lecture Notes in Computer Science volume 1000 pp 426{440[Bur96] \Rising from the Rubble", G Burton, in Computer Weekly (29 Feb 1996) p20[BFL+93] S Blythe, B Fraboni, S Lall, H Ahmed, U de Riu, \Layout Reconstructionof Complex Silicon Chips", in IEEE J. of Solid-State Circuits v 28 no 2 (Feb93) pp 138{145[Cha81] D Chaum, \Untraceable electronic mail, return addresses, and digitalpseudonyms", in Communications of the ACM v 24 no 2 (Feb 1981) pp84{88[Cha88] D Chaum, \The Dining Cryptographers Problem: Unconditional Sender andRecipient Untraceability", in Journal of Cryptology v 1 (1988) pp 65{75[IBM93] `Up the creek? | The business perils of computer failure', IBM, 1993[JDK+91] DB Johnson, GM Dolan, MJ Kelly, AV Le, SM Matyas, \Common Crypto-graphic Architecture Application Programming Interface", in IBM SystemsJournal 30 no 2 (1991) pp 130 - 150[Nee94] RM Needham, \Denial of Service: an Example", in Communications of theACM v 37 no 11 (Nov 94) pp 42{46[Rei94] MK Reiter, \Secure Agreement Protocols: Reliable and Atomic Group Mul-ticast in Rampart", in Proc. ACM Conf. on Computer and CommunicationsSecurity 1994 pp 68{80[Rot95] J Rothenberg, \Ensuring the Longevity of Digital Documents", in Scienti cAmerican (January 1995) pp 24{29[VN94] BR Venkataraman, RE Newman-Wolfe, \Performance Analysis of a Methodfor High Level Prevention of Tra c Analysis Using Measurements from aCampus Network", in Computer Security Applications 94 pp 288{297[Won94] K Wong, \Business Continuity Planning", in Computer Fraud and SecurityBulletin (April 94) pp 10 - 16
The Gutenberg Bible displayed by the United States...
A bible from 1859.
English: Russian Air Force MiG-25PU. Français : U...