← Back to branch summary

~ubuntu-branches/ubuntu/utopic/dropbear/utopic-proposed

« back to all changes in this revision

Viewing changes to libtomcrypt/src/prngs/sober128.c

  • Committer: Bazaar Package Importer
  • Author(s): Matt Johnston
  • Date: 2005-12-08 19:20:21 UTC
  • mfrom: (1.2.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20051208192021-nyp9rwnt77nsg6ty
Tags: 0.47-1
* New upstream release.
* SECURITY: Fix incorrect buffer sizing.

Show diffs side-by-side

added added

removed removed

Lines of Context:
libtomcrypt/src/prngs/sober128.c
 
1
/* LibTomCrypt, modular cryptographic library -- Tom St Denis
 
2
 *
 
3
 * LibTomCrypt is a library that provides various cryptographic
 
4
 * algorithms in a highly modular and flexible manner.
 
5
 *
 
6
 * The library is free for all purposes without any express
 
7
 * guarantee it works.
 
8
 *
 
9
 * Tom St Denis, tomstdenis@gmail.com, http://libtomcrypt.org
 
10
 */
 
11
#include "tomcrypt.h"
 
12
 
 
13
/**
 
14
 @file sober128.c
 
15
 Implementation of SOBER-128 by Tom St Denis.
 
16
 Based on s128fast.c reference code supplied by Greg Rose of QUALCOMM.
 
17
*/
 
18
 
 
19
#ifdef SOBER128
 
20
 
 
21
#include "sober128tab.c"
 
22
 
 
23
const struct ltc_prng_descriptor sober128_desc = 
 
24
{
 
25
   "sober128", 64,
 
26
    &sober128_start,
 
27
    &sober128_add_entropy,
 
28
    &sober128_ready,
 
29
    &sober128_read,
 
30
    &sober128_done,
 
31
    &sober128_export,
 
32
    &sober128_import,
 
33
    &sober128_test
 
34
};
 
35
 
 
36
/* don't change these... */
 
37
#define N                        17
 
38
#define FOLD                      N /* how many iterations of folding to do */
 
39
#define INITKONST        0x6996c53a /* value of KONST to use during key loading */
 
40
#define KEYP                     15 /* where to insert key words */
 
41
#define FOLDP                     4 /* where to insert non-linear feedback */
 
42
 
 
43
#define B(x,i) ((unsigned char)(((x) >> (8*i)) & 0xFF))
 
44
 
 
45
static ulong32 BYTE2WORD(unsigned char *b)
 
46
{
 
47
   ulong32 t;
 
48
   LOAD32L(t, b);
 
49
   return t;
 
50
}
 
51
 
 
52
#define WORD2BYTE(w, b) STORE32L(b, w)
 
53
 
 
54
static void XORWORD(ulong32 w, unsigned char *b)
 
55
{
 
56
   ulong32 t;
 
57
   LOAD32L(t, b);
 
58
   t ^= w;
 
59
   STORE32L(t, b);
 
60
}
 
61
 
 
62
/* give correct offset for the current position of the register,
 
63
 * where logically R[0] is at position "zero".
 
64
 */
 
65
#define OFF(zero, i) (((zero)+(i)) % N)
 
66
 
 
67
/* step the LFSR */
 
68
/* After stepping, "zero" moves right one place */
 
69
#define STEP(R,z) \
 
70
    R[OFF(z,0)] = R[OFF(z,15)] ^ R[OFF(z,4)] ^ (R[OFF(z,0)] << 8) ^ Multab[(R[OFF(z,0)] >> 24) & 0xFF];
 
71
 
 
72
static void cycle(ulong32 *R)
 
73
{
 
74
    ulong32 t;
 
75
    int     i;
 
76
 
 
77
    STEP(R,0);
 
78
    t = R[0];
 
79
    for (i = 1; i < N; ++i) {
 
80
        R[i-1] = R[i];
 
81
    }
 
82
    R[N-1] = t;
 
83
}
 
84
 
 
85
/* Return a non-linear function of some parts of the register.
 
86
 */
 
87
#define NLFUNC(c,z) \
 
88
{ \
 
89
    t = c->R[OFF(z,0)] + c->R[OFF(z,16)]; \
 
90
    t ^= Sbox[(t >> 24) & 0xFF]; \
 
91
    t = RORc(t, 8); \
 
92
    t = ((t + c->R[OFF(z,1)]) ^ c->konst) + c->R[OFF(z,6)]; \
 
93
    t ^= Sbox[(t >> 24) & 0xFF]; \
 
94
    t = t + c->R[OFF(z,13)]; \
 
95
}
 
96
 
 
97
static ulong32 nltap(struct sober128_prng *c)
 
98
{
 
99
    ulong32 t;
 
100
    NLFUNC(c, 0);
 
101
    return t;
 
102
}
 
103
 
 
104
/**
 
105
  Start the PRNG
 
106
  @param prng     [out] The PRNG state to initialize
 
107
  @return CRYPT_OK if successful
 
108
*/  
 
109
int sober128_start(prng_state *prng)
 
110
{
 
111
    int                   i;
 
112
    struct sober128_prng *c;
 
113
 
 
114
    LTC_ARGCHK(prng != NULL);
 
115
 
 
116
    c = &(prng->sober128);
 
117
    
 
118
    /* Register initialised to Fibonacci numbers */
 
119
    c->R[0] = 1;
 
120
    c->R[1] = 1;
 
121
    for (i = 2; i < N; ++i) {
 
122
       c->R[i] = c->R[i-1] + c->R[i-2];
 
123
    }
 
124
    c->konst = INITKONST;
 
125
 
 
126
    /* next add_entropy will be the key */
 
127
    c->flag  = 1;
 
128
    c->set   = 0;
 
129
 
 
130
    return CRYPT_OK;
 
131
}
 
132
 
 
133
/* Save the current register state
 
134
 */
 
135
static void s128_savestate(struct sober128_prng *c)
 
136
{
 
137
    int i;
 
138
    for (i = 0; i < N; ++i) {
 
139
        c->initR[i] = c->R[i];
 
140
    }
 
141
}
 
142
 
 
143
/* initialise to previously saved register state
 
144
 */
 
145
static void s128_reloadstate(struct sober128_prng *c)
 
146
{
 
147
    int i;
 
148
 
 
149
    for (i = 0; i < N; ++i) {
 
150
        c->R[i] = c->initR[i];
 
151
    }
 
152
}
 
153
 
 
154
/* Initialise "konst"
 
155
 */
 
156
static void s128_genkonst(struct sober128_prng *c)
 
157
{
 
158
    ulong32 newkonst;
 
159
 
 
160
    do {
 
161
       cycle(c->R);
 
162
       newkonst = nltap(c);
 
163
    } while ((newkonst & 0xFF000000) == 0);
 
164
    c->konst = newkonst;
 
165
}
 
166
 
 
167
/* Load key material into the register
 
168
 */
 
169
#define ADDKEY(k) \
 
170
   c->R[KEYP] += (k);
 
171
 
 
172
#define XORNL(nl) \
 
173
   c->R[FOLDP] ^= (nl);
 
174
 
 
175
/* nonlinear diffusion of register for key */
 
176
#define DROUND(z) STEP(c->R,z); NLFUNC(c,(z+1)); c->R[OFF((z+1),FOLDP)] ^= t; 
 
177
static void s128_diffuse(struct sober128_prng *c)
 
178
{
 
179
    ulong32 t;
 
180
    /* relies on FOLD == N == 17! */
 
181
    DROUND(0);
 
182
    DROUND(1);
 
183
    DROUND(2);
 
184
    DROUND(3);
 
185
    DROUND(4);
 
186
    DROUND(5);
 
187
    DROUND(6);
 
188
    DROUND(7);
 
189
    DROUND(8);
 
190
    DROUND(9);
 
191
    DROUND(10);
 
192
    DROUND(11);
 
193
    DROUND(12);
 
194
    DROUND(13);
 
195
    DROUND(14);
 
196
    DROUND(15);
 
197
    DROUND(16);
 
198
}
 
199
 
 
200
/**
 
201
  Add entropy to the PRNG state
 
202
  @param in       The data to add
 
203
  @param inlen    Length of the data to add
 
204
  @param prng     PRNG state to update
 
205
  @return CRYPT_OK if successful
 
206
*/  
 
207
int sober128_add_entropy(const unsigned char *in, unsigned long inlen, prng_state *prng)
 
208
{
 
209
    struct sober128_prng *c;
 
210
    ulong32               i, k;
 
211
 
 
212
    LTC_ARGCHK(in != NULL);
 
213
    LTC_ARGCHK(prng != NULL);
 
214
    c = &(prng->sober128);
 
215
 
 
216
    if (c->flag == 1) {
 
217
       /* this is the first call to the add_entropy so this input is the key */
 
218
       /* inlen must be multiple of 4 bytes */
 
219
       if ((inlen & 3) != 0) {
 
220
          return CRYPT_INVALID_KEYSIZE;
 
221
       }
 
222
    
 
223
       for (i = 0; i < inlen; i += 4) {
 
224
           k = BYTE2WORD((unsigned char *)&in[i]);
 
225
          ADDKEY(k);
 
226
          cycle(c->R);
 
227
          XORNL(nltap(c));
 
228
       }
 
229
 
 
230
       /* also fold in the length of the key */
 
231
       ADDKEY(inlen);
 
232
 
 
233
       /* now diffuse */
 
234
       s128_diffuse(c);
 
235
 
 
236
       s128_genkonst(c);
 
237
       s128_savestate(c);
 
238
       c->nbuf = 0;
 
239
       c->flag = 0;       
 
240
       c->set  = 1;
 
241
    } else {
 
242
       /* ok we are adding an IV then... */
 
243
       s128_reloadstate(c);
 
244
 
 
245
       /* inlen must be multiple of 4 bytes */
 
246
       if ((inlen & 3) != 0) {
 
247
          return CRYPT_INVALID_KEYSIZE;
 
248
       }
 
249
    
 
250
       for (i = 0; i < inlen; i += 4) {
 
251
           k = BYTE2WORD((unsigned char *)&in[i]);
 
252
          ADDKEY(k);
 
253
          cycle(c->R);
 
254
          XORNL(nltap(c));
 
255
       }
 
256
 
 
257
       /* also fold in the length of the key */
 
258
       ADDKEY(inlen);
 
259
 
 
260
       /* now diffuse */
 
261
       s128_diffuse(c);
 
262
       c->nbuf = 0;
 
263
    }
 
264
 
 
265
    return CRYPT_OK;
 
266
}
 
267
 
 
268
/**
 
269
  Make the PRNG ready to read from
 
270
  @param prng   The PRNG to make active
 
271
  @return CRYPT_OK if successful
 
272
*/  
 
273
int sober128_ready(prng_state *prng)
 
274
{
 
275
   return prng->sober128.set == 1 ? CRYPT_OK : CRYPT_ERROR;
 
276
}
 
277
 
 
278
/* XOR pseudo-random bytes into buffer
 
279
 */
 
280
#define SROUND(z) STEP(c->R,z); NLFUNC(c,(z+1)); XORWORD(t, out+(z*4));
 
281
 
 
282
/**
 
283
  Read from the PRNG
 
284
  @param out      Destination
 
285
  @param outlen   Length of output
 
286
  @param prng     The active PRNG to read from
 
287
  @return Number of octets read
 
288
*/  
 
289
unsigned long sober128_read(unsigned char *out, unsigned long outlen, prng_state *prng)
 
290
{
 
291
   struct sober128_prng *c;
 
292
   ulong32               t, tlen;
 
293
 
 
294
   LTC_ARGCHK(out  != NULL);
 
295
   LTC_ARGCHK(prng != NULL);
 
296
 
 
297
   c = &(prng->sober128);
 
298
   t = 0;
 
299
   tlen = outlen;
 
300
   
 
301
   /* handle any previously buffered bytes */
 
302
   while (c->nbuf != 0 && outlen != 0) {
 
303
      *out++ ^= c->sbuf & 0xFF;
 
304
       c->sbuf >>= 8;
 
305
       c->nbuf -= 8;
 
306
       --outlen;
 
307
   }
 
308
 
 
309
#ifndef LTC_SMALL_CODE
 
310
    /* do lots at a time, if there's enough to do */
 
311
    while (outlen >= N*4) {
 
312
      SROUND(0);
 
313
      SROUND(1);
 
314
      SROUND(2);
 
315
      SROUND(3);
 
316
      SROUND(4);
 
317
      SROUND(5);
 
318
      SROUND(6);
 
319
      SROUND(7);
 
320
      SROUND(8);
 
321
      SROUND(9);
 
322
      SROUND(10);
 
323
      SROUND(11);
 
324
      SROUND(12);
 
325
      SROUND(13);
 
326
      SROUND(14);
 
327
      SROUND(15);
 
328
      SROUND(16);
 
329
      out    += 4*N;
 
330
      outlen -= 4*N;
 
331
    }
 
332
#endif
 
333
 
 
334
    /* do small or odd size buffers the slow way */
 
335
    while (4 <= outlen) {
 
336
      cycle(c->R);
 
337
      t = nltap(c);
 
338
      XORWORD(t, out);
 
339
      out    += 4;
 
340
      outlen -= 4;
 
341
    }
 
342
 
 
343
    /* handle any trailing bytes */
 
344
    if (outlen != 0) {
 
345
      cycle(c->R);
 
346
      c->sbuf = nltap(c);
 
347
      c->nbuf = 32;
 
348
      while (c->nbuf != 0 && outlen != 0) {
 
349
          *out++ ^= c->sbuf & 0xFF;
 
350
          c->sbuf >>= 8;
 
351
          c->nbuf -= 8;
 
352
          --outlen;
 
353
      }
 
354
    }
 
355
 
 
356
    return tlen;
 
357
}
 
358
 
 
359
/**
 
360
  Terminate the PRNG
 
361
  @param prng   The PRNG to terminate
 
362
  @return CRYPT_OK if successful
 
363
*/  
 
364
int sober128_done(prng_state *prng)
 
365
{
 
366
   LTC_ARGCHK(prng != NULL);
 
367
   return CRYPT_OK;
 
368
}
 
369
 
 
370
/**
 
371
  Export the PRNG state
 
372
  @param out       [out] Destination
 
373
  @param outlen    [in/out] Max size and resulting size of the state
 
374
  @param prng      The PRNG to export
 
375
  @return CRYPT_OK if successful
 
376
*/  
 
377
int sober128_export(unsigned char *out, unsigned long *outlen, prng_state *prng)
 
378
{
 
379
   LTC_ARGCHK(outlen != NULL);
 
380
   LTC_ARGCHK(out    != NULL);
 
381
   LTC_ARGCHK(prng   != NULL);
 
382
 
 
383
   if (*outlen < 64) {
 
384
      return CRYPT_BUFFER_OVERFLOW;
 
385
   }
 
386
 
 
387
   if (sober128_read(out, 64, prng) != 64) {
 
388
      return CRYPT_ERROR_READPRNG;
 
389
   }
 
390
   *outlen = 64;
 
391
 
 
392
   return CRYPT_OK;
 
393
}
 
394
 
 
395
/**
 
396
  Import a PRNG state
 
397
  @param in       The PRNG state
 
398
  @param inlen    Size of the state
 
399
  @param prng     The PRNG to import
 
400
  @return CRYPT_OK if successful
 
401
*/  
 
402
int sober128_import(const unsigned char *in, unsigned long inlen, prng_state *prng)
 
403
{
 
404
   int err;
 
405
   LTC_ARGCHK(in   != NULL);
 
406
   LTC_ARGCHK(prng != NULL);
 
407
 
 
408
   if (inlen != 64) {
 
409
      return CRYPT_INVALID_ARG;
 
410
   }
 
411
   
 
412
   if ((err = sober128_start(prng)) != CRYPT_OK) {
 
413
      return err;
 
414
   }
 
415
   if ((err = sober128_add_entropy(in, 64, prng)) != CRYPT_OK) {
 
416
      return err;
 
417
   }
 
418
   return sober128_ready(prng);
 
419
}
 
420
 
 
421
/**
 
422
  PRNG self-test
 
423
  @return CRYPT_OK if successful, CRYPT_NOP if self-testing has been disabled
 
424
*/  
 
425
int sober128_test(void)
 
426
{
 
427
#ifndef LTC_TEST
 
428
   return CRYPT_NOP;
 
429
#else
 
430
   static const struct { 
 
431
     int keylen, ivlen, len;
 
432
     unsigned char key[16], iv[4], out[20];
 
433
   } tests[] = {
 
434
 
 
435
{
 
436
   16, 4, 20,
 
437
 
 
438
   /* key */
 
439
   { 't', 'e', 's', 't', ' ', 'k', 'e', 'y', 
 
440
     ' ', '1', '2', '8', 'b', 'i', 't', 's' },
 
441
 
 
442
   /* IV */
 
443
   { 0x00, 0x00, 0x00, 0x0 },
 
444
 
 
445
   /* expected output */
 
446
   { 0x43, 0x50, 0x0c, 0xcf, 0x89, 0x91, 0x9f, 0x1d,
 
447
     0xaa, 0x37, 0x74, 0x95, 0xf4, 0xb4, 0x58, 0xc2, 
 
448
     0x40, 0x37, 0x8b, 0xbb }
 
449
}
 
450
 
 
451
};
 
452
   prng_state    prng;
 
453
   unsigned char dst[20];
 
454
   int           err, x;
 
455
 
 
456
   for (x = 0; x < (int)(sizeof(tests)/sizeof(tests[0])); x++) {
 
457
       if ((err = sober128_start(&prng)) != CRYPT_OK) {
 
458
          return err;
 
459
       }
 
460
       if ((err = sober128_add_entropy(tests[x].key, tests[x].keylen, &prng)) != CRYPT_OK) {
 
461
          return err;
 
462
       }
 
463
       /* add IV */
 
464
       if ((err = sober128_add_entropy(tests[x].iv, tests[x].ivlen, &prng)) != CRYPT_OK) {
 
465
          return err;
 
466
       }
 
467
 
 
468
       /* ready up */
 
469
       if ((err = sober128_ready(&prng)) != CRYPT_OK) {
 
470
          return err;
 
471
       }
 
472
       memset(dst, 0, tests[x].len);
 
473
       if (sober128_read(dst, tests[x].len, &prng) != (unsigned long)tests[x].len) {
 
474
          return CRYPT_ERROR_READPRNG;
 
475
       }
 
476
       sober128_done(&prng);
 
477
       if (memcmp(dst, tests[x].out, tests[x].len)) {
 
478
#if 0
 
479
          printf("\n\nSOBER128 failed, I got:\n"); 
 
480
          for (y = 0; y < tests[x].len; y++) printf("%02x ", dst[y]);
 
481
          printf("\n");
 
482
#endif
 
483
          return CRYPT_FAIL_TESTVECTOR;
 
484
       }
 
485
   }
 
486
   return CRYPT_OK;
 
487
#endif
 
488
}
 
489
 
 
490
#endif
 
491
 
 
492
 
 
493
/* $Source: /cvs/libtom/libtomcrypt/src/prngs/sober128.c,v $ */
 
494
/* $Revision: 1.3 $ */
 
495
/* $Date: 2005/05/05 14:35:59 $ */