## Saturday, July 16, 2016

### ECRYPT-NET Workshop on Crypto Design for IoT: talk on physical security

IoT stands for "Internet of Things": thousands of interconnected devices sharing (sensitive) information and personal data. As many of them are small and embedded (not all: during a summary talk, Florian Böhl pointed out the existence of connected Caterpillars, for instance...these, not these), this directly translates to the need for a careful evaluation of threats due to side-channel attacks.

Benedikt Gierlichs gave a talk about such a crucial aspect of IoT deployment. He introduced the subject by means of possible applications and use-cases (many of which were the main focus of other talks) and by explaining common issues when securing IoT nodes. In particular, he gave a nice "equation" that succinctly describes them.

IoT device = embedded device + network

Although being a quite simplistic representation of nodes, the equation suggests a very interesting peculiarity of IoT devices within the security framework: the possible points of failure are more in number and also more dangerous than usual non-connected devices. As Ingrid Verbauwhede also remarked during the discussion phase, many of those devices are secure by themselves; it's the fact of being part of a network that raises security issues. Indeed network security adds a non-trivial challenge to the already tough work of securing an embedded device. Since such a discussion is prohibitively broad for a workshop talk (in fact spanned the whole workshop), Benedikt outlined three essential components in IoT security. The nodes need:

1. good cryptography: self-explanatory;
2. secure interfaces: nodes need to communicate among each other and with hubs, the cloud, servers, smartphones. Each of these exchange of information must happen in a formatted and standardised way, using protocols for instance. In these regards Johan Stokking, co-founder of The Things Network, said in his talk that many devices can't even support the IP protocol because it's too complicated. On top of this, at some point all the data should reach final users, for which secure GUIs and access points are needed;
3. secure implementations.

Taken the first two points for granted, the remaining of the talk focused on the third one by providing introductory notions on side-channels analysis, in particular an overview on possible attacks (active/passive, invasive/non-invasive). The speaker remarked the number of things that can possibly go wrong even in the situation in which good crypto and secure interfaces are deployed. If such an assumption is dropped, the scenario is even scarier. In the end the moral was that, within the framework of IoT, "protecting against physical attacks is perhaps not the most pressing issue". Arguably the most pressing issue is depicted by the following picture.

