Distributed Ledgers: what is so interesting about them?

Some may have noticed I have gone part-time at University College London, and plan to spend the next two years engineering and launching distributed systems as part of the Chainspace project, Vega Protocol and Kryptik. A number of people have asked me “Why would an expert on Privacy Enhancing Technologies develop such an interest in distributed ledgers and blockchains?”. In this post, I will lay down why I think this space is interesting technologically, and also how it interacts and influences the engineering, adoption, and deployment of Privacy Technologies; and  how a number of  societal issues in Privacy may in fact be deeply linked with developments in Blockchains in unexpected ways.

Why are Privacy Enhancing Technologies so interesting in the first place?

Privacy is a multi-faceted field, and I have spent about 20 years working on, evaluating, and advising on systems that broadly protect privacy better than current engineering practices. Those who follow my work may notice a pattern: I research what I call in class “hard privacy” systems, namely those that assume there is no central party that may be trusted to manage honestly user data. Instead, I have used cryptography, and distributed trust to ensure that users can do useful work in a peer-to-peer manner — without disclosing any data to third parties — or, when there is a need for infrastructure, it is distributed and data is encrypted in such a way that multiple entities need to conspire to violate user privacy properties.

“Soft privacy” systems, such as those that help organizations manage privacy of data they hold better, guide cookie and retention policies, prevent discriminatory uses, and implement internal controls are very important and useful — but they are just not my main thing. Why is that? I am fascinated about how privacy interacts with power, be it corporate or government power, and see privacy as a means to ensure both liberty and the possibility of political dissent as well as economic equity through undermining what is now broadly called surveillance capitalism. Collection and access of vast personal datasets already creates such a huge imbalance of power and potential for abuse, that I would rather prevent it through “hard privacy” technologies, rather than manage it through alternatives.

It should already be obvious that the engineering tools we have to use to build cryptographic and distributed systems for privacy, are related to those used to build distributed ledgers: they involve top-notch networking and distributed systems security, including prevention of byzantine faults; the most cutting edge of zero-knowledge and other modern crypto that was initially developed for privacy applications; and a good dose of security economics to ensure all participants in the system have incentives to do the right thing. As such the technical tools between  my type of Privacy Engineering and Distributed Ledgers are one and the same.

So it is obvious why, purely on the basis of technical affinity and curiosity, I may be attracted to distributed ledgers. But it turns out there are also deeper reasons.

So what are distributed ledgers good for?

This is the question that many ask today, as the hype around this family of systems is somewhat tempered by the falling prices of tokens. And the reason the answer is harder than one might expect for a technology that has been in the public eye for over a year, is that many have promised that blockchains are a panacea for all social and technical evils that no technology can possibly be.

So let’s start with what current distributed ledgers are not particularly good for — research challenges that are best summarized in an article by Sarah Meiklejohn. Blockchains do not scale particularly well, and in particular open Nakamoto consensus based on PoW or even PoS does not seem to scale. A number of proposals are on the table, but right now they are all experimental. Blockchains are not particularly usable, either in terms of software but also due to their semantics: probabilistic finality, and a resulting high latency to get assurance. Blockchains also struggle to provide data privacy guarantees for transactional data in the chain — zcash is a gold standard in that space, and recent research shows most transactions are not very private despite best-of-breed techniques being employed. Particularly under the light of the last issue, what could possibly make blockchains interesting to a Privacy Engineer, besides technical curiosity?

There are two interesting aspects of blockchains in that respect: (1) they decentralize transaction systems; and (2) they provide an alternative monetization strategy for providing on-line services. Those, it turns out, could — and the path of technology and its impact on social life is always contingent — be extremely influential when it comes to privacy. I will explain those in turn.

Decentralized Transactions are hard.

As many in the redecentralize movement have pointed out the web and other internet systems, such as email, were initially decentralized. Then something happened in the years 2000-2010, and somehow large quasi-monopolistic service providers appeared to dominate most interactions (lets not be coy we are talking about Facebook, Google, Amazon, and smaller friends). What happened is no conspiracy: we have very good tools to decentralize the distribution of static, read-only, content. In 2000 research on peer-to-peer systems was all the rage, and led to bittorrent on the edgy side, to the DHTs that underpin today interesting projects such as IPFS. Cloudflare could be distributed with the right technical model using those techniques, and we could serve most static content in a decentralized manner.

What we do not know how to decentralize — in general — are “transaction systems”. Those are system, in which users from different security domains (not just one natural owner) may “write” to objects, and mutate their state. The core business of Amazon, Uber, AirBnB as well as more traditional industries such as banking, travel, HR, etc are based on keeping such records and mutating them safely. Traditional databases from oracle to mysql have been the traditional workhorse behind such systems. Cloud platforms allow databases to scale, using complex techniques such as crash-fail resilient consensus and replication — but they require all the infrastructure to be under a single authority.

This technical reality, namely that it is hard to build scalable decentralized transaction systems is one of the reasons why internet monopolies came to dominate most of our interactions.  However, this cannot explain everything (nothing can): techniques for achieving decentralized byzantine fault tolerance have been known since the 1980s-1990s, with PBFT and all that. So how comes they did not catch up? And when I say they did not catch up, I mean pretty much not at all: a couple of years ago one would struggle to find a single PBFT usable library in most languages. I would argue this is related to economics.

Lack of Economic model.

When the googles and facebooks of this earth established themselves it was not clear how they would make any money. Therefore they innovated, and established the ad-based model by which the user is not the customer, but rather their attention is a product to be targeted and sold for adverts. This led to the establishment of surveillance capitalism that now seems to run deeper, and also interacts in questionable ways with the advancements in machine learning — another fascinating field of computer science.

