Cryptography

Pre-loading HSTS for sibling domains through this one weird trick

The vast majority of websites now support encrypted connections over HTTPS. This prevents eavesdroppers from monitoring or tampering with people’s web activity and is great for privacy. However, HTTPS is optional, and all browsers still support plain unsecured HTTP for when a website doesn’t support encryption. HTTP is commonly the default, and even when it’s not, there’s often no warning when access to a site falls back to using HTTP.

The optional nature of HTTPS is its weakness and can be exploited through tools, like sslstrip, which force browsers to fall back to HTTP, allowing the attacker to eavesdrop or tamper with the connection. In response to this weakness, HTTP Strict Transport Security (HSTS) was created. HSTS allows a website to tell the browser that only HTTPS should be used in future. As long as someone visits an HSTS-enabled website one time over a trustworthy Internet connection, their browser will refuse any attempt to fall back to HTTP. If that person then uses a malicious Internet connection, the worst that can happen is access to that website will be blocked; tampering and eavesdropping are prevented.

Still, someone needs to visit the website once before an HSTS setting is recorded, leaving a window of opportunity for an attacker. The sooner a website can get its HSTS setting recorded, the better. One aspect of HSTS that helps is that a website can indicate that not only should it be HSTS enabled, but that all subdomains are too. For example, planet.wikimedia.org can say that the subdomain en.planet.wikimedia.org is HSTS enabled. However, planet.wikimedia.org can’t say that commons.wikimedia.org is HSTS enabled because they are sibling domains. As a result, someone would need to visit both commons.wikimedia.org and planet.wikimedia.org before both websites would be protected.

What if HSTS could be applied to sibling domains and not just subdomains? That would allow one domain to protect accesses to another. The HSTS specification explicitly excludes this feature, for a good reason: discovering whether two sibling domains are run by the same organisation is fraught with difficulty. However, it turns out there’s a way to “trick” browsers into pre-loading HSTS status for sibling domains.

Continue reading Pre-loading HSTS for sibling domains through this one weird trick

Apple letting the content-scanning genie out of the bottle

When Apple announced that they would be scanning iPhones for child sexual abuse material (CSAM), the push-back appears to have taken them by surprise. Since then, Apple has been engaging with experts and developing their proposals to mitigate risks that have been raised. In this post, I’ll discuss some of the issues with Apple’s CSAM detection system and what I’ve learned from their documentation and events I’ve participated in.

Technically Apple’s CSAM detection proposal is impressive, and I’m pleased to see Apple listening to the community to address issues raised. However, the system still creates risks that will be difficult to avoid. Governments are likely to ask to expand the system to types of content other than CSAM, regardless of what Apple would like to happen. When they do, there will be complex issues to deal with, both for Apple and the broader technology community. The proposals also risk causing people to self-censor, even when they are doing nothing wrong.

How Apple’s CSAM detection works

The iPhone or iPad scans images for known CSAM just before it uploads the image to Apple’s cloud data storage system – iCloud. Images that are not going to be uploaded don’t get scanned. The comparison between images and the database is made in such a way that minor changes to CSAM, like resizing and cropping, will trigger a match, but any image that wasn’t derived from a known item of CSAM should be very unlikely to match. The results of this matching process go into a clever cryptographic system designed to ensure that the user’s device doesn’t learn the contents of the CSAM database or which of their images (if any) match. If more than a threshold of about 30 images match, Apple will be able to verify if the matching images are CSAM and, if so, report to the authorities. If the number of matching images is less than the threshold, Apple learns nothing.

Risk of scope creep

Now that Apple has built their system, a risk is that it could be extended to search for content other than CSAM by expanding the database used for matching. While some security properties of their system are ensured through cryptography, the restriction to CSAM is only a result of Apple’s policy on the content of the matching database. Apple has clearly stated that it would resist any expansion of this policy, but governments may force Apple to make changes. For example, in the UK, this could be through a Technical Capability Notice (under the Investigatory Powers Act) or powers proposed in the Online Safety Bill.

