A blog for the cryptography group of the University of Bristol. To enable discussion on cryptography and other matters related to our research.

## Tuesday, October 27, 2015

### Sardinia eCrypt School, October 2015

One of the reasons I applied for a PhD at the University of Bristol was to travel; to travel all around the world attending conferences, networking with other academics in my field and collaborating on applicable pieces of work. However, I hadn't anticipated that I would arrive at Bristol and meet my supervisors (Elisabeth Oswald and Daniel Page) for them to say "thank goodness you're here, now pack your bags and head to Sardinia for a week".

I didn't argue.

The school I'm referring to is the "School on Design and Security of Cryptographic Algorithms and Devices", and this year it was co-sponsored by the International Association for Cryptologic Research (IACR). A total of roughly 80 Academics and Professionals from all around the globe attended the conference, many of whom were new PhD students (comme moi), and a few were seasoned Crypto School Veterans. As a newbie I experienced the excitement of meeting all these new faces, and getting to know them over a few glasses of wine (the magnificent hotel resort was very generous with its distribution of wine, particularly to my table).

The Summer School took the form of a crash course in all different aspects of cryptography, focusing on covering a lot of ground with introductory lectures. For my first blog post I really wanted to focus on one particular talk, but after attending them all it became clear that I had quite a few favourites; for their content, Benedikt Gierlichs "Introduction to Implementation Attacks" and Josep Balash "Introduction to Fault Attacks" were fascinating. With a background of little knowledge of practical attacks on embedded security, I was shocked to see just how easy one could manipulate theoretically secure devices, simply by making minor alterations to the embedded circuit (see slides from Benedikt Gierlich "Introduction to Implementation Attacks" for more detail).

As for the presentation of the talk, I give a special mention to Gregor Leander. He was able to introduce Lightweight Block Cipher design whilst holding the attention of his audience through quick wit; he told stories of multiple attempts to create nifty lightweight block ciphers, for them to be proven weak and useless within several months of publication. My favourite was the story of Keeloq - a proprietary hardware-dedicated block cipher that uses a non-linear feedback shift register. It was sold to Microchip Technology Inc in 1995 for $10 million (wow), and it was (maybe is) used in many remote keyless entry systems by companies such as Chrysler, Daewoo, Fiat, GM, Honda, Toyota, Volvo, Volkswagen Group, Clifford, Shurlok, Jaguar, etc. However, the Keeloq algorithm does not use cryptographic nonces (for simplicity), nor does it include time stamping (due to clock drift). This means, of course, that the algorithm is vulnerable to replay attacks: simply jam the channel while intercepting the code, and one can obtain a code that may still be usable at a later stage. If your car still uses Keeloq, you should probably either invest in a steering wheel lock, or paint your car bright pink.

To summarise, the organisers of the School did a fantastic job of bringing everyone together, the speakers were all fantastic and engaging, and I learnt a great deal about Cryptography whilst having the greatest week in Sardinia. I would strongly recommend this school to anyone who has just started a PhD in cryptography, regardless of their topic title. I will most certainly be getting involved in as many of these schools as I can!

Finally, a big shout out to all the friends I made at the School - you are all brilliant and I can't wait for the next one. Also, sorry for my atrocious dancing throughout the week. Blame the bar for playing 'Barbie Girl'.

## Thursday, October 22, 2015

### Obfuscation: Hiding Secrets in Software

Suppose you want to keep a secret, but some adversary has taken over your brain: whenever you think about the secret, the adversary is able to read it. While this Orwellian nightmare is not realisable for us (at the moment!), in software this happens all the time. This is the fundamental question of obfuscation; i.e., Can we keep a secret from some adversary if all of the functionality is known? Indistinguishability obfuscation is an attempt to realise this.

One early idea on the way to program obfuscation was secure multi-party computation (MPC). The rough idea of secure MPC is to allow each individual of a party to compute some function on everyone's input without anyone learning too much about the input of any other person. In such a situation, an adversary may be one member of the party, or even act as multiple members in order to try to work out something about the input of one of the other party members. In this case, the adversary has a lot of information he can exploit; for true obfuscation, however, we want that nothing at all be revealed to an adversary.

Now we ask the important question, Which programs allow for secrets to be kept? Suppose we have a program with some secret $s$ accepting an integer $x$ as input such that it outputs 1 if $x<s$ and 0 otherwise. By a simple binary search, $s$ can be determined by the adversary. Plausible security requires unknowable queries, so if we are to succeed in obfuscation we need to have a 'virtual black box'.