So for the years 2000-2010 the main monetization vision of online services launched was the collection of personal information, and the resulting generation of ad revenue. However, it turns out that personal information is more akin to tar sands than oil: an organization needs a lot of it to refine it into something useful — and that also leads to a monopolistic situation in which platforms that already have captured the ad revenue and a lot of personal data are difficult to dislodged. I think this has now sank in the psyche of engineers and entrepreneurs and I hardly hear any new businesses aiming to dislodge Google in terms of ad revenue — for which I am thankful. That market is captured and closed.

For a while an alternative model, based on selling mobile apps first, and then selling in-app purchases gave a glimpse of hope that on line services may be able to monetize, but that also did not last. The most monetized app were akin to “digital crack”, seeking to develop users with strange addictions; eventually others such as Instagram and Whatsapp got bough by large incumbents. Today most independent app developers make little money are are subject to the whims of every app store that may delist them at will — also controlled by large incumbents that take up to a 30% cut on revenues.

How could one have built decentralized alternatives to those? What is WhatsApp or Instagram were to operate their systems on the basis of decentralization — they would each require not one, by over four authorities to operate. What would be the incentives of such authorities to do a good job? And how could they cover their costs? This was a problem. The Tor network, for example, operates on the basis of volunteers running relays, research, foundation and state department funding — a model that cannot scale to run significant infrastructures.

Blockchains provide both technical and economic answers to enable decentralization.

This is where blockchains start to become interesting. Distributed ledgers provide platforms to technically make building decentralized apps minimally humane. Now, writing larger correct decentralized apps in solidity for Ethereum, for example, cannot be described as the most pleasant development experience. But take my word for it, it is much better than having to start from scratch writing your own byzantine consensus protocols, and ensuring they are correct. Thus they offer a technical alternative for writing transaction systems that are decentralized.

Secondly, blockchain systems integrate a system of incentives and monetization. Nodes operating the infrastructure are remunerated in many ways, from mining rewards to fees, using a micropayment system that is integrated into the platform. This solves the question of “who are the decentralized authorities and why would they work for me?” that blocked the deployment of such decentralized systems before.

At the same time, for all its ills, the ICO model — by which projects would issue their own tokens for use in a system — also provided incentives for founders and developers to initiate a project, fund development and often maintenance. Thus services on blockchains do not have to rely on ad revenue, but can instead rely on fees to survive and be sustainable, at least in theory. The open access model of those platforms also ensure that both infrastructure nodes and developers can invest in building apps without fear they may be arbitrarily excluded.

Those two features of blockchain platforms have profound implication for privacy, even though the platforms themselves today do not protect data privacy very well. First, they undermine the monopolistic position of large service providers — that by virtue of accumulating masses of user data, and using it as part of an advertising based economic model, fundamentally cannot be privacy friendly. Undermining those large silos of data both frees people from the whims of those platforms, the wide use of data to manipulate them, but also the secondary threats of governments (domestic and foreign) then dipping into those databases for their own purposes. Allowing users to pay for services they access also ensures that those services can survive and be sustainable, in ways other than selling out their users’ data.

So in brief, blockchains align incentives correctly: control over the service is decentralized, and usually subject to code (smart contracts) to ensure users are not subject to the arbitrary and opaque decision making of large online service monopolies; and secondly that payments are made to those that maintain infrastructure and services, to ensure they do not need to be tempted to pry as a business model. If this model is a success — subject to a number of contingencies — it may provide a good foundation for better, more open and humane, transaction systems that could actually redecentralize the internet.

Challenges ahead.

While the incentives are aligned this does not mean that current blockchains actually achieve all those great goals, and in particular that they provide strong privacy guarantees. For this reason I have spent some of my research time in the past looking at how we can use efficient zero-knowlege to protect privacy in transaction systems, as well as how to scale up cryptographic monetary systems and smart contract platforms with Chainspace. Scaling up those platforms to make them truly competitive with large on-line service providers and other ‘sharing economy’ silos is indeed the subject of my new start-up chainspace.io.

With their fall the adoption of Privacy Enhancing Technologies can finally be unblocked. And already we see some of the most advanced cryptographic techniques, including zero-knowledge and selective disclosure credentials, being fielded in the context of blockchains, where they have seen little traction elsewhere in the past 20 years. While large internet services make most of their money from mining user data for ads or optimization those technologies stand no chance to see the light of day at a large scale.

I would welcome anyone working in the fields of threshold crypto-systems, multi-party computation, and censorship circumvention — techniques that intrinsically require multiple authorities to work together, to consider how their distributed infrastructures could be both engineered and incentivized using and adapting ideas from the distributed ledger research community.

Are you off for good?

The final question people ask: am I going away from academia and UCL for good? Rest assured I am coming back. My roles in all ventures involve research; I am committed to my PhD students, joint projects and colleagues at UCL; and I feel deeply passionate about teaching new generation both security engineering and privacy technologies. UCL is my natural home in the UK, being a truly open university to the world, traditionally progressive in its outlook, and in the heart of London. My adventures in industry, however successful, will only make me a stronger scholar.

Thoughts on “Oft Target” (HotPETs 17)

I just watched the, as ever provocative, presentation of Paul Syverson at HotPETs 2017, on targeting adversaries against Tor. I will just put down here some thoughts on onion routing, threat models, and security engineering loosely related to the talk.

Onion routing, as a concept, has committed an original sin, that has since its inception been haunting it: it dismisses the Global Passive Adversary as “unrealistic”, and attempts to provide anonymity properties against most limited “realistic” adversaries. This was necessary to achieve the performance and low cost required for anonymizing streams; it also seems logical enough to only protect against the actual adversaries that can be instantiated. Yet, with hint sight, it opens the door to all sorts of practical attacks, and also (importantly) theoretical confusion.

