Study group: Algebraic side-channel analysis

Today's study group was presented by Carolyn and Valentina on the subject of Algebraic Side Channel Analysis (ASCA).

The goal of algebraic cryptanalysis is to express a cryptosystem as a set of equations in function of its (known) inputs and outputs and its (unknown) secret keys, and to solve that system. Take, for example, the block cipher PRESENT:

64-bit blocks: P₁,...,P₆₄ (plaintexts), C₁,...,C₆₄ (ciphertexts).
80-bit key: K₁,...,K₈₀.
31 rounds of nonlinear substitutions.

Of course, theoretically one can write (and try to solve):

C₁ = f₁(P₁,...,P₆₄,K₁,...,K₈₀)
C₂ = f₂(P₁,...,P₆₄,K₁,...,K₈₀)
...
C₆₄ = f₆₄(P₁,...,P₆₄,K₁,...,K₈₀)

Obviously, though, any such cipher is especially designed to make this hard to solve. Diffusion in the system ensures that each of the above polynomial expressions involves every single bit of the plaintext and key, and the nonlinear S-Box substitions (repeated over a large number of rounds) ensures that there are lots of high degree monomials.

The strategy for algebraic cryptanalysis is therefore to attempt to simplify this system into a large number of small, low degree polynomial equations. This can be helped by introducing dummy variables for intermediate values:

x_i -- each input bit of each S-Box (in each round);
y_i -- each output bit of each S-Box (in each round);
k_i -- each bit of each roundkey.

The authors of the first paper we looked at (Renauld and Standaert, 'Algebraic Side-Channel Attacks' [link]) thus transformed the PRESENT cipher into a system of 40,000 equations in 7,000 variables (50,000 monomials). Of course, it was very sparse -- in matrix form only 0.0155% of entries were non-null.

To help solve this system more efficiently they propose introducing side-channel leakage measurements as extra constraints to make the system more overdefined. Whereas side-channel analysis (SCA) is normally used to recover the key directly, they aim at simpler targets -- for example, the Hamming weights of all the S-Box inputs and outputs in each round -- and express them as additional simultaneous equations.

There are substantial differences between ASCA and SCA: The latter requires predicting intermediate values and so typically focuses on only the first or last round, as diffusion in the system makes intermediate rounds problematic to predict. ASCA does not need to do this and so can use measurements from all the rounds. SCA is very data heavy, and exploits only part of the cipher structure, while ASCA exploits the cipher structure more thoroughly, using fewer trace measurements (often only one) but more points within a trace. Lastly, SCA takes a divide-and-conquer strategy, targetting small bits of the key in succession, whilst ASCA is aimed at recovering the entire key in one go.

Because an S-Box is naturally expressed as a vector of Boolean polynomials an intutitive approach to solving the system (as described in this first paper) is to treat it as a satisfiability problem and feed it to a SAT solver (converting it into conjunctive normal form along the way). They demonstrate good results in the PRESENT case, and even find attacks which work against masking or without knowledge of the plaintext/ciphertext pairs.

However, such an approach is extremely intolerant to errors in the side-channel measurements, which produce conflicts in the system so that the SAT solver will reject the problem as unsatisfiable. In practice it is very hard to recover perfect side-channel information due to the presence of electronic and switching noise in the targeted device, and errors produced by the measurement set-up. The second paper we looked at (Oren et al, 'Algebraic Side-Channel Analysis in the Presence of Errors' [link]) is focused on developing a more error-tolerant methodology.

They propose framing the problem as a pseudo-Boolean optimisation (PBOPT) task rather than a SAT instance. The primary advantage of such an approach is that rather than a hard yes/no decision problem we simply seek a solution which minimises an objective function. Moreover, constraints involving integers (for example, Hamming weights) become much easier to express than in a SAT instance, and extra variables can be assigned to represent error quantities. Since there is a yearly competition for PBOPT solvers there are a wide range of increasingly efficient implementations available. Indeed, their strategy produces realistic attacks against KeeLoq and up to 3 rounds of AES.

