GCM Multiplication Implementation

Question

I am puting up a C code for the Multiplication of block (Alogrithm 1) in the GCM SP-800-38D document here. Page 11-12.

Having completed the code, I want to see if there are any way I can test the code. You can find attached below the code I have put up. Note that instead of the 128 bit block, I used a 24 bit block just for testing purposed. I will appreciate any suggestions where necessary.

void BLK_MUL (u8 *val_1,u8 *val_2, u8 *out_val)
{ 

    u8 xdata R_val = 0xE1;     
    u8 xdata Z_val[3],V_val[3];
    u8 mask_b   = 0x80;        
    u16 i;  u8 j;           
    bit rnd;                

    for(j=0;j<3;j++,++val_2)    
    {
        Z_val[j]=0x00;      
        V_val[j]=*val_2;    
    }       


    for(i=0;i<24;i++)
    { 
        if (*val_1 & mask_b)
        {
            for(j=0;j<3;j++)    
                Z_val[j]^=V_val[j]; 
        }
        if (!(V_val[2] & 0x01))
        {//if LSB of V_val is 0
            for(j=0;j<3;j++)
            { //V_val = rightshift(V_val)
                if (j!=0)
                    if (V_val[2-j] & 0x01)
                        V_val[3-j] |= 0x80;
                V_val[2-j]>>=1;          
            }
        }
        else
        {//if LSB of V_val is 1
            for(j=0;j<3;j++)
            {//V_val = rightshift(V_val)
                if (j!=0)
                    if (V_val[2-j] & 0x01)
                        V_val[3-j] |= 0x80;
                V_val[2-j]>>=1;          
            }
            V_val[0]^=R_val; //V_val = rightshift(V_val) ^ R                
        }
        if(mask_b & 0x01)   { val_1++; rnd=1;}  
        mask_b >>= 1;                       
        if (rnd)    { mask_b=0x80; rnd=0; } 
    }

    STR_CPY(out_val,Z_val,3);   

    return ;        
}


void main()
{

    code unsigned char val_1[3] ={  0x2b,0x7e,0x15  };
    code unsigned char val_2[3] ={  0x39,0x25,0x84  };
    unsigned char out[3];

    BLK_MUL (val_1,val_2,out);

    return;
}

Answer 1

At some point you will of course have to check your code against test vectors. But there are quite a few tests that you can perform without having to know or compute any test vectors at all.

First the multiplication in GF(2^128) is commutative. Hence you can just compute BLK_MUL(val_1, val_2, out1) and BLK_MUL(val_2, val_1, out2) with any input and you should get the same result. Since your code uses val_1 and val_2 differently this is already quite a good test.

Then you can use that multiplication is distributive, I.e. you can test that (x+y)*z = (x*z)+(y*z), (where the addition in GF(2^128) is computed by xoring corresponding bytes of the two values together).

Finally, once you have implemented the whole field GF(2^128) you can also exploit that its order is 2^128-1. I.e. if you start with a value x then square it 128 times, then you should get x back.

---

A few additional comments:

The advantage of using equations for testing (over only using test vectors) is that you can easily run a large number of tests. Because it is rather easy to add tests this way I frequently do some simple tests with sparse inputs (e.g. just single bits set in the input) first. If something is wrong then this helps to identify the bugs fast.

Your current code uses temporary variables for the result. This is indeed a good idea, since it ensures copy safety. I think a good unit test should also cover this case. I.e. you might want to compute the same result twice: once with input and output pointing to different memory location, and once with the output being the same memory as the input.

Furthermore, at least one of the other answers talks about optimizations. I think if you refactor the code then you should look for meaningful components to reuse, rather than blindly looking for look-a-like code snippets. Since GF(2^128) is a field, of course addition and multiplication in the field are meaningful components. Another meaningful component is the multiplication by the polynomial x (which is something that is quite frequently used in crypto).

Answer 2

Test vectors for GCM mode can be found here and there's a bunch of NIST test vectors here.

Answer 3

A test example for GF(2^128) can be found at: PCLMULQDQ CPU instruction, page 78