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: P1,...,P64 (plaintexts), C1,...,C64 (ciphertexts).Of course, theoretically one can write (and try to solve):
80-bit key: K1,...,K80.
31 rounds of nonlinear substitutions.
C1 = f1(P1,...,P64,K1,...,K80)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.
C2 = f2(P1,...,P64,K1,...,K80)
...
C64 = f64(P1,...,P64,K1,...,K80)
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:
xi -- each input bit of each S-Box (in each round);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.
yi -- each output bit of each S-Box (in each round);
ki -- each bit of each roundkey.
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.
No comments:
Post a Comment