The third paper we looked at (Carlet et al, 'Analysis of the Algebraic Side-Channel Attack' [link]) was concerned with the problem of quantifying resistance to ASCA (in the error-free scenario for now). The previous two papers largely focus on experimental, proof-of-concept type results. Indeed, the very nature of SAT problems makes theoretical analysis problematic: SAT is NP-complete in the general case, and although efficient solutions exist for large subsets of instances, there is no reliable way of determining whether a given instance can be efficiently solved without trying it.

So, in the absence of concrete statements about attack complexity Carlet et al propose a criteria for ASCA resistance which they argue is meaningfully indicative of complexity (which argument is supported by their experimental results). They revisit the notion of algebraic immunity (AI) of an S-Box: the degree of the lowest degree polynomial in the ideal generated by the set of equations representing the S-Box (and the field equations). The smaller this is, the more vulnerable is an S-Box (and a cipher which uses it) to algebraic cryptanalysis. The AES S-Box, for example, has an AI of 2 -- there are no linear relations in the associated ideal. Also of importance is the number of independent equations of that lowest degree.

They then look at what happens when side-channel information is added, and define the 'AI with leakage' as the degree of the lowest degree polynomial in the ideal generated by the S-Box, the field equations, and the equations representing the leakage information. They show that Hamming weight and Hamming distance leakage functions both reduce the 'AI with leakage' to 1 for any S-Box, although the number of independent linear equations varies depending (inversely) on the size of the pre-images of the leakage values. (For example, these pre-images are smaller -- and the number of linear relations larger -- in the case that input and output Hamming weight pairs are known than in the case that only the Hamming distances between the input and output pairs are known). They show that any optimally resistant S-Box (i.e. one minimising the number of linear relations) has a nonlinearity of zero and is therefore vulnerable to linear cryptanalysis. This concords with previous results about resistance to SCA and resistance to classical cryptanalysis: it seems that there is an inevitable trade-off (see, for example, Prouff 'DPA Attacks and S-Boxes' [pdf]). In the end, the authors conclude that the best way to defend against ASCA is simply to increase the bus size, as this produces exponential growth in the cardinality of the leakage pre-images.

FlipIt: "A model of the British weather"

In the latest study group, Nigel and Theo talked about FlipIt: The Game of "Stealthy Takeover", the subject of the 2011 IACR Distinguished Lecture given by Ron Rivest at CRYPTO. FlipIt is a two-player game that aims to model various computer security scenarios, allowing these scenarios to be analysed using a game-theoretic framework. Van Dijk, Juels, Oprea and Rivest formally define FlipIt and show that there are many possible interesting variants of the game that correspond to different applications. They also show that even in simple cases the analysis can become quite complex.

To understand the FlipIt game in its most simple form, consider the following example implementation. There are two players in seperate rooms, as well as a 'resource' that neither of the players can see. This resource can be 'controlled' or 'owned' by either of the players. Both players have a control panel with a light and a single button which they can press at any time. When a player moves, i.e., presses their button, they are given ownership of the resource. If they did not own the resource before they moved, the light on their control panel will flash. This is called a 'takeover'. When the light does not flash after a player moves, this means the resource was already under their control.

An important feature of this game is that neither player can see who is currently in control of the resource, nor can they see when the other player presses their button to take control, hence the description "Stealthy Takeover". The players can only find out who owns the resource by pressing the button. Players gain 'points' for every second that they own the resource. However, making a move comes with a certain cost. The goal of the players is to maximize their own score, which consists of the total time they owned the resource minus the cost of the player's combined moves. To do this, both players implement some sort of strategy that decides when they should press the button.

What makes this game interesting is that it models the behaviour of several applications in the area of computer security. For example, FlipIt can be used as a macro-level game to model Advanced Persistent Threats, where one player (the 'defender') tries to keep his sensitive assets (which are modeled as an aggregate FlipIt resource) secure from the other player (the 'attacker'). Here, a move by the attacker corresponds to a campaign that results in the attacker breaching the system and gaining 'control' of the sensitive assets. A move by the defender corresponds to a system-wide remediation campaign, such as patching all machines, resetting passwords, reinstalling servers and so on.

