2
$\begingroup$

I'm trying to understand how Shamir's Secret Sharing algorithm is applied to AES when doing threshold masking.

I understand how the secrets are created and the secret is calculated and I'm now trying to figure out how the math operations (that are needed for AES) work when you have the shares. To do that I'm reading this source: Goubin et al, Protecting AES with Shamir's Secret Sharing Scheme. (pages 79-94 in isbn 978-3-642-23951-9)

It says: addition of shares with an unmasked value: $$\{(x_i', y_i') \leftarrow (x_i,y_i \oplus u) | \forall (x_i, y_i) \in shares\}$$ Where $u$ is the to be added value and $(x_i, y_i)$ is an original share. Addition results in a new $(x_i', y_i')$ share.

I've implemented this in python (not in a finite field) in this way:

def add_unmasked(self, shares, value):
    return [{'x': share['x'], 'y': share['y'] ^ value} for share in shares]

However I don't see the correct results, if I have a secret of 20 being shared and unshared results it in 20, but if I add 1, I get the wrong result 80% of the time.

For completeness sake my code:

def create_shares(self, to_create):
    if to_create < self.degree + 1:
        raise Exception('shares don\'t cover the order')

    coefficients = self.generate_polynomial(self.degree, self.secret)

    points = random.sample(range(self.finite_field), to_create)
    shares = [{'x': point, 'y': sum(coefficient * point ** n for n, coefficient in enumerate(coefficients))} for
              point in points]

    return shares

def tell_secret(self, shares):
    # doing a polynomial interpolation using the basic definition. sum y * l where l is the product of x - xi / xm - xi. x is 0 in our case
    xs = [share['x'] for share in shares]

    y = 0
    for share in shares:
        l = 1
        for x in xs:
            if x != share['x']:
                l *= (- x) / (share['x'] - x)
        y += share['y'] * l
    return int(round(y))

edit: Reading wikipedia about the definitions of operators in a finite field, I've found this:

A particular case is GF(2), where addition is exclusive OR (XOR) and multiplication is AND.

AES uses a $GF(2)$ finite field, the Galois field $GF(2^8)$ So when my paper says: $\oplus$ they mean the addition operator for the finite field GF(2). This is confirmed by my test when doing an addition in my non finite field program.


edit 2:

enter image description here

As such I read this as doing a $GF(2^8)$ addition to all the shares. It is using the word XOR and I've read that it should be XOR in the finite field but when I do this in my testing program, I don't get the correct result. This seems to be because of at least one share having an y value which overflows with the addition.


edit 3:

So I've found the following lines in the referenced paper:

Our scheme maintains the same compatibility as Boolean masking with the linear transformations of the algorithm

So it seems that the paper proposes some kind of SSS mixed with boolean masking on an AES implementation. I still don't get it completely but I'm moving on and maybe if I come back to it later my understanding will have improved.

$\endgroup$
3
$\begingroup$

It seems that the question you're asking is about how to add a public (unmasked?) value to a secret-shared value. I suggest you edit the question a bit to clarify that this is not related to AES directly.

With that aside, adding a public value to a secret-shared value depends heavily on what secret-sharing scheme you're using, and also the algebraic structure where you're doing it, of course.

To secret-share a single bit $b$ using additive secret sharing, you sample random bits $b_1$ and $b_2$ constrained to $b=b_1\oplus b_2$. The pair of shares is then $(b_1,b_2)$. To add a publicly known bit $u$, you only need to add it to one of the shares, say to $b_2$, so the new shares are $(b_1, b_2\oplus u)$. You can check that if you add (i.e. XOR) these together then you get $b\oplus u$, so you effectively added $u$ to the secret.

If you're additively secret-sharing elements of $\mathsf{GF}(2^8)$ instead of single bits the principle is the same, except that XOR is replaced with addition in $\mathsf{GF}(2^8)$. Quite coincidentally though, addition in $\mathsf{GF}(2^8)$ is precisely component-wise XOR, but this didn't need to be the case, specially if you used instead, say, $\mathsf{GF}(3^8)$.

Now, all of this was for additive secret-sharing, but this is not how Shamir secret-sharing works. In this scheme, secret-sharing a value $s$ among $n$ parties with threshold $t$ consists of sampling a random polynomial $f(\mathtt{X})$ of degree at most $t$, constrained to $f(0)=s$, and letting the $i$-th share be $s_i=f(i)$.¹ With this secret-sharing scheme, adding a public value $u$ is done by letting each party (not only one) add this value to its share, getting $(f(1)+u,\ldots,f(n)+u)$ as the vector of shares. I encourage you to check why this is a valid Shamir sharing of $s+u$.

To sum up from the discussion above, I think you are mixing additive with Shamir secret-sharing. The method you described and implemented is for adding a public value to an additive sharing, yet you mention in the title and the text Shamir secret-sharing.


¹ Here, the "numbers" $0,1,\ldots,n$ that we are evaluating into the polynomial are simply symbols to represent different elements of the field you're considering, e.g. $\mathsf{GF}(2^8)$.

$\endgroup$
7
  • $\begingroup$ I think I'm using $GF(2^8)$ as I want to mask AES bytes. I'm trying to understand SSS, not additive. (my higher goals is to protect AES against t'th order key leakage attacks, a t+1'th order SSS does that). I'll update the question with more context info. $\endgroup$ Apr 8 at 14:43
  • $\begingroup$ @TarickWelling I mentioned additive secret sharing since, although I didn't read the reference you provided, the method for adding constants you wrote looks more like the one you use in additive secret-sharing. As I explained in the answer, in Shamir secret-sharing, you add the public value to every share, not only to one. $\endgroup$
    – Daniel
    Apr 8 at 14:47
  • $\begingroup$ Yes I add the unmasked value to all the shares. I've included the paragraph with the definition for addition I'm trying to understand. $\endgroup$ Apr 8 at 14:55
  • $\begingroup$ Oh! $(x_i,y_i)$ is not the pair of shares, but rather the $x$ and $y$-coordinates of each share! This was not clear from the original question $\endgroup$
    – Daniel
    Apr 8 at 14:56
  • $\begingroup$ Does the order of the SSS have a relation to the size of the finite field? $\endgroup$ Apr 8 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.