If a government legally compelled them to expand the matching database, Apple may have to choose between complying or leaving the market. So far, Apple has refused to say which of these choices they would take.

Continue reading Apple letting the content-scanning genie out of the bottle

Making sense of EMV card data – how to decode the TLV data format

At the Payment Village in DEFCON 28, I presented a talk about my research in payment system security. While my talks have in the past covered high-level issues or particular security vulnerabilities, for this presentation, I went into depth about the TLV (tag-length-value) data format that anyone researching payment security is going to have to deal with. This format is used for Chip and PIN cards, as specified by the EMV standard, and is present in related standards like contactless and mobile payments. The TLV format used in EMV is also closely related to the ASN.1 format used in HTTPS certificates. There are automated decoders for TLV (the one I wrote is available on EMVLab), but for the purposes of debugging, testing and handling corrupt or incomplete data, it’s sometimes necessary to get your hands dirty and understand the format yourself. In this talk, I show how this can be done.

Rather than the usual PowerPoint, I tried something different for this talk. The slides are an interactive RISE show based on a Juptyer notebook, demonstrating a Python library I wrote to show TLV data-structure decoding. Everything is in my talk’s GitHub repository, and you can experiment with the notebook and view the slides without installing any software through its Binder. I have an accompanying Sway notebook with the reference guides I relied upon for the talk. Do have a try with this material, and I’d welcome your comments on how well (or badly) this approach works.

The DEFCON Payment Village is running again this year in August. If you’ve got something you would like to share with the community, the call for papers is open until 15 July 2021.

Aggregatable Distributed Key Generation

We present our work on designing an aggregatable distributed key generation algorithm, which will appear at Eurocrypt 2021. This is joint work with Kobi Gurkan, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, Gilad Stern, and Alin Tomescu.

What is a Distributed Key Generation Algorithm?

Ever heard of Shamir’s secret sharing algorithm? It’s a classic. The overriding idea is that it is harder to corrupt many people than corrupting one person. Shamir’s secret sharing algorithm ensures that you can only learn a secret if multiple people cooperate. In cryptography, we often want to share a secret key so that we can distribute trust. The secret key might be used to decrypt a database, sign a transaction, or compute some pseudo-randomness.

In a secret sharing scheme, there is a trusted dealer who knows the whole secret, shares it out, and then goes offline. This begs the question: why bother to share the secret in the first place if you have a trusted dealer who knows the whole secret? Often the reason is that the secret sharing scheme is merely being used as an ingredient in a larger distributed key generation algorithm in which nobody knows the full secret. This isn’t always true; certainly, there are cases where a central authority might delegate tasks to workers with less authority. But in the case where there is no central authority, we need a more complete solution.

Continue reading Aggregatable Distributed Key Generation

A Marlin is One of the Fastest SNARKs in the Ocean

In this post, we discuss our new zero-knowledge proving system, Marlin, by Chiesa, Hu, Maller, Mishra, Vesely, and Ward. This year has been the year of the universal SNARK, with Sonic, Libra, and Plonk all bidding for attention. Marlin is yet another competitor, one which we recommend using when you require fast verification time without the use of batching.

Why Universal SNARKs?

A universal SNARK is a proving system in which a single trusted setup suffices to prove anything that we know how to prove. That means that the same setup could be used across all applications and that parameters could be stored in a general-purpose library. Additionally, these universal SNARKs typically have relatively easy to coordinate setup procedures, which makes it easier to convince users that the procedure has been carried out correctly and securely.

Some SNARKs avoid setup procedures altogether. Such works include Spartan, Halo, and Hyrax. However, the cost of avoiding a trusted setup can generally be seen in the proof sizes and verification time.

Marlin or Sonic?