However, back in 2001, black box obfuscation was suggested and ruled out in the same paper: it cannot be achieved for all programs. The authors go on to describe and define indistinguishability obfuscation (iO) -- obfuscating two programs with the same functionality so the programs are computationally indistinguishable. Interestingly, if P=NP then any circuit can be obfuscated, and so iO cannot produce hardness itself.

This well-known paper was the first construction of iO for NC$^{1}$ circuits. The authors describe a useful possible application: crippleware. Suppose you are a software vendor and have written a program with lots of functionality, and you want to distribute a trial version of the software which is somewhat restricted. In order to block out trial users from using content for which they have not yet paid, one possibility is for you to go through the code and manually remove the blocks of code for which a full licence should be required. In a large program this very cost- and time-inefficient. However, if instead you simply restrict the functionality of the user interface and release an obfuscated version of the program, this version will not have any functionality beyond that which was intended.

Very recently, there have been many attacks on multi-linear maps, many of which rely on obtaining top-level encodings of zero. Because in obfuscation the adversary never has access to encodings of zero, it is resistant to these attacks. Thus the hope remains that obfuscation will not be broken.

## Wednesday, October 21, 2015

### Using Linearly-Homomorphic Encryption to Evaluate Degree-2 Functions on Encrypted Data

*Homomorphic Encryption*(HE) provides a solution to the problem of outsourcing computations privately to a cloud. There are a number of

*Somewhat*

*Homomorphic Encryption*(SHE) schemes that support many additions but only a limited number of multiplications. Some examples of such schemes in the chronological order are Goldwasser-Micali, El Gamal, Okamoto-Uchiyama, Paillier, Boneh-Goh-Nissim, and all the underlying SHE schemes of

*Fully Homomorphic Encryption*(FHE) schemes since the construction of Gentry. Though SHE schemes can evaluate only a limited set of circuits compared to FHE schemes, it is still interesting to consider them for applications mainly for efficiency reason. Those SHE schemes that support only a single operation on ciphertexts - addition or multiplication - is called

*linearly homomorphic*. That is, (additive) linearly-homomorphic encryption schemes can evaluate only linear functions on ciphertexts. (Here, by a "linear function" we mean that the function can be expressed as a polynomial of degree one in the input variables with the scalars coming from a ring.)

The main problem addressed in the current work is to enable evaluation of degree-two functions using linearly-homomorphic encryption schemes. To this end, the authors propose a generic transformation that extends an (additively-written) linearly-homomorphic scheme to support a single multiplication operation so that it will now be able to evaluate a subset of functions of degree two. The only requirement of the underlying linearly-homomorphic scheme is that it should be

*public space*, which means that the message space must be a publicly known finite commutative ring and that it is possible to efficiently sample a random element from this ring. This property seems to hold for nearly all of the known linearly-homomorphic encryption schemes or can be easily adapted to become so.

Compactness is one of the three main requirements of a (fully) HE scheme that says that the complexity of decryption must be independent of the complexity of the circuit evaluating the given function. The other two requirements are

*semantic security*and

*circuit privacy*for the underlying plaintext messages. The latter means that it must not be possible to learn anything about the messages in the ciphertexts input to a function. It is shown that the proposed transformation preserves semantic security and the transformed scheme will be

*levelled circuit private*if the underlying scheme is circuit private. The transformed scheme will be able to

*compactly*evaluate a subset of degree-two functions (represented as polynomials) $\mathcal{F}_2^* $ consisting of the following polynomials $f$

\[

f(m_1,...,m_t) = P(m_1,...,m_t) + \sum_{i=1}^L Q_i(m_1,...,m_t) * R_i(m_1,...,m_t),

\]

where $P$, $Q_i$, $R_i$ are linear polynomials. It turns out that the subclass $\mathcal{F}_2^*$ of quadratic polynomials is relevant for applications, for example, SPDZ protocol for multi-party computation requires a HE scheme for $\mathcal{F}_2^*$ with $L=1$. Though there are many prior works that aim to construct efficient SHE schemes, they do not achieve full compactness even for this subclass of quadratic functions. In the current work, this limitation for the quadratic functions outside $\mathcal{F}_2^*$ is overcome by working in a different model that uses two servers that do not communicate nor collude. A transformation of the underlying HE scheme is given in this model that is similar to the previous transformation, using which it is now possible to evaluate any quadratic polynomial compactly. Interestingly, the former (single-server) transformation preserves other properties such as zero-knowledge proofs of plaintext knowledge, threshold decryption, and multi-key homomorphicity. Also, the above results are generalised to obtain a $d$-homomorphic to $2d$-homomorphic transformation, and to obtain a two-server protocol to evaluate all degree-three polynomials from BGN HE scheme.

