Study Group: Towards Sound Fresh Re-keying with Hard (Physical) Learning Problems

The first study group on side-channel analysis in the academic year 2016/2017 is "Towards Sound Fresh Re-keying with Hard (Physical) Learning Problems" from Stefan Dziembowski, Sebastian Faust, Gottfried Herold, Anthony Journault, Daniel Masny and Francois-Xavier Standaert, and recently published at Crypto this year. There are mainly two reasons why I chose to present it: it is somehow close to my personal research and, generally speaking, I like to read of different areas influencing each other. In this particular case, learning problems which are usually associated to post-quantum cryptography (more specifically to lattice-based cryptography) have been used to prove a security result in leakage-resilient cryptography.

In one sentence and very loosely speaking, the content of the paper which has been covered in the study group can be summarised as: the authors construct a fresh re-keying scheme and show it is secure under the LPN assumption. The remaining of this blog post is structured as a number of questions and answers on the previous statement that will hopefully clarify and detail its meaning.

Q: what is a fresh re-keying scheme?

A: intuitively, a fresh re-keying scheme is a set of cryptographic algorithms which allows the generation of session keys from a master secret key and some publicly known randomness. A session key is used to encrypt a message and then discarded. The following diagram nicely represents what is going on.

Protecting block ciphers (or other cryptographic primitives) against DPA is an expensive procedure that introduces overhead in the design and whose security is often based on heuristic arguments. Such attacks exploit the dependence of multiple power traces with the same secret key to retrieve it. Hence, fresh re-keying schemes represent a solution that try to structurally avoid the threat by using each session key only once. Both the receiver and the sender can compute the same session key by means of the shared master secret key and some randomness associated with the ciphertext. At that point, the underlying block cipher should retain security only against SPA, while the algorithm the session key is computed by should resist DPA to prevent the adversary to gain information about the master secret key thanks to leakage. The overall scheme is designed to be more efficient than a one which applies DPA countermeasures directly to the block cipher because the GenSK algorithm is built to be easier to protect.

Q: what is the LPN assumption?

A: the Learning Parity with Noise (LPN) problem asks to find a vector $\mathbf{k}\in\mathbb{Z}_2^n$ given query access to an oracle that outputs $$ (\mathbf{r},<\mathbf{r},\mathbf{k}>\oplus e) \in \mathbb{Z}_2^n\times\mathbb{Z}_2 $$ where $\mathbf{r}\in\mathbb{Z}_2^n$ is a uniformly random vector and $e\leftarrow \mathcal{B}_\tau$ is an error bit drawn from the Bernoulli distribution of a fixed parameter $0<\tau<1/2$, i.e. $\mathbb{P}(e=1)=\tau$. The decisional version, instead, asks to distinguish the above distribution from the uniform one on $\mathbb{Z}_2^n\times\mathbb{Z}_2$. The first step in the overall proof is to define a similar version of such a problem, what the author call the Learning Parity with Leakage (LPL) problem, in which everything is the same bar the distribution of the noise, which is now taken to be the Gaussian distribution over the reals. Note that the second component of the LPL distribution is then a real number. It is shown that: $$ \text{LPN is hard} \Rightarrow \text{LPL is hard}. $$

Q: what does it mean for a fresh re-keying scheme to be secure?

A: since we deal with an environment where leakage exists, we should specify both what kind of security model the proof follows and what kind of leakage the adversary is allowed to query.

Security can be stated as the indistinguishability game in the above picture. In the real part on the left, the adversary plays with and queries a real oracle, that is to say an oracle that generates all keys and randomness according to the scheme to be secured. Hence also the leakage is computed on the sensitive variables. Instead, the right-hand side depicts the random game: an ideal oracle generates keys at random, which are then passed to a simulator which computes leakage on them. For the security claim to be valid, the (computational) adversary shouldn't distinguish the oracles she is playing with.
The leakage model is the $t$-noisy probing model. If you imagine a circuit, such a model can be depicted as the adversary being allowed to put probes on up to $t$ wires and to read a noisy version of the values being carried on them. In the specific case of their construction, since there isn't a circuit from which the adversary can get leakage from, the authors specify a set of variables on which noisy bit-selector functions are applied.