The Global Passive Adversary (GPA) is an abstraction, not a real thing. In security engineering, saying that the GPA is the adversary of a scheme means that the designers ensure that the schemes security properties hold even though all network communications are visible to the adversary. However, this is not the important practical implication. When a scheme is secure against the GPA it is also secure against any subset of network traffic, or any aspects of the network traffic — content or meta-data — being available to the adversary.

So while the GPA cannot exist, adversaries that have subsets of the GPA capability of course exist and are ubiquitous. Trivially, your ISP, your employer, an internet exchange, or the NSA, all can capture some traffic. The GPA model ensures a scheme is secure against them all. So while the GPA in its full capacity is not realistic, any subset of the GPA becomes realistic. The key question is: which subset is relevant? Different users would be concerned with different subsets; which exact subset the adversary has, is usually a well guarded secret; and assumptions about cost etc, are fragile.

A subtle implication of a scheme being secure against a GPA is that any aspect of the traffic can be seen by the adversary without compromising the anonymity system. That is not limited to actually capturing the traffic on the list, but also all partial function or views of the traffic. Paul presents a very interesting example of IRC traffic: even observing one user’s IRC traffic to a hidden IRC server, gives a very good idea of what the traffic will look like in all other links carrying the same IRC channel. In this case the adversary leverages knowledge of the structure of the IRC protocol (namely it relays chat traffic and mirrors it to all users in a channel), to build models of the network traffic that can be used to detect the channel.

This capability is taken into account when a system protects against the GPA. However, when a system like onion routing, only protects against “partial” or “local” adversaries, it is unclear what this implies about an adversary’s prior knowledge about the protocol, and indirect observations of load on far links. Such indirect observations were used in our early 2005 traffic analysis of tor paper. Fingerprinting websites is also another setting in which an an adversary does not have to “see” one side of an onion routing connection, and may simply model it and match the model using machine learning techniques.

So to conclude: the GPA does not exist, it is a super set of all adversaries users may care. But because we cannot know which is real, we chose to protect against the GPA. Furthermore, not only we do not what links or messages real adversaries can access, but we are also unsure about what other types of information they may extract from links that are not fully observed — through indirect observation, knowledge of the protocols, or modelling. Thus it is very likely that we will continue to see the slow trickle of attacks against onion routing systems as researchers discover more about capabilities or real adversaries, better side-channels to observe relevant information from far links, or better models for web or IRC traffic that require no or few observations.

Simpler secure group messaging? (PETS17)

I am at the Privacy Enhancing Technologies Symposium in Minnesota. As it is customary the conversations with other privacy researchers and developers are extremely engaging. One topic I discussed over beer with Mike Perry and Natalie Eskinazi is whether secure group messaging protocols could be simplified by relaxing some of their security and systems assumptions.

In the past I questioned whether group key agreements need to be contributory of symmetric. In this post I argue that plausible deniability properties can be relaxed, leaderlessness assumptions may be too strong, full asynchrony unnecessary, and high-scalability unlikely to make a difference. In brief, protocol designers should stop looking for the perfect protocol, with all features, and instead design a protocol that is good enough. This is controversial, so I will discuss those one by one.

Plausible deniability within a group?

Off-the-record messaging protocols, from OTR to the protocols underlying signal / whatsapp, provide cryptographic plausible deniability. In a nutshell, this means that when Alice talks to Bob, after a certain point in time Bob will not be able to prove cryptographically to any other party that Alice sent a particular message. This is technically achieved by either publishing the signature keys used after a while, or using symmetric message authentication codes to ensure Bob could have forged any authenticatior.

Before moving to the group setting it is worth thinking what plausible deniability buys you in the 2-party case: It protects Alice from an adversary, that needs cryptographic proof that she said a particular thing to Bob. However, the adversary — at the time of the conversation cannot be Bob. Bob is convinced that it is Alice that sent a message — and thus there is no need for other evidence. Similarly, if Bob is fully trusted by the adversary — for example to keep a tamper proof log of all messages sent and received and all secrets — then the defense is ineffective.

Plausible deniability protects Alice in a very narrow setting: When Alice sent a message to Bob, who at the time was honestly following the protocol, and that in the future decides to work with an adversary (that does not fully trust Bob) to convince the adversary that Alice said something. Even in the 2-party case, this is quite eclectic.

However, this property becomes even more elusive in the multi-party case. Imagine that Alice sends a message to a group of 7 participants, though a channel providing plausible deniability. At the time the message is received by 6 parties, that are all convinced that it came from Alice. For plausible deniability to be meaningful, all those parties at that time should not be adversaries. Then, down the line one or more (incl. Alice) transcripts are leaked, and the those transcripts do not contain any cryptographic authenticators for Alice.

However, for adversaries not performing legal attacks (when a court needs to be convinced of a fact) the lack of authenticators has never been a barrier to believe in a transcript of a conversation. Similarly, courts in the UK, do not rely on cryptographic authenticators to ensure authenticity: a record of a conversation, backed by an expert witness that states that it is unlikely to have been modified (through forensics) is sufficient. Furthermore, in the context of a group chat there will be multiple transcripts, all matching — unless users engaged in a very wide conspiracy to make the discussion look like something else. No software facilitates this, and without this facility, plausible deniability would provide a meaningless protection.

So my conclusion is as follow: a weak form of plausible deniability may be provided by ensuring honest parties delete authenticators (incl. signatures) once they have been checked. This ensures that honest captured devices do not contain cryptographic evidence. However, as we discussed above, dishonest parties can anyway bypass plausible deniability — and thus providing it through crypto tricks increases complexity without providing much protection.

