Can we solve the Hidden Number Problem in $GF(2^n)$?

Question

Is it possible to solve the Hidden Number Problem in extension fields? In particular in $GF(2^n)$?

Let's suppose an attacker knows some least/most significant bits of $r_i = a_i \times k$ in a given field $GF(2^n)$, for many uniformly distributed and known $a_i$ and a fixed and unknown $k$. Is it possible to recover $k$ ?

This is, as far as I know, an instance of the Hidden Number Problem originally introduced by Boneh and Venkatesan, used mainly to break digital signature schemes provided several signatures and partial knowledge of the respective nonces.

As far as I know HNP has always been applied in $GF(p)$, and furthermore the technique used to solve it, through Lattices and Closest Vector Problem, can't be easily adapted, IMHO, to $GF(2^n)$.

Rationale behind the question (not required for answering it):

I was comparing the authentications of GCM and Poly1305 in a specific, purely hypothetical, scenario where the attacker gets some knowledge of bits of the result of the authentication function, prior to the final addition of the encrypted nonce.

Let's assume we have single block messages.

Poly1305 authentication (without addition of encrypted nonce) is just: $(c\times r)\mod {2^{130}-5}$ where $c$ is the message block and $r$ is the authentication key. I can see how to apply HNP to solve for $r$ in this case.

But GCM performs (I'm assuming to use an HW accelerator so that I can cheat in providing the final message with the aad and payload sizes): $ (c\times h) \mod {x^{128}+x^7+x^2+x+1}$ where $h$ is the GHASH key. I don't see how to solve for $h$, having several partial information of the result for different and known $c$.

Answer 1

Yes, it appears that it can be solved in practical time in $GF(2^n)$, if the attacker gets $n+\epsilon$ random $a_i$ values, even if he gets a single bit of the $a_i \times k$ values.

The chief observation is that the mapping from $a_i$ to bit $j$ of $a_i \times k$ (which I'll refer to as $bit_j(a_i \times k)$) is bitwise linear (for constant $j$, $k$).

So, assuming that we have $a_i$ and the corresponding $bit_m(a_i \times k)$ values (for some known $m$), our first step is to find $n$ linear independent $a_i$ values (which, given $n+\epsilon$ random $a_i$ values, we'll have with good probability); we view this as a set of $n$ linear equations, and solve them in $O(n^3)$ time, giving us the mapping between any value $a$ and $bit_m(a \times k)$

Now, for polynomial representations of $GF(2^n)$, for every $i, j$ pair, there is a constant $c_{i,j}$ where $bit_i(a) = bit_j(a \times c_{i,j})$ for all $a$.

This observation allows us to find the linear mapping of $bit_n(a \times k)$ for any $n$, as $bit_n(a \times k) = bit_m(a \times k \times c_{n,m}) = bit_m( (a \times c_{n,m} ) \times k )$; in other words, to perform this mapping, we multiply the vector by the constant $c_{n,m}$, and then apply the mapping we already know (both of which are linear operations).

The result of this are $n$ linear maps giving us all $n$ bits of the product. Then, we can solve these $n$ linear maps for the input that gives a 1 bit for the lsbit map, and 0 for the rest; the solution for this is $k^{-1}$, which immediately gives us the value for $k$.

I suspect that there are signficantly more efficient ways to solve this; however this algorithm should be enough to answer the question.

Answer 2

Thanks @poncho for providing a correct answer. I investigated it deeply, viewing it as a linear algebra problem.

Here's what I obtained: in $GF(2^n)$, the series of equations $r_i=a_i\times k$ can be written as $R = K \cdot A$ where:

• $A$ is a known $n \times n$ matrix, where each column is a bit representation of $n$, linearly independent, $a_i$
• $R$ is a $n \times n$ matrix where the attacker only knowns one row to the attacker (because we know one bit of the original $r_i$)
• $K$ is a matrix encoding both $k$ and the modular reduction.

$K$ can be constructed in this way: $\begin{bmatrix}k\times x^0 & k\times x^1 &... &k\times x^{n-1}\end{bmatrix}$ where $\times$ performs the proper modular reduction.

Actually $K$ can be rewritten as the product of two matrices: $Mr$ (size $n\times2n$) and $Mk$ (size $2n \times n$) where:

• $Mr = \begin{bmatrix}x^0 & x^1 &... &x^{2n-1}\end{bmatrix}$ where the exponentiation is evaluated with the proper modular reduction
• $Mk = \begin{bmatrix}k*x^0 & k*x^1 &... &k*x^{n-1}\end{bmatrix}$ where $*$ is evaluated without modular reduction.

So we have $R = Mr \cdot Mk \cdot A$.

We invert $A$ to obtain: $R\cdot A^{-1} = Mr \cdot Mk$

But we only know row $R_m$ of index $m$ of $R$, therefore we have: $R_m\cdot A^{-1} = Mr_m \cdot Mk$

Now, $Mk$ has a particular shape, where in the first column (of size $2n$) only the elements in index $0$ to $n-1$ can be different from zero (they encode $k$), in the second column only the elements from index $1$ to $n$ are different from zero (and encode $k$) and so on.

This allows to rewrite $R_m\cdot A^{-1} = Mr_m \cdot Mk$ into $(R_m\cdot A^{-1})^T = MN \cdot \vec{k}$ where $\vec{k}$ is a column vector encoding the coefficients of $k$. $MN$ is a $n\times n$ matrix defined as:

$MN = \begin{bmatrix} Mr_m[0:n-1]& \\ Mr_m[1:n] &\\ Mr_m[2:n+1] &\\ ... &\\ Mr_m[n:2n-1] & \end{bmatrix}$

where the notation $Mr_m[x:y]$ indicates the subrow of $Mr_m$ with indexes from $x$ to $y$

Now the solution can be found by computing $\vec{k} = MN^{-1} \cdot (R_m\cdot A^{-1})^T$ if $MN$ is invertible.

I've tested for all rows of the matrixes generated by all irreducible polynomials of degree 8 and it was always the case, maybe it can be shown this is always the case. Also I suspect there's a better way to solve without creating $MN$ in that way, maybe rewriting $K$ in a different way.