025f20ecb27b7853e014b3ef9663ba81dff3e9a5
[gnupg.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  * How it works:
24  *
25  * See Peter Gutmann's Paper: "Software Generation of Practically
26  * Strong Random Numbers"
27  *
28  * fixme!
29  */
30
31
32 #include <config.h>
33 #include <stdio.h>
34 #include <stdlib.h>
35 #include <assert.h>
36 #include <errno.h>
37 #include <sys/time.h>
38 #include <sys/types.h>
39 #include <sys/stat.h>
40 #ifndef HAVE_GETTIMEOFTIME
41   #include <sys/times.h>
42 #endif
43 #ifdef HAVE_GETRUSAGE
44   #include <sys/resource.h>
45 #endif
46 #include <string.h>
47 #include <unistd.h>
48 #include <fcntl.h>
49 #include "util.h"
50 #include "random.h"
51 #include "rmd.h"
52 #include "ttyio.h"
53 #include "i18n.h"
54
55
56 #define BLOCKLEN  64   /* hash this amount of bytes */
57 #define DIGESTLEN 20   /* into a digest of this length (rmd160) */
58 /* poolblocks is the number of digests which make up the pool
59  * and poolsize must be a multiple of the digest length
60  * to make the AND operations faster, the size should also be
61  * a multiple of ulong
62  */
63 #define POOLBLOCKS 30
64 #define POOLSIZE (POOLBLOCKS*DIGESTLEN)
65 #if (POOLSIZE % SIZEOF_UNSIGNED_LONG)
66   #error Please make sure that poolsize is a multiple of ulong
67 #endif
68 #define POOLWORDS (POOLSIZE / SIZEOF_UNSIGNED_LONG)
69 #if SIZEOF_UNSIGNED_LONG == 8
70   #define ADD_VALUE 0xa5a5a5a5a5a5a5a5
71 #elif SIZEOF_UNSIGNED_LONG == 4
72   #define ADD_VALUE 0xa5a5a5a5
73 #else
74   #error weird size for an unsigned long
75 #endif
76
77 struct cache {
78     int len;
79     int size;
80     byte *buffer;
81 };
82
83
84 static int is_initialized;
85 static struct cache cache[3];
86 #define MASK_LEVEL(a) do {if( a > 2 ) a = 2; else if( a < 0 ) a = 0; } while(0)
87 static char *rndpool;   /* allocated size is POOLSIZE+BLOCKLEN */
88 static char *keypool;   /* allocated size is POOLSIZE+BLOCKLEN */
89 static size_t pool_readpos;
90 static size_t pool_writepos;
91 static int pool_filled;
92 static int pool_balance;
93 static int just_mixed;
94
95 static int secure_alloc;
96 static int quick_test;
97
98
99
100 static void read_pool( byte *buffer, size_t length, int level );
101 static void read_dev_random( byte *buffer, size_t length, int level );
102
103
104 static void
105 initialize()
106 {
107     /* The data buffer is allocated somewhat larger, so that
108      * we can use this extra space (which is allocated in secure memory)
109      * as a temporary hash buffer */
110     rndpool = secure_alloc ? m_alloc_secure_clear(POOLSIZE+BLOCKLEN)
111                            : m_alloc_clear(POOLSIZE+BLOCKLEN);
112     keypool = secure_alloc ? m_alloc_secure_clear(POOLSIZE+BLOCKLEN)
113                            : m_alloc_clear(POOLSIZE+BLOCKLEN);
114     is_initialized = 1;
115 }
116
117 void
118 secure_random_alloc()
119 {
120     secure_alloc = 1;
121 }
122
123 int
124 quick_random_gen( int onoff )
125 {
126     int last = quick_test;
127     if( onoff != -1 )
128         quick_test = onoff;
129   #ifndef HAVE_DEV_RANDOM
130     last = 1; /* insecure RNG */
131   #endif
132     return last;
133 }
134
135
136 /****************
137  * Fill the buffer with LENGTH bytes of cryptologic strong
138  * random bytes. level 0 is not very strong, 1 is strong enough
139  * for most usage, 2 is good for key generation stuff but may be very slow.
140  */
141 void
142 randomize_buffer( byte *buffer, size_t length, int level )
143 {
144     for( ; length; length-- )
145         *buffer++ = get_random_byte(level);
146 }
147
148
149 byte
150 get_random_byte( int level )
151 {
152     MASK_LEVEL(level);
153     if( !cache[level].len ) {
154         if( !is_initialized )
155             initialize();
156         if( !cache[level].buffer ) {
157             cache[level].size = 100;
158             cache[level].buffer = level && secure_alloc?
159                                          m_alloc_secure( cache[level].size )
160                                        : m_alloc( cache[level].size );
161         }
162         read_pool(cache[level].buffer, cache[level].size, level );
163         cache[level].len = cache[level].size;
164     }
165
166     return cache[level].buffer[--cache[level].len];
167 }
168
169
170
171 /****************
172  * Return a pointer to a randomized buffer of level 0 and LENGTH bits
173  * caller must free the buffer. This function does not use the
174  * cache (will be removed in future). Note: The returned value is
175  * rounded up to bytes.
176  */
177 byte *
178 get_random_bits( size_t nbits, int level, int secure )
179 {
180     byte *buf;
181     size_t nbytes = (nbits+7)/8;
182
183     MASK_LEVEL(level);
184     buf = secure? m_alloc_secure( nbytes ) : m_alloc( nbytes );
185     read_pool( buf, nbytes, level );
186     return buf;
187 }
188
189
190 /****************
191  * Mix the pool
192  */
193 static void
194 mix_pool(byte *pool)
195 {
196     char *hashbuf = pool + POOLSIZE;
197     char *p, *pend;
198     int i, n;
199     RMD160_CONTEXT md;
200
201     rmd160_init( &md );
202  #if DIGESTLEN != 20
203     #error must have a digest length of 20 for ripe-md-160
204  #endif
205     /* loop over the pool */
206     pend = pool + POOLSIZE;
207     memcpy(hashbuf, pend - DIGESTLEN, DIGESTLEN );
208     memcpy(hashbuf+DIGESTLEN, pool, BLOCKLEN-DIGESTLEN);
209     rmd160_mixblock( &md, hashbuf);
210     memcpy(pool, hashbuf, 20 );
211
212     p = pool;
213     for( n=1; n < POOLBLOCKS; n++ ) {
214         memcpy(hashbuf, p, DIGESTLEN );
215
216         p += DIGESTLEN;
217         if( p+DIGESTLEN+BLOCKLEN < pend )
218             memcpy(hashbuf+DIGESTLEN, p+DIGESTLEN, BLOCKLEN-DIGESTLEN);
219         else {
220             char *pp = p+DIGESTLEN;
221             for(i=DIGESTLEN; i < BLOCKLEN; i++ ) {
222                 if( pp >= pend )
223                     pp = pool;
224                 hashbuf[i] = *pp++;
225             }
226         }
227
228         rmd160_mixblock( &md, hashbuf);
229         memcpy(p, hashbuf, 20 );
230     }
231 }
232
233
234 static void
235 read_pool( byte *buffer, size_t length, int level )
236 {
237     int i;
238     ulong *sp, *dp;
239
240     if( length >= POOLSIZE )
241         BUG(); /* not allowed */
242     if( !level ) { /* read simple random bytes */
243         read_dev_random( buffer, length, level );
244         return;
245     }
246
247     /* for level 2 make sure that there is enough random in the pool */
248     if( level == 2 && pool_balance < length ) {
249         size_t needed;
250         byte *p;
251
252         if( pool_balance < 0 )
253             pool_balance = 0;
254         needed = length - pool_balance;
255         if( needed > POOLSIZE )
256             BUG();
257         p = m_alloc_secure( needed );
258         read_dev_random( p, needed, 2 ); /* read /dev/random */
259         add_randomness( p, needed, 3);
260         m_free(p);
261         pool_balance += needed;
262     }
263
264     /* make sure the pool is filled */
265     while( !pool_filled )
266         random_poll();
267     /* do always a fast random poll */
268     fast_random_poll();
269
270     /* mix the pool (if add_randomness() didn't it) */
271     if( !just_mixed )
272         mix_pool(rndpool);
273
274     /* create a new pool */
275     for(i=0,dp=(ulong*)keypool, sp=(ulong*)rndpool;
276                                 i < POOLWORDS; i++, dp++, sp++ )
277         *dp = *sp + ADD_VALUE;
278     /* and mix both pools */
279     mix_pool(rndpool);
280     mix_pool(keypool);
281     /* read the required data
282      * we use a readpoiter to read from a different postion each
283      * time */
284     while( length-- ) {
285         *buffer++ = keypool[pool_readpos++];
286         if( pool_readpos >= POOLSIZE )
287             pool_readpos = 0;
288         pool_balance--;
289     }
290     if( pool_balance < 0 )
291         pool_balance = 0;
292     /* and clear the keypool */
293     memset( keypool, 0, POOLSIZE );
294 }
295
296
297 /****************
298  * Add LENGTH bytes of randomness from buffer to the pool.
299  * source may be used to specify the randomeness source.
300  */
301 void
302 add_randomness( const void *buffer, size_t length, int source )
303 {
304     if( !is_initialized )
305         initialize();
306     while( length-- ) {
307         rndpool[pool_writepos++] = *((byte*)buffer)++;
308         if( pool_writepos >= POOLSIZE ) {
309             pool_filled = 1;
310             pool_writepos = 0;
311             mix_pool(rndpool);
312             just_mixed = !length;
313         }
314     }
315 }
316
317
318
319 /********************
320  *  FIXME: move these functions to rand_unix.c
321  */
322
323 void
324 random_poll()
325 {
326     char buf[POOLSIZE/5];
327     read_dev_random( buf, POOLSIZE/5, 1 ); /* read /dev/urandom */
328     add_randomness( buf, POOLSIZE/5, 2);
329     memset( buf, 0, POOLSIZE/5);
330 }
331
332
333 void
334 fast_random_poll()
335 {
336   #ifdef HAVE_GETTIMEOFTIME
337     {   struct timeval tv;
338         if( gettimeofday( &tv, NULL ) )
339             BUG();
340         add_randomness( &tv.tv_sec, sizeof(tv.tv_sec), 1 );
341         add_randomness( &tv.tv_usec, sizeof(tv.tv_usec), 1 );
342     }
343   #else /* use times */
344     {   struct tms buf;
345         times( &buf );
346         add_randomness( &buf, sizeof buf, 1 );
347     }
348   #endif
349   #ifdef HAVE_GETRUSAGE
350     {   struct rusage buf;
351         if( getrusage( RUSAGE_SELF, &buf ) )
352             BUG();
353         add_randomness( &buf, sizeof buf, 1 );
354         memset( &buf, 0, sizeof buf );
355     }
356   #endif
357 }
358
359
360 #ifdef HAVE_DEV_RANDOM
361
362 static int
363 open_device( const char *name, int minor )
364 {
365     int fd;
366     struct stat sb;
367
368     fd = open( name, O_RDONLY );
369     if( fd == -1 )
370         log_fatal("can't open %s: %s\n", name, strerror(errno) );
371     if( fstat( fd, &sb ) )
372         log_fatal("stat() off %s failed: %s\n", name, strerror(errno) );
373   #if defined(__sparc__) && defined(__linux__)
374     #warning something is wrong with UltraPenguin /dev/random
375   #else
376     if( !S_ISCHR(sb.st_mode) )
377         log_fatal("invalid random device!\n" );
378   #endif
379     return fd;
380 }
381
382
383 static void
384 read_dev_random( byte *buffer, size_t length, int level )
385 {
386     static int fd_urandom = -1;
387     static int fd_random = -1;
388     int fd;
389     int n;
390     int warn=0;
391
392     if( level == 2 && !quick_test ) {
393         if( fd_random == -1 )
394             fd_random = open_device( "/dev/random", 8 );
395         fd = fd_random;
396     }
397     else {
398         /* fixme: we should use a simpler one for level 0,
399          * because reading from /dev/urandom removes entropy
400          * and the next read on /dev/random may have to wait */
401         if( fd_urandom == -1 )
402             fd_urandom = open_device( "/dev/urandom", 9 );
403         fd = fd_urandom;
404     }
405
406
407     do {
408         fd_set rfds;
409         struct timeval tv;
410         int rc;
411
412         FD_ZERO(&rfds);
413         FD_SET(fd, &rfds);
414         tv.tv_sec = 3;
415         tv.tv_usec = 0;
416         if( !(rc=select(fd+1, &rfds, NULL, NULL, &tv)) ) {
417             if( !warn )
418                 tty_printf( _(
419 "\n"
420 "Not enough random bytes available.  Please do some other work to give\n"
421 "the OS a chance to collect more entropy! (Need %d more bytes)\n"), length );
422             warn = 1;
423             continue;
424         }
425         else if( rc == -1 ) {
426             tty_printf("select() error: %s\n", strerror(errno));
427             continue;
428         }
429
430         assert( length < 500 );
431         do {
432             n = read(fd, buffer, length );
433             if( n >= 0 && n > length ) {
434                 log_error("bogus read from random device (n=%d)\n", n );
435                 n = length;
436             }
437         } while( n == -1 && errno == EINTR );
438         if( n == -1 )
439             log_fatal("read error on random device: %s\n", strerror(errno) );
440         assert( n <= length );
441         buffer += n;
442         length -= n;
443     } while( length );
444 }
445
446 #else /* not HAVE_DEV_RANDOM */
447
448
449 #ifndef RAND_MAX   /* for SunOS */
450   #define RAND_MAX 32767
451 #endif
452
453 static void
454 read_dev_random( byte *buffer, size_t length, int level )
455 {
456     static int initialized=0;
457
458     if( !initialized ) {
459         log_info(_("warning: using insecure random number generator!!\n"));
460         tty_printf(_("The random number generator is only a kludge to let\n"
461                    "it compile - it is in no way a strong RNG!\n\n"
462                    "DON'T USE ANY DATA GENERATED BY THIS PROGRAM!!\n\n"));
463         initialized=1;
464       #ifdef HAVE_RAND
465         srand(make_timestamp()*getpid());
466       #else
467         srandom(make_timestamp()*getpid());
468       #endif
469     }
470
471   #ifdef HAVE_RAND
472     while( length-- )
473         *buffer++ = ((unsigned)(1 + (int) (256.0*rand()/(RAND_MAX+1.0)))-1);
474   #else
475     while( length-- )
476         *buffer++ = ((unsigned)(1 + (int) (256.0*random()/(RAND_MAX+1.0)))-1);
477   #endif
478 }
479
480 #endif
481