Q: which is their fresh re-keying scheme?

A: even if the scheme, called $\Pi_{noisy}$ in the paper, is composed of a set of algorithms, I only specify the core of GenSK, which is responsible for generating the session key. I assume the inputs are some randomness $R$ and a set of shares of the master secret key $\{msk_i\}_{i\leq d}$, which are needed in order to secure the algorithm against DPA. $$ \begin{align*} 1.\ & u_i \leftarrow R\cdot msk_i \\ 2.\ & u \leftarrow \sum_{i\leq d} u_i \\ 3.\ & sk \leftarrow H(u) \\ \end{align*} $$ The sum in the second line is computed iteratively as $((\dots (u_1 +u_2)+u_3)+\dots )+u_d$ for security reasons, while the $H$ in the third line is an hash function modelled as a random oracle. In the game, the adversary is given $sk$ and $R$ and can query leakage on a certain amount of bits of: $msk_i$, $R\cdot msk_i$ and $\sum u_i$. A further step not specified in the previous list is the application of a refreshing algorithm to the shares of the master secret key, in such a way that they look like new shares when the next session key is generated. Finally, the author prove the following: $$ \text{LPL is hard} \Rightarrow \Pi_{noisy} \text{ is secure}. $$

For many other details, the paper is available on ePrint.

What is SPDZ? Part 2: Circuit Evaluation

This blog post is the second in a series of three in which we describe what SPDZ is. The first part can be found here and the third here.

In this part we discuss how we perform the additions and multiplications of shared secret values as in the SPDZ protocol.

The Preprocessing Model

The preprocessing model is a framework in which we assume the existence of a 'trusted dealer' who distributes 'raw material' to the parties before any circuit evaluation takes place. The reason for doing this is that if we have the 'raw material' already in place, the circuit can be evaluated very efficiently.

We realise this by splitting the protocol into two phases: a 'preprocessing' (or 'offline') phase where we generate the preprocessed data, and an 'online' phase where we evaluate the circuit. (The term 'offline' is a little misleading, since the parties still communicate.)

Evaluating the Circuit

We now suppose that the parties have agreed on some arithmetic circuit they want to evaluate jointly.

Providing input

The first step of the circuit evaluation is to read in values from (some of) the parties. In SPDZ, this means getting each party with input, $P_i$ with $x^i$ (the superscript $i$ is an index to avoid confusion with $x_i$ which is a share of $x$), to secret-share input $x^i$ to the other parties.

To do this, we need to use a share of a random value: each party $P_i$ holds some $r_i$ and the value $r = \sum_i r_i$ is uniformly random and not known by any party. First, every party sends their share $r_j$ of $r$ to party $P_i$. This is called a 'partial opening' because $P_i$ now discovers the value of $r$ (by summing the shares).

Party $P_i$ then broadcasts the value $x^i - r$. Party $P_1$ sets its share of $x^i$ as $x_1^i=r_1 + x^i - r$, and $P_j$ for $j > 1$ sets its share of $x^i$ as $x^i_j=r_j$. (In practice, it is not always $P_1$ who does a different computation.)

Thus we have turned $x^i$ into $\langle x^i \rangle$.

Addition

Suppose we want to compute some arithmetic circuit on our data; that is, some series of additions and multiplications. We have the following very useful properties of an additive sharing scheme:

• If we have some secret-shared field elements $\langle a \rangle$ and $\langle b \rangle$, so party $P_i$ has $a_i$ and $b_i$, each party can locally compute $a_i + b_i$, and hence, since $\sum_i a_i + \sum_i b_i = \sum_i (a_i+b_i)$, they obtain a secret sharing $\langle a + b \rangle$ of the value $a+b$.
• If each party multiplies its share by some public value $\alpha$, then since $\sum_i \alpha a_i = \alpha \sum_i a_i = \alpha a$ the parties obtain a secret sharing $\langle \alpha a \rangle$ of the value $\alpha a$.