So I advocate for the simple options of using signatures and deleting them upon reception. If your chat partners are bad, and do not delete it at this point, you are in trouble anyway.

Groups will always be small.

People want to have private conversations within groups. However, how large can these groups be until at least one of the participants or their device is compromized? The size of the group is often used in secure group chat protocols as a parameters N, and the cost of the  protocol in terms of number of messages or their size can be O(N) or O(1) or O(logN). However, this is meaningless since N will never become too big — for systems or operational security reasons.

Thus secure group chat protocols that work well for small number of users are likely to be good enough — no need to optimize in terms of N. Optimizations that reduce the constant factors are likely to be as important.

Submitting to a leader & asynchrony

Significant complexities arise in secure group chat protocols from the implicit assumption that all members of the group are equal, they talk through point-to-point messages, and that no infrastructure exists that can be trusted to anything relating to the chat. However, this is not how popular chat programs work: irc, xmpp, signal, whatsapp all rely on servers to mediate communications, and provide some services!

The most important service that can be provided by a central party is ordering: a server or a special participant can assume a “leader” role to order messages, in a total order that others will accept. They may be prevented from doing this arbitrarily: clients can include enough information to ensure that the total order imposed is compatible with causal ordering of messages (as Ximin Luo points out). However, since there is no canonical total ordering, why not rely on the ordering imposed by one of the members of the group (the leader) or a services mediating the communications.

Of course, a key challenge when relying on a leader is what happens when the leader dies or goes off line. When there is a graceful exit the leader can handover to the next leader. When there is a crash-failure things become more complex: group member need to detect the failure and replace the leader. This is complex in systems assuming high degrees of asynchrony, where there is no cut-off time out after which one can be sure another node it dead. In that case paxos or pBFT protocols need to be used to do leader election and consensus. However, if one ditches this assumption, and instead assumes that there exists a perfect failure detector — then nodes can detect failures and replace the leader.

Now, in practice users do not expect a chat session to survive the demise of the service they use (be it skype, whatsapp, or facebook). So it seems that providing such a property for secure group chat is unnecessarily complex.

Conclusion.

I would now advocate group secure messaging systems on the following lines:

• Ditch full plausible deniability; use signatures, and rely on honest parties to delete them upon checking.
• Design systems for optimal operation with group sizes of 3-50. There is no point in having much larger groups, or killing designs on the basis they do not perform when N goes to infinity.
• Rely on an infrastructure server or a leader within the group to offer consistent total ordering to all. Assume that others can detect its liveness through a timeout (synchronous), and either elect or rotate another one in. Or simply, stop the chat session once they become unavailable.

The politics of the NHS WannaCrypt ransomware outbreak

You know you live in 2017 when the top headline on national newspapers relates to a ransomware attack on the National Heath Service, the UK Prime minister comments on the matter, and the the security researchers dealing with the outbreak are presented as heroic figures. As ever, The Register, has the most detailed and sophisticated technical article on the matter. But also strangely the most informative in terms of public policy. As if somehow, in our days, technical sophistication is a prerequisite also for sophisticated political comment on those matters. Other news outlets present a caricature, of the bad malware authors, the good security researcher and vendors working around the clock, the valiant government defenders, and a united humanity trying to beat the virus. I want to break that narrative open in this article, and discuss the actual political and social lessons we should be learning. In part to avoid similar disasters in the future.

First off, I am always surprised when such massive systemic outbreaks of malware, are blamed squarely on the author(s) of the malware itself, and the blame game ends there. It is without doubt that the malware author has a great share of responsibility. I personally think it is immoral to deploy ransomware in the wild, deny people access to their data, and seek to benefit from this. It is also a crime in the UK and elsewhere.

However, it is strange that a single author, or a small group of authors, without any major resources can have such a deep and widespread effect on major technological infrastructures. The absurdity becomes clear if we transpose the situation into the world of traditional engineering. Imagine all skyscrapers in major cities had to be evacuated, because a couple of teenagers with rocks were trying to blackmail business owners to pay up, to protect their precious glass windows. The fragility of software and IT systems seems to have no parallel in any other large scale engineering infrastructure — and this is not inherent, but the result of very specific micro-political, geo-political and economic decisions.

Lets take the WannaCrypt outbreak and look at the political and other social decisions that lead to the disaster — besides the agency of the malware authors:

