I will be trying to liveblog Financial Cryptography 2014. I just gave a keynote talk entitled “EMV – Why Payment Systems Fail” summarising our last decade’s research on what goes wrong with Chip and PIN. There will be a paper on this out in a few months; meanwhile here’s the slides and here’s our page of papers on bank security.
The sessions of refereed papers will be blogged in comments to this post.
Rafik Ansari gave the first regular paper, on Digital check forgery attacks on client check truncation systems. A check system typically had an untrusted part, that transports paper checks physically to the trusted part, where the checks are scanned and send electronically into clearing. Check fraud was $645m in 2012, 37% of all payment fraud. The Check 21 Act (2004) allowed remote deposit capture, and move to client truncation (photograph your checks to cash them) which however renders the fancy papers and inks useless. Rafik is an image processing guy, interested in attacks via the client software that takes the images and sends them to the bank. There is rapid advance in digital forgery tools; he discussed what can be done to cut and past handwriting on a background. To see whether it could be industrialised, he tapped into the camera and network APIs on an Android phone; he found he could alter amounts on cheques that were then successfully deposited. The banks used fairly crummy 80kb jpeg images to save badnwidth. They were notified following a responsible disclosure protocol. He mentioned some techniques that could be used for manipulation detection.
Steven Murdoch followed on Security protocols and evidence: where many payment systems fail (declaration: I’m a coauthor). Despite the fact that fraud victims are supposed to get their money back, the British Crime Survey shows that 44% don’t get their money back. Steven discussed how the Payment Services Directive was neutered by the insertion of “necessarily” in the Directive following lobbying by Barclays in 2002 to have their records considered definitive evidence. Yet technical failures and insider attacks abound; Steven described a case in Turkey where the bank records said the PIN was used but the shop receipt showed they were wrong. In the Job case, the bank got away with saying it could not supply the keys needed to verify ARQCs as they had no implemented system to extract them and such a system would compromise security in any case. He presented a series of principles for designing robust dispute resolution procedures, which can be summarised by saying that the dispute resolution mechanisms must be properly engineered and properly governed. It’s not reasonable to expect judges to invent systems and procedures on the fly, with little technical access or insight. He then discussed how these principles might be applied to EMV in an incremental way and requiring changes only by the card issuer, so that it’s deployable in practice. Finally, he applied the principles to other payment systems: phone banking systems fail miserably (as seen in the NatWest Getcash scheme); Sofortueberweising fails all but one of the principles, and Bitcoin fails all but two.
The third talk of the first session was by Tyler Moore on The Ghosts of Banking Past. What happens when a bank passes away? They found the website of “Mid-Valley Bank” in 2013, spotted the CEO had a CRT monitor, and found that MVB closed in 2004. Hundreds of banks close a year, whether from mergers or collapses. They found 3181 banks that closed 2003–2013; some had a redirect to the bank that acquired them, but in many other cases there were domain parking pages with syndicated ads, URLs blacklisted for malware distribution, a whole range of blog spam and blackhat SEO, and a number of relinquished domains. In total 47% were still owned by a bank, but the proportion drops off exponentially with age to a steady state of about 30%. Bank-owned domains are 3.5y old on average; spam domains about 6 and malware domains about 7.5. Statistical testing showed that time since closure, troubled circumstances at closure, and small bank size, are all significant (p < 0.001). Of 535 sites that died, 326 were resurrected; these were more likely to be big banks closed recently. Now businesses die all the time and their domains are bought by scavengers; in what cases is it justifiable to have restrictions on re-registration, and what should we do? Permanent cancellation would be heavyweight, to ensure permanence; it might be better to demand that banks and other players in regulated industries to pay registration fees many years in advance; or have a trusted repository to own them. Their recommendation is that regulators should tackle the problem.
The first speaker after lunch was Ben Smyth describing Hawk and Aucitas: e-auction schemes from the Helios and Civitas e-voting schemes. He observes that electronic voting and auctions are similar, but with the former being more advanced; so is there a systematic way of turning a voting scheme into an auction one? In each case bids/ballots are opened: the difference is that one’s analysed to get winning price, and in the other to tally. One simple way for first-price auctions is to treat the voting system as a black box and get bidders to vote for prices; but then you need extra work to link the winning price to the winning bidder, while taking care that losing bidders cannot be linked to a price; and to turn coercion resistance into collusion resistance. To illustrate this he turns two voting schemes into auctions, including Helios, which has been used by the IACR and universities.
Next was Franziska Roesner on Sex Lies or Kittens? she studied snapchat, which lets people send messages that self-destruct after a set period of 1-10 seconds. It’s been estimated that snapchat has over 3m active users sending 350m snaps a day. Yet various people found that with moderate technical expertise, users could retrieve supposedly deleted snaps from the phone. So they were interested in what people used snapchat for, how they used it, and whether the vulnerabilities had any effect. They surveyed 127 adult snapchat users drawn via snowball sampling from a social network (and found en route that younger adults tended to use snapchat more). Sending sensitive content (whether sexual or offensive) is uncommon, though a quarter may do so experimentally; the most common response was that they use it for funny stuff. Almost a half change the timeout period depending on the content and the recipient; almost half value it because content is unlikely to be saved. Yet about half have either taken screenshots, or had them taken by others (3.9% used a separate camera); about ten percent said they’d taken a screenshot to embarrass the sender. Among some users, a long (10 sec) timeout is seen as implicit permission for a screenshot. Anger, or changed behaviour, are fairly rare in response to a screenshot. 14.1% know that snapchat is insecure; yet 79.5% in total either know or suspect this, and about half wouldn’t change behaviour if they learned it definitely was. A majority of respondents would not send illegal, offensive or sexual material; most because they “never take pictures of that sort of thing” and the rest because they’re concerned about security. This work explodes the misconceptions that snapchat is mostly for sexting, and that it’s threatened by insecurity. Perhaps in response, snapchat is now moving away from security to general social interaction in its marketing material.
The third speaker was Matthew Smith On the awareness, control and privacy of shared photo metadata. He’s concerned about damage from photo metadata which enable third-party photos to be linked with and embarrass a subject. For example, John McAfee allowed himself to be interviewed provided the journalist didn’t say where he was; but he was located and captured thanks to location data on the photo (and he of all people should have known better). In a survey last year, he found 22% of students remove some metadata before sharing; 3.4% remove all. However 35.5% do not know what photo services do with metadata (but only 16% say they don’t care). To see if this could be improved, he built a chrome extension to enable users to visualise relevant metadata. In a user study by 43 people, most liked the extension and interacted with it to encrypt or delete some or all of the metadata. Leaving it as is was the last option of all the participants.
Last speaker was Zakir Durumeric on Outsmarting Proctors with Smart Watches. He notes that almost all the smartphone security concerns apply to wearables, plus some: they’re easy to lose or steal, and have new sensors we haven’t thought about yet. For example, people publish their exercise patterns, but these can leak who you’re having sex with. The problem they studied is that encouraging students to take watches into exams becomes questionable once the watch is programmable. They developed ConTest, an exam cheating app for the pebble smartwatch. Previous research showed that colluding with 3 other people is enough to cheat effectively by voting on multiple-choice answers. The trick is to flip a few pixels in the watch digits to create a covert channel that’s hard for a proctor to see. Should we ban watches (as GRE did) or make exams collusion-resistant? The takeaway is that we have to start thinking through the social implications of such technologies. Options range from open-book exams to randomised questions. The same issues arise in many other places, such as casinos.
Elli Androulaki started the last session of the day, talking about A Secure Data Deduplication Scheme for Cloud Storage. She’s looking for efficient ways for multiple users to keep encrypted shared files on a cloud service. She uses an auxiliary data structure to map users to files. Previous work used “convergent encryption” where file encryption keys are derived from file contents, but this doesn’t support semantic security as content guessing attacks are possible. Her innovation is to encrypt only unpopular files securely, and convergent crypto for popular files as these are generally less sensitive. The basic idea is to wrap convergent crypto in threshold crypto.
Monday’s last paper was Confidentiality Issues on a GPU in a Virtualized Environment, presented by Clementine Maurice. People now rent clouds of GPUs for number crunching, but there have been only a couple of papers on GPU information leakage. Virtualisation can involve different techniques; a split driver model can enable a driver flaw to compromise separation while direct device assignment restricts this to the IOMMU, and devices capable of single-root I/O virtualisation leaves the separation to the device itself. Her experiments tried to taint GPU memory with a secret and then search for it using a subsequent process. Various results are presented in the paper. Neither Xen virtualisation nor KVM paravirtualisation prevented leakage; in general only a hard reboot did that. However they found that turning on error correction often prevented leakage, as memory was cleaned by default on initialisation. Memory cleaning should be much more widely used, principally by the service provider in both hypervisor and runtime code, although in some limited circumstances by users.
Tuesday’s first talk was Elligator Squared by Mehdi Tibouchi. His aim is to avoid distinguishing attacks on elliptic curve cryptography, which is starting to become popular, being promoted by Google and appearing in e-passports, OpenSSH, Tor and Bitcoin. The curve points transmitted during protocols are very easy to distinguish from random, leaving the traffic open to filtering and tampering. This led Bruce Schneier to recommend using vanilla discrete log; so is there any way to make elliptic curve bitstrings look random? Previously, Moeller suggested computing the public points at random either on the curve or its quadratic twist, which works for some protocols but not others; and Bernstein’s Elligator chooses a curve with an efficiently invertible injective encoding, but this limits the choice of curves with pairing-friendly curves unsupported. The author’s alternative is to represent points as uniformly sampled pre-images: he proposes a simple, explicit sampling algorithm and proves its efficiency.
Eric Wustrow followed on Elliptic Curve Cryptography in Practice. In 2009, RFC5656 introduced ECC to SSH, with ECDH and ECDSA on offer; in Oct 2013 they found over 12m SSH host keys of which 10.3% supported ECDSA, with over 99% using the NIST p256 curve. 13.8% supported ECDH, and again over 99.8% supported P256 in preference to P384 and P512; only 0.2% preferred stronger keys first. OpenSSL added ECC ciphersuites even earlier, in 2006; they did a scan covering every server a list of all 38 EC ciphersuites and found that 7.3% of 30.2m servers supported EC with 98% supporting P256, and again a preference for shorter curves over larger ones. Bitcoin uses ECDSA with a special curve secp256k1; in Aug 2013 there were 15.3m unique keys out of 46m (for 11m bitcoins). Lenstra (Crypto 2012) and Henninger (Usenix 2012) previously looked at what goes wrong with conventional PKC and found a percent or so of public keys were really weak thanks to poor entropy. Only 0.8m of the 1.2m SSH keys were unique; some were known bugs (such as Digital Ocean’s VMs, all instances of a device with the same keypair) but others OK. 158 bitcoin transactions reused nonces; they had little money (in at least ten cases, the wallets were looted after the nonces were reused). These thefts were traced back to a javascript RNG problem and an Android issue. There are other unspendable bitcoins: the empty public key has 68.8 bitcoins in it, while the point at infinity has 2.08! (This is surely due to bugs in implementations.) In questions, people pointed other elliptic curve implementations; Blackberry, for example, used ECC from day one.
The morning’s remaining talks were on theory topics (zero knowledge and private information retrieval); I headed off to the beach.
The rump session started at 2225 after a long business meeting and ran until we were kicked out just after midnight.
Ethan Heilman, “One weird trick to stop selfish bitcoin miners: fresh bitcoins, a solution for honest miners”. Selfish mining (Thursday) is selfishly withholding blocks to disadvantage honest miners; Ethan proposes a defence that uses unforgeable timestamps based on random beacons to raise the size of the needed conspiracy from 25% to 32%. A preference for fresher blocks will cause selfish miners to tend to lose blockraces.
Garrick Hileman talked on “History and prospects for alternative currencies”. There have been 4000 alternative currencies, driven by sustainability, local issues, tech change, outrage against bankers and so on. Mark Carney talks of the USA in the 19th century, but according to Garrick that’s not alternative. He has a paper on variants from lindendollars to bitcoin. Fiat currencies die quickly because of regulation, technology and insufficient demand. Strange things happen nowadays: Dogcoin was created as a joke but jumped in value. The bitcoin phenomenon is so strange he’s not sure history is a good guide.
Alexandra Dimitrienko talked on “Bitcoin2Go”. Bitcoin is accepted in over 3000 shops but not in offline apps such as vending machines or where immediate payments are needed. How can you prevent double spending? Her proposal is for the payer to pre-load coins into a trusted wallet that controls the relevant signing keys backed by time-based transaction confirmation: this outsources verification to bitcoin miners. She has an implementation for Android.
Ian Goldberg followed with a talk not on bitcoin: “Convergent semanticaly secure encryption”. Elli’s paper yesterday pointed out that cloud servers would like to store single copies of files stored by multiple users, but government users want crypto to be semantically secure. That paper prompted Ian to think that you can use semantically secure encryption in such a way that you can tell if two files are the same. The trick is that semantically secure encryption doesn’t protect file length; so encode the data in the file length, and you’re done 🙂
Jason Cronk complained that back in the 1990s nobody had slides and talked without them. Is bitcoin against money-laundering laws? The regulators appear to be clueless as they think of miners as coin creators rather than as transaction performers. Eventually the wording “any other person engaged in the transfer of funds” might catch them; and big mining pools are easy for regulators to find.
Rachel Greenstadt called for nominations to the PET award which gives a pretty crystal statue and $3000 for outstanding research in privacy technology.
Ian Goldberg and Micah Gordon gave powerpoint karaoke: they talked to a slide deck they’d not seen before (on elastomer-based MEMS fabrication) to general entertainment.
Tadatoshi Nakamura talked on proxy signatures for general access structures. Existing schemes support only simple types of policy; he extends this to an arbitrary monotone span program. He showed slides with a number of equations in them.
Ian Miers apologised for giving yet another talk on bitcoin; in fact it’s even worse than that: it’s a talk on zerocoin that we’ll hear again at Oakland in May. There, instead of showing a coin you prove that you possess a coin on a list. The proofs were inefficient, taking about 25k; zerocash was more efficient; now, there’s a scheme in which payments have payees and values, hidden by the zero-knowledge, coin-commitment and Merkle-tree mechanisms. The critical tool is succinct non-interactive arguments of knowledge (zkSNARKs).
Joe Bonneau announced yet another bitcoin thing: how much energy does bitcoin use? The $2.5m/day in mining fees gives an upper bound of 1.75 GW, while the best claimed efficiency would give 14.5MW, a small factory. But such claims are an order of magnitude off. He’s trying to get closer estimates of the hardware fleet, and expects something in the hundreds of megawatts range. 800MW is half the Hoover dam! He also announced the Bitcoin and Cryptocurrency research conference; and has a joint project with EFF to try to figure out if any of the dozens of end-to-end encryption apps are any good. There will be a workshop on July 9 2014 at Menlo Park: the EFF CUP Workshop, modelled on the AES and SHA contests. Email effcup@eff.org.
Peter Todd did powerpoint karaoke on “Turbulence as a unifying principle in coronal heating”.
Someone from the bitcoin foundation talked on transaction malleability and denied that it was probably behind the Mt Gox collapse. He suggested a script between a cold-storage wallet and a hot wallet might have had a bug, perhaps to do with multi-byte length. Perhaps miners malleated some of your inter-wallet transactions to save bandwidth, so that over time you get more and more transactions out of your cold wallet to your hot wallet that don’t work. You recover, and think nothing of it … until it’s all gone. In questions, someone asked that if the funds are still there and it’s just a matter of analysing the blockchain, then why hasn’t someone done it?
Steven Murdoch presented a Newsnight video of Sandra Quinn, the UK banks’ representative, commenting on his research in 2008.
Sven Dietrich asked why don’t we just standardise MITM? It turns out it’s not a joke: there is a working document on loretto on exactly that.
Yvo Desmedt talked on AI, Computational lingustics, Nieman Marcus and Target. Why didn’t these stores buy anti-malware products? That question may have been answered by Kahneman and Tversky in 1979. Could we make a tool to help companies assess the loss they might avoid by buying a security product? But theory researchers should beware of overpromising.
Roger Dingledine reported that Tor now has 800-900,000 users per day and 30Gb of traffic. Its problem is no longer ISPs not wanting exit nodes, but services not wanting anonymous users: when cloudflare decides it doesn’tr like your IP address, a lot of websites stop working. Also, skype stops working from Tor IP addresses; and Yelp blocks all anonymous users. There is a competition between blacklisters, and a whole lot of outsourcing between web services firms, and many of them undermine anonymity. People are working on this; as for criminals, they have plenty IP addresses so there are other things they can do. The next step might be activists engaging with websites that cause real problems for anonymous users. Wikipedia simultaneously says there are so many trolls on the Internet that they won’t let anonymous people edit, and also that nobody’s interested in editing wikipedia any more. These are related! Fixing them will require case-by-case engagement with the top sinners, then perhaps a conference. it won’t be done by half-baked academic techie “solutions”.
Peter Todd just had pieces of paper, not slides. His idea, “tree chains”, is that bitcoin scales as n^2 which is hopeless. He wants to split consensus by announcing payers and payees to separate subsets but creating compact proofs that other groups of miners know the missing information. This leads to binary trees, which are vulnerable to occasional forgery at the leaves, but who cares so long as it can’t be industrialised.
Jordi Herrera Joancomarti announced the 9th workshop on data privacy management which is co-located with ESORICS.
Stefano pointed us to http://andrototal.org, a website with data on Android malware.
The last talk was Andrew Miller: Why wasn’t bitcoin invented 15 years ago? Well, it would be hard to specify the protocol using the kind of language and models used at Crypto or PODC. Assumptions about majority-of-computational-power are hard to deal with and have very weird properties. So the significance of bitcoin isn’t just that it’s a new app, but that it’s a new model. The closest seems to be Aspnes, Jackson and Krishnamurthy: Yale TR 1332 from 2005. Other ideas included b-money and hashcash but neither was taken far enough into the engineering detail. Previous economic conclusions such as “proof of work proves not to work” are also sidelined now that bitcoin is driven not by spare cycles but by competitive enthusiasts.
The first speaker on Wednesday was Roch Lescuyer on Efficient and Strongly Secure Dynamic Domain-Specific Pseudonymous Signatures for ID Documents. He described the crypto protocols currently used or proposed by researchers for passports: password authenticated connection establishment (PACE), extended access control (EAC) and restricted identification (RI). The last of these aims to provide pseudonyms that are linkable within domains; but their authenticity cannot be established cross-domain. This can be fixed using pseudonymous signatures, group signatures and anonymous attestation, though there are some subtleties: conventional privacy-friendly crypto primitives are too heavyweight for current equipment, so you have to delegate some of the work from the passport to the reader. In questions, people asked when there would ever be an app for government-issue e-id that supports pseudonyms; the speaker said this was under discussion in France.
Lucjan Hanzlik was next with A Short Paper on How to Improve U-Prove Using Self-Blindable Certificates. Microsoft’s U-Prove has the property that verifiers can distinguish if a user’s token was used twice; so verifiers could collude to track users. The author’s innovation is to introduce self-blindable certificates instead of blind signatures to close this loophole. The trick is to use a random multiple of his original private key plus a proof of knowledge of it.
Lucjan gave the next talk too, on Attack on a U-Prove Revocation Scheme from FC’13 – Exploiting the Weakness of the Underlying Accumulator Scheme. A paper from last year had a flaw which enables a user to pass verification even if their token is revoked; this turned out to be a flaw in the description in the original paper.
Sebastian Pape ended the first session with Sample or Random Security – A Security Model for Segment-Based Visual Encryption. How would visual crypto be used in practice? The existing security models don’t quite fit, especially if key slides are used more than once. He discussed other specialised models from the literature, and explored a definition of “sample or random security”, proving a number of results. A variant of this might work for visual encryption schemes with noise if the parameters are suitably chosen.
Michael Brenner gave a talk on You Won’t Be Needing These Any More: On Removing Unused Certificates From Trust Stores on behalf of Henning Perl who couldn’t make it. Verisign made $73m, Comodo $5m in 2010 from selling certs; yet Verisign issued malware certs in 2010, Comodo got hacked in 2011, and then Diginotar too. With ~1500 trusted CAs from 650 organisations, it’s weakest-link security on a global scale. Proposed fixes range from Perspectives through DANE to sovereign keys, certificate transparency and pinning. Michael presented statistics on used and unused certs in major distributions, and which certs might safely be removed; it turns out there are eight certs that appear in almost all major distributions but which have never been seen to sign anything, so their use is unknown. So do you remove the 148 unused certs from Windows, or merely the 140 that are not used in any other system? Could be move towards inclusion policies that require CA certificates to be actually used, or that do inclusion based on policies?
Nicholas Hopper was next on Challenges in protecting Tor hidden services from botnet abuse. Tor hidden services make available a descriptor which let sa client find an introduction point from which she eventually finds a rendezvous point. Last August, a clickfraud botnet (sefnit/mevade) started running his command and control as a hidden service, which resulted in a million connections to Tor, rising by mid-September to 6 million. This doubled the time it took to download 5kb from 1.5sec to 3sec, even though the botnet shifted very little data. The reason is that every connection to a hidden service needs four messages each of three Diffie-Hellman key exchanges; it was the CPUs being maxed out, not the bandwidth. The pain was mitigated in the third week of September when elliptic curve crypto was pushed out, and then some more in early October when the Windows Defender team started removing the botnet malware. But there’s always a bigger botnet, and what do we do next time? Four possibilities are: resource throttling via a proof-of-work (which is nontrivial to engineer with anonymous clients) or even CAPTCHAs for prioritised service; better is entry throttling, to say 30 circuits per hour, which would throttle the botmaster but also legitimate hidden services unless you have “green” entry nodes for them, which causes further problems in turn; reducing the load of building circuits by allowing nodes to deal with circuit failures adaptively, but this makes selective service denial easier; or isolating regular Tor circuits from hidden-service circuits, but this would give away the fact that some users are hidden-service users (and how do you turn this on securely only when there’s a real botnet, without exposing operators to compulsion from government agencies). None of these is an obvious win; does anyone have any better ideas?
Marie Vasek gave the morning’s last talk, on Identifying Risk Factors for Webserver Compromise. She explored the hypothesis that content management systems like wordpress and joomla tend to attract attacks. She compared hacked servers with a random sample of servers and looked at server attributes, CMS attributes and hygiene. They searched for the seven CMSes with over 1% market share. It turned out that WordPress, Joomla and Zen Cart get phishing attacks; WordPress, Joomla, Drupal and Typo3 are more vulnerable to search redirection attacks. On server software, Apache and Nginx were both more at risk. Every time you double the market share of a CMS, the odds of being hacked increase by 9%. The conventional approach is to name and shame sites running too-out-of-date wordpress servers (say earlier than 3.0) yet it’s the most recent version (3.5) where the compromised systems are most over-represented. The takeaway message is that such case control studies are a powerful tool for measuring outcomes.
It fell to Babins Shrestha to wake us up after lunch, which he did with Drone to the Rescue: Relay-Resilient Authentication using Ambient Multi-Sensing. He’s interested in zero-interaction authentication, such as where your car gets locked when you leave it and unlocked when you approach it. This was initiated by Corner and Noble and is fielded in systems such as Keyless and Blueproximity. A vulnerability is relay attacks, such as the ghost-and-leech attack of Kfir and Wool. Babins’ proposal is to add shared ambient context such as temperature, humidity, gas (CO level), altitude and air pressure. They devised mechanisms to combine multiple modalities into authentication protocols and did experiments involving a sensordrone, collecting 207 samples from 21 locations. They found that the single sensors had error rates of 10-20% but combinations could get an equal error rate around 5%. Forging multiple environmental variables at once should at least be hard enough to make attacks less convenient.
Alexandra Dmitrienko continued the theme with When More Becomes Less: On the (In)Security of Mobile Two-Factor Authentication. She’s been studying various OTPs and found vulnerabilities in every investigated scheme. For example, Google OTPs are global and only changed once an hour: so malware can prevent a user completing login and forward the OTP to a remote location for exploit. A session hijacker can also turn off two-factor authentication: Facebook and Google require no additional authentication to turn off OTP while twitter and dropbox require username and password only. So she wondered whether malware already attacks two-factor: she analysed 207 samples from Malgenome, Contagiodump and Virustotal; current banking mobile malware is not that sophisticated, and depends on user interaction to install mobile components, but she expects it to evolve. As a proof of concept she created stealthy cross-platform infection code that enables a Windows PC to infect an Android (2.2.1) mobile and vice versa via tethering or shared LANs. (A demo is promised for the break.) She implemented attacks on SMS-based TAN schemes ran by four banks (the names of which are still withheld under responsible disclosure); the CrontoSign demo; the Google, Facebook, Twitter and Dropbox 2fa schemes; and several dozen other websites. She concludes it can no longer be assumed that a mobile device is sufficiently isolated from a primary device with which it may be used in high-value applications. In questions, the existing attacks depend on targeted SMS spearphish.
Wednesday’s last paper was MoP-2-MoP – Mobile private microblogging. Marius Senftleben explained that microblogging systems like Twitter and Sina Weibo offer little in the way of sender or receiver anonymity, or censorship resistance. His goal is mobile private microblogging; a key idea is to use local communications to form small crowds with messages encrypted by a group key. The threat model includes a global passive adversary on the WAN, regional kill switches, and occasional local adversaries that can do jamming; this might be extended to include node compromise by malware or social engineering.
John Ross Wallrabenstein kicked off the last day’s sessions with Privacy Preserving Tatonnement; A Cryptographic Construction of an Incentive Compatible Market. Tatonnement is hill-climbing to achieve equilibrium in markets, in the Walrasian auction model. John is interested in whether this can be implemented using secure multi-party computation to give an oblivious auction. He uses a ring protocol based on homomorphic encryption, and this works with Cobb-Douglas utility functions: participants can compute utilities on blinded prices. Elaborations include strategic versus malicious adversary models, local versus monolithic adversaries, piecewise utilities and quantity control.
Jens Grossklags was next with Estimating Systematic Risk in Real-World Networks. This is a follow-on paper to The complexity of estimating systemic risk in networks. The positive value of network effects is counterbalanced by the negative value of correlated risk. Future insurance models must pay heed to the distribution of losses now just their expectation value. We’ve heard of black swans, large events that we rationalise only in hindsight; there are many white swans, well-understood risks; there are also grey swans in between. On the assumption that networks are scale-free, there’s a general solution for the distribution (shown in their first paper) although it’s NP-hard and their algorithms don’t scale indefinitely. In this paper they investigate the fact that insurers operate with partial data; incentives are misaligned. They explored this by taking the CAIDA dataset and Gjoka’s Facebook dataset, simulating a Kunreuther-Heal risk propagation process on them, and testing the sampling errors. On the Facebook graph, if the insurers misunderstands risk to be independent due to local sampling, then he can underestimate the probability of ruin by two orders of magnitude. He shows that the insurer can get a better estimate of the safety loading by multiplying the standard deviation by a constant that’s derived from the network structure and can be estimated by repeated, small-scale sampling. Future work might include different sampling strategies and different risk-arrival processes.
All the remaining conference talks are on bitcoin, and Emin Gün Sirer presented a paper that’s already caused a bit of a stir: Majority is not Enough: Bitcoin Mining is Vulnerable. It had been assumed that in the presence of an honest majority, rational bitcoin miners would follow the official protocol, and that miners would earn bitcoins in proportion to their mining power; thus, it was expected, the core mining protocol was incentive compatible. This turns out to be untrue: selfish bitcoin miners can get an unfair advantage by hoarding hashes they’ve found. In fact it needs 2/3 of the miners to be honest for the protocol to be incentive-compatible. Holding back discovered blocks forces the majority to waste effort computing blocks to follow blocks that are about to become stale. There is a subtlety: if the selfish miners are well-positioned on the network, perhaps with lots of sybils, so they can advertise their disclosed blocks efficiently, then they can make more money even with a small share of the total mining pool. In any case, there are increasing returns to scale, and some of the existing mining pools are above the relevant thresholds. A selfish pool could tip 50% and get all the coins, in effect becoming the coin issuer. A protocol-level fix is proposed whereby every miner propagates each block she hears and puts in an explicit randomisation step. In summary, the blockchain is a fantastic innovation, but it’s not enough. In questions: can selfish mining be detected by zero-transaction blocks? In practice it would be seen by orphan blocks.
The last session was started by Michele Spagnuolo talking about BitIodine: Extracting Intelligence from the Bitcoin Network. Bitcoin is not anonymous, in the sense that all transactions are public; but it is somewhat anonymous in that you can transact anonymously. BitIodine is a tool for analysing and profiling the blockchain; it scrapes the transactions from the web, classifies them, clusters them and graphs them. For example, if a transaction has multiple input addresses, it’s a fair assumption that all those addresses are controlled by the same wallet; and addresses created to collect change from a transaction typically belong to the payer (and until Jan 2013, a bug left the change in the first of two output addresses). With a number of other heuristics, they have now put 90% of addresses into a bit over 2 million clusters. They investigated an address associated with the Silk Road: they deposited 0.001 btc to the silk road one-time deposit address and followed the flow of coins two steps through the mixer; this led to an address that sent btc 7000 to a high-value address that has btc 111,114; this might be part of the SR cold wallet. Dread Pirate Roberts offered $150,000 for a hit on FriendlyChemist who blackmailed him; they used BitIodine to track the btc 1670 transaction to a wallet from which it was emptied (they have no idea whether this was a scammer or law enforcement). They also looked at the Cryptolocker malware which from Sep 5 2013; they tracked 771 ransoms paid to Dec 15 for a total of btc 1226 or $1.2m. There is a strong correlation between the ransoms paid and Dell’s infection rate figures from SecureWorks. They also managed to identify some random-paying victims such as CAESAR09. In questions, the code is publicly available; there’s a link to a tarball in the paper.
Diana Koshy was next with An Analysis of Anonymity in Bitcoin Using P2P Network Traffic. Rather than using clustering, flow analysis or identity leaks, she preferred to analyse bitcoin anonymity using the IP addresses associated with bitcoin addresses. The typical bitcoin client is not designed for data collection; she wanted the metadata, and the invalid messages too; she built CoinSeer, a custom data-collection client. She collected 1.4Tb of transaction data over 6 months. Most transactions are sent once by each peer; they saw odds stuff such as a transaction seen once from a single peer, and then the next day from the same address but in the normal way (and ended up in the blockchain). This led her to suspect that the creator had leaked one of his transactions by mistake. In another case, a single IP relayed the same double-spend transaction every hour for 54 days straight. In fact, 91% of transactions were relayed once each by many IPs, while 6% were relayed by many people at least one of whom relayed it twice, and 2% were sent by only one. They then realised by studying the protocol that only the sender or recipient will re-relay a transaction. Such behaviour suggested that software bugs can leak transaction creators. Depending on how conservative the analytics thresholds are set, they managed to tie 252-1162 bitcoin addresses to IP addresses.
The final speaker of the conference was Joe Bonneau, talking about Mixcoin: Anonymity for Bitcoin with accountable mixes. The previous talks showed that there are anonymity issues with bitcoin; what can be done? Web-wallets and exchanges like Mt Gox have a high failure rate; marketplaces like Silk Road only mix what you buy; dedicated laundry services have high fees (to 3%); ad-hoc mixing protocols like CoinJoin are too hard to scale. As a general proposition, any mix can run away with your money. Joe’s proposed fix is accountability, so you can use reputation to prevent theft; and to put users in control by simplifying the interaction with mixes. The mix signs an offer to accept v coins at kesc by t1 and send v-t coins to kout by t2; if it doesn’t, the user publishes this. Mixing fees can be probabilistic; if the roulette comes up 00, the mix keeps the lot; the blockchain itself provides the roulette wheel, so you can prove if the mix cheated you. So long as the mix is rational and the volume is roughly steady, the expected future transaction fees will be greater than the gains from absconding. The security analysis draws on Tor and remailers: the differences are that everyone’s a global passive adversary (as the blockchain is public), padding is impossible, and you can’t drop messages. Thus low-latency mixing won’t be secure; but a few hours of latency don’t matter as much as they do in communications, and mix addresses are largely indistinguishable. For a passive adversary, a cloud of one-time mixes looks rather like one giant mix; but an active adversary can make life harder, especially with colluding mixes, and converges in the limit to stop-go mixes. At higher levels, intersection attacks can be done by coin counting, which suggests that mixing times should be randomised. In general, we know very little about the uniqueness of individuals’ spending patterns. The takeaway messages are that one-sided accountability can sometimes be useful, and that doing mixing in a financial setting is interesting and nontrivial. In questions, Joe said he hadn’t implemented it, as Princeton lawyers said he’d get into a grey area very quickly.
Prof. Anderson: I went to read the Smart Watches paper, and I think the link you give above is wrong (404), the correct one being fc14.ifca.ai/papers/fc14_submission_139.pdf . It is possible that all the links you give, being in a standard format, are wrong; the “/fc14” at the beginning of the path element, and some trailing encoded characters, seem to be the problem.
Thanks for blogging this conference so quickly.
Tom, thanks for pointing that out. I miscopied the links; I think I’ve fixed them up now
The majority of the links are still invalid due to the following string being appended to URLs:
%E2%80%8EThe problem occurs using Chrome and Firefox on Ubuntu, but not Lynx. This may be a wordpress bug.
This link doesn’t seem to lead to the appropriate paper: “Monday’s last paper was Confidentiality Issues on a GPU in a Virtualized Environment, presented by Clementine Maurice.” (but to the previous paper).
Regards,
bernard
Thanks for pointing that out; now fixed
There is further commentary on Schneier’s blog.
Fascinating, thanks. And… crikey.
Here in the UK it’s getting harder and harder to demand a non-RFID equipped bank card these days – they want us to use a card I don’t even have to take out of my pocket for naughty passers-by to read… eek. But that’s another story. (Hint: I’m waiting for your analysis)