In other words, the secret-sharing is linear; this is good because it means there is no communication cost for doing these operations. Unfortunately, we have to do a bit more work to multiply secret-shared elements.

Multiplication

In 1991, Donald Beaver [2] observed the following: suppose we want to compute $\langle x y \rangle$ given some $\langle x \rangle$ and $\langle y \rangle$, and we already have three secret-shared values, called a ‘triple’, $\langle a \rangle$, $\langle b \rangle$ and $\langle c \rangle$ such that $c = a b$. Then note that if each party broadcasts $x_i-a_i$ and $y_i - b_i$, then each party $P_i$ can compute $x-a$ and $y-b$ (so these values are publicly known), and hence compute \[ z_i=c_i + (x-a) b_i + (y-b) a_i\] Additionally, one party (chosen arbitrarily) adds on the public value $(x-a)(y-b)$ to their share so that summing all the shares up, the parties get \[\sum_i z_i = c + (x-a)b + (y-b)a + (x-a)(y-b) = xy\] and so they have a secret sharing $\langle z \rangle$ of $xy$.

The upshot is that if we have lots of triples, then we can perform many multiplications on secret-shared data and hence we can compute any arithmetic circuit. (Note that a triple cannot be reused because this would reveal information about the secrets we are trying to multiply - i.e. since $x-a$ and $y-b$ are made public in the process above)

Importantly, observe that not only do these triples not depend on the input secret-shared values they are used to multiply, they are also completely independent of the circuit to be evaluated. This means that we can generate these triples at any point prior to evaluating the circuit. The values of $a$, $b$ and $c$ are not known by any parties when generated - each party only knows a share of each of 'some values' for which they are told this relation holds.

Moreover, if these triples are generated in the offline phase at some point before the circuit evaluation, since addition, scalar multiplication and field multiplication are inexpensive in terms of communication and computation, the online phase is both highly efficient and information-theoretically secure.

Combining the above, we have now established roughly how SPDZ evaluates an arithmetic circuit.

Next time: In the final part, we will look at what makes SDPZ different from other MPC protocols which achieve the same thing.

References 

[1] B. Applebaum, Y. Ishai, and E. Kushilevitz. How to garble arithmetic circuits. 52nd FOCS, pp120–129. IEEE Computer Society Press, 2011

[2] D. Beaver. Efficient Multiparty Protocols using Circuit Randomisation. In J. Feigenbaum, editor, CRYPTO, volume 576 of Lecture Notes in Computer Science, pp420-432, Springer, 2012.

[3] R. Bendlin, I. Damgard, C. Orlandi, and S. Zakarias. Semi-homomorphic encryption and multiparty computation. In EUROCRYPT, pp169-188, 2011.

[4] I. Damgard, M. Keller, E. Larraia, V. Pastro, P. Scholl, N. P. Smart. Practical covertly secure MPC for dishonest majority - or: Breaking the SPDZ limits. In ESORICS (2013), J. Crampton, S. Jajodia, and K. Mayes, Eds., vol. 8134 of Lecture Notes in Computer Science, Springer, pp. 1–18.

[5] I. Damgard, V. Pastro, N. P. Smart, and S. Zakarias. Multiparty computation from somewhat homomorphic encryption. In Advances in Cryptology – CRYPTO 2012, volume 7417 of LNCS, pp643–662. Springer, 2012.

[6] I. Damgard and S. Zakarias. Constant-overhead secure computation of

boolean circuits using preprocessing. In TCC, pp621-641, 2013.

[7] M. Keller and E. Orsini and P. Scholl. MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer. Cryptology ePrint Archive, Report 2016/505, 2016.