• The disaster was possible in part, and foremost, because IT systems within the UK critical NHS infrastructure are outdated — and for example rely on Windows XP that is not any more being maintained by Microsoft. Well, actually this is not strictly true: Microsoft does make security updates for Windows XP, but does not provide them for free — and instead Microsoft expects organizations that are locked in the OS to pay up to get patches and stay safe. So two key questions need to be asked …
• Why is the NHS not upgrading to a new versions of Windows, or any other modern operating system? The answer is simple: line of business applications (LOB: from heath record management, specialist analysis and imaging software, to payroll) may not be compatible with new operating systems. On top of that a number of modern medical devices, such as large X-ray scanners or heart monitors, come with embedded computers running Windows XP — and only Windows XP. There is no way of upgrading them. The MEDJACK cyber-attacks were leveraging this to rampage through hospitals in 2015.
• Is having LOB software tying you to an outdated OS, or medical devices costing millions that are not upgradeable, a fact of nature? No. It is down to a combination of terrible and naive procurement processes in health organizations, that do not take into account the need and costs if IT and security maintenance — and do not entrench it into the requirements and contracts for services, software and devices. It is also the result of the health software and devices industries being immature and unsophisticated as to the needs to secure IT. They reap the benefits of IT to make money, but without expending much of it to provide quality and security. The tragic state of security of medical devices has built the illustrious career of my friend Prof. Kevin Fu, who has found systemic attacks against implanted heart devices that could kill you, noob security bugs in medical device software, and has written extensively on the poor strategy to tackle these problem. So today’s attacks were a disaster waiting to happen — and expect more unless we learn the right lessons.
• So given the terrible state of IT that prevents upgrading the OS, why is the NHS not paying up Microsoft to get security patches? That is because the government, and Jeremy Hunt in particular, back in 2014 decided to not pay up the money necessary to keep receiving security updates for Windows XP, despite being aware of the absolute reliance of the NHS on the outdated software. So in effect, a deliberate political decision was taken, at the highest level of the government to leave the NHS open to cyber attack. This is unlikely to be the last Windows XP security bug, so more are presumably to come.
• Then there is the question of how malware authors, managed to get access to security bugs for windows XP? How did they get the tools necessary to attack such a mature, and rather common system, about 15 years after Windows XP was released, and only after it went out of maintenance? It turn out that the vulnerabilities they used, were in fact hoarded by the NSA as a cyber weapon — which was lost or stolen by hackers or leakers, and released into the wild! (The tool was codenamed EternalBlue). For may years, the computer security research community has been warning that stockpiling vulnerabilities in very common software for cyber-offense purposes, is dangerous. When those cyber weapons are lost, leaked, or even just used, there is proliferation of the technology necessary to attack, which criminals and foreign states can turn against critical infrastructure. This blog commented on the matter as recently as March 8, 2017 in a post entitled “What the CIA hack and leak teaches us about the bankruptcy of current “Cyber” doctrines”. This now feels like an unfortunately fulfilled prophesy, but the NHS attack was just the expected outcome of the US/UK and now common place doctrine around cyber — that contributes to and leverages insecurity rather than security. Alternative public policy options exist of course.

So to summarize, besides the author of the malware, a number of other social and systemic factors contribute to making such cyber attacks possible: from poor security standards in heath informatics industries; poor procurement processes in heath organizations; lack of liability on any of the software vendors (incl. Microsoft) for providing insecure software or devices; cost-cutting from the government on NHS cyber security with no constructive alternatives to mitigate risks; and finally the UK/US cyber-offense doctrine that inevitably leads to proliferation of cyber-weapons and their use on civilian critical infrastructures.

It it those systemic factors that need to change to avoid future failures. Bad people wishing to make money from ransomware, or other badness, will always exist. There is a discipline devoted to preventing this, and it is called security engineering. It is time industry and goverment start taking its advice seriously.

 

What the CIA hack and leak teaches us about the bankruptcy of current “Cyber” doctrines

Wikileaks just published a trove of documents resulting from a hack of the CIA Engineering Development Group, the part of the spying agency that is in charge of developing hacking tools. The documents seem genuine and catalog, among other things,  a number of exploits against widely deployed commodity devices and systems, including Android, iPhone, OS X and Windows. Also smart TVs. This hack, with appropriate background, teaches us a lesson or two about the direction of public policy related to “cyber” in the US and the UK.

PETS 2016: On Realistically Attacking Tor with Website Fingerprinting

I am at PETS 2016 writing this summary in real-time as Tao Wang presents his work with Ian Goldberg on “On Realistically Attacking Tor with Website Fingerprinting“. This is the latest paper addressing challenges identified by the Tor project to make website fingerprinting (WF) research more informative about real-world threats. We have a stake in this since Jamie Hayes from UCL will be presenting a joint paper on k-fingerprinting: a Robust Scalable Website Fingerprinting Technique.

The key problem is that a number of reported website fingerprinting results are evaluated in laboratory conditions. Website fingerprinting considers an adversary looking at an encrypted and anonymized stream, and the task is to recognize which website is being accessed through the protections. However, the evaluation of the attacks consider a restricted and stylized setting, where a single client accesses a single (usually landing) page from a server. This is restrictive: it does not consider accessing multiple pages, it assumed the start and end of pages is known, and that the training data is up to date.

So this paper consider how to deal with such setting. First, how to deal with noisy data? For example, what is another tab creates some continuous traffic, aka noise that may confuse the attacker? In this case the attacker will see a combined stream of the signal from a page load superimposed on the noise. Tao illustrates that as the volume of noise increases the accuracy of attacks radically drops. Trivial solutions such as trying to subtract noise are not likely to succeed.So the actual solution is to train on the noisy version of the stream, and that indeed increases the accuracy of the attack back to dangerous levels.

The second problem is splitting: how can an attacker detect the start and end of loading a specific bundle of resources corresponding to a web page. There can either be a lot of quiet time between loads, no time, or even a negative time when the loads overlap. It turns out when there is a large gap it can be overcome with little effect on the True positive rate — as the split is obvious. However, the problem has a generic solution for other cases: you simply use a classifier to learn where to split, and then apply the classifier. I do wonder if using both incoming and outgoing channels could improve this.

Finally, they address the issue of maintaining a training set, since it is expensive to collect such data continuously. So either you have a small fresh training set, or a larger but out of date training set. There is a trade-off, but Tao demonstrates that even old-ish (10 days) still provides good accuracy. In conclusion, it seems that those roadblocks can be tackled to make WF practical, and there is an increased call to implement defenses.

