e173a527971868ba6f64680151f97f99e4a0d319
[libgcrypt.git] / cipher / random.c
1 /* random.c  -  random number generator
2  *      Copyright (C) 1998 Free Software Foundation, Inc.
3  *
4  * This file is part of GNUPG.
5  *
6  * GNUPG is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * GNUPG is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
19  */
20
21
22 /****************
23  * This random number generator is modelled after the one described
24  * in Peter Gutmann's Paper: "Software Generation of Practically
25  * Strong Random Numbers".
26  */
27
28
29 #include <config.h>
30 #include <stdio.h>
31 #include <stdlib.h>
32 #include <assert.h>
33 #include <errno.h>
34 #include <string.h>
35 #include "util.h"
36 #include "rmd.h"
37 #include "ttyio.h"
38 #include "i18n.h"
39 #include "random.h"
40 #include "rand-internal.h"
41 #include "dynload.h"
42
43
44 #if SIZEOF_UNSIGNED_LONG == 8
45   #define ADD_VALUE 0xa5a5a5a5a5a5a5a5
46 #elif SIZEOF_UNSIGNED_LONG == 4
47   #define ADD_VALUE 0xa5a5a5a5
48 #else
49   #error weird size for an unsigned long
50 #endif
51
52 #define BLOCKLEN  64   /* hash this amount of bytes */
53 #define DIGESTLEN 20   /* into a digest of this length (rmd160) */
54 /* poolblocks is the number of digests which make up the pool
55  * and poolsize must be a multiple of the digest length
56  * to make the AND operations faster, the size should also be
57  * a multiple of ulong
58  */
59 #define POOLBLOCKS 30
60 #define POOLSIZE (POOLBLOCKS*DIGESTLEN)
61 #if (POOLSIZE % SIZEOF_UNSIGNED_LONG)
62   #error Please make sure that poolsize is a multiple of ulong
63 #endif
64 #define POOLWORDS (POOLSIZE / SIZEOF_UNSIGNED_LONG)
65
66
67 static int is_initialized;
68 #define MASK_LEVEL(a) do {if( a > 2 ) a = 2; else if( a < 0 ) a = 0; } while(0)
69 static char *rndpool;   /* allocated size is POOLSIZE+BLOCKLEN */
70 static char *keypool;   /* allocated size is POOLSIZE+BLOCKLEN */
71 static size_t pool_readpos;
72 static size_t pool_writepos;
73 static int pool_filled;
74 static int pool_balance;
75 static int just_mixed;
76
77 static int secure_alloc;
78 static int quick_test;
79 static int faked_rng;
80
81
82 static void read_pool( byte *buffer, size_t length, int level );
83 static void add_randomness( const void *buffer, size_t length, int source );
84 static void random_poll(void);
85 static void read_random_source( byte *buffer, size_t length, int level );
86 #ifndef HAVE_DEV_RANDOM
87 static int gather_faked( byte *buffer, size_t *r_length, int level );
88 #endif
89
90
91 static void
92 initialize()
93 {
94     /* The data buffer is allocated somewhat larger, so that
95      * we can use this extra space (which is allocated in secure memory)
96      * as a temporary hash buffer */
97     rndpool = secure_alloc ? m_alloc_secure_clear(POOLSIZE+BLOCKLEN)
98                            : m_alloc_clear(POOLSIZE+BLOCKLEN);
99     keypool = secure_alloc ? m_alloc_secure_clear(POOLSIZE+BLOCKLEN)
100                            : m_alloc_clear(POOLSIZE+BLOCKLEN);
101     is_initialized = 1;
102
103   #if   USE_RNDLINUX
104     rndlinux_constructor();
105   #elif USE_RNDUNIX
106     rndunix_constructor();
107   #elif USE_RNDW32
108     rndw32_constructor();
109   #elif USE_RNDOS2
110     rndos2_constructor();
111   #elif USE_RNDATARI
112     rndatari_constructor();
113   #elif USE_RNDMVS
114     rndmvs_constructor();
115   #endif
116 }
117
118 void
119 secure_random_alloc()
120 {
121     secure_alloc = 1;
122 }
123
124
125 int
126 quick_random_gen( int onoff )
127 {
128     int last;
129
130     read_random_source( NULL, 0, 0 ); /* load module */
131     last = quick_test;
132     if( onoff != -1 )
133         quick_test = onoff;
134     return faked_rng? 1 : last;
135 }
136
137
138 /****************
139  * Fill the buffer with LENGTH bytes of cryptographically strong
140  * random bytes. level 0 is not very strong, 1 is strong enough
141  * for most usage, 2 is good for key generation stuff but may be very slow.
142  */
143 void
144 randomize_buffer( byte *buffer, size_t length, int level )
145 {
146     char *p = get_random_bits( length*8, level, m_is_secure(buffer) );
147     memcpy( buffer, p, length );
148     m_free(p);
149 }
150
151
152
153 /****************
154  * Return a pointer to a randomized buffer of level 0 and LENGTH bits
155  * caller must free the buffer.
156  * Note: The returned value is rounded up to bytes.
157  */
158 byte *
159 get_random_bits( size_t nbits, int level, int secure )
160 {
161     byte *buf;
162     size_t nbytes = (nbits+7)/8;
163
164     if( quick_test && level > 1 )
165         level = 1;
166     MASK_LEVEL(level);
167     buf = secure && secure_alloc ? m_alloc_secure( nbytes ) : m_alloc( nbytes );
168     read_pool( buf, nbytes, level );
169     return buf;
170 }
171
172
173 /****************
174  * Mix the pool
175  */
176 static void
177 mix_pool(byte *pool)
178 {
179     char *hashbuf = pool + POOLSIZE;
180     char *p, *pend;
181     int i, n;
182     RMD160_CONTEXT md;
183
184     rmd160_init( &md );
185  #if DIGESTLEN != 20
186     #error must have a digest length of 20 for ripe-md-160
187  #endif
188     /* loop over the pool */
189     pend = pool + POOLSIZE;
190     memcpy(hashbuf, pend - DIGESTLEN, DIGESTLEN );
191     memcpy(hashbuf+DIGESTLEN, pool, BLOCKLEN-DIGESTLEN);
192     rmd160_mixblock( &md, hashbuf);
193     memcpy(pool, hashbuf, 20 );
194
195     p = pool;
196     for( n=1; n < POOLBLOCKS; n++ ) {
197         memcpy(hashbuf, p, DIGESTLEN );
198
199         p += DIGESTLEN;
200         if( p+DIGESTLEN+BLOCKLEN < pend )
201             memcpy(hashbuf+DIGESTLEN, p+DIGESTLEN, BLOCKLEN-DIGESTLEN);
202         else {
203             char *pp = p+DIGESTLEN;
204             for(i=DIGESTLEN; i < BLOCKLEN; i++ ) {
205                 if( pp >= pend )
206                     pp = pool;
207                 hashbuf[i] = *pp++;
208             }
209         }
210
211         rmd160_mixblock( &md, hashbuf);
212         memcpy(p, hashbuf, 20 );
213     }
214 }
215
216
217 static void
218 read_pool( byte *buffer, size_t length, int level )
219 {
220     int i;
221     ulong *sp, *dp;
222
223     if( length >= POOLSIZE )
224         BUG(); /* not allowed */
225
226     /* for level 2 make sure that there is enough random in the pool */
227     if( level == 2 && pool_balance < length ) {
228         size_t needed;
229         byte *p;
230
231         if( pool_balance < 0 )
232             pool_balance = 0;
233         needed = length - pool_balance;
234         if( needed > POOLSIZE )
235             BUG();
236         p = secure_alloc ? m_alloc_secure( needed ) : m_alloc(needed);
237         read_random_source( p, needed, 2 ); /* read /dev/random */
238         add_randomness( p, needed, 3);
239         m_free(p);
240         pool_balance += needed;
241     }
242
243     /* make sure the pool is filled */
244     while( !pool_filled )
245         random_poll();
246
247     /* do always a fast random poll */
248     fast_random_poll();
249
250     if( !level ) { /* no need for cryptographic strong random */
251         /* create a new pool */
252         for(i=0,dp=(ulong*)keypool, sp=(ulong*)rndpool;
253                                     i < POOLWORDS; i++, dp++, sp++ )
254             *dp = *sp + ADD_VALUE;
255         /* must mix both pools */
256         mix_pool(rndpool);
257         mix_pool(keypool);
258         memcpy( buffer, keypool, length );
259     }
260     else {
261         /* mix the pool (if add_randomness() didn't it) */
262         if( !just_mixed )
263             mix_pool(rndpool);
264         /* create a new pool */
265         for(i=0,dp=(ulong*)keypool, sp=(ulong*)rndpool;
266                                     i < POOLWORDS; i++, dp++, sp++ )
267             *dp = *sp + ADD_VALUE;
268         /* and mix both pools */
269         mix_pool(rndpool);
270         mix_pool(keypool);
271         /* read the required data
272          * we use a readpoiter to read from a different postion each
273          * time */
274         while( length-- ) {
275             *buffer++ = keypool[pool_readpos++];
276             if( pool_readpos >= POOLSIZE )
277                 pool_readpos = 0;
278             pool_balance--;
279         }
280         if( pool_balance < 0 )
281             pool_balance = 0;
282         /* and clear the keypool */
283         memset( keypool, 0, POOLSIZE );
284     }
285 }
286
287
288 /****************
289  * Add LENGTH bytes of randomness from buffer to the pool.
290  * source may be used to specify the randomness source.
291  */
292 static void
293 add_randomness( const void *buffer, size_t length, int source )
294 {
295     if( !is_initialized )
296         initialize();
297     while( length-- ) {
298         rndpool[pool_writepos++] = *((byte*)buffer)++;
299         if( pool_writepos >= POOLSIZE ) {
300             if( source > 1 )
301                 pool_filled = 1;
302             pool_writepos = 0;
303             mix_pool(rndpool);
304             just_mixed = !length;
305         }
306     }
307 }
308
309
310
311 static void
312 random_poll()
313 {
314     char buf[POOLSIZE/5];
315     read_random_source( buf, POOLSIZE/5, 1 );
316     add_randomness( buf, POOLSIZE/5, 2);
317     memset( buf, 0, POOLSIZE/5);
318 }
319
320
321 void
322 fast_random_poll()
323 {
324     static void (*fnc)( void (*)(const void*, size_t, int)) = NULL;
325     static int initialized = 0;
326
327     if( !initialized ) {
328         if( !is_initialized )
329             initialize();
330         initialized = 1;
331         fnc = dynload_getfnc_fast_random_poll();
332         if( !fnc )
333             log_info("Ooops: No fast random poll function\n");
334     }
335     if( fnc )
336         (*fnc)( add_randomness );
337 }
338
339
340
341 static void
342 read_random_source( byte *buffer, size_t length, int level )
343 {
344     static int (*fnc)(byte*, size_t*, int) = NULL;
345     int nbytes;
346     int goodness;
347
348     if( !fnc ) {
349         if( !is_initialized )
350             initialize();
351         fnc = dynload_getfnc_gather_random();
352         if( !fnc ) {
353             faked_rng = 1;
354           #ifndef HAVE_DEV_RANDOM
355             fnc = gather_faked;
356           #else
357             BUG();
358           #endif
359         }
360     }
361     while( length ) {
362         nbytes = length;
363         goodness = (*fnc)( buffer, &nbytes, level );
364         buffer +=nbytes;
365         length -= nbytes;
366         /* FIXME: how can we handle the goodness */
367     }
368 }
369
370
371 #ifndef HAVE_DEV_RANDOM
372 static int
373 gather_faked( byte *buffer, size_t *r_length, int level )
374 {
375     static int initialized=0;
376     size_t length = *r_length;
377
378     if( !initialized ) {
379         log_info(_("WARNING: using insecure random number generator!!\n"));
380         tty_printf(_("The random number generator is only a kludge to let\n"
381                    "it compile - it is in no way a strong RNG!\n\n"
382                    "DON'T USE ANY DATA GENERATED BY THIS PROGRAM!!\n\n"));
383         initialized=1;
384       #ifdef HAVE_RAND
385         srand(make_timestamp()*getpid());
386       #else
387         srandom(make_timestamp()*getpid());
388       #endif
389     }
390
391   #ifdef HAVE_RAND
392     while( length-- )
393         *buffer++ = ((unsigned)(1 + (int) (256.0*rand()/(RAND_MAX+1.0)))-1);
394   #else
395     while( length-- )
396         *buffer++ = ((unsigned)(1 + (int) (256.0*random()/(RAND_MAX+1.0)))-1);
397   #endif
398     return 100; /* We really fake it ;-) */
399 }
400
401 #endif /* ! HAVE_DEV_RANDOM */
402