Keccak Permutation Function

Introduction

Keccak is a cryptographic permutation function designed by Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. Keccak can be used to construct a stream cipher, a cryptographic hash function, a Pseudo Random Number Generator (PRNG), Message Authentication Code (MAC) or an Authenticated Encryption Associated Data (AEAD) algorithm. It is incredibly versatile and considered the swiss army knife of cryptographic primitives. For more detailed information, please refer to the documentation provided by the designers.

Keccak Parameters

The following table lists parameters for the Keccak function and what architecture it’s most suitable for.

F Target Architecture Capacity Rounds
200 8-bit 200-bits 18
400 16-bit 400-bits 20
800 32-bit 800-bits 22
1600 64-bit 1600-bits 24

Macros, data types

To build keccak for a specific architecture, I’ve defined parameters for K200 (8-bit), K400 (16-bit), K800 (32-bit) with the default being 64-bit or K1600.

#if defined(K200)
  // keccak-f[200, 18]
  #define ROUNDS  18
  #define WORDLEN  8
  typedef unsigned char W;
#elif defined(K400)
  // keccak-f[400, 20]
  #define ROUNDS  20
  #define WORDLEN 16
  typedef unsigned short W;
#elif defined(K800)
  // keccak-f[800, 22]
  #define ROUNDS  22
  #define WORDLEN 32
  typedef unsigned int W;
#else
  // keccak-f[1600, 24]
  #define ROUNDS  24
  #define WORDLEN 64
  typedef unsigned long long W;
#endif

#define R(v,n)(((v)<<(n))|((v)>>(WORDLEN-(n))))
#define F(a,b)for(a=0;a<b;a++)

Keccak Modules

Module Description
Theta Renders the internal state into a 5-by-5 array of n-bit elements. Computes the parity of each column and combines them with an exclusive-or (XOR) operator.
Rho Rotates each element by a triangular number.
Pi Permutes the elements.
Chi Adds a non-linear aspect to the permutation round. Combines the row elements using only three bitwise operators: AND, NOT, and XOR.
Iota Breaks up any symmetry caused by the other modules. This is done by XORing one of the array elements to a round constant. Without iota, the round mapping would be symmetric. Without iota, all rounds would be the same.
void keccak(void *state) {
    W n,i,j,r,x,y,t,Y,b[5],*s=state;
    unsigned char c=1;

    F(n, ROUNDS){
      // Theta
      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],1);
        F(j,5)s[i+j*5]^=t;}
      t=s[1],y=r=0,x=1;
      // Rho and Pi
      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%WORDLEN),t=Y;
      // Chi
      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]);}
      // Iota
      F(j,7)
        if((c=(c<<1)^((c>>7)*113))&2)
          *s^=1ULL<<((1<<j)-1);
    }
}

Sources here.

This entry was posted in assembly, cryptography, encryption, programming and tagged , , , . Bookmark the permalink.

1 Response to Keccak Permutation Function

  1. Pingback: XooDoo Permutation Function | crypto on x86 and ARM

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s