My meta-conclusion is twofold: first, it is clear that the roadblocks presented first by the tor project blog post are indeed issues, but are not a game stopper for website fingerprinting. It took the community about 2 years to mature into using more modern machine learning (ML) techniques, and this work illustrates this. Yet, my second conclusion is that the maturity of the ML usage for fingerprinting is still low: it is pretty self-evident that to be robust to noise one should train on noisy data — I am glad this is now explicit. It is also self-evident that we can take small data sets of pages and network conditions and synthesize a very large set of training examples to make learning even more robust to noise and better at detecting splits. No one has done this yet — maybe that would be a nice paper for PETs next year.

 

 

Strategic nation-state attacks on proof-of-work cryptocurrencies

I am currently attending the Corfu Bitcoin “school” partly supported by our NEXTLEAP project, and gathering some of my favourite researchers, including Joe Bonneau who just presented a lecture on bitcoin mining. He gave a fantastic overview of the evolution of mining technology, leading to large specialized pools of custom hardware located in jurisdictions with cheap subsidised electricity. He dispelled the myth that bitcoin mining consumes vast amounts of energy: it apparently consumes about one coal plant’s worth. He also presented many attacks devised in the literature, including selfish mining and beyond. Interestingly he concluded that those sophisticated attacks would leave traces on the network, and have never been observed.

However, considering that the purpose of bitcoin / proof-of-work type crypto-currencies is to free such systems from the control of nation states the above is quite worrisome. A strategic nation state that seeks to increase control over such a currency has a simple and deniable strategy: such a nation simply has to provide a small subsidy for electricity used to mine. As a result market forces will ensure that a majority of miners will move there; make immovable investments in the form of data centres and mining gear; and eventually be within reach of traditional regulatory mechanisms in that jurisdiction. Preventing such centralizing tendencies would require institutions ensuring the jurisdictional diversity of mining – akin to anti-monopoly regulators – that are antithetical to proof-of-work consensus (unless they could be implemented in a peer-to-peer manner?).

Interestingly, Joe, in his talk hinted that the concentration of mining pools and farms in China and elsewhere might be the result of better deals and state subsidies for electricity. Of course, whether this is the result of a strategic choice to control a crypto-currency or simply a contingent effect is difficult to determine. This proves that such an attack would indeed be very hard to detect as an attack.

It is in fact doubtful if this is, strictly speaking, an attack or simply an instrument of national industrial or foreign policy. After all states have been using modest subsidies to attract, control and regulate industries: London provides a favourable regime for finance, and Greece has good provisions to attract tourism. Thus it is conceivable that a nation may choose to attract and then benefit from such a control over proof-of-work cryptocurrencies. What is certain is that proof-of-work is far from being the silver bullet against centralization and potential state control.

The Poverty of “Crypto and Empire”: against a narrowing of the politics of cryptography

One of the rare joys of being a live author, is the ability to interpret your own works, as well as to help others when they try to do so. In that context it was, as ever, a pleasure to read Gürses et al. recent article on “Crypto and empire: the contradictions of counter-surveillance advocacy” and reflect on the insights it provides. It is also nice to be in a position to highlight that a number of thesis it puts forward are in fact artefacts of preconceptions and selective reading of events. While this is useful to abstract and present a clear argument, it is unhelpful when it results in misleading conclusions and interpretations.

Broadly speaking the article argues that the distinction between mass surveillance and targeted surveillance, sweeps under the carpet questions of political legitimacy of current forms of targeted surveillance. It also ignores the fact that mass electronic surveillance, as revealed by Edward Snowden, was in fact targeted towards select populations, for specific political reasons.

I think this is insightful — although I like this straight forward formulation better than the one from the original article, which makes broad assertions linked with a specific, US centric view of identity politics. Are the mass surveillance programs selecting on a “racial, gendered, classed, and colonial” basis per se? Or simply on the basis of the national and economic interests of the nations that implemented them, current geopolitical priorities, and the needs of political elites that commissioned them? I find the latter explanation simpler. Although, I have written in some length about how control of technology among certain nations could lead to a new form of cyber-colonialism. So I may be partly to blame for inspiring this — to which I will return.

A technical reading of the “HIMR Data Mining Research Problem Book”

Boing Boing just released a classified GCHQ document that was meant to act as the Sept 2011 guide to open research problems in Data Mining. The intended audience, Heilbronn Institute for Mathematical Research (HIMR), is part of the University of Bristol and composed of mathematicians working for half their time on classified problems with GCHQ.

First off, a quick perusal of the actual publication record of the HIMR makes a sad reading for GCHQ: it seems that very little research on data mining was actually performed post-2011-2014 despite this pitch. I guess this is what you get trying to make pure mathematicians solve core computer science problems.

However, the document presents one of the clearest explanations of GCHQ’s operations and their scale at the time; as well as a very interesting list of open problems, along with salient examples.

Overall, reading this document very much resembles reading the needs of any other organization with big-data, struggling to process it to get any value. The constrains under which they operate (see below), and in particular the limitations to O(n log n) storage per vertex and O(1) per edge event, is a serious threat — but of course this is only for un-selected traffic. So the 5000 or so Tor nodes probably would have a little more space and processing allocated to them, and so would known botnets — I presume.

Secondly, there is clear evidence that timing information is both recognized as being key to correlating events and streams; and it is being recorded and stored at an increasing granularity. There is no smoking gun as of 2011 to say they casually de-anonymize Tor circuits, but the writing is on the wall for the onion routing system. GCHQ at 2011 had all ingredients needed to trace Tor circuits. It would take extra-ordinary incompetence to not have refined their traffic analysis techniques in the past 5 years. The Tor project should do well to not underestimate GCHQ’s capabilities to this point.

Thirdly, one should wonder why we have been waiting for 3 years until such clear documents are finally being published from the Snowden revelations. If those had been the first published, instead of the obscure, misleading and very non-informative slides, it would have saved a lot of time — and may even have engaged the public a bit more than bad powerpoint.

