sdcc/support/regression/tests/rabbit.c

   1 /*
   2    rabbit.c
   3
   4    While looking up information on the Rabbit processors SDCC targets, I stumbled upon
   5    the (unrelated) Rabbit cipher. For details, see Boesgaard et alii,
   6    "The Rabbit Stream Cipher - Design and Security Analysis".
   7    Cryptography is cool, so let's put it into a regression test!
   8    More seriously: the diffusion design goal of ciphers makes them highly suitable as tests,
   9    since we get high coverage for exposing errors in the generated code,
  10    and the Rabbit cipher is small enough to be suitable for some SDCC targets.
  11    Indeed adding this regression test found issues in the f8 and ds390 ports.
  12
  13    This test is based on the sample implementation from the Rabbit paper. That is not
  14    an implementation optimized for 8-bit devices, but good enough as test case.
  15    Changes were made: the type declarations have been changed to use stdint.h types,
  16    and type punning that assumed little endian has been replaced.
  17    In the paper, the code has a non-free license, but it was later released
  18    to the public domain, text of the message repeated below:
  19
  20    Hi all!
  21
  22    On behalf of Cryptico A/S, the company who designed the Rabbit stream cipher, I'm happy to relay the following:
  23
  24    "Rabbit has been released into the public domain and may be used freely for any purpose."
  25
  26    So in retrospect, I think that it was a good decision not to make patent issues a key criterion for the eStream portfolio: The patent status can change, the algorithmic properties can't.
  27
  28    Best regards
  29
  30    Erik Zenner
  31 */
  32
  33 #include <testfwk.h>
  34
  35 #if !defined(__SDCC_pdk13) && !defined(__SDCC_pdk14) && !defined(__SDCC_pdk15) && !defined(__SDCC_mcs51) // Lack of memory
  36
  37 #ifndef _RABBIT_H
  38 #define _RABBIT_H
  39
  40 #include <stddef.h>
  41
  42 // Type declarations of 32-bit and 8-bit unsigned integers
  43 #if 0
  44 typedef unsigned char rabbit_uint32;
  45 typedef unsigned int rabbit_byte;
  46 #else
  47 #include <stdint.h>
  48 typedef uint32_t rabbit_uint32;
  49 typedef uint8_t rabbit_byte;
  50 static inline rabbit_uint32 rabbit_uint32_from_bytes(const rabbit_byte *p)
  51 {
  52   return ((rabbit_uint32)(p[0])<< 0) | ((rabbit_uint32)(p[1])<< 8) | ((rabbit_uint32)(p[2])<<16) | ((rabbit_uint32)(p[3])<<24);
  53 }
  54 static inline void rabbit_bytes_from_uint32(rabbit_byte *p, rabbit_uint32 u)
  55 {
  56   p[0] = (u>> 0)&0xff;
  57   p[1] = (u>> 8)&0xff;
  58   p[2] = (u>>16)&0xff;
  59   p[3] = (u>>24)&0xff;
  60 }
  61 #endif
  62
  63 // Structure to store the instance data (internal state)
  64 typedef struct
  65 {
  66    rabbit_uint32 x[8];
  67    rabbit_uint32 c[8];
  68    rabbit_uint32 carry;
  69 } rabbit_instance;
  70
  71 // All function calls returns zero on success
  72 int rabbit_key_setup(rabbit_instance *p_instance, const rabbit_byte *p_key, size_t key_size);
  73 int rabbit_iv_setup(const rabbit_instance *p_master_instance,
  74               rabbit_instance *p_instance, const rabbit_byte *p_iv, size_t iv_size);
  75 int rabbit_cipher(rabbit_instance *p_instance, const rabbit_byte *p_src,
  76               rabbit_byte *p_dest, size_t data_size);
  77
  78 #endif
  79
  80 // Left rotation of a 32-bit unsigned integer
  81 static rabbit_uint32 rabbit_rotl(rabbit_uint32 x, int rot)
  82 {
  83    return (x<<rot) | (x>>(32-rot));
  84 }
  85
  86 // Square a 32-bit unsigned integer to obtain the 64-bit result and return
  87 // the 32 high bits XOR the 32 low bits
  88 static rabbit_uint32 rabbit_g_func(rabbit_uint32 x)
  89 {
  90    // Construct high and low argument for squaring
  91    rabbit_uint32 a = x&0xFFFF;
  92    rabbit_uint32 b = x>>16;
  93
  94    // Calculate high and low result of squaring
  95    rabbit_uint32 h = ((((a*a)>>17) + (a*b))>>15) + b*b;
  96    rabbit_uint32 l = x*x;
  97
  98    // Return high XOR low
  99    return h^l;
 100 }
 101
 102 // Calculate the next internal state
 103 static void rabbit_next_state(rabbit_instance *p_instance)
 104 {
 105    // Temporary data
 106    rabbit_uint32 g[8], c_old[8], i;
 107
 108    // Save old counter values
 109    for (i=0; i<8; i++)
 110       c_old[i] = p_instance->c[i];
 111
 112    // Calculate new counter values
 113    p_instance->c[0] += 0x4D34D34D + p_instance->carry;
 114    p_instance->c[1] += 0xD34D34D3 + (p_instance->c[0] < c_old[0]);
 115    p_instance->c[2] += 0x34D34D34 + (p_instance->c[1] < c_old[1]);
 116    p_instance->c[3] += 0x4D34D34D + (p_instance->c[2] < c_old[2]);
 117    p_instance->c[4] += 0xD34D34D3 + (p_instance->c[3] < c_old[3]);
 118    p_instance->c[5] += 0x34D34D34 + (p_instance->c[4] < c_old[4]);
 119    p_instance->c[6] += 0x4D34D34D + (p_instance->c[5] < c_old[5]);
 120    p_instance->c[7] += 0xD34D34D3 + (p_instance->c[6] < c_old[6]);
 121    p_instance->carry = (p_instance->c[7] < c_old[7]);
 122
 123    // Calculate the g-functions
 124    for (i=0;i<8;i++)
 125       g[i] = rabbit_g_func(p_instance->x[i] + p_instance->c[i]);
 126
 127    // Calculate new state values
 128    p_instance->x[0] = g[0] + rabbit_rotl(g[7],16) + rabbit_rotl(g[6], 16);
 129    p_instance->x[1] = g[1] + rabbit_rotl(g[0], 8) + g[7];
 130    p_instance->x[2] = g[2] + rabbit_rotl(g[1],16) + rabbit_rotl(g[0], 16);
 131    p_instance->x[3] = g[3] + rabbit_rotl(g[2], 8) + g[1];
 132    p_instance->x[4] = g[4] + rabbit_rotl(g[3],16) + rabbit_rotl(g[2], 16);
 133    p_instance->x[5] = g[5] + rabbit_rotl(g[4], 8) + g[3];
 134    p_instance->x[6] = g[6] + rabbit_rotl(g[5],16) + rabbit_rotl(g[4], 16);
 135    p_instance->x[7] = g[7] + rabbit_rotl(g[6], 8) + g[5];
 136 }
 137
 138 // Initialize the cipher instance (*p_instance) as function of the key (*p_key)
 139 int rabbit_key_setup(rabbit_instance *p_instance, const rabbit_byte *p_key, size_t key_size)
 140 {
 141    // Temporary data
 142    rabbit_uint32 k0, k1, k2, k3, i;
 143
 144    // Return error if the key size is not 16 bytes
 145    if (key_size != 16)
 146       return -1;
 147
 148    // Generate four subkeys
 149 #if 0
 150    k0 = *(rabbit_uint32*)(p_key+ 0);
 151    k1 = *(rabbit_uint32*)(p_key+ 4);
 152    k2 = *(rabbit_uint32*)(p_key+ 8);
 153    k3 = *(rabbit_uint32*)(p_key+12);
 154 #else
 155    k0 = rabbit_uint32_from_bytes(p_key+ 0);
 156    k1 = rabbit_uint32_from_bytes(p_key+ 4);
 157    k2 = rabbit_uint32_from_bytes(p_key+ 8);
 158    k3 = rabbit_uint32_from_bytes(p_key+12);
 159 #endif
 160
 161    // Generate initial state variables
 162    p_instance->x[0] = k0;
 163    p_instance->x[2] = k1;
 164    p_instance->x[4] = k2;
 165    p_instance->x[6] = k3;
 166    p_instance->x[1] = (k3<<16) | (k2>>16);
 167    p_instance->x[3] = (k0<<16) | (k3>>16);
 168    p_instance->x[5] = (k1<<16) | (k0>>16);
 169    p_instance->x[7] = (k2<<16) | (k1>>16);
 170
 171    // Generate initial counter values
 172    p_instance->c[0] = rabbit_rotl(k2, 16);
 173    p_instance->c[2] = rabbit_rotl(k3, 16);
 174    p_instance->c[4] = rabbit_rotl(k0, 16);
 175    p_instance->c[6] = rabbit_rotl(k1, 16);
 176    p_instance->c[1] = (k0&0xFFFF0000) | (k1&0xFFFF);
 177    p_instance->c[3] = (k1&0xFFFF0000) | (k2&0xFFFF);
 178    p_instance->c[5] = (k2&0xFFFF0000) | (k3&0xFFFF);
 179    p_instance->c[7] = (k3&0xFFFF0000) | (k0&0xFFFF);
 180
 181    // Reset carry bit
 182    p_instance->carry = 0;
 183
 184    // Iterate the system four times
 185    for (i=0; i<4; i++)
 186       rabbit_next_state(p_instance);
 187
 188    // Modify the counters
 189    for (i=0; i<8; i++)
 190       p_instance->c[(i+4)&0x7] ^= p_instance->x[i];
 191
 192    // Return success
 193    return 0;
 194 }
 195
 196 // Initialize the cipher instance (*p_instance) as function of the IV (*p_iv)
 197 // and the master instance (*p_master_instance)
 198 int rabbit_iv_setup(const rabbit_instance *p_master_instance,
 199 rabbit_instance *p_instance, const rabbit_byte *p_iv, size_t iv_size)
 200 {
 201    // Temporary data
 202    rabbit_uint32 i0, i1, i2, i3, i;
 203
 204    // Return error if the IV size is not 8 bytes
 205    if (iv_size != 8)
 206       return -1;
 207
 208    // Generate four subvectors
 209 #if 0
 210    i0 = *(rabbit_uint32*)(p_iv+0);
 211    i2 = *(rabbit_uint32*)(p_iv+4);
 212 #else
 213    i0 = rabbit_uint32_from_bytes(p_iv+0);
 214    i2 = rabbit_uint32_from_bytes(p_iv+4);
 215 #endif
 216    i1 = (i0>>16) | (i2&0xFFFF0000);
 217    i3 = (i2<<16) | (i0&0x0000FFFF);
 218
 219    // Modify counter values
 220    p_instance->c[0] = p_master_instance->c[0] ^ i0;
 221    p_instance->c[1] = p_master_instance->c[1] ^ i1;
 222    p_instance->c[2] = p_master_instance->c[2] ^ i2;
 223    p_instance->c[3] = p_master_instance->c[3] ^ i3;
 224    p_instance->c[4] = p_master_instance->c[4] ^ i0;
 225    p_instance->c[5] = p_master_instance->c[5] ^ i1;
 226    p_instance->c[6] = p_master_instance->c[6] ^ i2;
 227    p_instance->c[7] = p_master_instance->c[7] ^ i3;
 228
 229    // Copy internal state values
 230    for (i=0; i<8; i++)
 231       p_instance->x[i] = p_master_instance->x[i];
 232    p_instance->carry = p_master_instance->carry;
 233
 234    // Iterate the system four times
 235    for (i=0; i<4; i++)
 236       rabbit_next_state(p_instance);
 237
 238    // Return success
 239    return 0;
 240 }
 241
 242 // Encrypt or decrypt a block of data
 243 int rabbit_cipher(rabbit_instance *p_instance, const rabbit_byte *p_src,
 244 rabbit_byte *p_dest, size_t data_size)
 245 {
 246    // Temporary data
 247    rabbit_uint32 i;
 248
 249    // Return error if the size of the data to encrypt is
 250    // not a multiple of 16
 251    if (data_size%16)
 252       return -1;
 253
 254    for (i=0; i<data_size; i+=16)
 255    {
 256       // Iterate the system
 257       rabbit_next_state(p_instance);
 258
 259       // Encrypt 16 bytes of data
 260 #if 0
 261       *(rabbit_uint32*)(p_dest+ 0) = *(rabbit_uint32*)(p_src+ 0) ^ p_instance->x[0] ^
 262                              (p_instance->x[5]>>16) ^ (p_instance->x[3]<<16);
 263       *(rabbit_uint32*)(p_dest+ 4) = *(rabbit_uint32*)(p_src+ 4) ^ p_instance->x[2] ^
 264                              (p_instance->x[7]>>16) ^ (p_instance->x[5]<<16);
 265       *(rabbit_uint32*)(p_dest+ 8) = *(rabbit_uint32*)(p_src+ 8) ^ p_instance->x[4] ^
 266                              (p_instance->x[1]>>16) ^ (p_instance->x[7]<<16);
 267       *(rabbit_uint32*)(p_dest+12) = *(rabbit_uint32*)(p_src+12) ^ p_instance->x[6] ^
 268                              (p_instance->x[3]>>16) ^ (p_instance->x[1]<<16);
 269 #else
 270       rabbit_bytes_from_uint32(p_dest+ 0, rabbit_uint32_from_bytes(p_src+ 0) ^ p_instance->x[0] ^
 271                              (p_instance->x[5]>>16) ^ (p_instance->x[3]<<16));
 272       rabbit_bytes_from_uint32(p_dest+ 4, rabbit_uint32_from_bytes(p_src+ 4) ^ p_instance->x[2] ^
 273                              (p_instance->x[7]>>16) ^ (p_instance->x[5]<<16));
 274       rabbit_bytes_from_uint32(p_dest+ 8, rabbit_uint32_from_bytes(p_src+ 8) ^ p_instance->x[4] ^
 275                              (p_instance->x[1]>>16) ^ (p_instance->x[7]<<16));
 276       rabbit_bytes_from_uint32(p_dest+12, rabbit_uint32_from_bytes(p_src+12) ^ p_instance->x[6] ^
 277                              (p_instance->x[3]>>16) ^ (p_instance->x[1]<<16));
 278 #endif
 279
 280       // Increment pointers to source and destination data
 281       p_src += 16;
 282       p_dest += 16;
 283    }
 284
 285    // Return success
 286    return 0;
 287 }
 288
 289 #include <string.h>
 290
 291 /* To simplify this, we just encrypt zero data with a zero key and initalization vector.
 292    Which is not as bad as it looks at first sight: the decryption routine is the same as
 293    the encrpytion, so it does get tested with nonzero data input during decryption. And
 294    when using an initialization vector, the actual key is derived from it, so we also test
 295    with a nonzero key. */
 296
 297 const rabbit_byte zero[384/8];
 298 const rabbit_byte s[384/8] = {0x02, 0xF7, 0x4A, 0x1C, 0x26, 0x45, 0x6B, 0xF5, 0xEC, 0xD6, 0xA5, 0x36, 0xF0, 0x54, 0x57, 0xB1,
 299                               0xA7, 0x8A, 0xC6, 0x89, 0x47, 0x6C, 0x69, 0x7B, 0x39, 0x0C, 0x9C, 0xC5, 0x15, 0xD8, 0xE8, 0x88,
 300                               0x96, 0xD6, 0x73, 0x16, 0x88, 0xD1, 0x68, 0xDA, 0x51, 0xD4, 0x0C, 0x70, 0xC3, 0xA1, 0x16, 0xF4};
 301 const rabbit_byte i[384/8] = {0xED, 0xB7, 0x05, 0x67, 0x37, 0x5D, 0xCD, 0x7C, 0xD8, 0x95, 0x54, 0xF8, 0x5E, 0x27, 0xA7, 0xC6,
 302                               0x8D, 0x4A, 0xDC, 0x70, 0x32, 0x29, 0x8F, 0x7B, 0xD4, 0xEF, 0xF5, 0x04, 0xAC, 0xA6, 0x29, 0x5F,
 303                               0x66, 0x8F, 0xBF, 0x47, 0x8A, 0xDB, 0x2B, 0xE5, 0x1E, 0x6C, 0xDE, 0x29, 0x2B, 0x82, 0xDE, 0x2A};
 304 rabbit_byte buffer[384/8];
 305 rabbit_instance instance;
 306
 307 #endif
 308
 309 void testRabbit(void)
 310 {
 311 #if !defined(__SDCC_pdk13) && !defined(__SDCC_pdk14) && !defined(__SDCC_pdk15) && !defined(__SDCC_mcs51) // Lack of memory
 312    // Test without IV
 313    ASSERT(!rabbit_key_setup(&instance, zero, 128/8));
 314    ASSERT(!rabbit_cipher(&instance, zero, buffer, 384/8));
 315 #if !defined(__SDCC_f8) && !defined(__SDCC_ds390) // bug
 316    ASSERT(!memcmp(s, buffer, 384/8));
 317 #endif
 318    ASSERT(!rabbit_key_setup(&instance, zero, 128/8));
 319    ASSERT(!rabbit_cipher(&instance, buffer, buffer, 384/8));
 320    ASSERT(!memcmp(zero, buffer, 384/8));
 321
 322    // Test with IV
 323    ASSERT(!rabbit_key_setup(&instance, zero, 128/8));
 324    ASSERT(!rabbit_iv_setup(&instance, &instance, zero, 64/8));
 325    ASSERT(!rabbit_cipher(&instance, zero, buffer, 384/8));
 326 #if !defined(__SDCC_f8) && !defined(__SDCC_ds390) // bug
 327    ASSERT(!memcmp(i, buffer, 384/8));
 328 #endif
 329    ASSERT(!rabbit_key_setup(&instance, zero, 128/8));
 330    ASSERT(!rabbit_iv_setup(&instance, &instance, zero, 64/8));
 331    ASSERT(!rabbit_cipher(&instance, buffer, buffer, 384/8));
 332    ASSERT(!memcmp(zero, buffer, 384/8));
 333 #endif
 334 }
 335