[8] J. Buus Nielsen, P. Nordholt, C. Orlandi, and S. Burra. A new approach to practical active-secure two-party computation. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology CRYPTO 2012, volume 7417 of Lecture Notes in Computer Science, pp681-700. Springer Berlin Heidelberg, 2012.

[9] A. Shamir. How to Share a Secret. In Communications of the ACM, Volume 22 Issue 11, Nov. 1979, pp612-613.

[10] A. Yao. How to generate and exchange secrets. In SFCS '86 Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pp162–167. IEEE, 1986.

What is SPDZ? Part 1: MPC Circuit Evaluation Overview

This blog post is the first in a series of three in which we look at what MPC circuit evaluation is, an outline of how MPC protocols in the so-called 'preprocessing model' work, and finally the specifics of SPDZ. They will come in weekly instalments.

In this part, we will introduce the idea of MPC circuit evaluation.

Introduction

If you do research in the field of cryptography, at some point you’ve quite possibly come across the curiously named SPDZ ('speedz'). The aim of this blog post is to explain what it is and why it’s used. In order to keep this post as short and accessible as possible, lots of the details are omitted, and where new concepts are introduced, they are kept superficial.

We start by defining secure multi-party computation (MPC): MPC is a way by which multiple parties can compute some function of their combined secret input without any party revealing anything more to the other parties about their input other than what can be learnt from the output.

Let’s make this more concrete: suppose there are two millionaires who want to know which of them has more money without revealing exactly how much money they have. How can they do this? Clearly we can do it with MPC, providing it exists.

Thankfully, MPC does exist. It is used in many different contexts and has various applications, ranging from the 'simple' and specific such as oblivious transfer (more on this later), to the relatively general-purpose functionality of joint circuit computation.  SDPZ is an MPC protocol allowing joint computation of arithmetic circuits.

Circuit Garbling vs Secret Sharing

There are two main constructions of MPC protocols for circuit evaluation: circuit garbling and secret sharing.

The answer to the so-called millionaire’s problem was first found in the 1980s with Yao’s garbled circuits [10]. As circuit garbling is somewhat parallel to the MPC model we work with in SPDZ, we will not discuss it here.

Contrasting this, the SPDZ protocol is a secret-sharing-based MPC protocol.

Secret-Sharing-Based MPC

Whereas circuit garbling involves encrypting and decrypting keys in a specific order to emulate a circuit evaluation (originally a Boolean circuit, but now arithmetic circuits too [1]), SPDZ instead ‘secret shares’ inputs amongst all parties and uses these shares to evaluate a circuit.

SPDZ is neither the first nor the only secret-sharing-based MPC protocol. Other well known constructions include BDOZ [3], TinyOT [8] and MiniMAC [6]. MASCOT [7] can be seen as an oblivious-transfer-based version of SPDZ. This will be discussed in a little more detail later on.

What is secret sharing?

Suppose I have some field element $a \in \mathbb{F}$, split it up ‘at random’ (uniformly) into two pieces, $a = a_1 + a_2$, and give party $P_1$ the value $a_1$ and $P_2$ the value $a_2$. Neither party knows the value $a$, but together they can recover it. We will write $\langle a \rangle$ to mean that the value $a$ is secret-shared between all parties (i.e. for each i, party $P_i$ has $a_i$, where $\sum_i a_i = a$).

Of course, there are different ways of secret sharing data (e.g. the analogous multiplicative sharing $a = a_1 \cdot a_2$, and also more complicated schemes like Shamir’s [9]), but it turns out that the additive scheme is particularly useful for MPC applications, as we shall see.

The basic overview of secret-sharing MPC of arithmetic circuits (SSMPCoAC?) is the following: 