In this authors’ humble opinion, Sonic is fabulous. The proofs are small, the provers are fast, and the verification is fast provided one is verifying many proofs at the same time. For applications that use batched verifications, Sonic currently remains the state-of-the-art. Cryptocurrency transactions are a classic example of this – nodes can verify all the transactions in a new block simultaneously (provided the miner aggregates the transactions). However, this setting in which Sonic excels, i.e. the setting in which the verifier is not just given a single proof but many, many proofs of the same thing, is not always a given. For an example where Sonic’s batched proofs would not suffice, consider a randomness beacon. Here verification of the beacons outputs is only done once in a while. Therefore it would be a setting where batching is totally inappropriate.

Continue reading A Marlin is One of the Fastest SNARKs in the Ocean

Efficient Cryptographic Arguments and Proofs – Or How I Became a Fractional Monetary Unit

In 2008, unfortunate investors found their life savings in Bernie Madoff’s hedge fund swindled away in a $65 billion Ponzi scheme. Imagine yourself back in time with an opportunity to invest in his fund that had for years delivered stable returns and pondering Madoff’s assurance that the fund was solvent and doing well. Unfortunately, neither Madoff nor any other hedge fund manager would take kindly to your suggestion of opening their books to demonstrate the veracity of the claim. And even if you somehow got access to all the internal data, it might take an inordinate effort to go through the documents.

Modern day computers share your predicament. When a computer receives the result of a computation from another machine, it can be critical whether the data is correct or not. If the computer had feelings, it would wish for the data to come with evidence of correctness attached. But the sender may not wish to reveal confidential or private information used in the computation. And even if the sender is willing to share everything, the cost of recomputation can be prohibitive.

In 1985, Goldwasser, Micali and Rackoff proposed zero-knowledge proofs as a means to give privacy-preserving evidence. Zero-knowledge proofs are convincing only if the statement they prove is true, e.g. a computation is correct; yet reveal no information except for the veracity of the statement. Their seminal work shows verification is possible without having to sacrifice privacy.

In the following three decades, cryptographers have worked tirelessly at reducing the cost of zero-knowledge proofs. Six years ago, we began the ERC funded project Efficient Cryptographic Argument and Proofs aimed at improving the efficiency of zero-knowledge proofs. In September 2018 the project came to its conclusion and throwing usual academic modesty aside, we have made remarkable progress, and several of our proof systems are provably optimal (up to a constant multiplicative factor).

As described in an earlier post, we improved the efficiency of generalised Sigma-protocols, reducing both the number of rounds in which the prover and verifier interact and the communication, with a proof size around 7 kB even for large and complex statements. Our proof techniques have been optimised and implemented in the Bulletproof system, which is now seeing widespread adoption.

We also developed highly efficient pairing-based non-interactive zero-knowledge proofs (aka zk-SNARKs). Here the communication cost is even lower in practice, enabling proofs to be just a few hundred bytes regardless of the size of the statement being proved. Their compactness and ease of verification make them useful in privacy-preserving cryptocurrencies and blockchain compression.

Continue reading Efficient Cryptographic Arguments and Proofs – Or How I Became a Fractional Monetary Unit

Introducing Sonic: A Practical zk-SNARK with a Nearly Trustless Setup

In this post, we discuss a new zk-SNARK, Sonic, developed by Mary Maller, Sean Bowe, Markulf Kohlweiss and Sarah Meiklejohn. Unlike other SNARKs, Sonic does not require a trusted setup for each circuit, but only a single setup for all circuits. Further, the setup for Sonic never has to end, so it can be continuously secured by accumulating more contributions. This property makes it ideal for any system where there is not a trusted party, and there is a need to validate data without leaking confidential information. For example, a company might wish to show solvency to an auditor without revealing which products they have invested in. The construction is highly practical.

More about zk-SNARKs

