serpent.c

   1 /* serpent.c
   2  * a bitsliced implementation of the serpent cipher for avr microcontrollers
   3  * author: Daniel Otte
   4  * email:  daniel.otte@rub.de
   5  * license: GPLv3
   6  */
   7
   8 #include <stdint.h>
   9 #include <string.h> /* memset() */
  10 #include <avr/pgmspace.h>
  11 #include "serpent.h"
  12
  13 uint8_t sbox[] PROGMEM = {
  14  0x38, 0xF1, 0xA6, 0x5B, 0xED, 0x42, 0x70, 0x9C,
  15  0xFC, 0x27, 0x90, 0x5A, 0x1B, 0xE8, 0x6D, 0x34,
  16  0x86, 0x79, 0x3C, 0xAF, 0xD1, 0xE4, 0x0B, 0x52,
  17  0x0F, 0xB8, 0xC9, 0x63, 0xD1, 0x24, 0xA7, 0x5E,
  18  0x1F, 0x83, 0xC0, 0xB6, 0x25, 0x4A, 0x9E, 0x7D,
  19  0xF5, 0x2B, 0x4A, 0x9C, 0x03, 0xE8, 0xD6, 0x71,
  20  0x72, 0xC5, 0x84, 0x6B, 0xE9, 0x1F, 0xD3, 0xA0,
  21  0x1D, 0xF0, 0xE8, 0x2B, 0x74, 0xCA, 0x93, 0x56,
  22 /* now the inverted sboxes */
  23  0xD3, 0xB0, 0xA6, 0x5C, 0x1E, 0x47, 0xF9, 0x82,
  24  0x58, 0x2E, 0xF6, 0xC3, 0xB4, 0x79, 0x1D, 0xA0,
  25  0xC9, 0xF4, 0xBE, 0x12, 0x03, 0x6D, 0x58, 0xA7,
  26  0x09, 0xA7, 0xBE, 0x6D, 0x35, 0xC2, 0x48, 0xF1,
  27  0x50, 0x83, 0xA9, 0x7E, 0x2C, 0xB6, 0x4F, 0xD1,
  28  0x8F, 0x29, 0x41, 0xDE, 0xB6, 0x53, 0x7C, 0xA0,
  29  0xFA, 0x1D, 0x53, 0x60, 0x49, 0xE7, 0x2C, 0x8B,
  30  0x30, 0x6D, 0x9E, 0xF8, 0x5C, 0xB7, 0xA1, 0x42
  31 };
  32
  33
  34 #define SHR_O(a) c=(a)&1; ((a) = (a)>>1)
  35 #define SHR_I(a) ((a) = (c?0x80:0x00)| ((a)>>1))
  36
  37 static void ip(uint8_t *o, uint32_t *i){
  38         uint8_t c; // carry
  39         uint8_t n,m;
  40         memset(o, 0, 16);
  41         for(n=0; n<16; ++n){
  42                 for(m=0; m<2; ++m){
  43                 SHR_O(i[0]);
  44                 SHR_I(o[n]);
  45                 SHR_O(i[1]);
  46                 SHR_I(o[n]);
  47                 SHR_O(i[2]);
  48                 SHR_I(o[n]);
  49                 SHR_O(i[3]);
  50                 SHR_I(o[n]);
  51                 }
  52         }
  53 }
  54
  55 #undef SHR_I
  56 #define SHR_I(a) ((a) = (c?0x80000000L:0x00L)| ((a)>>1)) /* we use 32-bit words here */
  57
  58
  59 static void fp(uint32_t *o, uint32_t *i){
  60         uint8_t c; // carry
  61         uint8_t n,m;
  62         memset(o, 0, 16);
  63         for(n=0; n<4; ++n){
  64                 for(m=0; m<8; ++m){
  65                 SHR_O(i[n]);
  66                 SHR_I(o[0]);
  67                 SHR_O(i[n]);
  68                 SHR_I(o[1]);
  69                 SHR_O(i[n]);
  70                 SHR_I(o[2]);
  71                 SHR_O(i[n]);
  72                 SHR_I(o[3]);
  73                 }
  74         }
  75 }
  76
  77 /******************************************************************************/
  78
  79 static void sbox128x(uint8_t box, void* w){
  80         uint8_t sb[16];
  81         uint8_t i,t,x;
  82         box &= 0x0f;
  83         /* load sbox */
  84         for(i=0; i<8; ++i){
  85                 t = pgm_read_byte(sbox + box*8 + i);
  86                 sb[2*i+0]=t>>4;
  87                 sb[2*i+1]=t&0xf;
  88         }
  89         uint8_t o[16];
  90         ip(o, w);
  91
  92         for(i=0; i<16; ++i){
  93                 t = ((uint8_t*)o)[i];
  94                 x = sb[t>>4];
  95                 x <<= 4;
  96                 x |= sb[t&0xf];
  97                 ((uint8_t*)o)[i] = x;
  98         }
  99         fp(w, (uint32_t*)o);
 100 }
 101
 102 static void sbox128(void * w, uint8_t box){
 103         sbox128x(box&0x7, w);
 104 }
 105
 106 static void inv_sbox128(void * w, uint8_t box){
 107         sbox128x(((box&0x7)|0x8), w);
 108 }
 109
 110 /******************************************************************************/
 111
 112 void memxor(void * dest, void * src, uint8_t size){
 113         while(size--){
 114                 *((uint8_t*)dest) ^= *((uint8_t*)src);
 115                 dest = (uint8_t*)dest +1;
 116                 src  = (uint8_t*)src  +1;
 117         }
 118 }
 119
 120 /******************************************************************************/
 121
 122 uint32_t rotl32(uint32_t a, uint8_t n){
 123         return ((a<<n) | (a>>(32-n)));
 124 }
 125
 126
 127 uint32_t rotr32(uint32_t a, uint8_t n){
 128         return ((a>>n) | (a<<(32-n)));
 129 }
 130
 131
 132 #define X0 (((uint32_t*)b)[0])
 133 #define X1 (((uint32_t*)b)[1])
 134 #define X2 (((uint32_t*)b)[2])
 135 #define X3 (((uint32_t*)b)[3])
 136
 137 static void lt(uint8_t *b){
 138         X0 = rotl32(X0, 13);
 139         X2 = rotl32(X2,  3);
 140         X1 ^= X0 ^ X2;
 141         X3 ^= X2 ^ (X0 << 3);
 142         X1 = rotl32(X1, 1);
 143         X3 = rotl32(X3, 7);
 144         X0 ^= X1 ^ X3;
 145         X2 ^= X3 ^ (X1 << 7);
 146         X0 = rotl32(X0, 5);
 147         X2 = rotr32(X2, 10);
 148 }
 149
 150 static void inv_lt(uint8_t *b){
 151         X2 = rotl32(X2, 10);
 152         X0 = rotr32(X0, 5);
 153         X2 ^= X3 ^ (X1 << 7);
 154         X0 ^= X1 ^ X3;
 155         X3 = rotr32(X3, 7);
 156         X1 = rotr32(X1, 1);
 157         X3 ^= X2 ^ (X0 << 3);
 158         X1 ^= X0 ^ X2;
 159         X2 = rotr32(X2,  3);
 160         X0 = rotr32(X0, 13);
 161 }
 162
 163 #define GOLDEN_RATIO 0x9e3779b9l
 164
 165 static uint32_t gen_w(uint32_t * b, uint8_t i){
 166         uint32_t ret;
 167         ret = b[0] ^ b[3] ^ b[5] ^ b[7] ^ GOLDEN_RATIO ^ (uint32_t)i;
 168         ret = rotl32(ret, 11);
 169         return ret;
 170 }
 171
 172 /* key must be 256bit (32 byte) large! */
 173 void serpent_genctx(void * key, serpent_ctx_t * ctx){
 174         uint32_t buffer[8];
 175         uint8_t i,j;
 176         memcpy(buffer, key, 32);
 177         for(i=0; i<33; ++i){
 178                 for(j=0; j<4; ++j){
 179                         ctx->k[i][j] = gen_w(buffer, i*4+j);
 180                         memmove(buffer, &(buffer[1]), 7*4); /* shift buffer one to the "left" */
 181                         buffer[7] = ctx->k[i][j];
 182                 }
 183         }
 184         for(i=0; i<33; ++i){
 185                 sbox128(ctx->k[i],3-i);
 186         }
 187 }
 188
 189
 190 void serpent_enc(void* buffer, serpent_ctx_t * ctx){
 191         uint8_t i;
 192         for(i=0; i<31; ++i){
 193                 memxor((uint8_t*)buffer, ctx->k[i], 16);
 194                 sbox128(buffer, i);
 195                 lt((uint8_t*)buffer);
 196         }
 197         memxor((uint8_t*)buffer, ctx->k[i], 16);
 198         sbox128(buffer, i);
 199         ++i;
 200         memxor((uint8_t*)buffer, ctx->k[i], 16);
 201 }
 202
 203 void serpent_dec(void* buffer, serpent_ctx_t * ctx){
 204         int8_t i=32;
 205
 206         memxor((uint8_t*)buffer, ctx->k[i], 16);
 207         --i;
 208         inv_sbox128(buffer, i);
 209         memxor((uint8_t*)buffer, ctx->k[i], 16);
 210         --i;
 211         for(; i>=0; --i){
 212                 inv_lt((uint8_t*)buffer);
 213                 inv_sbox128(buffer, i);
 214                 memxor((uint8_t*)buffer, ctx->k[i], 16);
 215         }
 216 }
 217
 218
 219
 220
 221
 222