1. The parties first secret-share their inputs; i.e. input $x^i$ is shared so that $\sum_j x_j^i = x^i$ and party $P_j$ holds $x_j^i$ (and $P_i$ which provides input is included in this sharing, even though it knows the sum).
2. The parties perform additions and multiplications on these secret values by local computations and communication of certain values (in methods specified below). By construction, the result of performing an operation is automatically shared amongst the parties (i.e. with no further communication or computation).
3. Finally, the parties 'open' the result of the circuit evaluation. This last step involves each party sending their 'final' share to every other party (and also performing a check that no errors were introduced by the adversary along the way).

These are the steps we follow in a few different MPC circuit evaluation protocols, as we have discussed. The way we compute the circuit differs (slightly) with the protocol.

Next time: In the next part in this series, we will see how to use these secret-shared values to evaluate an arithmetic circuit as in the SDPZ protocol.

 

References

[1] B. Applebaum, Y. Ishai, and E. Kushilevitz. How to garble arithmetic circuits. 52nd FOCS, pp120–129. IEEE Computer Society Press, 2011

[2] D. Beaver. Efficient Multiparty Protocols using Circuit Randomisation. In J. Feigenbaum, editor, CRYPTO, volume 576 of Lecture Notes in Computer Science, pp420-432, Springer, 2012.

[3] R. Bendlin, I. Damgard, C. Orlandi, and S. Zakarias. Semi-homomorphic encryption and multiparty computation. In EUROCRYPT, pp169-188, 2011.

[4] I. Damgard, M. Keller, E. Larraia, V. Pastro, P. Scholl, N. P. Smart. Practical covertly secure MPC for dishonest majority - or: Breaking the SPDZ limits. In ESORICS (2013), J. Crampton, S. Jajodia, and K. Mayes, Eds., vol. 8134 of Lecture Notes in Computer Science, Springer, pp. 1–18.

[5] I. Damgard, V. Pastro, N. P. Smart, and S. Zakarias. Multiparty computation from somewhat homomorphic encryption. In Advances in Cryptology – CRYPTO 2012, volume 7417 of LNCS, pp643–662. Springer, 2012.

[6] I. Damgard and S. Zakarias. Constant-overhead secure computation of

boolean circuits using preprocessing. In TCC, pp621-641, 2013.

[7] M. Keller and E. Orsini and P. Scholl. MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer. Cryptology ePrint Archive, Report 2016/505, 2016.

[8] J. Buus Nielsen, P. Nordholt, C. Orlandi, and S. Burra. A new approach to practical active-secure two-party computation. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology CRYPTO 2012, volume 7417 of Lecture Notes in Computer Science, pp681-700. Springer Berlin Heidelberg, 2012.

[9] A. Shamir. How to Share a Secret. In Communications of the ACM, Volume 22 Issue 11, Nov. 1979, pp612-613.

[10] A. Yao. How to generate and exchange secrets. In SFCS '86 Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pp162–167. IEEE, 1986.

Study Group: Crying Wolf: An Empirical Study of SSL Warning Effectiveness

Today's study group was on the now a little dated paper of 2009 'Crying Wolf: An Empirical Study of SSL Warning Effectiveness' [1], which was published at USENIX. In cryptography research, it is easy to overlook implementation and usability and instead focus on theory. As is succinctly explained in Randall Munroe's well-known comic, the weaknesses in our cryptographic solutions are seldom in the constructions themselves, but in their real-world application.

This paper explores the use and design of warnings which modern (!) browsers present to a user when SSL certificates cannot be verified, and in particular the user's reaction to them. There is little point in a cryptographically secure system of authentication if the end user ignores and proceeds past warnings when presented with them. The authors suggests that when browsers 'cry wolf' upon encountering SSL errors, users become desensitised over time, learn to ignore these warnings, and thus become susceptible to having their data stolen.

What is SSL?

(The initiated can skip this.)
SSL stands for Secure Sockets Layer, and is a method by which a client can access a web server securely. The SSL Handshake protocol uses a so-called SSL certificate to verify a server's authenticity to a client. An SSL certificate specifies whom the certificate was issued to, whom it was issued by, the period of validity and the server's public key. (Old SSL protocols have been superseded by TLS, but the principles involved are essentially the same.) At a very high level, the protocol proceeds as follows:

1.  The client sends a 'hello' message to the server, requesting content.
2.  The server sends the client its certificate, which contains its public key.
3.  The client checks that the certificate is valid.
4.  If the check passes, the client generates a session key, encrypts using the server's public key, and sends this to the server. If the check fails, the client aborts.
5.  The server decrypts the session key using its secret key.

The client and the server can now encrypt all data sent between them using the (symmetric) session key.

What can go wrong?

If the certificate is invalid, the client aborts. The problems this study considers are:

•  Expired certificate: the certificate is no longer valid.
•  Unknown certificate authority: the issuing authority is not known.
•  Domain mismatch: the domain of the web server and the certificate's listed domain do not match.

If one of the above occurs, the web browser will alert the user. The purpose of the study was to assess the effectiveness of the browser in conveying the severity of the problem to the user: strong warnings where the risks are small cause people to assume high-risk situations given the same warning are just as innocuous.

The Studies

Survey

Using a survey, the authors gathered data from 409 web users on their reactions to SSL warnings and their overall comprehension of the risks involved in ignoring them.

They found that context (i.e. the type of website visited) made little difference to whether or not a user would heed the warnings.

According to the data, respondents who understood 'Domain mismatch' and 'Unknown certificate authority' warnings were less likely to proceed than those who did not, whereas those who understood certificate expiry errors were more likely to proceed. In fact, the experimenters found that users consistently rated risk of an expired certificate lower than the other two errors.

The authors additionally report some wonderful responses from users, including:

•  'I use a Mac, so nothing bad would happen'
•  'Since I use FreeBSD, rather than Windows, not much [risk]'
•  'On my Linux box, nothing significantly bad would happen'

Laboratory Experiment

A set of 100 participants were asked to use four websites to complete different tasks. One website was a banking website with an invalid certificate, one a library website with an invalid certificate, and two were other sites used as dummies.

The participants were shown either Internet Explorer 7 (IE7), Firefox 2 (FF2), Firefox 3 (FF3), or one of two newly-designed SSL warnings. The IE7 warning is whole page but requires just one click to ignore. The FF2 warning is a pop-up window but also only requires one click to ignore. The first version of the FF3 warning needed 11 steps. 'They made the original version of the warning so difficult for users to override, that only an expert could be likely to figure out how to do it.' The first new design was multi-page and asked users to specify the nature of the website they were visiting, presenting severe warnings for websites requiring a high level of security and milder warnings otherwise. The second new design was similar to the FF3 warning but 'looked more severe'. Images can be found in the paper.

For the library website, the IE7, FF2 and multi-page warnings did not prevent people from proceeding compared to the FF3 warning, and the single-page warning was similar to the previous warnings.

For the banking website, the two new warnings did prevent people from accessing the website, but no more than the FF3 warning. The new warnings and the FF3 warning outperformed the IE7 and FF2 warnings in preventing people from accessing the website.

Conclusions

In conclusion, the authors say that the average user does not understand the dangers of SSL warnings, and as such the decision of whether or not to proceed should essentially be made for them by the browser in most cases.

More recently, Chrome recently redesigned its SSL warnings due to the large proportion of users who simply ignored all SSL warnings [2].

To see different SSL warnings in your current browser, visit badssl.com.

References 

[1] Crying Wolf: An Empirical Study of SSL Warning Effectiveness by Joshua Sunshine, Serge Egelman, Hazim Almuhimedi, Naha Atri and Lorrie Faith Cranor. In Proceedings of the 18th Conference on USENIX Security Symposium, 2009; link.
[2] Improving SSL Warnings: Comprehension and Adherence by Adrienne Porter Felt, Alex Ainslie, Robert W. Reeder, Sunny Consolvo, Somas Thyagaraja, Alan Bettes, Helen Harris and Jeff Grimes. In CHI 2015; link.