Like all other zero-knowledge proofs, zk-SNARKs are a tool used to build applications where users must prove the validity of their data, such as in verifiable computation or anonymous credentials. Additionally, zk-SNARKs have the smallest proof sizes and verifier time out of all other known techniques for building zero-knowledge proofs. However, they typically require a trusted setup process, introducing the possibility of fraudulent data being input by the actors that implemented the system. For example, Zcash uses zk-SNARKs to send private cryptocurrency transactions, and if their setup was compromised then a small number of users could generate an unlimited supply of currency without detection.

Characteristics of zk-SNARKs
🙂 Can be used to build many cryptographic protocols 🙂 Very small proof sizes 🙂 Very fast verifier time 😐 Average prover time ☹️ Requires a trusted setup ☹️ Security assumes non-standard cryptographic assumptions

In 2018, Groth et al. introduced a zk-SNARK that could be built from an updatable and universal setup. We describe these properties below and claim that these properties help mitigate the security concerns around trusted setup. However, unlike Sonic, Groth et al.’s setup outputs a large set of global parameters (in the order of terabytes), which would be unwieldy to store, update and verify.

Updatability

Updatability means that any user, at any time, can update the parameters, including after the system goes live. After a single honest user has participated, no party can prove fraudulent data. This property means that a distrustful user could update the parameters themselves and have personal confidence in the parameters from that point forward. The update proofs are short and quick to verify.

Universality

Universality means that the same parameters can be used for any application using this zk-SNARK. Thus one can imagine including the global parameters in an open-source implementation, or one could use the same parameters for all smart contracts in Ethereum.

Why Use Sonic?

Sonic is universal, updatable, and has a small set of global parameters (in the order of megabytes). Proof sizes are small (256 bytes) and verifier time is competitive with the fastest zk-SNARKs in the literature. It is especially well suited to systems where the same zk-SNARK is run by many different provers and verified by many different parties. This is exactly the situation for many blockchain systems.

Continue reading Introducing Sonic: A Practical zk-SNARK with a Nearly Trustless Setup

Protecting human rights by avoiding regulatory capture within surveillance oversight

Regulation is in the news again as a result of the Home Office blocking surveillance expert Eric Kind from taking up his role as Head of Investigation at the Investigatory Powers Commissioner’s Office (IPCO) – the newly created agency responsible for regulating organisations managing surveillance, including the Home Office. Ordinarily, it would be unheard of for a regulated organisation to be able to veto the appointment of staff to their regulator, particularly one established through statute as being independent. However, the Home Office was able to do so here by refusing to issue the security clearance required for Kind to do his job. The Investigatory Powers Commissioner, therefore, can’t override this decision, the Home Office doesn’t have to explain their reasoning, nor is there an appeal process.

Behaviour like this can lead to regulatory capture – where the influence of the regulated organisation changes the effect of regulation to direct away from the public interest and toward the interests of the organisations being regulated. The mechanism of blocking security clearances is specific to activities relating to the military and intelligence, but the phenomenon of regulatory capture is more widespread. Consequently, regulatory capture has been well studied, and there’s a body of work describing tried and tested ways to resist it. If the organisations responsible for surveillance regulation were to apply these recommendations, it would improve both the privacy of the public and the trust in agencies carrying out surveillance. When we combine these techniques with advanced cryptography, we can do better still.

Regulatory capture is also a problem in finance – likely contributing to high-profile scandals like Libor manipulation, and payment-protection-insurance misselling. In previous articles, we’ve discussed how regulators’ sluggish response to new fraud techniques has led to their victims unfairly footing the bill. Such behaviour by regulators is rarely the result of clear corruption – regulatory capture is often more subtle. For example, the skills needed by the regulator may only be available by hiring staff from the regulated organisations, bringing their culture and mindset along with them. Regulators’ staff often find career opportunities within the regulator limited and so are reluctant to take a hard-line against the regulated organisation and so close off the option of getting a job there later – likely at a much higher salary. Regulatory capture resulting from sharing of staff and their corresponding culture is, I think, a key reason for surveillance oversight bodies having insufficient regard for the public interest.

