Crypto 2016: Provable Security for Symmetric Cryptography

On the morning that the CAESAR competition entered its third round, track A of CRYPTO 2016 begin with a session on provable security for symmetric cryptography. It contained 5 talks, all of which were very well presented. In each case the results were given in context, along with a sketch of the key techniques behind their proofs, and very clear diagrams.

First up was Viet Tung Hoang, presenting joint work with Stefano Tessaro on the multi-user security of Key-alternating Ciphers. Key Alternating Ciphers can be seen as a generalisation of the Evan-Mansour construction, and are a natural idealisation of the AES design.  Often work is done in the single-user setting, leaving multi-user security to be reaching via a hybrid argument. However, this leads to a reduction in security linear in the number of users.

The speaker explained two ways in which their work improves upon the previous techniques for applying the H-coefficient techinque to bound adversarial advantages using the statistical distance between possible sets of transcripts, allowing them to achieve tighter bounds.would have possible previously. They termed the first of these the "Expectation Method", where they replace an upper bound with an expected value bound to significantly improve the tightness of one of the internal bounds (specifically, when one is measuring the total probability of an adversary being able to distinguish the systems from a good transcript), while the second is a tightening of the hybrid (by pushing the hybridisation step back to the transcript stage rather than waiting until the final bound has been collected).  These are both very neat observations, and it will be interesting to see how easily they can be applied to other related problems.

Next, Yannick Seurin gave the first of his two talks, on the Counter-in-Tweak (CTRT) mode for bootstrapping AE from a TBC, based on joint work with Thomas Peyrin.  In this work, the authors set out to construct an AE scheme that was:

• Beyond-Birthday-Bound Secure in the nonce-respecting case
• Birthday-bound secure in the nonce-abusing case

They do so using a generic-composition style approach, demonstrating that a slight variant of SIV mode can be used to combine an encryption and an authentication mechanism that each meet these security requirements such that their composition inherits this security.  For their result, an encryption routine is required that takes both a random IV and a nonce. To get this, Yannick explained how one can use a Tweakable Block Cipher to improve upon the classic counter mode, by instead putting the counter into the tweak.  Thus their scheme uses a counter (in the tweak) that is initialised with a random IV to encrypt the nonce, security of which is proven using a neat little balls-and-bins game.

After a short break, Bart Mennink introduced the XPX construction.  His construction generalises single-round most tweakable Even-Mansour constructions by considering them all as being equal to the TBC

\[ \begin{array}{cccccccc} & t_{11}K \oplus t_{12}P(K) & & t_{21}K \oplus t_{22}P(K) \\ & \downarrow & & \downarrow \\ m & \to \oplus \to & P & \to \oplus \to & c \\ \end{array} \]

 under certain sets of tweaks $(t_{11},t_{12},t_{21},t_{22}) \in \mathcal{T}$ (apologies for the terrible diagram!). After describing conditions for such Tweak sets to be weak (ie, totally insecure), he explains that all other sets are in fact reasonably secure.  Developing this further, the work then investigates certain forms of related key security, and the conditions one must impose on the tweak set to achieve these.  Bart then explained how these results apply to some preexisting schemes, recovering the security of the CAESAR candidates MinAlpha and Prost-COPA (for which the work also demonstrates a certain degree of related key security).  Finally, he showed how these results can be applied to the Chaskey MAC algorithm, and suggested a possible modification that would (at the cost of slightly more expensive key rotation) provide some related key security, a method that might also be applicable to sponge-based schemes.

The penultimate talk was on "Indifferentiability of 8-Round Feistel Networks" by
Yuanxi Dai describing his work with John Steinberger.  It is next in a long line of papers seek to best describe the extent to which one can substitute a Fiestel network in for a random permutation, even when the adversary has access to the internal functions.  The presentation was well delivered and described the overall intuition behind the proof, and the design of their simulator, but the details of such results are generally very complicated indeed.

Finally, Yannick Seurin returned to describe "EWCDM", a block-cipher based MAC construction that one could use to more efficiently instantiate the CTRT mode described previously, based on joint research with Benoît Cogliati, which looks something like:

