blogs

Reversing bits using gf2p8affineqb

Instructions from Intel GFNI (Galois Field New instructions) designed to perform affine transformations on packed 8-bit elements.

Introduction

The instruction name can broken into fairly understandable bits

GF2-P8-AFFINE-Q-B, where

  1. GF2 stands for GF(2)\mathbb{GF}(2), the Galois field with two elements
  2. P8 is for power of 8 (282^8). It specifies the field sizea as it works with 8-bit bytes, so operation operating within the finite field GF(28)\mathbb{GF}(2^8)
  3. Affine indicates affine transformations, which means it multiplies and 8-bit element by an 8 ×\times 8 bit matrix and then adds (XORs) and 8-bit vector constant.
  4. Qword variant, the transformation matrix is supplied as a qword 64-bit; each 64-bit chunk contains the 8 ×\times 8 matrix representations
  5. B, the elements being transforrmed are bytes.

A high level interpretation is: perform an affine transformations over GF(2)\mathbb{GF}(2) on packed 8-bit elements.

Here each byte is treated as an 8-bit vector over GF(2)\mathbb{GF}(2). Mathematically operation can be represented as:

y=Ax⊕by = Ax \oplus b

,the matmul is operated over Galois field, whichm means instruction is essentially performing 8 XOR equations in parallel for every byte.

A byte as a vector over 8-bit Galois field

Consider an 8-bit byte

x=x7x6x5x4x3x2x1x0x = x_7x_6x_5x_4x_3x_2x_1x_0

where each bit satisfies

xi∈GF(2)={0,1}x_i \in \mathbb{GF}(2)=\{0,1\}

We can represent the byte as an 8-dimensional vector over GF(2)\mathbb{GF}(2):

x=[x7x6x5x4x3x2x1x0]∈GF(2)8\mathbf{x} = \begin{bmatrix} x_7\\ x_6\\ x_5\\ x_4\\ x_3\\ x_2\\ x_1\\ x_0 \end{bmatrix} \in \mathbb{GF}(2)^8

An 8×88\times8 matrix whose entries are elements of GF(2)GF(2) can then operate on this vector:

A∈GF(2)8×8A \in \mathbb{GF}(2)^{8\times8}

The resulting vector is

y=Ax\mathbf{y}=A\mathbf{x}

Because the arithmetic is performed over GF(2)\mathbb{GF}(2), addition is XOR and multiplication is AND.

For example, if

A=[1010000001010000001010000001010000001010000001011000001001000001]A= \begin{bmatrix} 1&0&1&0&0&0&0&0\\ 0&1&0&1&0&0&0&0\\ 0&0&1&0&1&0&0&0\\ 0&0&0&1&0&1&0&0\\ 0&0&0&0&1&0&1&0\\ 0&0&0&0&0&1&0&1\\ 1&0&0&0&0&0&1&0\\ 0&1&0&0&0&0&0&1 \end{bmatrix}

then

y=[x7⊕x5x6⊕x4x5⊕x3x4⊕x2x3⊕x1x2⊕x0x7⊕x1x6⊕x0]\mathbf{y} = \begin{bmatrix} x_7\oplus x_5\\ x_6\oplus x_4\\ x_5\oplus x_3\\ x_4\oplus x_2\\ x_3\oplus x_1\\ x_2\oplus x_0\\ x_7\oplus x_1\\ x_6\oplus x_0 \end{bmatrix}

Thus, an 8×88\times8 binary matrix can be viewed as eight XOR equations, one for each output bit.

For an affine transformation, an additional constant vector b∈GF(2)8\mathbf{b}\in \mathbb{GF}(2)^8 is added:

y=Ax⊕b\mathbf{y}=A\mathbf{x}\oplus\mathbf{b}

just a draft, will continue later