Salsa Stream Cipher

Introduction

Salsa20 or Snuffle 2005 is a stream cipher with support for 128 and 256-bit keys. It was designed by Daniel Bernstein, the same author behind ChaCha, Poly1305, Curve25519 and Ed25519. It was selected for the final portfolio of the eStream (ECRYPT Stream Cipher Project). The implementation here only supports 256-bit keys and was only tested on little-endian architecture.

Macros, data types

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

typedef unsigned char B;
typedef unsigned int W;
typedef unsigned long long Q;

typedef union _salsa_ctx_t {
    B b[64];
    W w[16];
    Q q[8];
} salsa_ctx;

Salsa20 Core

The 64-byte input x to Salsa20 is viewed in little-endian form as 16 words x0, x1, x2, …, x15 in {0,1,…,2^32-1}. These 16 words are fed through 320 invertible modifications, where each modification changes one word. The resulting 16 words are added to the original x0, x1, x2, …, x15 respectively modulo 2^32, producing, in little-endian form, the 64-byte output Salsa20(x).

Each modification involves xor’ing into one word a rotated version of the sum of two other words modulo 2^32. Thus the 320 modifications involve, overall, 320 additions, 320 xor’s, and 320 rotations. The rotations are all by constant distances.

The entire series of modifications is a series of 10 identical double-rounds. Each double-round is a series of 2 rounds. Each round is a set of 4 parallel quarter-rounds. Each quarter-round modifies 4 words.

void salsa20_core(void *input, void *output) {
    W a,b,c,d,i,*s=(W*)input, *x=(W*)output;
    W v[8]={0xC840, 0x1D95, 0x62EA, 0xB73F,     // column index
            0x3210, 0x4765, 0x98BA, 0xEDCF };   // diagonal index
            
    // load state into local buffer
    F(16)x[i]=s[i];
    
    // for 80 rounds
    F(80) {
      d=v[i%8];
      a=(d&15);b=(d>>4&15);
      c=(d>>8&15);d>>=12;
      
      x[b]^=R((x[a]+x[d]), 7);
      x[c]^=R((x[b]+x[a]), 9);
      x[d]^=R((x[c]+x[b]),13);
      x[a]^=R((x[d]+x[c]),18);
    }
    // add state to local buffer
    F(16)x[i]+=s[i];
}

Initialization

void salsa20_setkey(salsa_ctx *c, void *key, void *nonce) {
    W   *k=(W*)key, *n=(W*)nonce;
    int i;
    
    c->w[ 0] = 0x61707865;
    // copy 1st half of 256-bit key 
    F(4) c->w[i+1] = k[i];
    c->w[ 5] = 0x3320646E;
    // copy 64-bit nonce
    c->w[ 6] = n[0];
    c->w[ 7] = n[1];
    // set 64-bit counter
    c->w[ 8] = 0;
    c->w[ 9] = 0;
    c->w[10] = 0x79622D32;
    // copy 2nd half of 256-bit key
    F(4) c->w[i+11] = k[i+4];
    c->w[15] = 0x6B206574;
}

Encryption/Decryption

void salsa20_encrypt(salsa_ctx *ctx, void *in, W len) {
    B c[64],*p=in;
    W i,r;

    // if we have data to encrypt/decrypt
    if(len) {
      while(len) {
        // permute state
        salsa20_core(ctx, c);
        // increase counter
        ctx->q[4]++;
        // encrypt 64 bytes or whatever is remaining
        r = (len > 64) ? 64 : len;
        // xor plaintext with ciphertext
        F(r)p[i] ^= c[i];
        // decrease length, advance buffer
        len -= r;
        p   += r;
      }
    }
}

Sources here.