SHA-3 Cryptographic hash

Introduction

Keccak is a permutation function designed by Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. It was selected by NIST to become the SHA-3 standard and is a complement to SHA-2 rather than a replacement. Currently, SHA-2 is widely used and not known publicly to have any weaknesses. Since SHA-2 is very similar to MD4, MD5 and SHA-1 in design, weaknesses may be identified in the future and SHA-3 is intended to be a drop in replacement.

Macros and data types

#define R(v,n)(((v)>>(n))|((v)<<(64-(n))))
#define F(a,b)for(a=0;a<b;a++)
  
typedef unsigned long long W;
typedef unsigned char B;

typedef struct _sha3_ctx {
    union {
      B b[200];
      W q[25];
    } s;
    int i,h,r;
}sha3_ctx;

Initialization

void sha3_init(sha3_ctx*c, int len) {
    W i;
    
    F(i,25)c->s.q[i]=0;
    
    c->h = len;
    c->r = 200-(2*len);
    c->i = 0;
}

Adding data

The Sponge construction is used for “absorbing” data into the internal state. Blocks of data are xor’d with the state buffer before being transformed using the permutation function. The authors have this to say.

the sponge construction is a mode of operation, based on a fixed-length permutation (or transformation) and on a padding rule, which builds a function mapping variable-length input to variable-length output. Such a function is called a sponge function.

void sha3_update(sha3_ctx*c, const void*in, W len) {
    W i;
    B *p=(B*)in;
  
    F(i,len) {
      c->s.b[c->i++] ^= *p++;    
      if(c->i == c->r) {
        P(&c->s); 
        c->i=0;
      }
    }
}

Finalization

void sha3_final(void*out, sha3_ctx*c) {
    B   *p=(B*)out;
    int i;
    
    c->s.b[c->i]^=6;
    c->s.b[c->r-1]^=0x80;
    P(&c->s);
    F(i,c->h)p[i]=c->s.b[i];
}

Compression

void P(void*p) {
    W n,i,j,r,x,y,t,Y,b[5],*s=p;
    B c=1;

    F(n,24){
      F(i,5){b[i]=0;F(j,5)b[i]^=s[i+j*5];}
      F(i,5){
        t=b[(i+4)%5]^R(b[(i+1)%5],63);
        F(j,5)s[i+j*5]^=t;}
      t=s[1],y=r=0,x=1;
      F(j,24)
        r+=j+1,Y=(x*2)+(y*3),x=y,y=Y%5,
        Y=s[x+y*5],s[x+y*5]=R(t, -r),t=Y;
      F(j,5){
        F(i,5)b[i]=s[i+j*5];
        F(i,5)
          s[i+j*5]=b[i]^( b[(i+2)%5] &~ b[(i+1)%5]);}
      F(j,7)
        if((c=(c<<1)^((c>>7)*113))&2)
          *s^=1ULL<<((1<<j)-1);
    }
}

Sources here.