The authors have compared implementations of the Paillier scheme and the Joyce-Libert scheme when transformed to support evaluation of degree-two functions, with that of the HElib implementation of the BGV FHE scheme instantiated with parameters to support a single multiplication, and also with an implementation of the BGN SHE scheme. Upto values of $L = 10$, the transformed Joyce-Libert scheme has comparable decryption time, but with ciphertexts 25 times shorter, and the encryption and the homomorphic operations at least 30 times faster.

## Tuesday, October 20, 2015

### 52 Things, Number 50: What is the BLS pairing-based signature scheme?

This signature scheme makes use of the Weil pairing on elliptic curves, essentially a bilinear form (with multiplicative notation) on points of order dividing $n$ on a curve, taking values in $n^{th}$ roots of unity.

So assume you have an elliptic curve $E/\mathbb{F}_{3^l}$, following the notation in the original paper. The scheme is as follows:

**KeyGen**: Let $E/\mathbb{F}_{3^l}$ be an elliptic curve and $q$ be the largest prime factor of the order of the curve. Let $P$ be a point on it of order $q$ and $x \in \mathbb{Z}_q^*$ be selected at random. Finally let $R = xP$. Then output $(l, q, P, R)$ as the public key and $x$ as the secret key.

**Sign**: To sign a message $M \in \{0,1 \}^*$ we map $M$ to a point $P_M$ in $<P>$. This is done via an algorithm $h$ described in section 3.3 of the paper, and is a hash function. Then let $S_M = xP_M$. The signature $\sigma$ is the $x$-coordinate of the point $S_M$, and $\sigma \in \mathbb{F}_{3^l}$.

**Verifiy**: Given a public key $(l, q, P, R)$, a message $M$ and a signature $\sigma$, do:

- find a point $S$ on the curve of order $q$ whose $x$-coordinate is $\sigma$ and whole $y$-coordinate belongs to $\mathbb{F}_{3^l}$. If no such point exists, reject the signature as invalid.
- set $u = e(P, \phi(S))$ and $v = e(R, \phi(h(M)))$, where $e$ is the Weil pairing on the curve and $\phi$ is an automorphism $E \leftarrow E$. $h$ is the same $h$ mentioned earlier.
- if either $u = v$ or $u^{-1} = v$ accept the signature as valid; reject otherwise.

## Monday, October 19, 2015

### 52 Things: Number 52: Pick an advanced application concept such as e-Voting, Auctions or Multi-Party Computation. What are the rough security requirements of such a system?

## Thursday, October 15, 2015

### Inference Attacks on Property Preserving Encrypted Databases

This saves bandwidth, and consequently time and money, but we really don't want the database (or queries to it) to leak anything more than the properties claimed by the encryption mechanisms, namely equality for DTE, and order+equality for OPE. Unfortunately, human characteristics and medical diagnoses have low entropy: if an adversary knows that a medical database holds records for patients from one geographic area, then the distributions of age and race are going to be very similar to the general population for that area, and even worse most of the data fields will be highly correlated to data from another nearby hospital. This opens the door to two attack vectors: inference attacks that use publicly-available data to gain information about queries (the focus of the paper), and de-anonymisation attacks (that can be built from inference attacks) that aim to identify entries of the EDB. Of course we can use semantically-secure encryption for sensitive attributes (requiring download of the whole column before analysis can occur) to try to thwart these attacks, but which attributes are sensitive? The answer to that question is beyond the scope of this post but the answer is, in general, as many as possible. Note that attributes may be sensitive not only for patients but also to hospitals, which may want to keep secret how many patients die of certain diseases.

The authors show that it is possible to mount inference attacks on encrypted databases (that are built on tools such as CryptDB and Cipherbase) storing real patient data from 200 US hospitals, using only the ciphertexts and public auxiliary information. The public data is obtained from the Healthcare Cost and Utilization Project (HCUP) National Inpatient Sample (NIS) database. The talk provided a jarring 'context is everything' moment by including a slide that displayed only the words "We attack each hospital individually" in large font. This means that the authors look at each hospital database on an individual basis rather than grouping them, and use the auxiliary info to mount their attacks. A number of tools are used and can be found in the paper. The easiest to explain is frequency analysis on a column encrypted using DTE (authors focus on mortality risk): sort the histogram, compare to the auxiliary histogram and map same-ranked elements to infer which entries correspond to which attribute. The authors' novel $l_p$ optimisation recovered mortality risk and patient death data for at least 99% of the 200 largest hospitals, and recovered disease severity for 100% of patients for at least 51% of those hospitals. Sorting attacks on data encrypted using OPE take columns that are 'dense' (meaning that all values have entries), and allow the attacker to decrypt all values with no knowledge of the key: the authors recovered the admission month and mortality risk of 100% of patients for at least 90% of the 200 largest hospitals. Another novel attack called the cumulative attack recovered disease severity, mortality risk, age, length of stay, admission month, and admission type of at least 80% of patients for at least 95% of the largest 200 hospitals. These results only exploit the databases themselves and not leakage from queries ('ciphertext only'), suggesting that the results are a lower bound on the information that could be gleaned from these encrypted databases.