Continue reading Protecting human rights by avoiding regulatory capture within surveillance oversight

New threat models in the face of British intelligence and the Five Eyes’ new end-to-end encryption interception strategy

Due to more and more services and messaging applications implementing end-to-end encryption, law enforcement organisations and intelligence agencies have become increasingly concerned about the prospect of “going dark”. This is when law enforcement has the legal right to access a communication (i.e. through a warrant) but doesn’t have the technical capability to do so, because the communication may be end-to-end encrypted.

Earlier proposals from politicians have taken the approach of outright banning end-to-end encryption, which was met with fierce criticism by experts and the tech industry. The intelligence community had been slightly more nuanced, promoting protocols that allow for key escrow, where messages would also be encrypted under an additional key (e.g. controlled by the government). Such protocols have been promoted by intelligence agencies as recently as 2016 and early as the 1990s but were also met with fierce criticism.

More recently, there has been a new set of legislation in the UK, statements from the Five Eyes and proposals from intelligence officials that propose a “different” way of defeating end-to-end encryption, that is akin to key escrow but is enabled on a “per-warrant” basis rather than by default. Let’s look at how this may effect threat models in applications that use end-to-end encryption in the future.

Legislation

On the 31st of August 2018, the governments of the United States, the United Kingdom, Canada, Australia and New Zealand (collectively known as the “Five Eyes”) released a “Statement of Principles on Access to Evidence and Encryption”, where they outlined their position on encryption.

In the statement, it says:

Privacy laws must prevent arbitrary or unlawful interference, but privacy is not absolute. It is an established principle that appropriate government authorities should be able to seek access to otherwise private information when a court or independent authority has authorized such access based on established legal standards.

The statement goes on to set out that technology companies have a mutual responsibility with government authorities to enable this process. At the end of the statement, it describes how technology companies should provide government authorities access to private information:

The Governments of the Five Eyes encourage information and communications technology service providers to voluntarily establish lawful access solutions to their products and services that they create or operate in our countries. Governments should not favor a particular technology; instead, providers may create customized solutions, tailored to their individual system architectures that are capable of meeting lawful access requirements. Such solutions can be a constructive approach to current challenges.

Should governments continue to encounter impediments to lawful access to information necessary to aid the protection of the citizens of our countries, we may pursue technological, enforcement, legislative or other measures to achieve lawful access solutions.

Their position effectively boils down to requiring technology companies to provide a technical means to fulfil court warrants that require them to hand over private data of certain individuals, but the implementation for doing so is open to the technology company.

Continue reading New threat models in the face of British intelligence and the Five Eyes’ new end-to-end encryption interception strategy

Coconut E-Petition Implementation

An interesting new multi-authority selective-disclosure credential scheme called Coconut has been recently released, which has the potential to enable applications that were not possible before. Selective-disclosure credential systems allow issuance of a credential (having one or more attributes) to a user, with the ability to unlinkably reveal or “show” said credential at a later instance, for purposes of authentication or authorization. The system also provides the user with the ability to “show” specific attributes of that credential or a specific function of the attributes embedded in the credential; e.g. if the user gets issued an identification credential and it has an attribute x representing their age, let’s say x = 25, they can show that f(x) > 21 without revealing x.

High-level overview of Coconut, from the Coconut paper

A particular use-case for this scheme is to create a privacy-preserving e-petition system. There are a number of anonymous electronic petition systems that are currently being developed but all lack important security properties: (i) unlinkability – the ability to break the link between users and specific petitions they signed, and (ii) multi-authority – the absence of a single trusted third party in the system. Through multi-authority selective disclosure credentials like Coconut, these systems can achieve unlinkability without relying on a single trusted third party. For example, if there are 100 eligible users with a valid credential, and there are a total of 75 signatures when the petition closes, it is not possible to know which 75 people of the total 100 actually signed the petition.

Continue reading Coconut E-Petition Implementation