Rewrote the transform function
[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  * 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 just_mixed;
93
94 static int secure_alloc;
95 static int quick_test;
96
97
98
99 static void read_pool( byte *buffer, size_t length, int level );
100 static void read_dev_random( byte *buffer, size_t length, int level );
101
102
103 static void
104 initialize()
105 {
106     /* The data buffer is allocated somewhat larger, so that
107      * we can use this extra space (which is allocated in secure memory)
108      * as a temporary hash buffer */
109     rndpool = secure_alloc ? m_alloc_secure_clear(POOLSIZE+BLOCKLEN)
110                            : m_alloc_clear(POOLSIZE+BLOCKLEN);
111     keypool = secure_alloc ? m_alloc_secure_clear(POOLSIZE+BLOCKLEN)
112                            : m_alloc_clear(POOLSIZE+BLOCKLEN);
113     is_initialized = 1;
114 }
115
116 void
117 secure_random_alloc()
118 {
119     secure_alloc = 1;
120 }
121
122 int
123 quick_random_gen( int onoff )
124 {
125     int last = quick_test;
126     if( onoff != -1 )
127         quick_test = onoff;
128   #ifndef HAVE_DEV_RANDOM
129     last = 1; /* insecure RNG */
130   #endif
131     return last;
132 }
133
134
135 /****************
136  * Fill the buffer with LENGTH bytes of cryptologic strong
137  * random bytes. level 0 is not very strong, 1 is strong enough
138  * for most usage, 2 is good for key generation stuff but may be very slow.
139  */
140 void
141 randomize_buffer( byte *buffer, size_t length, int level )
142 {
143     for( ; length; length-- )
144         *buffer++ = get_random_byte(level);
145 }
146
147
148 byte
149 get_random_byte( int level )
150 {
151     MASK_LEVEL(level);
152     if( !cache[level].len ) {
153         if( !is_initialized )
154             initialize();
155         if( !cache[level].buffer ) {
156             cache[level].size = 100;
157             cache[level].buffer = level && secure_alloc?
158                                          m_alloc_secure( cache[level].size )
159                                        : m_alloc( cache[level].size );
160         }
161         read_pool(cache[level].buffer, cache[level].size, level );
162         cache[level].len = cache[level].size;
163     }
164
165     return cache[level].buffer[--cache[level].len];
166 }
167
168
169 /****************
170  * Mix the pool
171  */
172 static void
173 mix_pool(byte *pool)
174 {
175     char *hashbuf = pool + POOLSIZE;
176     char *p, *pend;
177     int i, n;
178     RMD160_CONTEXT md;
179
180     rmd160_init( &md );
181  #if DIGESTLEN != 20
182     #error must have a digest length of 20 for ripe-md-160
183  #endif
184     /* loop over the pool */
185     pend = pool + POOLSIZE;
186     memcpy(hashbuf, pend - DIGESTLEN, DIGESTLEN );
187     memcpy(hashbuf+DIGESTLEN, pool, BLOCKLEN-DIGESTLEN);
188     rmd160_mixblock( &md, hashbuf);
189     memcpy(pool, hashbuf, 20 );
190
191     p = pool;
192     for( n=1; n < POOLBLOCKS; n++ ) {
193         memcpy(hashbuf, p, DIGESTLEN );
194
195         p += DIGESTLEN;
196         if( p+DIGESTLEN+BLOCKLEN < pend )
197             memcpy(hashbuf+DIGESTLEN, p+DIGESTLEN, BLOCKLEN-DIGESTLEN);
198         else {
199             char *pp = p+DIGESTLEN;
200             for(i=DIGESTLEN; i < BLOCKLEN; i++ ) {
201                 if( pp >= pend )
202                     pp = pool;
203                 hashbuf[i] = *pp++;
204             }
205         }
206
207         rmd160_mixblock( &md, hashbuf);
208         memcpy(p, hashbuf, 20 );
209     }
210 }
211
212
213 static void
214 read_pool( byte *buffer, size_t length, int level )
215 {
216     int i;
217     ulong *sp, *dp;
218
219     if( length >= POOLSIZE )
220         BUG(); /* not allowed */
221     if( !level ) { /* read simple random bytes */
222         read_dev_random( buffer, length, level );
223         return;
224     }
225
226     /* always do a random poll if we need strong numbers */
227     if( pool_filled && level == 2 )
228         random_poll();
229     /* make sure the pool is filled */
230     while( !pool_filled )
231         random_poll();
232     /* do always a fast random poll */
233     fast_random_poll();
234
235     /* mix the pool (if add_randomness() didn't it) */
236     if( !just_mixed )
237         mix_pool(rndpool);
238
239     /* create a new pool */
240     for(i=0,dp=(ulong*)keypool, sp=(ulong*)rndpool;
241                                 i < POOLWORDS; i++, dp++, sp++ )
242         *dp = *sp + ADD_VALUE;
243     /* and mix both pools */
244     mix_pool(rndpool);
245     mix_pool(keypool);
246     /* read the required data
247      * we use a readpoiter to read from a different postion each
248      * time */
249     while( length-- ) {
250         *buffer++ = keypool[pool_readpos++];
251         if( pool_readpos >= POOLSIZE )
252             pool_readpos = 0;
253     }
254     /* and clear the keypool */
255     memset( keypool, 0, POOLSIZE );
256 }
257
258
259 /****************
260  * Add LENGTH bytes of randomness from buffer to the pool.
261  * source may be used to specify the randomeness source.
262  */
263 void
264 add_randomness( const void *buffer, size_t length, int source )
265 {
266     if( !is_initialized )
267         initialize();
268     while( length-- ) {
269         rndpool[pool_writepos++] = *((byte*)buffer)++;
270         if( pool_writepos >= POOLSIZE ) {
271             pool_filled = 1;
272             pool_writepos = 0;
273             mix_pool(rndpool);
274             just_mixed = !length;
275         }
276     }
277 }
278
279
280
281 /********************
282  *  FIXME: move these functions to rand_unix.c
283  */
284
285 void
286 random_poll()
287 {
288     char buf[POOLSIZE/5];
289     read_dev_random( buf, POOLSIZE/5, 1 ); /* read /dev/urandom */
290     add_randomness( buf, POOLSIZE/5, 2);
291     memset( buf, 0, POOLSIZE/5);
292 }
293
294
295 void
296 fast_random_poll()
297 {
298   #ifdef HAVE_GETTIMEOFTIME
299     {   struct timeval tv;
300         if( gettimeofday( &tv, NULL ) )
301             BUG();
302         add_randomness( &tv.tv_sec, sizeof(tv.tv_sec), 1 );
303         add_randomness( &tv.tv_usec, sizeof(tv.tv_usec), 1 );
304     }
305   #else /* use times */
306     {   struct tms buf;
307         times( &buf );
308         add_randomness( &buf, sizeof buf, 1 );
309     }
310   #endif
311   #ifdef HAVE_GETRUSAGE
312     {   struct rusage buf;
313         if( getrusage( RUSAGE_SELF, &buf ) )
314             BUG();
315         add_randomness( &buf, sizeof buf, 1 );
316         memset( &buf, 0, sizeof buf );
317     }
318   #endif
319 }
320
321
322 #ifdef HAVE_DEV_RANDOM
323
324 static int
325 open_device( const char *name, int minor )
326 {
327     int fd;
328     struct stat sb;
329
330     fd = open( name, O_RDONLY );
331     if( fd == -1 )
332         log_fatal("can't open %s: %s\n", name, strerror(errno) );
333     if( fstat( fd, &sb ) )
334         log_fatal("stat() off %s failed: %s\n", name, strerror(errno) );
335   #if defined(__sparc__) && defined(__linux__)
336     #warning something is wrong with UltraPenguin /dev/random
337   #else
338     if( !S_ISCHR(sb.st_mode) )
339         log_fatal("invalid random device!\n" );
340   #endif
341     return fd;
342 }
343
344
345 static void
346 read_dev_random( byte *buffer, size_t length, int level )
347 {
348     static int fd_urandom = -1;
349     static int fd_random = -1;
350     int fd;
351     int n;
352     int warn=0;
353
354     if( level == 2 && !quick_test ) {
355         if( fd_random == -1 )
356             fd_random = open_device( "/dev/random", 8 );
357         fd = fd_random;
358     }
359     else {
360         /* fixme: we should use a simpler one for level 0,
361          * because reading from /dev/urandom removes entropy
362          * and the next read on /dev/random may have to wait */
363         if( fd_urandom == -1 )
364             fd_urandom = open_device( "/dev/urandom", 9 );
365         fd = fd_urandom;
366     }
367
368
369     do {
370         fd_set rfds;
371         struct timeval tv;
372         int rc;
373
374         FD_ZERO(&rfds);
375         FD_SET(fd, &rfds);
376         tv.tv_sec = 3;
377         tv.tv_usec = 0;
378         if( !(rc=select(fd+1, &rfds, NULL, NULL, &tv)) ) {
379             if( !warn )
380                 tty_printf( _(
381 "\n"
382 "Not enough random bytes available.  Please do some other work to give\n"
383 "the OS a chance to collect more entropy! (Need %d more bytes)\n"), length );
384             warn = 1;
385             continue;
386         }
387         else if( rc == -1 ) {
388             tty_printf("select() error: %s\n", strerror(errno));
389             continue;
390         }
391
392         assert( length < 500 );
393         do {
394             n = read(fd, buffer, length );
395             if( n >= 0 && n > length ) {
396                 log_error("bogus read from random device (n=%d)\n", n );
397                 n = length;
398             }
399         } while( n == -1 && errno == EINTR );
400         if( n == -1 )
401             log_fatal("read error on random device: %s\n", strerror(errno) );
402         assert( n <= length );
403         buffer += n;
404         length -= n;
405     } while( length );
406 }
407
408 #else /* not HAVE_DEV_RANDOM */
409
410
411 #ifndef RAND_MAX   /* for SunOS */
412   #define RAND_MAX 32767
413 #endif
414
415 static void
416 read_dev_random( byte *buffer, size_t length, int level )
417 {
418     static int initialized=0;
419
420     if( !initialized ) {
421         log_info(_("warning: using insecure random number generator!!\n"));
422         tty_printf(_("The random number generator is only a kludge to let\n"
423                    "it compile - it is in no way a strong RNG!\n\n"
424                    "DON'T USE ANY DATA GENERATED BY THIS PROGRAM!!\n\n"));
425         initialized=1;
426       #ifdef HAVE_RAND
427         srand(make_timestamp()*getpid());
428       #else
429         srandom(make_timestamp()*getpid());
430       #endif
431     }
432
433   #ifdef HAVE_RAND
434     while( length-- )
435         *buffer++ = ((unsigned)(1 + (int) (256.0*rand()/(RAND_MAX+1.0)))-1);
436   #else
437     while( length-- )
438         *buffer++ = ((unsigned)(1 + (int) (256.0*random()/(RAND_MAX+1.0)))-1);
439   #endif
440 }
441
442 #endif
443