2
$\begingroup$

While reading about AES-GCM, I discovered there is a multiplication over $\operatorname{GF}(2^{128}$). My question is about its cryptographic properties, such as:

  1. Take a random element $X$ from $\operatorname{GF}(2^{128}$) (which is not $0$ or $1$). Multiply it with a constant $Y$ (say, the plaintext, which is defined over the same field, $Y\neq 0$). Given the product $XY$, is it possible to recover $Y$ (or some non-trivial information about $Y$)?
  2. If the product $XY$ satifies some regularity condition (such as $XY=1$), is it possible to gain information on $Y$?
  3. If multiple conditions like this are given, is it possible to gain information on $Y$? I mean, say for randomly chosen $X_i$'s, the product $X_iY$'s are given.

If the above problems are hard to solve, probably finite field multiplication can be used as a method for masking countermeasure for side channel (at least theoretically).

$\endgroup$
  • $\begingroup$ Unrelated to masking: worth noting that multiplication by a constant in $GF(2^n)$ is linear over $GF(2)$. $\endgroup$ – Fractalic Oct 7 at 14:24
  • $\begingroup$ @Fractalic Oh, I see. That would probably mean, given $X\odot Y$ ($\odot$ is the finite field multiplication) and $X \oplus Y$, it may be possible to recover $X$ and $Y$. I will ask a follow-up question for better clarification. $\endgroup$ – hola Oct 7 at 15:19
  • $\begingroup$ @Fractalic Update My follow-up question is here $\endgroup$ – hola Oct 7 at 15:32
  • $\begingroup$ while what you say is possible, I meant that the map $X \mapsto c \odot X$ can be expressed as a binary matrix. $\endgroup$ – Fractalic Oct 7 at 16:19
  • $\begingroup$ @Fractalic That leads us to a new question $\endgroup$ – hola Oct 8 at 8:57
8
$\begingroup$

You're asking about the multiplication operation over $GF(2^{128})$; it turns out that, if we exclude the element 0, then the multiplication operation over that modified set of $2^{128}-1$ elements is a group operation; for example, inverses exist.

And, for any group operation $\odot$, we have:

  • For any element $Y$, if we multiply it by a random (and independent) element $X$, the result $X \odot Y$ is random (and revealing it does not reveal anything about $Y$).

This answers your question one (with your question being modified by having $X$ exclude the 0 element only, not the 1 element) . Remember, 0 is not a member of the group (even though it is a member of the field; we deliberately excluded it when defining the group); in contrast, 1 is a member of the group, and avoiding it would leak some information, in particular, the value that $Y$ is not (because $Y \ne X \odot Y$ )

  • If both $X$ and $Y$ are unknown, then revealing $X \odot Y$ does not reveal any information about $Y$

This answers your question two.

  • Revealing $X_i \odot Y$ for a large number of random $X_i$ values also does not reveal any information about $Y$.

This answers your question three.

If the above problems are hard to solve, probably finite field multiplication can be used as a method for masking countermeasure for side channel (at least theoretically).

Possibly, but it wouldn't be ideal. For one, we had to deliberately exclude the 0 value; a real implementation that does masking can't ignore such a possible value; in particular, if you had a $Y=0$ value, masking wouldn't work in that case. On a more practical note, masking would usually involve computing inverses, and while computing multiplicative inverses over $GF(2^{128})$ isn't that hard, it isn't exceptionally trivial either.

| improve this answer | |
$\endgroup$

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.