The Social Construction of Trust in Cryptographic Systems

(This is an extract from my contribution to Harper, Richard. “Introduction and Overview”, Trust, Computing, and Society. Ed. Richard H. R. Harper. 1^st ed. New York: Cambridge University Press, 2014. pp. 3-14. Cambridge Books Online. Web. 03 February 2016. http://dx.doi.org/10.1017/CBO9781139828567.003)

Cryptography has been used for centuries to secure military, diplomatic, and commercial communications that may fall into the hands of enemies and competitors (Kahn 1996). Traditional cryptography concerns itself with a simple problem: Alice wants to send a message to Bob over some communication channel that may be observed by Eve, but without Eve being able to read the content of the message. To do this, Alice and Bob share a short key, say a passphrase or a poem. Alice then uses this key to scramble (or encrypt) the message, using a cipher, and sends the message to Bob. Bob is able to use the shared key to invert the scrambling (or “decrypt”) and recover the message. The hope is that Eve, without the knowledge of the key, will not be able to unscramble the message, thus preserving its confidentiality.

It is important to note that in this traditional setting we have not removed the need for a secure channel. The shared key needs to be exchanged securely, because its compromise would allow Eve to read messages. Yet, the hope is that the key is much shorter than the messages subsequently exchanged, and thus easier to transport securely once (by memorizing it or by better physical security). What about the cipher? Should the method by which the key and the message are combined not be kept secret? In “La Cryptographie Militaire” in 1883, Auguste Kerckhoffs stated a number of principles, including that only the key should be considered secret, not the cipher method itself (Kerckhoffs 1883). Both the reliance on a small key and the fact that other aspects of the system are public is an application of the minimization principle we have already seen in secure system engineering. It is by minimizing what has to be trusted for the security policy to hold that one can build and verify secure systems – in the context of traditional cryptography, in principle, this is just a short key.

Kerckhoffs argues that only the key, not the secrecy of the cipher is in the trusted computing base. But a key property of the cipher is relied on: Eve must not be able to use an encrypted message and knowledge of the cipher to recover the message without access to the secret key. This is very different from previous security assumptions or components of the TCB. It is not about the physical restrictions on Eve, and it is not about the logical operations of the computer software and hardware that could be verified by careful inspection. It comes down to an assumption that Eve cannot solve a somehow difficult mathematical problem. Thus, how can you trust a cipher? How can you trust that the adversary cannot solve a mathematical problem?

To speak the truth, this was not a major concern until relatively recently, compared with the long history of cryptography. Before computers, encoding and decoding had to be performed by hand or using electromechanical machines. Concerns such as usability, speed, cost of the equipment, and lack of decoding errors were the main concerns in choosing a cipher. When it comes to security, it was assumed that if a “clever person” proposes a cipher, then it would take someone much cleverer than them to decode it. It was even sometimes assumed that ciphers were of such complexity that there was “no way” to decode messages without the key. The assumption that other nations may not have a supply of “clever” people may have to do with a colonial ideology of nineteenth and early twentieth centuries. Events leading to the 1950s clearly contradict this: ciphers used by major military powers were often broken by their opponents.

In 1949, Claude Shannon set out to define what a perfect cipher would be. He wanted it to be “impossible” to solve the mathematical problem underlying the cipher (Shannon 1949). The results of this seminal work are mixed. On the positive side, there is a perfect cipher that, no matter how clever an adversary is, cannot be solved – the one-time pad. On the down side, the key of the cipher is as long as the message, must be absolutely random, and can only be used once. Therefore the advantage of short keys, in terms of minimizing their exposure, is lost and the cost of generating keys is high (avoiding bias in generating random keys is harder than expected). Furthermore, Shannon proves that any cipher with smaller keys cannot be perfectly secure. Because the one-time pad is not practical in many cases, how can one trust a cipher with short keys, knowing that its security depends on the complexity of finding a solution? For about thirty years, the United States and the UK followed a very pragmatic approach to this: they kept the cryptological advances of World War II under wraps; they limited the export of cryptographic equipment and know-how through export regulations; and their signal intelligence agencies – the NSA and GCHQ, respectively – became the largest worldwide employers of mathematicians and the largest customers of supercomputers. Additionally, in their roles in eavesdropping on their enemies’ communications, they evaluated the security of the systems used to protect government communications. The assurance in cryptography came at the cost of being the largest organizations that know about cryptography in the world.

The problem with this arrangement is that it relies on a monopoly of knowledge around cryptology. Yet, as we have seen with the advent of commercial telecommunications, cryptography becomes important for nongovernment uses. Even the simplest secure remote authentication mechanism requires some cryptography if it is to be used over insecure channels. Therefore, keeping cryptography under wraps is not an option: in 1977, the NSA approved the IBM design for a public cipher, the Data Encryption Standard (DES), for public use. It was standardized in 1979 by the US National Institute for Standards and Technology (NIST).

The publication of DES launched a wide interest in cryptography in the public academic community. Many people wanted to understand how it works and why it is secure. Yet, the fact that the NSA tweaked its design, for undisclosed reasons, created widespread suspicion in the cipher. The fear was that a subtle flaw was introduced to make decryption easy for intelligence agencies. It is fair to say that many academic cryptographers did not trust DES!

Another important innovation in 1976 was presented by Whitfield Diffie and Martin Hellman in their work “New Directions in Cryptography” (Diffie & Hellman 1976). They show that it is possible to preserve the confidentiality of a conversation over a public channel, without sharing a secret key! This is today known as “Public Key Cryptography,” because it relies on Alice knowing a public key for Bob, shared with anyone in the world, and using it to encrypt a message. Bob has the corresponding private part of the key, and is the only one that can decode messages used with the public key. In 1977, Ron Rivest, Adi Shamir, and Leonard Adleman proposed a further system, the RSA, that also allowed for the equivalent of “digital signatures” (Rivest et al. 1978).

What is different in terms of trusting public key cryptography versus traditional ciphers? Both the Diffie-Hellman system and the RSA system base their security on number theoretic problems. For example, RSA relies on the difficulty of factoring integers with two very large factors (hundreds of digits). Unlike traditional ciphers – such as DES – that rely on many layers of complex problems, public key algorithms base their security on a handful of elegant number theoretic problems.

Number theory, a discipline that G.H. Hardy argued at the beginning of the twentieth century was very pure in terms of its lack of any practical application (Hardy & Snow 1967), quickly became the deciding factor on whether one can trust the most significant innovation in the history of cryptology! As a result, a lot of interest and funding directed academic mathematicians to study whether the mathematical problems underpinning public key cryptography were in fact difficult and how difficult the problems were.

Interestingly, public key cryptography does not eliminate the need to totally trust the keys. Unlike traditional cryptography, there is no need for Bob to share a secret key with Alice to receive confidential communications. Instead, Bob needs to keep the private key secret and not share it with anyone else. Maintaining the confidentiality of private keys is simpler than sharing secret keys safely, but it is far from trivial given their long-term nature. What needs to be shared is Bob’s public key. Furthermore, Alice need to be sure she is using the public key associated with the Bob’s private key; if Eve convinces Alice to use an arbitrary public key to encrypt a message to Bob, then Eve could decrypt all messages.

The need to securely associate public keys with entities has been recognized early on. Diffie and Hellman proposed to publish a book, a bit like the phone register, associating public keys with people. In practice, a public key infrastructure is used to do this: trusted authorities, like Verisign, issue digital certificates to attest that a particular key corresponds to a particular Internet address. These authorities are in charge of ensuring that the identity, the keys, and their association are correct. The digital certificates are “signed” using the signature key of the authorities that anyone can verify.

The use of certificate authorities is not a natural architecture in many cases. If Alice and Bob know each other, they can presumably use another way to ensure Alice knows the correct public key for Bob. Similarly, if a software vendor wants to sign updates for their own software, they can presumably embed the correct public key into it, instead of relying on public key authorities to link their own key with their own identity.

The use of public key infrastructures (PKI) is necessary in case Alice wants to communicate with Bob without them having any previous relationship. In that case Alice, given only a valid name for Bob, can establish a private channel to Bob (as long as it trusts the PKI). This is often confused: the PKI ensures that Alice talks to Bob, but not that Bob is “trustworthy” in any other way. For example, a Web browser can establish a secure channel to a Web service that is compromised or simply belong to the mafia. The secrecy provided by the channel does not, in that case, provide any guarantees as to the operation of the Web service. Recently, PKI services and browsers have tried to augment their services by only issuing certificates to entities that are verified as somehow legitimate.

Deferring the link between identities and public keys to trusted third parties places this third party in a system’s TCB. Can certification authorities be trusted to support your security policy? In some ways, no. As implemented in current browsers, any certification authority (CA) can sign a digital certificate for any site on the Internet (Ellison & Schneier 2000). This means that a rogue national CA (say, from Turkey) can sign certificates for the U.S. State Department, that browsers will believe. In 2011, the Dutch certificate authority Diginotar was hacked, and their secret signature key was stolen (Fox-IT 2012). As a result, fake certificates were issued for a number of sensitive sites. Do CAs have incentives to protect their key? Do they have enough incentives to check the identity of the people or entities behind the certificates they sign?

Cryptographic primitives like ciphers and digital signatures have been combined in a variety of protocols. One of the most famous is the Secure Socket Layer SSL or TLS, which provides encryption to access encrypted Web sites on the Internet (all sites following the https://  protocol). Interestingly, once secure primitives are combined into larger protocols, their composition is not guaranteed to be secure. For example a number of problems have been identified against SSL and TLS that are not related to the weaknesses of the basic ciphers used (Vaudenay 2002).

The observation that cryptographic schemes are brittle and could be insecure even if they rely on secure primitives (as did many deployed protocols) led to a crisis within cryptologic research circles. The school of “provable security” proposes that rigorous proofs of security should accompany any cryptographic protocol to ensure it is secure. In fact “provable security” is a bit of a misnomer: the basic building blocks of cryptography, namely public key schemes and ciphers cannot be proved secure, as Shannon argued. So a security proof is merely a reduction proof: it shows that any weakness in the complex cryptographic scheme can be reduced to a weakness in one of the primitives, or a well-recognized cryptographic hardness assumption. It effectively proves that a complex cryptographic scheme reduces to the security of a small set of cryptographic components, not unlike arguments about a small Trusted Computing Base. Yet, even those proofs of security often work at a certain level of abstraction and often do not include all details of the protocol. Furthermore, not all properties can be described in the logic used to perform the proofs. As a result, even provably secure protocols have been found to have weaknesses (Pfitzmann & Waidner 1992).

So, the question of “How much can you trust cryptography?” has in part itself been reduced to “How much can you trust the correctness of a mathematical proof on a model of the world?” and “How much can one trust that a correct proof in a model applies to the real world?” These are deep epistemological questions, and it is somehow ironic that national, corporate, and personal security depends on them. In addition to these, one may have to trust certificate authorities and assumptions on the hardness of deep mathematical problems. Therefore, it is fair to say that trust in cryptographic mechanisms is an extremely complex social process.