Score:3

Protecting AES via Shamir Secret Sharing

ru flag

This is about the paper Protecting AES with Shamir's Secret Sharing Scheme by Louis Goubin and Ange Martinelli which describes how to use Shamir Secret Sharing to obtain masked implementations of AES.

The end of section 3.1 suggests that the $\text{GF}(2)$-affine transformation $A$ involved in the definition of the AES S-Box is compatible with SSS in the sense that if $(x_i,y_i)$ is an SSS sharing of $x$, then $(x_i, A(y_i))$ is an SSS sharing of $A(x)$. This isn't clear to me, and there has been a corresponding errata claim long ago, which however hasn't been publicly replied to.

Are there indeed details to be filled in here, and if so, can someone comment one how it can be done?

Score:1
sa flag

The objection on the eprint.iacr forum is below and seems to be correct at a quick first look.

Did you search literature that cites this paper? Have the authors published further on this?

Edit: There is further work here which may validate the claim, in an MPC framework. Just putting this note up since I will not have time to look more deeply for a while.

“At the end of section 3.1 the authors claim that affine component A of the AES S-box (which is the composition of inversion in GF(256) with an GF(2)-affine map that is NOT affine over GF(256)) can be simply implemented by applying the affine map A on the shares $y_i$ (ignoring the constant term of the affine map making it linear for simplicity's sake).

This is wrong.

As proof the authors claim that A(P) is a polynomial of degree d. A(P) can be interpreted as such a polynomial, but NOT as a polynomial of one variable over GF(256), ONLY as a polynomial in 8 variables over GF(2) when choosing a basis of GF(256) over GF(2). It is not clear at all, how to convert such a polynomial back to the form the authors need.

An easy way to see that replacing $y_i$ by $A(y_i)$ does NOT correspond to applying the affine map A to the secret value is by taking equation (1) of section 2.2:

The secret $a_0$ can be reconstructed given the shares $y_i$ by evaluating the sum $\sum_0^d y_i \cdot \beta_i$. Applying the affine map A on both sides (for simplicity, we assume again A to be linear over GF(2)) one gets $A(a_0) = A(\sum_0^d y_i \cdot \beta_i) = \sum_0^d A(y_i \cdot \beta_i)$.

As $A$ is NOT affine/linear over GF(256), in general $A(y_i \cdot \beta_i)$ does NOT equal $A(y_i) \cdot \beta_i$ and having $A(a_0)$ equal to $\sum_0^d A(y_i) \cdot \beta_i$ would be pure coincidence.”

Hanno avatar
ru flag
Thank you Kodlu for finding this! It seems that this is a critique separate from the one regarding the application of the affine part of the S-box, since it concerns the proposed new secure SSS-multiplication algorithm
Score:0
ru flag

There are in fact two separate things to be discussed w.r.t. the paper:

  1. The details of how to apply a $\text{GF}(2)$-affine function to an SSS-shared variable.

  2. The correctness of the new SSS-multiplication scheme proposed in the paper.

The paper On the Use of Shamir’s Secret Sharing Against Side-Channel Analysis mentioned by Kodlu suggests that there is a flaw in 2. Thanks for finding that, Kodlu!

Regarding the original question about 1., the paper Higher-Order Glitches Free Implementation of the AES using Secure Multi-Party Computation Protocols by Roche and Prouff explains how to apply a $\text{GF}(2)$-affine function in the context of SSS over $\text{GF}(2^8)$. For convenience, and because it's elegant, I'll reproduce it here with some filled-in details:

The crucial observation is the following:

Claim: Any $\text{GF}(2)$-affine function on $\text{GF}(2^n)$ is uniquely of the form $a_{-1} + \sum_{k=0}^{n-1} a_k \text{Frob}^k$, where $\text{Frob}: y\mapsto y^2$ is the Frobenius, and $a_k\in\text{GF}(2^n)$.

Proof: Since $\text{Gal}(\text{GF}(2^n)/\text{GF}(2))=\{\text{Frob}^k\}_{k=0,\ldots,n-1}$, this is a special case of the fact that for any Galois extension $L/K$, $\text{Gal}(L/K)$ is an $L$-basis of $\text{End}_K(L)$. This in turn follows from (a) the fact that $\text{dim}_K(L)=|\text{Gal}(L/K)|$, hence $\dim_L\text{Hom}_K(L,L)=\text{dim}_L\text{Hom}_K(K^{|\text{Gal}(L/K)|},L)=|\text{Gal}(L/K)|$, and (b) the fact that the elements of $\text{Gal}(L/K)$ are $L$-linear independent, which is a special case of the linear independence of characters.

With the claim, the application of $\text{GF}(2)$-affine functions on $\text{GF}(2^n)$ to SSS-shares reduces to the application of functions of the form $y\mapsto b y^{2^k}$ for some $b\in \text{GF}(2^n)$. Here, it is observed that things get simpler by assuming the set of public SSS evaluation points $\{\alpha_i\}$ to be stable under $\text{Frob}$, in which case an SSS-sharing $(\alpha_i, y_i)$ of $x$ transforms into an SSS-sharing $(\alpha_{\pi^k(i)}, b y_i^{2^k})=(\alpha_i, b y_{\pi^{-k}(i)}^{2^k})$ of $b x^{2^k}$ for the permutation $\pi$ determined by $\text{Frob}(\alpha_i) = \alpha_{\pi(i)}$. Such $\text{Frob}$-stable subsets of $\text{GF}(2^n)$ can be constructed based on the observation that $\text{GF}(2^n)\setminus\bigcup_{k|n}\text{GF}(2^k)$ decomposes into $\text{Frob}$-orbits of size $n$, so inductively there are $\text{Frob}$-orbits of size $k|n$ for all $k|n$.

So, putting it all together, applying $a_{-1} + \sum_{k=0}^{n-1} a_k \text{Frob}^k$ to an SSS-shared variable $(\alpha_i,y_i)$ with $\text{Frob}$-stable $\{\alpha_i\}$ is algebraically similar to applying it share-wise, but one has to add a permutation to the shares: The new $i$-th share $a_{-1} + \sum_{k=0}^{n-1} a_{k} \text{Frob}^k(y_{\pi^{-k}(i)})$, where $\pi$ is the permutation on $\{\alpha_i\}$ induced by $\text{Frob}$.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.