Interestingly, the following talk in the session was given by Florian Kerschbaum defined a new security model for order-preserving encryption, potentially giving a countermeasure against some of the attacks on OPE given above.

### Face/Off: Preventing Privacy Leakage From Photos in Social Networks

One of the worst features of Facebook is when a friend uploads a photo of you looking awful and then tags you in it so all of your friends can have a good laugh. You can untag yourself and burn your ugly outfit but the photo is still there. Worse still, your friend might have terrible privacy settings allowing anyone to see the picture.

Wouldn’t it be nice if you had more control over the privacy settings for photos you’re in? At CCS today Panagiotis Ilia spoke about a tool to give you just that. With their system, when a user uploads a photo it gets run through facial recognition software to identify the people in it. The photo is then split into layers so that each person gets control over the layer containing their own face. Users then choose who can see their face in the photo, with people outside the privileged group seeing a blurred face instead.

Ilia and his team ran experiments, showing people blurred face photos of random friends and found that 82% of those polled could not say which of their friends featured in the photos. Of those who could, their friend’s identity was given away in most cases by the other people in the photo, followed by their body or hair, and finally by their clothing, for example their characteristic Hawaiian shirt and running shoes.

A member of the audience asked what would happen if you used your favourite photo editing software to manipulate a person’s face so that the facial recognition software would be fooled but a human could still recognise the person, and was assured that should the facial recognition software fail to find a match for the person in the photo, they would appear blurred by default. This protects those who opt out of social networking from appearing in pictures. A potential issue here is if I get a selfie with my favourite celebrity then their face may be blurred by the software and no one will believe I really did meet Alan Hansen in a KFC.

If you make bad fashion choices, are regularly photographed in compromising positions, or just want to know more about the technical details you can read the paper here.

## Tuesday, October 13, 2015

### Network protocol obfuscation

CCS 2015 kicked off in Denver today, with three parallel sessions in play throughout the conference. Today I'm going to write a little bit about the first talk in the session on censorship and resistance, "Seeing through Network Protocol Obfuscation" by Liang Wang, Kevin P. Dyer, Aditya Akella, Thomas Ristenpart and Thomas Shrimpton, with the talk delivered by Liang.

The authors framed the adversary in the context of their work as a nation state armed with deep-packet inspection (DPI) capabilities, where the adversary wishes to block network access to certain sites or resources, and uses DPI to identify and nullify attempts to circumvent these blocks.

Typically, anti-censorship attempts follow fairly typical strategies; if a particular circumvention protocol is blocked (Tor being the canonical example), then an anti-censorship mechanism will typically try to either randomise bytes sent over the wire with the goal of looking like 'nothing', to 'look' like an unblocked protocol (e.g make Tor look like HTTP) or to tunnel the blocked protocol over an unblocked protocol.

The adversary here is probabilistic; it must guess whether a particular connection is attempting circumvention or not. As a consequence, it's important to understand both the false positive (blocking a genuine connection) and false negative (not identifying a circumvention attempt) rates to be able to judge most accurately the effectiveness of the strategy followed by the adversary.

A valid and I think very important criticism of a proportion of research into this area of classification of network trace information is that often the data set used to evaluate success rates of adversarial strategies isn't representative enough of the real-world environment; the laboratory data sets may be too small, only sampled from a small subset of the 'population', and a classifier may be heavily over-fitted to the training data and thus performance results will not translate to a different data set (see, for example, Mike Perry's blog post and an associated paper). In this regard, this work appears to do a reasonable job; one data set gathered contained packet level information from a variety of locations and over a variety of connection types from a campus networks, and researcher-generated obfuscated Tor connections generated from a reasonably wide range of environments.

The attack strategies used by the adversary are often very straightforward. The authors explored a wide range of circumvention strategies and consequent detection mechanisms that are better explained in the research paper rather than here, but as a motivating example, to detect usage of the format-transforming encryption (FTE) technique, which attempts to make Tor traffic mimic standard HTTP traffic, the adversary can achieve fairly low false positive rates (< 4 percent) by simply reassembling HTTP streams and checking the header information for correctness.