The graph is not based on real data, making it somewhat informal (and accordingly, it's been drawn with an informal graphic tool). The x-axis represents the number of IoT devices and the y-axis carries an extremely informal notion of "percentage of security". The story told is that the majority of devices come with almost no security, and a very small part delivers very strong security. A lot of effort has been put to target the left-most part of the graph: developing really secure protocols and algorithms to make the latter, perhaps already reasonably robust, better. What it should be done (more) in order to ship secure products in every house is pushing the overall "percentage of security" up in (almost) all devices.

## Thursday, July 7, 2016

### WHEAT 2016: The Pre-history of Lattice-based Cryptanalysis

On the second day of the Workshop HEAT, Antoine Joux gave an invited talk on the history of cryptanalytic applications of  lattice-basis reduction algorithms.

Lattice is a discrete subgroup of $\mathbb{R}^n$. Equivalently, it is a span of integer-linear combinations of $\mathbb{R}$-linearly independent vectors in $\mathbb{R}^n$. Finding a short basis in $\mathbb{R}^2$ is relatively easy and Gauss' lattice-basis reduction algorithm is effective for this purpose. As the speaker emphasised, things become more complicated when we move to higher dimensions. He then went on to discuss the details of the famous LLL algorithm, invented by Lenstra, Lenstra and Lovász in 1982, for lattice-basis reduction in arbitrary dimensions. LLL is a polynomial-time algorithm but returns a short vector within an exponential approximation factor of the length of the shortest vector in the lattice. This algorithm, which performs well in practice, may be viewed as a combination of the Gauss lattice reduction and the Gram-Schmidt orthogonalisation methods.

An early application of lattice-basis reduction is the cryptanalysis of knapsack-based cryptosystems. The knapsack problem, a.k.a. the subset-sum problem, is given integers $a_1, \ldots, a_n$, and $S$, find $\epsilon_1,\ldots,\epsilon_n \in \{0,1\}$ such that
$S = \overset{n}{\underset{i=1}{\sum}} \epsilon_i \cdot a_ i.$
This problem is NP-hard though some cases are easy, and it served as a basis for cryptosystems such as Merkle-Hellman cryptosystem. The basic idea is to hide an easy knapsack in a hard-looking one. However, at CRYPTO 1982, Shamir broke this cryptosystem using lattice-basis reduction. This attacks works for super-increasing knapsacks, where we have $a_i > \sum_{j=1}^{i-1} a_j$.  Other works starting with that of Lagarias-Odlyzko in 1985 lead to improved attacks on low-density knapsacks.

The speaker also briefly spoke about the application of lattie-basis reduction to the problems of

•   reconstructing small linear dependencies: let  $(x_1,\ldots,x_n)$ be a sequence of real numbers, we need to find small coefficients $v_i$ such that $\sum v_i\cdot x_i =0$,
• constructing polynomials for use in the Number Field Sieve for solving the Discrete Logarithm Problem, and
• finding small roots of univariate and bivariate integer polynomials modulo composite numbers: Coppersmith's attack.

## Tuesday, July 5, 2016

### WHEAT Workshop 2016, Paris

The second HEAT workshop on Fully Homomorphic Encryption (otherwise known as WHEAT) kicked off this morning in (disappointingly cloudy) Paris.

The first talk of the day was Martin Albrecht's invited talk on solving short secret LWE instances. This is joint work with Rachel Player and Sam Scott. He provided a clear summary of the state of the art in terms of algorithms available and thus set the grounds for the rest of the day. Attacks using parameter choices inspired by HElib and the LP model were discussed and where possible, estimate running times were provided. A partial conclusion was the latter should not be assumed. For a more detailed read, see https://eprint.iacr.org/2015/046.pdf.

Also discussed was RLWE security in the FHE case, a talk given by Guillaume Bonnoron. This is joint work with Caroline Fontaine. They present an attack on specific FHE parameter choices and use the FV scheme for the reason that they wish to avoid doing a Modulus Switch Operation (see for example https://eprint.iacr.org/2015/889.pdf for a description). The conclusion of this talk is that their attack does work, but FHE and RLWE are not broken, because it does not scale up. A bigger parameter $n$ leads to bigger errors. Whilst they took one day to complete the attack versus a previous 3.5 days (https://eprint.iacr.org/2015/176.pdf), this talk's final conclusion was that more cryptanalysis is needed.

The second invited talk in the afternoon was Leo Ducas', joint work with Martin Albrecht and Shi Bai. This discussed the subfield lattice attack on "over stretched NTRU assumptions"; for the full technical read, see https://eprint.iacr.org/2016/127.pdf. This attack is based on using a subfield of the field we are working in - they assume the latter is a power of two cyclotomic, but claim it can be done using any field which is Galois. We map down our RLWE instances using the (partial) norm map in order to solve a (hopefully) easier problem in the subfield. Given the right conditions, we can then map the solution we find back up and recover a short enough solution to carry through with the attack. The practicality grows with the modulus $q$, hence the "over stretched" condition. Although this does not seem (yet?) to affect the NTRU schemes used in practice, this talk's conclusion was to drop the NTRU assumption altogether.

## Tuesday, June 7, 2016

### From IND-CPA to Robust AEAD: Security Notions for Symmetric Encryption

Edit 09/06/16: When I originally wrote this post, I was under the impression that the Robust AE notion had been widely adopted in the symmetric community. Since this is not yet the case, I have edited the post to emphasise that this is a new notion of Rogaway et al. and not a standard one.

This week I'm at the Summer School on Real-World Crypto and Privacy in a beautiful beach resort near Šibenik, Croatia. Obviously spending time by the hotel pool / Mediterranean sea is terribly dull and exhausting, so I was delighted that today I could instead attend a two-hour lecture by Phil Rogaway on security notions for symmetric encryption.

In all seriousness, Phil gave an excellent tour of the (recent) history of symmetric encryption research and I'll try to sketch some of the key points here.

OK, let's first recall the classical notions for symmetric encryption. We assume that, for any key $k$, encryption is a probabilistic function $E_k$ from the message space $\mathcal{M}$ to the ciphertext space $\mathcal{C}$ and that decryption is a deterministic function $D_k: \mathcal{C} \to \mathcal{M}$. Then the advantage of an adversary is the adversary's ability to distinguish between the oracles $E_k(\cdot)$ and $E_k(\$(\cdot))$, where$\$(\cdot)$ returns a random string of the same length as the input. This is called IND-CPA security.

The above notion captures privacy, but not authenticity. But in practice, people want to use a single encryption scheme to achieve both of these goals. So the security definition evolved to probabilistic Authenticated Encryption (pAE): first we allow the decryption function to return $\bot$, meaning the ciphertext is inauthentic. Then we define the privacy advantage just as in the IND-CPA game, but additionally consider the authenticity advantage, which is the probability that an adversary with access to $E_k(\cdot)$ outputs a forgery: a ciphertext that did not come from the encryption oracle and that is decrypted by $D_k$ to something other than $\bot$.

## Sunday, May 29, 2016

### 37th IEEE Symposium on Security and Privacy

The 37th IEEE Symposium on Security and Privacy took place last week in San Jose, California. Although there wasn't an awful lot to see in San Jose itself (direct quote from the Uber driver who took me to the hotel), the conference was full of people from all different backgrounds and interests, which made networking very interesting indeed.

This was my first big conference I had attended, so I wasn't quite sure what to expect. I definitely didn't expect six hundred people to turn up, which was quite overwhelming at first. It also meant the biscuits at break time went very quickly. However, the atmosphere was very enjoyable and I had a fantastic time listening to all the presentations and speeches from various members of the IEEE community.

The papers covered all different aspects of Security and Privacy, from a paper on the Formal Treatment and Implications for TLS 1.3 [1], to a Survey of Techniques against Telephone Spam [2]. After the three days of the conference, it split into six 'workshops'. I mostly attended MoST - the Mobile Security Technologies Workshop - but went to a couple of talks on the BioStar stream - the Workshop on Bio-inspired Security, Trust, Assurance and Resilience.

One of the most enjoyable talks of the conference was on a paper titled "Users Really Do Plug In USB Drives They Find" [3], which follows academics from the University of Illinois littering USB drives round the University campus, containing labels like 'Top Secret Information', or even 'All Exam Answers' (this experiment took place just before finals). Inside each drive were a variety of 'inconspicuous' documents, all html files in disguise linking to a survey that logged the time and filename to a server when users clicked on one of the files. They dropped 297 USB drives around, and 290 of these were picked up (or rather, no longer in their original position). From these 290 that were picked up, 135 people opened a file on them. This is a big security risk, as these USB drives could have malicious files on them, that could infect the host machine if plugged in and run.

The most interesting talk for me was "Dedup Est Machina: Memory Deduplication as an Advanced Exploitation Vector" [4]. Memory deduplication is a technique (default in Windows 8.1 and 10) that 'maps multiple identical copies of a physical page onto a single shared copy with copy-on-write semantics'. However, as writing to a shared page takes longer than writing to a normal page, this is a target for timing side channel attacks. The paper not only exploits this, but goes on to develop a JavaScript-based attack against the Microsoft Edge browser, that allows arbitrary memory read and write access in the browser using a reliable Rowhammer exploit.

Overall, the conference was rewarding and worthwhile experience, and I recommend the conference to anyone interested in the fields of Security and Privacy, or who want some free t-shirts from the various sponsors.

[1] http://www.ieee-security.org/TC/SP2016/papers/0824a470.pdf
[2] http://www.ieee-security.org/TC/SP2016/papers/0824a320.pdf
[3] http://www.ieee-security.org/TC/SP2016/papers/0824a306.pdf
[4] http://www.ieee-security.org/TC/SP2016/papers/0824a987.pdf