There are many more applications, especially when moving away from the simple implementation mentioned before and introducing additional elements. For example, it is possible that players can make several moves, each of which as a different cost and efficacy in gaining ownership of the resource. An attacker might have access to a known exploit but also a zero-day exploit. If he chooses to take control of the resource using the known exploit, the defender can regain control by applying a security patch that fixes this known exploit. However, if the attacker chooses to use the more costly zero-day exploit, the defender is forced to reinstall the software of the resource, which is also more costly than applying a patch. This gives the players several options to consider when choosing their strategy.

It is also interesting to consider variations of the game where at least one of the players gets additional feedback from pressing the button, which can be incorporated in his strategy. For example, the player could learn the last time that his opponent played ('Last Move') or he could learn the complete history of moves made by both players so far ('Full History'). When a player gets no additional feedback, his strategy must be fixed at the start of the game ('Nonadaptive'). Another interesting variation is where one of the players receives feedback before the first move, such as the strategy of his opponent.

In the paper, the authors analyse the most simple form of the game, where there is only one move for both players. The strategy of the first player, the defender, is always nonadaptive, whereas the strategy of the second player, the attacker, is possibly adaptive, up to the point where he gets information on the last move of the defender. They model everything formally and apply game theory to analyse the strategies of both players. Formally, both players have a 'view', which encodes their knowledge of the history and includes all their previous moves and the feedback they received for these moves. Then, their strategy consists of a function that maps a view on the positive real numbers and tells a player how long they should wait until their next move. This strategy function is possibly randomized. Another important concept is the rate of play, which is the average number of moves the players perform as time goes on.

The simplest class of strategies arises when both players fix their strategy before the first move. Here the authors consider a so-called 'periodic strategy', where both players select a random phase p and a rate of play d and then make a move at time p + k*d for k = 0,1,2,... In this case, the authors find a Nash equilibrium, which is a choice of strategies for both players such that neither player stands to gain by changing his strategy if the strategy of the other player would remain unchanged.

They also consider 'renewal strategies' where players move according to a renewal process. Such a process 'renews' itself after every move, i.e., the time until the next move is independent from the previous time, but distributed identically. Here, the authors try to find 'strongly dominant' strategies. A strategy is strongly dominant if it nets the player a better score than all his other strategies would, given that the strategy of his opponent can be any one from some set of strategies. They show that when a player has a fixed rate of play a, the periodic strategy with period a strongly dominates all non-arithmetic renewal strategies. This result holds for both players and even transfers to the case where the players get some information on the rate of play of the other player before the game.

The analysis of FlipIt teaches some valuable lessons to the security community. First of all, systems should be designed under the assumption that they can be completely compromised at times. This includes the theft of cryptographic keys. "Many times, attackers cross the line of secrecy cryptographers assume in their protocol designs." Secondly, the defender can force the attacker out of the game in some cases, by playing very aggressively. This is especially interesting when the move cost for the defender is quite low. The authors mention the example of Virtual Machines that can easily be refreshed from clean images and whose data can be restored from a centralized server. Finally, the analysis shows that any extra amount of feedback will benefit the player during the game. Thus, defenders should monitor their systems frequently to gain insight into the strateegy of the attacker.

The work also raises many open questions, especially as the strategy classes get bigger. Most of them are of the form "If player A uses a strategy from class X, which strategy from class Y would be strongly dominant for player B?" The authors state that the most interesting open questions arise when one of the players uses an adaptive strategy, but that the most challenging instances are when both players can use adaptive strategies.

ACNS 2012 - Day 3

Today's the last day of ACNS 2012. As we'll be immediately heading off to the conference VIP dinner after the last session and I'll probably don't want to whip out my laptop afterwards ;-) I'll give a short day's summary before the last session (dedicated to web security) takes place.

