Published on

Symbolic analysis of side channel countermeasures

Authors

Cryptography’s current research trends show that there is an increasing concern about identifying if a side-channel countermeasure is vulnerable to higher-order attacks.

In a recent work published this year on IEEE Trans. on Computers, me and my co-authors, Elia Bisi (U. Warwick) and Filippo Melzani (Security Pattern), just introduced a new mathematical tool to assess the higher order vulnerability of a hardware cryptographic circuit.

The method empowers the circuit designer to detect if the chosen countermeasure (Boolean masking or some parts of a threshold implementation) is effective up to the desired order. Our overarching goal was (and is) to promote the implied statistical reasoning behind the countermeasure into a symbolical one, eventually extending ordinary computer aided design of integrated circuits. I'll recap in this post the major findings.

Background

A side-channel attack corresponds to a set of queries to a physical observable whose aim is to identify the value of a master key/sub-key KK of the primitive. Cryptographic primitives may expose, through a side-channel, one or many intermediate sensitive variables SS that are deterministic functions of both the master key KK and the public input PP. To safeguard against a possible vulnerability, a customary solution is to prevent a sensitive value SS to become visible, by processing the following value instead V=SM1MdV = S \oplus M_1 \oplus \cdots \oplus M_d, where \oplus is the bitwise XOR and M1,,MdM_1, \ldots, M_d are random uniformly distributed values called masks. However, this does not rule out the case where some SS can be derived from observations of a (data dependent) leakage: L=ψ(V)+NL = \psi(V) + N where ψ\psi is a mapping from the Boolean space, often defined to be the Hamming weight function.

Original findings

We now focus on a specific but very common case where the components of the leakage vector LL are of the form Li=j=1vci,jVj+NiL_i = \sum_{j=1}^v c_{i,j} V_j + N_i. Moreover, we assume that visible variables are related to masks and sensitive variables by the following matrix expression in F2\mathbb{F}_2:

V=C[MS]=[BA][MS]=BMAS{V} = C \cdot \begin{bmatrix} {M} \\ {S} \end{bmatrix} = \begin{bmatrix} B & A \end{bmatrix} \cdot \begin{bmatrix} {M} \\ {S} \end{bmatrix} = B{M} \oplus A{S}

In the paper, we have shown that SS is vulnerable to a correlation attack on LL if there exists a constant row vector ϵ=(ϵi)i=1vF2v{\epsilon}=(\epsilon_i)_{i=1}^v\in\mathbb{F}_2^v such that the product

ϵV=i=1vϵiVi{\epsilon} {V} = \bigoplus_{i=1}^v \epsilon_i V_i

cancels out any mask contribution (i.e. ϵB=0{\epsilon} B={0}). In particular, a vulnerability can be found if and only if the reduced row echelon form of CC (i.e., CRC_R) has a sensitive pivot column.

Example

Consider the following visible variables (V1,V2,V3,V4)=V(V_1,V_2,V_3,V_4) = {V}:

V1=S1M1,V2=S2M2,V3=S1S2M1M2,V4=M1M2.\begin{aligned} V_1 &= S_1 \oplus M_1 \, , \\ V_2 &= S_2 \oplus M_2 \, , \\ V_3 &= S_1 \oplus S_2 \oplus M_1 \oplus M_2 \, , \\ V_4 &= M_1 \oplus M_2 \, .\end{aligned}

which corresponds to the following visible matrix CC:

C=[1010010111111100],C = \left[ \begin{array}{cc|cc} 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ \end{array} \right] \, ,

where the vertical line divides the submatrix BB, corresponding to the masks M1,M2M_1,M_2, from the submatrix AA, corresponding to the sensitive variables S1,S2S_1,S_2. The reduced row echelon form of CC is

CR=[1001010100110000].C_R = \left[ \begin{array}{cc|cc} 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ \end{array} \right] \, .

We can see that the column of S1S_1 is a pivot column and thus S1S_1 is vulnerabile.