![[*]](../../latex2html-icons/foot_motif.gif){kind=icon}
.
University of Cambridge Computer Laboratory
New Museums Site, Pembroke Street, Cambridge CB2 3QG, UK
[email protected]
In this note, I report an experiment to see whether a high quality system specification can also be produced by a large number of people working in parallel with a minimum of communication.
(This paper appeared as an invited talk at the 1999 Computer Security Applications Conference. You can download pdfs of the a two column version that appeared in the proceedings, and if your prefer larger type the original single column version.)
Experienced software engineers know that perhaps 30% of the cost of a software product goes into specifying it, 10% into coding, and the remaining 60% on maintenance. This has profound effects on computer science. For example, when designing new programming languages the motive nowadays is mostly not to make coding easier, but to cut the costs of maintenance. There has also been massive interest in open source software products such as Linux and Apache, whose maintenance is undertaken by thousands of programmers working worldwide in a voluntary and cooperative way.
Open source software is not entirely a recent invention; in the early days of computing most system software vendors published their source code. This openness started to recede in the early 1980s when pressure of litigation led IBM to adopt an `object-code-only' policy for its mainframe software, despite bitter criticism from its user community. The pendulum now seems to be swinging back, with Linux and Apache gaining huge market share.
In his influential paper `The Cathedral and the Bazaar' [1], Eric Raymond compares the hierarchical organisation of large software projects in industry (`the cathedral') with the more open, unstructured approach of cooperative developers (`the bazaar'). He makes a number of telling observations about the efficiency of the latter, such as that ``Given enough eyeballs, all bugs are shallow''. His more recent paper, `The Magic Cauldron' [2], explores the economic incentives that for-profit publishers have found to publish their source code, and concludes that IBM's critics were right: where reliability is paramount, open source is best, as users will cooperate in finding and removing bugs.
There is a corollary to this argument, which I explore in this paper: the next priority after cutting the costs of maintenance should be cutting the costs of specification.
Specification is not only the second most expensive item in the system development life cycle, but is also where the most expensive things go wrong. The seminal study by Curtis, Krasner and Iscoe of large software project disasters found that failure to understand the requirements was mostly to blame [3]: a thin spread of application domain knowledge typically led to fluctuating and conflicting requirements which in turn caused a breakdown in communication. They suggested that the solution was to find an `exceptional designer' with a deep understanding of the problem who would assume overall responsibility.
But there are many cases where an established expert is not available, such as when designing a new application from scratch or when building a competitor to a closed, proprietary system whose behaviour can only be observed at a distance.
There are also some particular domains in which specification is well known to be hard. Security is one example; the literature has many examples of systems which protected the wrong thing, or protected the right thing but using the wrong mechanisms. Most real life security failures result from the opportunistic exploitation of elementary design flaws rather than `high-tech' attacks such as cryptanalysis [4]. The list of possible attacks on a typical system is long, and people doing initial security designs are very likely to overlook some of them. Even in a closed environment, the use of multiple independent experts is recommended [5].
Security conspicuously satisfies the five tests which Raymond suggested would identify the products most likely to benefit from an open source approach [2]. It is based on common engineering knowledge rather than proprietary techniques; it is sensitive to failure; it needs peer review for verification; it is business critical; and its economics include strong network effects. Its own traditional wisdom, going back at least to Auguste Kerkhoffs in 1883, is that cryptographic systems should be designed in such a way that they are not compromised if the opponent learns the technique being used. In other words, the security should reside in the choice of key rather than in obscure design features [6].
It therefore seemed worthwhile to see if a high quality security specification could be designed in a highly parallel way, by getting a lot of different people to contribute drafts in the hope that most of the possible attacks would be considered in at least one of them.
The opportunity to test this idea was provided by the fact that I teach courses in cryptography and computer security to second and third year undergraduates at Cambridge. By the third year, students should be able to analyse a protection problem systematically by listing the threats, devising a security policy and then recommending mechanisms that will enforce it. (The syllabus and lecture notes are available online at [7].)
By a security policy, we mean a high level specification which sets out the threats to which a system is assumed to be exposed and the assurance properties which are to be provided in response. Like most specifications, it is a means of communication between the users (who understand the environment) and the system engineers (who will have to implement the encryption, access control, logging or other mechanisms). So it must be clearly comprehensible to both communities; it should also be concise.
The students see, as textbook examples of security policy:
The first three of these are documented in [8] and the fourth in [9]. Further examples of security policy models are always welcome, as they help teach the lesson that `security' means radically different things in different applications. However, developing a security policy is usually hard work, involving extensive consultation with domain experts and successive refinement until a model emerges that is compact, concise and agreed by all parties.
Exceptions include designing a policy for a new application, and for a competitor to a closed system. In such cases, the best we can do may be to think long and hard, and hope that we will not miss anything important.
I therefore set the following exam question to my third year students:
You have been hired by a company which is bidding to take over the National Lottery when Camelot's franchise expires, and your responsibility is the security policy. State the security policy you would recommend and outline the mechanisms you would implement to enforce it.
For the benefit of overseas readers, I will now give a simplified description of our national lottery. (British readers can skip the next two paragraphs.)
The UK's national lottery is operated by a consortium of companies called Camelot which holds a seven year licence from the government. This licence is up for renewal, which makes the question topical; and presumably Camelot will refuse to share its experience with potential competitors. A large number of franchised retail outlets sell tickets. The customer marks six out of 49 numbers on a form which he hands with his money to the operator; she passes it through a machine that scans it and prints a ticket containing the choice of numbers plus some further coded information to authenticate it.
Twice a week there is a draw on TV at which a machine selects seven
numbered balls from 49 in a drum. The customers who have predicted the
first six share a jackpot of several million pounds; the odds should
be (49 choose 6) or 13,983,816 to one against, meaning that with much
of the population playing there are several winners in a typical draw.
(Occasionally there are no winners and the jackpot is `rolled over' to
the next draw, giving a pot of many millions of pounds which whips
the popular press to a frenzy.) There are also smaller cash prizes for
people who guessed only some of the numbers. Half the takings go on
prize money; the other half gets shared between Camelot, the taxman
and various charitable good causes.
The model answer I had prepared had a primary threat model that attackers, possibly in cahoots with insiders, would try to place bets once the result of the draw is known, whether by altering bet records or forging tickets. The secondary threats were that bets would be placed that had not been paid for, and that attackers might operate bogus vending stations which would pay small claims but disappear if a client won a big prize.
The security policy that follows logically from this is that bets should be registered online with a server which is secured prior to the draw, both against tampering and against the extraction of sufficient information to forge a winning ticket; that there should be credit limits for genuine vendors; and that there should be ways of identifying bogus vendors. Once the security policy has been developed in enough detail, designing enforcement mechanisms should not be too hard for someone skilled in the art - though there are some subtleties, as we shall see below.
The exam was set on the first of June 1999 [10], and when the scripts were delivered that evening, I was eager to find out what the students might have come up with.
Thirty four candidates answered the question, and five of their papers were good enough to be kept as model answers. All of these candidates had original ideas which are incorporated in this paper, as did a further seven candidates whose answers were less complete. As the exam marking is anonymous, the `co-authors' of this specification are a subset of the candidates listed in the ackowledgements below. The question was a `good' one in that it divided the students up about equally into first, second and third class ranges of marks. Almost all the original ideas came from the first class candidates.
The contributions came at a number of levels, including policy goal statements, discussions of particular attacks, and arguments about the merits of particular protection mechanisms.
On sorting out the high level policy statements from the more detailed contributions, the first thing to catch the eye was a conflict reminiscent of the old debate over who should pay when a `phantom withdrawal' happens via an automatic teller machine - the customer or the bank [4].
One of the candidates assumed that the customer's rights must have precedence: `All winning tickets must be redeemable! So failures must not allow unregistered tickets to be printed.' Another candidate assumed the contrary, and thus the `worst outcome should be that the jackpot gets paid to the wrong person, never twice.' Ultimately, whether systems fail in the shop's favour or the customer's is a regulatory issue. However, there are consequences for security. In the context of cash machine disputes, it was noted that if the customer carries the risk of fraud while only the bank is in a position to improve the security measures, then the bank may get more and more careless until an epidemic of fraud takes place. We presumably want to avoid this kind of `moral hazard' in a national lottery; perhaps the solution is for disputed sums to be added back to the prize fund, or distributed to the `good causes'.
As well as protecting the system from fraud, the operator must also convince the gaming public of this. This was expressed in various ways: `take care how you justify your operations;' `don't forget the indirect costs of security failure such as TV contract penalties, ticket refund, and publicity of failure leading to bogus claims;' `at all costs ensure that there is enough backup to prevent unverifiable ticket problems.' The operator can get some protection by signs such as `no winnings due unless entry logged' but this cover is never total.
Next, a number of candidates argued that it was foolish to place sole reliance on any single protection mechanism, or any single instance of a particular type of mechanisms. A typical statement was: `Don't bet the farm on tamper-resistance'. For example, if the main threat is someone forging a winning ticket after tapping the network which the central server uses to send ticket authenticator codes to vending machines, we might not just encrypt the line but also delay paying jackpots for several days to give all winners a chance to claim. (Simply encrypting the authentication codes would not be enough, if a technician who dismantled the encryption device at the server could get both the authentication keys and the encryption keys.) Translated into methodology, this suggests a security matrix approach which maps the threats to the protection mechanisms, and makes it easy for us to check that at least two independent mechanisms constrain every serious threat.
Various attempts were made to reuse existing security policies, and particularly Clark-Wilson. These were mostly by weak candidates and not very convincing. But three candidates did get some mileage; for example, one can model the lottery terminal as a device that turns an unconstrained data item (the customer selection) into a constrained data item (the valid lottery ticket) by registering it and printing an authentication code on it. Such concepts can be useful in designing separation-of-duty mechanisms for ticket redemption and general financial control, but do not seem to be enough to cover all the novel and interesting security problems which a lottery provides.
Some candidates wondered whether a new franchisee would want to extend the existing lottery's business model, such as by allowing people to buy tickets over the phone or the net. In that case, one should try to design the policy to be extensible to non-material sales channels. (Internet based lottery ticket sales have since been declared to be a good thing by the government [11].)
Finally, some attention needs to be paid to protecting genuine winners. The obvious issue is safeguarding the privacy of winners who refuse publicity; less obvious issues include the risk that winners might be traced, robbed and perhaps even murdered during the claim process. For example, the UK has some recent history of telephone technicians abusing their access to win airline tickets and other prizes offered during phone-in competitions; one might be concerned about the risk that a technician, in cahoots with organised crime, would divert the winners' hotline, intercept a jackpot claim, and dispatch a hit squad to collect the ticket. In practice, measures to control this risk are likely to involve the phone company as much as the lottery itself.
This leads to a discussion of attacks. There were several views on how
the threat model should be organised; one succinct statement was `Any attack that can be done by an outsider can be done at least as
well by an insider. So concentrate on insider attacks'. This is
something that almost everyone knows, but which many system designers
disregard in practice. Other candidates pointed out that no system can
defend itself against being owned by a corrupt organisation, and that
senior insiders should be watched with particular care.
Moving now to the more technical analysis, a number of interesting attack scenarios were explored.
. So would banking
industry style batch controls and totals.
There are some secondary design concerns here. How will the machines validate the lower-value tickets that are paid out locally - only online? Or will some of the authenticator code be kept in the vending station? But in that case, how do we cope with the accidental or malicious destruction of the machine that sold a jackpot winning ticket, and how do we pay small winnings when the machine that sold the ticket is offline?
The third type of contribution from the candidates can be roughly classed as reasoning about particular mechanisms.
would do; three pointed
out that even a random number generated by the central server would be
enough (though a MAC might be more convenient).
. Is
this all of the central server or just part of it? How much protection
can you get by separating function across replicated hardware, such as
multiple databases or crypto boxes at the centre, or by having part of
the authenticator computed centrally and part by the vending machine?
In the latter case, do you need to have all the vending machines
online when claims are paid, or do you upload winning authenticators
- in which case what did you gain by decentralising part of the codes
before the draw? The efficacy of replication is well known to be
bounded by common mode errors (particularly specification
errors [13]). And in any case,
how do you prevent yourself
being laid open to service denial attacks? There are similar tradeoffs
involving security and resilience when we consider whether to put the
value counters at the server, in the terminals, or in both. Managing
these tradeoffs may involve several iterations of a detailed design,
with criticism from a number of bright people in parallel.
As we work through these details, it becomes clear that for most of the system, `Trusted' means not just tamper resistant but subject to approved audit and batch control mechanisms.
At the time I set the exam question, I had never played the lottery. I did not perform this experiment until after marking the exam scripts; this helped ensure an even playing field for the candidates. In fact, by the time I got round to buying a ticket, I had already written the first draft of this article and circulated it to colleagues. My description of the ticket purchase process in that draft had been based on casual observation of people ahead of me in Post Office queues, and was wrong in an unimportant but noticeable detail: I had assumed that the authentication code was printed on the form filled by the customer whereas in fact it appears on the receipt (which I have therefore called `the ticket' in this version of the paper). None of my colleagues noticed, and none of them has since admitted to having ever played. Indeed, only one of the candidates shows any sign of having done so. I had expected a negative correlation between education and lottery participation (many churches already denounce the lottery as a regressive tax on the poor, the weak and the less educated) but the strength of this correlation surprised me.
So the above security analysis was done essentially blind - that is, without looking at the existing system. Subsequent observation of the procedures actually implemented by Camelot suggests only two further issues.
The final drafting of the threat model, security policy and detailed functional design is now left as an exercise to the reader.
Linux and Apache prove that software maintenance can be done in parallel; the experiment reported in this paper shows that requirements engineering can too.
There has been collaborative specification development before, as with the `set-discuss' mailing list used to gather feedback during the development of the SET protocol for electronic payments. However, such mechanisms tend to have been rather ad-hoc, and limited to debugging a specification that was substantially completed in advance by a single team. The contribution of this paper is twofold: to show that it is possible to parallelise right from the start of the exercise, and to illustrate how much value one can add in a remarkably short period of time. Our approach is a kind of structured brainstorming, and where a complete specification is required for a new kind of system to a very tight deadline, it looks unbeatable: it produced high quality input at every level from policy through threat analysis to technical design detail.
The bottleneck is the labour required to edit the contributions into shape. In the case of this paper, the time I spent marking scripts, then rereading them, thinking about them and drafting the paper was about five working days. A system specification would usually need less polishing than a paper aimed at publication, but the time saved would have been spent on other activities such as doing a formal matrix analysis of threats and protection mechanisms, and finalising the functional design.
Finally, there is an interesting parallel with testing. It is known that different testers find the same bugs at different rates - even if Alice and Bob are equally productive on average, a bug that Alice finds after half an hour will only be spotted by Bob after several days, and vice versa. This is because different people have different areas of focus in the testing space. The consequence is that it is often cheaper to do testing in parallel rather than series, as the average time spent finding each bug goes down [14]. The exercise reported in this paper strongly supports the notion that the same economics apply to requirements engineering too. Rather than paying a single consultant to think about a problem for twenty days, it will often be more efficient to pay fifteen consultants to think about it for a day each and then have an editor spend a week hammering their ideas into a single coherent document.
I am grateful to the security group at Cambridge, and in particular to Frank Stajano, for a number of discussions. also thank JR Rao of IBM for the history of the `object code only' effort, and Karen Spärck Jones who highlighted those parts of the first draft that assumed too much knowledge of computer security for a general engineering audience, and also persuaded me to buy a ticket.
Finally, the students who contributed many of the ideas described here were an anonymous subset of our third year undergraduates for 1998-9, who were:
PP Adams, MSD Ashdown, JJ Askew, T Balopoulos, KE Bebbington, AR Beresford, TJ Blake, NJ Boultbee, DL Bowman, SE Boxall, G Briggs, AJ Brunning, JR Bulpin, B Chalmers, IW Chaudhry, MH Choi, I Clark, MR Cobley, DP Crowhurst, AES Curran, SP Davey, AJB Evans, MJ Fairhurst, JK Fawcett, KA Fraser, PS Gardiner, ADOF Gregorio, RG Hague, JD Hall, P Hari Ram, DA Harris, WF Harris, T Honohan, MT Huckvale, T Huynh, NJ Jacob, APC Jones, SR King, AM Krakauer, RC Lamb, RJP Lancaster, CK Lee, PR Lee, TY Leung, JC Lim, MS Lloyd, TH Lynn, BR Mansell, DH Mansell, AD McDonald, NG McDonnell, CJ McNulty, RD Merrifield, JT Nevins, TM Oinn, C Pat Fong, AJ Pearce, SW Plummer, C Reed, DJ Scott, AA Serjantov, RW Sharp, DJ Sheridan, MA Slyman, AB Swaine, RJ Taylor, ME Thorpe, BT Waine, MR Watkins, MJ Wharton, E Young, HJ Young, WR Younger, W Zhu.
This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)
Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 lottery.tex.
The translation was initiated by Ross Anderson on 1999-08-17