Today was dedicated mainly to security and privacy issues in current and emerging application fields like social networks, cloud systems and smart grids. Personally I found the talks regarding smart grids interesting as this field is very important to help us to reduce overall power consumption (through an increase of awareness in consumers) as well as to increase the efficiency of energy use (through the interplay of a smart grid with smart household appliances and devices). While it is clear that there is a communication need for individual smart meters to the grid operator and/or electricity provider, the different solutions presented in this session vary in the requirement of communication amongst smart meters themselves. The first system presented by Hsiao-Ying Lin does not require such communication but in turn has a few shortcomings which the authors hope to address in their future work. The second system presented by Zekeriya Erking requires communication amongst smart meters and employs an additive homomorphic encryption (Paillier) in a modified variant so that individual power readings cannot be decrypted, but a sum of such readings can. While this is certainly an interesting approach, it also requires all smart meters to be "honest" (as a single "dishonest" smart meter contributing malformated ciphertexts will prevent correct decryption of the sum of the readings).

ACNS 2012 - Day 2

The second day was mainly devoted to theoretical works on various new or improved cryptographic primitives or cryptanalytic methods. Unfortunately I missed the invited talk of the industry track for "A New Masking Scheme for Side-Channel Protection of the AES" as it clashed with the session where I presented our work. Apart from that, the last session featured three talks on side channel attacks with some first results on zero-value point attacks on computations on Kummer surfaces (which can be used to speed up ECC/HECC), a new block cipher (Picardo), whose S-box is specifically designed to make higher-order masking more efficient, and practical results on power-analysis attacks on AES using wide collisions. Wide collisions mean that a number of intermediate values of two encryptions end up having the same value (instead of e.g. just a single S-box output byte). The price to pay for this is the requirement for the attacker to be in control of the plaintext fed to the cryptographic device. Of the three side-channel talks, the wide-collision one has probably the most immediate practical relevance, as these results need to be taken into account when implementing AES in a side-channel resistant way.

ACNS 2012 - Day 1

We've just concluded the first "working" day of ACNS 2012 (this year in its 10th installment and taking place in Singapore). There have been quite a few interesting talks regarding practical security applications.

Hao and Clarke have analyzed a multi-factor authenticated key exchange protocol (using passwords, tokens, and biometric data) and have shown it to be insecure once only one of the authentication factors (in this case the password) is learned by an attacker. As similar multi-factor authentication protocols have been shown to be insecure in the past, it seems that the design of such protocols is trickier as one would expect.

Another work by Nguyen et al. analyzed the security of an animated CAPTCHA scheme and showed with successful attacks that the introduction of animation does not improve the security of such systems.

Apart from giving the first keynote talk on 10 years of ACNS (and an outlook to the next 10 years), Moti Yung (currently Research Scientist with Google) presented joint work with Ben-David et al. on extending current one-time password (OTP) systems to counter more powerful man-in-the-middle (MITM) attacks (current OTP systems are susceptible to active MITM attacks). Their proposed extended OTP (XOTP) systems takes some additional contextual information about the communication channel into account, which must be recognized by the communicating parties and which must differ for each communication session. They also propose to use smartphones as OTP generators (and use their wireless communication capabilities as a means to convey the OTP) in order to relieve users from carrying around a number of custom-build OTP generators from a number of different companies.

Zhang et al. propose to merge public-key encryption and identity-based encryption to add a feature of key escrow (which would usually conflict with non-repudiation). Their basic idea is to employ the user's PKI certificate as an identity in IBE to generate a second (escrowed) key pair. All traditional PKI mechanisms (like certificate validation and revocation) can still be applied as usual and the new system (called RIKE for Revocable Identities to Support Key Escrow) can be used with little changes from a traditional PKI.

Mueller et al. presented the implementation of platform independent full disk-encryption (called TreVisor) which utilizes many features of advanced 64-bit CPUs (like VT-x/VT-d and AES-NI) and which is resistant to both DMA-attacks and cold-boot attacks.

Study Group: Side-channels and PUFs