\[ \begin{array}{cccccccc} & & & & N & \to & \downarrow \\ & & & & \downarrow & & \downarrow \\ & & & & E_{k_1} & & \downarrow \\ & & & & \downarrow & & \downarrow \\ M&\to&\text{Hash} & \to & \oplus & \leftarrow & \leftarrow \\ & & & & \downarrow & & \\ & & & & E_{k_2} & & \\ & & & & \downarrow & & \\ & & & & T & & \\ \end{array} \]

  It is secure up to ~$2^{n/2}$ queries under nonce-reuse, and achieves security for $2^{2n/3}$ queries in the nonce-respecting setting.  Moreover, for the nonce-respecting case the actual security level might be even better, since the best known attack in the currently sits at around $2^{n}$ queries, leaving scope for further research.

USENIX 2016: How to Scrutinize "Password1"

On the first day of USENIX, there was one talk particularly catching my attention. Daniel Lowe Wheeler from Dropbox talked about a password strength estimation, and he started with the USENIX online account registration, which rates "password" as a fair password, "Password" as good, and "Password1" as strong, while "zjwca" is rated as weak. He argued that, while password guessing has improved over the last 35 years, password policy has not evolved much since 1979. Moreover, there are inconsistent and not always helpful password policies. Two previous studies have found 142 distinct policies on 150 sites and 50 distinct policies on 50 sites, respectively.

To put an end to this, the authors propose a client-side piece of JavaScript that takes 3 ms to run and gives accurate estimates for online attacks by the best available algorithms. The core estimator takes a minimum rank of the input over lists such as top passwords ("password", "123456", etc.), top surnames (Li, Khan, etc.), and specific information (user name, etc.). It also considers word transformations such as 1337, caps, and reversing, as well as keyboard patterns and sequence patterns. All this information is combined into an estimate how many guesses a sophisticated algorithm would need to find the password.

To evaluate the estimates, the authors used a large data set consisting of leaked passwords as well as other sources. On this data set, other password strength estimators perform quite badly, overestimating the number of attempts for a lot of passwords that would be found in less than 10^5 tries. A particular offender is NIST entropy, which is completely oblivious to real-world choices such as "password". In comparison, overestimating happens for very few passwords with zxcvbn.

The software is available on https://github.com/dropbox/zxcvbn, and it is already used by a number of companies, most notably WordPress.

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.

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.

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.

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$.

This definition still has practical problems. Firstly, it still requires probabilistic encryption and - as we all know - truly random coins are hard to come by. So we want to swap true randomness with nonces: numbers that should only be used once. Then encryption can be implemented using a deterministic function that takes a nonce as an extra input. Secondly, practitioners often need to transmit some header data along with the ciphertext, and this associated data needs to be authenticated but not encrypted. So here's yet another definition(!): a nonce-based AEAD scheme is a function that takes a key, a nonce, some associated data and a message and returns a ciphertext. The authenticity notion is defined essentially as in pAE, but the privacy notion is strengthened: the adversary is asked to distinguish between $E_k(\cdot,\cdot,\cdot)$ and $\$(E_k(\cdot,\cdot,\cdot)),$ i.e. the ciphertexts need to look like random strings, not just encryptions of random strings. These definitions assume that the adversary is nonce-respecting: the adversary never repeats the nonce in their encryption queries.

Of course, nonces are not always used just once, as we would like. To move even closer to the messy world of practical security, we introduce Misuse-Resistant Authenticated Encryption (MRAE) where the adversary can repeat nonces, as long as they don't repeat the entire nonce-data-message triple (otherwise they could trivially distinguish the corresponding identical ciphertexts from independent random strings).

"Surely that's the last one!", I hear you cry. Not quite. It's easy to show that MRAE requires significant ciphertext expansion: ciphertexts must be significantly longer than the plaintexts. This is a problem in certain lightweight applications like in the Internet of Things. So, accepting that there's a tradeoff between the amount of ciphertext expansion and the level of security, Phil and others have recently introduced robust AE (RAE), where the encryption function now has an additional argument specifying the amount of ciphertext expansion. One then tries to obtain the best possible security with that amount of expansion. I'll omit the details in the interest of space.

What was most interesting about Phil's talk was to learn how the evolution of the theoretical notions of security was driven by practical considerations. On the other hand, since the security goalposts seem to be moving all the time, perhaps practitioners will just stop trying to reach them.

Workshop on the Theory and Practice of Secure Multi-Party Computation 2016: Efficient Constant-Round Multiparty Computation

Inspired by Yehuda's talk, I decided to render the history 'flow' which lead today to efficient MPC against malicious parties with a $O(1)$ number of rounds and ending with descriptions of some current state of the art techniques.

