git.distorted.org.uk Git - u/mdw/catacomb/blob - dsarand.c

   1 /* -*-c-*-
   2  *
   3  * $Id: dsarand.c,v 1.3 2001/02/03 16:08:56 mdw Exp $
   4  *
   5  * Random number generator for DSA
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: dsarand.c,v $
  33  * Revision 1.3  2001/02/03 16:08:56  mdw
  34  * Give generic random objects separate namespaces for their supported misc
  35  * ops.  Add operations for reading the current seed value.
  36  *
  37  * Revision 1.2  2000/06/17 10:54:00  mdw
  38  * Typesetting fixes.  Arena support.
  39  *
  40  * Revision 1.1  1999/12/22 15:53:12  mdw
  41  * Random number generator for finding DSA parameters.
  42  *
  43  */
  44
  45 /*----- Header files ------------------------------------------------------*/
  46
  47 #include <stdarg.h>
  48 #include <string.h>
  49
  50 #include <mLib/alloc.h>
  51 #include <mLib/bits.h>
  52 #include <mLib/sub.h>
  53
  54 #include "dsarand.h"
  55 #include "grand.h"
  56 #include "sha.h"
  57
  58 /*----- Main code ---------------------------------------------------------*/
  59
  60 /* --- @STEP@ --- *
  61  *
  62  * Arguments:   @dsarand *d@ = pointer to context
  63  *
  64  * Use:         Increments the buffer by one, interpreting it as a big-endian
  65  *              integer.  Carries outside the integer are discarded.
  66  */
  67
  68 #define STEP(d) do {                                                    \
  69   dsarand *_d = (d);                                                    \
  70   octet *_p = _d->p;                                                    \
  71   octet *_q = _p + _d->sz;                                              \
  72   unsigned _c = 1;                                                      \
  73   while (_c && _q > _p) {                                               \
  74     _c += *--_q;                                                        \
  75     *_q = U8(_c);                                                       \
  76     _c >>= 8;                                                           \
  77   }                                                                     \
  78 } while (0)
  79
  80 /* --- @dsarand_init@ --- *
  81  *
  82  * Arguments:   @dsarand *d@ = pointer to context
  83  *              @const void *p@ = pointer to seed buffer
  84  *              @size_t sz@ = size of the buffer
  85  *
  86  * Returns:     ---
  87  *
  88  * Use:         Initializes a DSA random number generator.
  89  */
  90
  91 void dsarand_init(dsarand *d, const void *p, size_t sz)
  92 {
  93   d->p = xmalloc(sz);
  94   d->sz = sz;
  95   d->passes = 1;
  96   if (p)
  97     memcpy(d->p, p, sz);
  98 }
  99
 100 /* --- @dsarand_reseed@ --- *
 101  *
 102  * Arguments:   @dsarand *d@ = pointer to context
 103  *              @const void *p@ = pointer to seed buffer
 104  *              @size_t sz@ = size of the buffer
 105  *
 106  * Returns:     ---
 107  *
 108  * Use:         Initializes a DSA random number generator.
 109  */
 110
 111 void dsarand_reseed(dsarand *d, const void *p, size_t sz)
 112 {
 113   xfree(d->p);
 114   d->p = xmalloc(sz);
 115   d->sz = sz;
 116   d->passes = 1;
 117   if (p)
 118     memcpy(d->p, p, sz);
 119 }
 120
 121 /* --- @dsarand_destroy@ --- *
 122  *
 123  * Arguments:   @dsarand *d@ = pointer to context
 124  *
 125  * Returns:     ---
 126  *
 127  * Use:         Disposes of a DSA random number generation context.
 128  */
 129
 130 void dsarand_destroy(dsarand *d)
 131 {
 132   xfree(d->p);
 133 }
 134
 135 /* --- @dsarand_fill@ --- *
 136  *
 137  * Arguments:   @dsarand *d@ = pointer to context
 138  *              @void *p@ = pointer to output buffer
 139  *              @size_t sz@ = size of output buffer
 140  *
 141  * Returns:     ---
 142  *
 143  * Use:         Fills an output buffer with pseudorandom data.
 144  *
 145  *              Let %$p$% be the numerical value of the input buffer, and let
 146  *              %$b$% be the number of bytes required.  Let
 147  *              %$z = \lceil b / 20 \rceil$% be the number of SHA outputs
 148  *              required.  Then the output of pass %$n$% is
 149  *
 150  *                %$P_n = \sum_{0 \le i < z} 2^{160i} SHA(p + nz + i)$%
 151  *                                                      %${} \bmod 2^{8b}$%
 152  *
 153  *              and the actual result in the output buffer is the XOR of all
 154  *              of the output passes.
 155  *
 156  *              The DSA procedure for choosing @q@ involves two passes with
 157  *              %$z = 1$%; the procedure for choosing @p@ involves one pass
 158  *              with larger %$z$%.  This generalization of the DSA generation
 159  *              procedure is my own invention but it seems relatively sound.
 160  */
 161
 162 void dsarand_fill(dsarand *d, void *p, size_t sz)
 163 {
 164   octet *q = p;
 165   unsigned n = d->passes;
 166
 167   /* --- Write out the first pass --- *
 168    *
 169    * This can write directly to the output buffer, so it's done differently
 170    * from the latter passes.
 171    */
 172
 173   {
 174     size_t o = sz;
 175
 176     while (o) {
 177       sha_ctx h;
 178
 179       /* --- Hash the input buffer --- */
 180
 181       sha_init(&h);
 182       sha_hash(&h, d->p, d->sz);
 183
 184       /* --- If enough space, extract the hash output directly --- */
 185
 186       if (o >= SHA_HASHSZ) {
 187         o -= SHA_HASHSZ;
 188         sha_done(&h, q + o);
 189       }
 190
 191       /* --- Otherwise take the hash result out of line and copy it --- */
 192
 193       else {
 194         octet hash[SHA_HASHSZ];
 195         sha_done(&h, hash);
 196         memcpy(q, hash + (SHA_HASHSZ - o), o);
 197         o = 0;
 198       }
 199
 200       /* --- Step the input buffer --- */
 201
 202       STEP(d);
 203     }
 204
 205     /* --- Another pass has been done --- */
 206
 207     n--;
 208   }
 209
 210   /* --- Write out subsequent passes --- *
 211    *
 212    * The hash output has to be done offline, so this is slightly easier.
 213    */
 214
 215   while (n) {
 216     size_t o = sz;
 217
 218     while (o) {
 219       sha_ctx h;
 220       octet hash[SHA_HASHSZ];
 221       size_t n;
 222       octet *pp, *qq;
 223
 224       /* --- Hash the input buffer --- */
 225
 226       sha_init(&h);
 227       sha_hash(&h, d->p, d->sz);
 228       sha_done(&h, hash);
 229
 230       /* --- Work out how much output is wanted --- */
 231
 232       n = SHA_HASHSZ;
 233       if (n > o)
 234         n = o;
 235       o -= n;
 236
 237       /* --- XOR the data out --- */
 238
 239       for (pp = hash + (SHA_HASHSZ - n), qq = q + o;
 240            pp < hash + SHA_HASHSZ; pp++, qq++)
 241         *qq ^= *pp;
 242
 243       /* --- Step the input buffer --- */
 244
 245       STEP(d);
 246     }
 247
 248     /* --- Another pass is done --- */
 249
 250     n--;
 251   }
 252 }
 253
 254 /*----- Generic pseudorandom-number generator interface -------------------*/
 255
 256 static const grand_ops gops;
 257
 258 typedef struct gctx {
 259   grand r;
 260   dsarand d;
 261 } gctx;
 262
 263 static void gdestroy(grand *r)
 264 {
 265   gctx *g = (gctx *)r;
 266   dsarand_destroy(&g->d);
 267   DESTROY(g);
 268 }
 269
 270 static int gmisc(grand *r, unsigned op, ...)
 271 {
 272   gctx *g = (gctx *)r;
 273   va_list ap;
 274   int rc = 0;
 275   va_start(ap, op);
 276
 277   switch (op) {
 278     case GRAND_CHECK:
 279       switch (va_arg(ap, unsigned)) {
 280         case GRAND_CHECK:
 281         case GRAND_SEEDBLOCK:
 282         case GRAND_SEEDRAND:
 283         case DSARAND_PASSES:
 284         case DSARAND_SEEDSZ:
 285         case DSARAND_GETSEED:
 286           rc = 1;
 287           break;
 288         default:
 289           rc = 0;
 290           break;
 291       }
 292       break;
 293     case GRAND_SEEDBLOCK: {
 294       const void *p = va_arg(ap, const void *);
 295       size_t sz = va_arg(ap, size_t);
 296       dsarand_reseed(&g->d, p, sz);
 297     } break;
 298     case GRAND_SEEDRAND: {
 299       grand *rr = va_arg(ap, grand *);
 300       rr->ops->fill(rr, g->d.p, g->d.sz);
 301     } break;
 302     case DSARAND_PASSES:
 303       g->d.passes = va_arg(ap, unsigned);
 304       break;
 305     case DSARAND_SEEDSZ:
 306       rc = g->d.sz;
 307       break;
 308     case DSARAND_GETSEED:
 309       memcpy(va_arg(ap, void *), g->d.p, g->d.sz);
 310       break;
 311     default:
 312       GRAND_BADOP;
 313       break;
 314   }
 315
 316   va_end(ap);
 317   return (rc);
 318 }
 319
 320 static void gfill(grand *r, void *p, size_t sz)
 321 {
 322   gctx *g = (gctx *)r;
 323   dsarand_fill(&g->d, p, sz);
 324 }
 325
 326 static const grand_ops gops = {
 327   "dsarand",
 328   0, 0,
 329   gmisc, gdestroy,
 330   grand_word, grand_byte, grand_word, grand_range, gfill
 331 };
 332
 333 /* --- @dsarand_create@ --- *
 334  *
 335  * Arguments:   @const void *p@ = pointer to seed buffer
 336  *              @size_t sz@ = size of seed buffer
 337  *
 338  * Returns:     Pointer to a generic generator.
 339  *
 340  * Use:         Constructs a generic generator interface over a Catacomb
 341  *              entropy pool generator.
 342  */
 343
 344 grand *dsarand_create(const void *p, size_t sz)
 345 {
 346   gctx *g = CREATE(gctx);
 347   g->r.ops = &gops;
 348   dsarand_init(&g->d, p, sz);
 349   return (&g->r);
 350 }
 351
 352 /*----- That's all, folks -------------------------------------------------*/