The last study group was chaired by Simon Hoerder and Philipp Grabher where the focus was on selected topics of Physically Unclonable Functions (PUFs). So what is the big deal with these PUFs? A PUF is a physical structure, in which, a unique challenge-response pair depends on manufacturing variations. The challenge-response pair is unique for each chip and can not be controlled during the manufacturing process, i.e., when it is used in a clever way, it can be useful, for instance, for authentication purposes. In this case each chip has some kind of unique "fingerprint". That's the most common way of using PUFs, e.g., as lightweight authentication mechanism in RFID tags.

In the first part, Simon introduced the basic definition of PUFs and definitions of PUF categories, like Strong PUFs, Controlled PUFs and Weak PUFs. Following the paper "Modelling Attacks on Physical Unclonable Functions" by Ulrich Rührmair, Frank Sehnke, Jan Sölter and Gideon Dror, Simon presented attacks on selected delay-based PUFs. Considering different types of PUFs like Arbiter PUF, XOR Arbiter PUF, Lightweight Secure PUF, Feed-Forwared Arbiter PUFs and Ring Oscilator PUFs, it is possible to build a model, using machine learning algorithms like Support Vector Machine, Logistic Regression, Evolution Strategies. In other words, gathering enough challenge-response pairs from a PUF and apply certain machine learning algorithms it is possible to predict other challenge-response pairs without any further access to the physical structure.

The next paper "A Formal Foundation for the Security Features of Physical Functions" by Frederik Armknecht, Roel Maes, Ahmad-Reza Sadeghi, Francois-Xavier Standaert and Christian Wachsmann, introduced us to a formal approach of PUFs, e.g., we discussed topics like existential physical unclonability, selective physical unclonability and weak/strong unpredictability.

The second part covered by Philipp focused more on practical attacks on PUFs. The discussion was based on two papers: "Semi-invasive EM attack on FPGA RO PUFs and countermeasures" and "Side-Channel Analysis of PUFs and Fuzzy Extractor" both by Dominik Merli, Dieter Schuster, Frederic Stumpf and Georg Sigl. Although a good PUF design should remain resistant against invasive and semi-invasive attacks (any modification of the PUF structure should change its behaviour), the first paper shows that sometimes this case doesn't hold and, e.g., titled Ring Oscillator based PUF is vulnerable to semi-invasive electromagnetic (EM) analysis attacks. In the second paper, the threat of side-channel attacks is being discussed when mounted on various PUF implementations.

All in all, Physically Unclonable Functions is an active filed of research, and there is not doubt that we see in the future many more interesting results both in theoretical as well as in practical implementations.

Study Group: Proving Correctness of a Shuffle

Today David and Essam talked about shuffle proofs. These allow to prove that a shuffle and re-randomisation of a list of ciphertexts was done correctly. The main application is e-voting, where several hosts in a so-called mix net sequentially shuffle and re-randomise ciphertexts containing the votes. Shuffle proofs ensure that no host can tamper with the votes. As usual, the requirements for shuffle proofs are completeness, soundness, and zero-knowledge. Most proofs are based on (semi-)homomorphic cryptosystems such as ElGamal that allow to re-randomise a ciphertext without knowing the cleartext.

In the last millennium, Sako and Kilian presented a cut-and-choose implementation of shuffle proofs: The prover shuffles the input ciphertext list X once more to get Z, and the verifier ask to see either the randomness used, or the randomness that would be used to shuffle X to Z. The correct response to both queries allows to compute the randomness for shuffling X to Y, which reveals a cheating prover with probability 1/2. Zero-knowledge follows from the fact that both replies on their own are independent on randomness used to shuffle X to Y.

More recently, Wikström presented a more efficient solution using extended Pedersen commitments, Schnorr-like protocols, and batch proof techniques. Extended Pedersen commitments allow to commit to a vector in only one group element. The protocol works in two phases. In an offline phase, the prover commits to a random permutation as a matrix and proves it be correct. Later, the provers shuffles the input ciphertext list according to the committed permutation and proves having done so.

At Eurocrypt 2012, Bayer and Groth presented another solution combining similar techniques, Groth's earlier work on sublinear size arguments and algebraic techniques like FFT and the Schwartz-Zippel lemma. An implementation of their protocol can prove the correctness of a shuffle of 100'000 ciphertext in 2 minutes.