First, let's begin with Yao's protocol [1]: $2$ parties - Alice and Bob - hold a function $f$ and they want to compute the output of $f$ with secret inputs. How is this possible? For this we introduce the notion of garbling a circuit of some $f$, $\mathcal{C}_f$ by writing $G(\mathcal{C}_f)$. A nice picture of how this process goes is found in these slides! After you have finished with the nice pictures, you can come back to see an example:

Suppose $f$ is a simple function which computes the addition of $2$ bits, with Alice's input 0, Bob's input 1. Alice computes the garbled circuit of $f$, $G(\mathcal{C}_f)$ and sends it to Bob along with the key corresponding to her garbled input: $k_{A_0}$. In order for Bob to compute the output of $f$ he needs the key corresponding to his input $k_{B_1}$, but he doesn't want for Alice to see his input. Luckily, there is a tool called OT (oblivious transfer) so the problem is solved.

Now, for the general case we can do all of these in $5$ rounds of communication: Alice sends to Bob $G(\mathcal{C}_f)$ (1), Bob does all the OT's in parallel (3) and at the end sends the output back to Alice (1). Great, let's go home now...well, not so fast: what if Charlie wants to join the party? Or Alice garbles a different circuit? Apparently we need something else for $3,4,\dots$ party computation.

Another approach appeared in 1990 and it's called the BMR protocol [2]. Assuming we have access to a protocol which generates random shared coins within $O(1)$ rounds of communication. BMR uses the coin generation to construct 'super-seeds' for wires and bits to mask parties inputs. Then, for each output wire is applied an one time pad using outputs from a PRG seeded by the input wire coins. Then some equations arise by treating individually each outcome of the gate depending on - $4$ possible - input wire labels $A_g, B_g, C_g, D_g$, but for more details we recommend the reader to go through the original article [2].

In 2015 it was published at Crypto the SPDZ-BMR variant [3] which in a nutshell replaces the random coins with calls to the SPDZ random functionality transforming for the first time BMR into a constant round protocol resistant to dishonest majority. Of course, there are many other security subtleties and optimizations presented in [3] such as using PRF's in prime fields instead PRG's in binary fields. SPDZ-BMR is organized in 2 phase offline step:

1. Key wire distribution and input bit mask generation.
2. Compute the wire labels $A_g, B_g, C_g, D_g$ of circuit $\mathcal{C}_f$.

The first step of the offline phase is very similar to the SPDZ offline phase for generating triples, bits, squares which will be later used in the online phase as well as in the step 2) of the offline phase! The computation of wire labels can be seen as evaluating a circuit in the MPC land with constant depth.

In the online phase the labels are revealed to all parties and then each locally computes the outcome of $G(\mathcal{C}_f)$. These all look nice but the scheme's major drawback is that it's cubic in the number of players which means $30$ parties is already too much. In these cases, GMW online phase based - like SPDZ - outperform the BMR in low circuit depth setting. The latest experiment using [4] proves that a vickrey auction with $100$ parties is practical.

In [5] the depth of the circuit shrunk with a slightly more computational overhead using a variant of the Gentry FHE-MPC protocol to only 3! Also the overall time complexity is now quadratic in the number of players.

As Yehuda said in his talk these approaches to constant round protocols are like 'low hanging fruits'. As a researcher, are you ready to pick one by combining different things a novel way? Can you find a scheme which is linear complexity in the number of players?

[1] Yao, Andrew C. "Protocols for secure computations." Foundations of Computer Science, 1982. SFCS'08. 23rd Annual Symposium on. IEEE, 1982.

[2] Beaver, Donald, Silvio Micali, and Phillip Rogaway. "The round complexity of secure protocols." Proceedings of the twenty-second annual ACM symposium on Theory of computing. ACM, 1990.

[3] Lindell, Yehuda, et al. "Efficient Constant Round Multi-Party Computation Combining BMR and SPDZ." Advances in Cryptology--CRYPTO 2015. Springer Berlin Heidelberg, 2015. 319-338.

[4] Keller, Marcel, Emmanuela Orsini, and Peter Scholl. MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer. Cryptology ePrint Archive, 2016. http://eprint.iacr.org/2016/505 .

[5] Lindell, Yehuda, Nigel P. Smart, and Eduardo Soria-Vazquez. "More Efficient Constant-Round Multi-Party Computation from BMR and SHE."