Across the board the authors find that they can construct attacks with false positive rates as low as 0.03 percent. The precise level at which the FPR becomes unacceptable for an organisation inspecting extremely large amounts of traffic (such as the Great Firewall of China) isn't clear, but it seems that anti-circumvention technologies face a tricky task in remaining useful over time. There's also an interesting comparison here with data exfiltration techniques---some anti-censorship mechanisms are viable as data exfiltration tools for extracting secure data unnoticed from a network.

Particularly when machine-learning techniques are involved, the future may yield a scenario in which the obfuscation tool has to adapt faster than the detection mechanism used to 'survive' (and vice versa).

## Monday, October 12, 2015

### 52 Things: Number 51: What is the security model for ID-based encryption, and describe one IBE scheme.

*This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. This week we introduce Identity-Based Encryption.*

*In public key cryptography, if Alice wants to send a message to Bob, she needs his*

*public key*. Typically this will be some very long bitstring (encoding, for example, the product of two large primes).

Suppose instead that Alice could use Bob's

*name*, or

*email address*, as his public key. Practically speaking, this is very convenient: there are no very long strings for Alice to obtain and remember and she doesn't need to verify that some seemingly random string is in fact Bob's public key (and not, for example, Charlie's public key). But to facilitate this, one needs

*Identity Based Encryption*, or

*IBE.*

In IBE, there is an entity called the

*Private Key Generator*, or

*PKG*. The

*PKG is able to compute Bob's private key using his ID (e.g. his email address) and a*

*master key.*Once Bob has authenticated himself to the PKG, he can ask for his private key and then, once he has it, he can decrypt any messages that have been encrypted under his ID.

There is an issue here, though. With the master key, the PKG can generate private keys for any agent it likes. Therefore the PKG can decrypt any messages intended for any agent. This is called

*key escrow*, and it means that you must either trust the PKG not to read your encrypted messages or else not care that it does. In a company, though, senior management often has the right to read your (work) emails, and so IBE can be an appropriate solution for internal correspondence.

Formally, an IBE scheme consists of four algorithms:

**setup, extract, encrypt**and

**decrypt**.

**Setup**takes a security parameter and outputs the (secret) master key and the (public) system parameters, such as the message and ciphertext spaces.

**Extract**takes an ID and a master key and returns a private key corresponding to the ID.

**Encrypt**takes a message and an ID, and returns a ciphertext.

**Decrypt**takes a ciphertext and a private key, and returns a message.

Boneh and Franklin gave an IBE scheme in this 2003 paper. They prove, under an assumption similar to assuming that the CDH problem is hard, that their scheme is

**IND-ID-CCA**secure in the Random Oracle Model. This means that (assuming all hash functions are random oracles), any attacker, running in polynomial-time with respect to the security parameter, wins the following security game with probability that is only negligibly (with respect to the security parameter) more than 1/2:

First, the attacker

- can request the private keys corresponding to any ID
- can request decryptions of any ciphertexts under any ID.

- can request the private keys corresponding to any ID apart from $ID^*$
- can request decryptions of any ciphertexts under any ID apart from $ \left ( c^*, ID^* \right) $

The scheme given by Boneh and Franklin relies on a non-degenerate bilinear map $e: G_1 \times G_1 \to G_2$, where $G_1$ is a group of prime order $q$, which we write additively, and $G_2$ is a group, also of order $q$, which we write multiplicatively. They instantiate this map with the Weil pairing on elliptic curves, but we omit details here. All that matters is

*bilinearity*: $e \left( aP, bQ \right ) = e \left( P, Q \right)^{ab}$ for any $a, b \in \mathbb{Z}_q$.

There's not enough space here to describe the scheme in full, but essentially the master key is some non-zero $s \in \mathbb{Z}_q$ and the private key corresponding to $ID$ is $sH \left(ID \right)$, where $H$ is a hash function sending bitstrings to elements of $G_1$. There are public generators $P$ and $P_{pub} = sP$ of $G_1$.

To encrypt $m$ under $ID$, one selects a random string $\sigma$ and XORs $m$ with a hash of $\sigma$, creating $c_m$. Then $M$ and $\sigma$ are hashed together, giving a non-zero element $r \in \mathbb{Z}_q$. Finally one computes the pairing $e \left( H \left( ID \right), P_{pub} \right) $, raises it to the power $r$, hashes this and XORs with $\sigma$, creating $c_{ID}$. The triple $\left( rP, c_{ID}, c_m \right)$ is the ciphertext.

With the private key $d = sH\left(ID \right)$, one decrypts the triple $\left (U, V, W \right)$ as follows: compute $e \left( d, U \right)$, which, by bilinearity, will equal $e \left( H \left( ID \right), P_{pub} \right)^r $ if the ciphertext was genuine. So one XORs $V$ with the hash of the pairing to obtain $\sigma$. Then XORing $W$ with the hash of $\sigma$ will give $m$. To check that this is the intended message, one verifies that $\sigma$ and $m$ hashed together gives $r$ such that $U = rP$.

## Sunday, October 11, 2015

### Study group: Provably weak instances of Ring-LWE

The authors build up on previous attack on Poly-LWE (EHL) to extend the attack to a larger class of number fields, and show how to apply that to construct an attack on Ring-LWE.

In a nutshell, Ring-LWE instances can be mapped into Poly-LWE ones, and if the distortion is not too large and there is an attack on the Poly-LWE instance, then this can be mapped back. The distortion is governed by the

**spectral norm**of the mapping, which we define later on.

Let us begin by re-stating the Poly-LWE problem. From now on, we take $f(x)$ to be a monic irreducible polynomial in $\mathbb{Z}[x]$ of degree $n$ and $q$ to be a prime such that $f$ factors completely modulo $q$ and has no repeated roots. Let $P = \mathbb{Z}[x]/(f(x))$ and $P_q = P/qP = \mathbb{F}_q[x]/(f(x))$. We denote the uniform distribution by $\mathcal{U}$ and the discrete spherical (with respect to power basis) Gaussian of mean 0 and variance $\sigma^2$ by $\mathcal{G}_\sigma$, both on $P_q$.

__Let $s(x) \in P_q$ be a secret, drawn from the uniform distribution. The Decision Poly-LWE problem is to distinguish, with non-negligible advantage, between the same number of independent samples in two distributions of $P_q \times P_q$. The first consists of samples of the form $(a(x), b(x)=a(x)s(x)+e(x))$, where $e(x)$ has been drawn from $\mathcal{G}_{\sigma}$ and $a(x)$ from the uniform distribution. The second consists of uniformly random and independent samples from $P_q \times P_q$.__

**Decision Poly-LWE Problem:**It is worth mentioning that this is slightly non-standard terminology. PLWE differs from RLWE in that RLWE samples the errors in the Minkowski embedding and then pulls these values back to obtain polynomials, whereas PLWE samples the polynomial coefficients directly. Now that we have established the problem, let's break it.

The attack on Poly-LWE is fairly straightforward. It proceeds as such.

1. Map the problem down to $\mathbb{F}_q$ via a homomorphism $\phi$.

2. Loop through all possible guesses of the image of the secret $\phi(s(x))$.

3. Gather the values $\phi(e_i(x))$ under the assumption that the guess is correct.

4. Examine the resulting samples to try and determine whether they are images of a uniform distribution or a Gaussian one.

We recall that in a previous work, an attack was presented in the case when $f$ has a root $\alpha \equiv 1 (\mod q)$ or has a root of small order modulo $q$.

We first map everything down to $\mathbb{F}_q$. Write $f(x) = \prod_{i=o}^{n-1} (x - \alpha_i)$, which we can do by assumption. We then use the Chinese Remainder Theorem to write

For each root $\alpha_i$ of $f$ (of which we recall there are $n$), there is a ring homomorphism

obtained by simply evaluating $g(x) \in P_q$ at the said root. We fix a root $\alpha = \alpha_i$. We then loop through all $g \in \mathbb{F}_q$, where each $g$ is taken as a guess for the image of the secret $s(\alpha)$. Assuming this is correct, we obtain

If our samples were of LWE nature, then the collection of ${e_i(\alpha)}_i$ will be distributed as the original errors. Thus this method relies on $\phi(\mathcal{U})$ and $\phi(\mathcal{G}_\sigma$ being distinguishable, as well as $q$ being small enough to allow looping through $\mathbb{F}_q$. We present the first algorithm in the paper; the other, based on the size of the error values, is similar and can be found here. It runs as follows.

We assume that $f$ has a root $\alpha$ of small order $r$ modulo $q$, i.e. $\alpha^r \equiv 1 \mod q$. Then

- Let $G$ be an empty list
- For $g \in \mathbb{F}_q$ from 0 to $q-1$, for (a(x), b(x)) in the collection
- if $b(\alpha)-ga(\alpha)$ does not equal an element of $S$ then break
- otherwise append $g$ to $G$

- If $G$ is empty, return
**NOT PLWE** - If $G = {g}$, return $g$
- If $|G| > 1$ return
**INSUFFICIENT SAMPLES**

**To finish this blog post, we explain how the authors move the attack from Poly-LWE to Ring-LWE. Suppose $K$ is a monogenic number field and $R$ its ring of integers, so that $R$ is isomorphic to the polynomial ring $P = \mathbb{Z}[x]/(f(x))$ for some monic irreducible $f$. Let $\Phi(R)$ be its canonical embedding into $\mathbb{R}^n$. Then there is a map which we'll denote by $M_\alpha$ giving an isomorphism $M_\alpha : P \rightarrow \Phi(R)$. We define the**

**spectral norm**of this map as the radius of the smallest ball containing the image of the unit ball under $M_\alpha$. This will govern the distortion of the error distribution on $\Phi(R)$. And if it not too large, then a solution to the Poly-LWE problem with the new spherical Gaussian distribution may be possible. In which case, it will give a solution to the original Ring-LWE problem. Loosely speaking, we require that the following conditions are satisfied.

1. $K$ is monogenic.

2. $f$ satisfies $f(1) \equiv 0 \mod q$ (or has a root of small order, as seen).

3. $\rho$ and $\sigma$ are sufficiently small.

If we denote the spectral norm by $\rho$, the main theorem in the paper tells us that if the spectral norm satisfies

then the (non-dual) Ring-LWE problem decision problem can be solved (for parameters) in time $\widetilde{O}(lq)$ with probability $1-2^{-l}$, where we recall $l$ is the number of samples.

## Thursday, October 8, 2015

### Partitioned caches redux: Intel CAT to thwart side-channel attacks?

### Caches: a Computer Science 101 explanation

The so-called
memory wall
is now and has long been a thorn in the side of computer architecture.
The issue is simple: modern processors are able to execute instructions
at a high rate (magnified by superscalar, SMT, multi-core and whatever
else), but are effectively limited by the (relatively) low performance
of memories they are attached to. The sticking plaster over this issue,
which has worked fairly well so far at least, is the
memory hierarchy.
Again put simply, in the absence of an ideal, infinitely large and
infinitely fast memory we're stuck with less ideal alternatives. So
as a compromise, we try to get the best out of each technology we
*do* have: this results in the memory hierarchy, where we have,
for example, some small, fast registers at one end and a larger, slow
memory at the other. As long as we retain the working set towards
the faster end of the hierarchy (which the
principle of locality
suggests we can), performance approaches the ideal.

Somewhere in the hierarchy between registers and memory, we typically
place a
cache
(or various levels of them). A given cache will have less capacity
than main memory, but can be faster as a consequence; using control
logic that transparently capitalises on locality of reference, most
accesses are (in theory) satisfied by the faster cache rather than
the slower memory. Or, if you just care about software, they pull
off a kind of magic trick: the program executes faster, and does so
"for free" in the sense the cache is transparent so the
program needn't do anything special. Or at least it does *on
average*: if can write some interesting
programs
to exercise the worst-case behaviour, which show the real and
quite alarmingly sized gap in performance patched over by caches.

### Partitioned caches, CAT and side-channel attacks

After years of increasing cache size, and tweaking their organisation and control strategies, Intel have now included something called Cache Allocation Technology (CAT) in their Xeon model processors: there's a great write-up here, although the original white-paper doesn't really do justice to the vast range of literature in this area. The idea is that the cache can be partitioned, or divided into protected regions with the goal of improving performance. For a server delivering a service with variable demand, for example, it makes sense to allow forms of variable resource allocation to match. Given it is transparent to your programs, by design, you might not think of the cache as a resource of this type. But it is of course: processes share and so compete for space in (any level of) the cache, so by allowing protected allocation via of said space via partitioning, one can eliminate said contention. For example, the OS might decide to allocate a large(r) region to some high-priority process and a small(er) region to another process deemed lower-priority; the former might execute faster as a result, since more of its working set is resident.

This is interesting from a security perspective, because when any resource
is shared between two processes, there is potential for leakage of information
from one process to another. For the specific case of caches, there's again
a *huge* amount of literature from the
side-channel
community, but the (fairly) recent work of
Eisenbarth,
Sunar
et.
al
goes a long way toward summing up one strand of the wider problem. The
good news is that wrt. the Last Level Cache (LLC), which is problematic
in the sense it's a target for cross-VM type attacks in the context of
cloud computing, CAT *might* offer a countermeasure. Depressingly
(for me), this is a sort of bitter sounding "I told you so"
stemming from admittedly quite speculative
work
I did 10 years ago. It's also depressing that was 10 years ago, but
that's another story.

### Knee-jerk conclusions

I said *might* offer carefully though, because although Intel may
have bought the idea of exposing the control of shared resources, this
is down to a focus on non-security metrics such as performance. That
focus seems to undermine the value of CAT for security: for example,
the technical
documentation
says that "power management may override CAT settings". It
might be hard to mount a PoC, but it at least seems feasible that an
attack process might force the security unaware power management system
to abandon CAT, then mount an LLC-based attack as normal.

I've only really started to look at the technical detail, so it's too
soon to jump to strong conclusions, but, to me, work like
Sanctum
and
CHERI
offer more considered (albeit more invasive) approaches to isolated,
compartmentalised instruction execution; in contrast, and at first
glance at least, CAT seems more like another bolt-on and so a missed
opportunity. Given the effort involved in deploying a technology
like CAT at all, it seems a shame security is again somewhere down
the metric pecking order: probably Intel *could* have done us
all a favour by helping to solve the underlying security problem
(and, to be fair, there may well be ways of using CAT to do so),
but instead opted to target (more saleable) performance again.

## Monday, October 5, 2015

### Study Group: Attacking PKCS#11 Tokens

This means that papers we're presenting won't all be particularly recent, but (hopefully) interesting and exciting bits of work.

I kicked things off last week by talking about Attacking and Fixing PKCS#11 Tokens [1], which is from CCS '10. I started my PhD just over a year ago and this was one of the first papers I read. It has stuck with me as a model of good scientific writing: the exposition is very clear, the content is cleanly presented and one doesn't need to have a huge amount of prerequisite knowledge in order to follow the methodology. More importantly, even a non-specialist reader can understand the main result of the paper and appreciate its significance.

In brief: the authors used a formal, symbolic model to analyse a number of commercial security devices implementing a standard key management API called PKCS#11. Of the 17 tokens tested,

*"9 were vulnerable to attack, while the other 8 had severely restricted functionality."*As I said, one doesn't need to have a PhD in Cryptography in order to get the point: real security devices were seriously flawed. In fact, they allowed you to obtain secret keys in plaintext.

A security token is designed to provide access to sensitive material in insecure environments. Your company might want you to access their (sensitive) system from your (potentially insecure) house, so they give you a USB stick (or similar) to bridge the gap. The token will do cryptography for you and your personal laptop, which could be infested with malware, won't be able to directly access the secret keys stored on the token. Instead, there's an API - an interface - between your machine and the token. Moreover, the token is (supposedly) tamper-resistant, so one cannot learn the key values by breaking open the hardware.

The most popular API for security tokens is PKCS#11, which is described in a vast document that was first published in the mid '90s and has been updated very little since then. The trouble is, while the document itself is public [2], the implementation of its contents within each security token is typically unknown to all but the token's manufacturer. So, while attacks on the standard had been known for quite some time prior to the publication of this paper [3, 4], it was unclear whether these attacks could actually be mounted on real devices. Perhaps the manufacturers had been smarter than those who had written the standard and had avoided the many pitfalls by adding extra safeguards?

Of course not. Compliance trumps security every time.

The authors of the paper built a tool that reverse-engineers a token to deduce its functionality, builds a formal model to represent this functionality, finds an attack in the model and then attempts to implement this attack on the real device. While the formal model is quite sophisticated, the attacks are not. Of the five presented in the paper, three are obvious non-compliance with the standard (such as the token just handing you a secret key in plaintext if you ask for it!) and the other two are versions of the famous Wrap/Decrypt attack first found in 2003 [3]. The only tokens that were not vulnerable to these basic attacks were those that disabled key wrapping (encrypting a key under another key) altogether, but this is an important feature of key management APIs.

It is, in fact, possible to do key wrapping in a secure way, but it requires great care. There has been some research in this direction since 2010, including my own ongoing work, but I don't have space to elaborate on this here.

For me, the take-home message from this paper is that, if you don't

*prove*the security of your security device, it's probably insecure. This insecurity makes for fun academic papers, but is also rather worrying when your device is widely used in the real world.

[1] - http://dl.acm.org/citation.cfm?doid=1866307.1866337

[2] - http://docs.oasis-open.org/pkcs11/pkcs11-base/v2.40/pkcs11-base-v2.40.pdf

[3] - http://link.springer.com/chapter/10.1007%2F978-3-540-45238-6_32

[4] - http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/DKS-tfit08.pdf