Skip to contentSkip to conversation

Concurrent access to /dev/urandom

DISCUSSION Bernard Normier 13 participants 39 messages Nov 27, 2004 – Dec 12, 2004 Random number driver

lore
Share & tools
lore
#0 lore raw

I use /dev/urandom to generate UUIDs by reading 16 random bytes from /dev/urandom (very much like e2fsprogs' libuuid).

As long as I serialize access to /dev/urandom, I get different values. However, with concurrent access to /dev/urandom, I quickly get duplicate values. libuuid uses one shared file descriptor for all threads, while the test case below uses a file descriptor per read; it does not appear to change anything ... duplicates appear very quickly (within seconds). I tried on 2.4.20-27.9smp, 2.6.8-1.521smp, 2.6.9-1.6_FC2smp.

Within one process, I could easily serialize access to /dev/urandom to avoid this problem. But I suspect the same would happen with concurrent access from different processes, and I'd rather avoid interprocess synchronization. Is this the expected behavior of /dev/urandom? Any suggestions on how to get unique values?

Thanks,
Bernard

#include <pthread.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>

#include <iostream>
#include <set>

using namespace std;

static pthread_mutex_t staticMutex = PTHREAD_MUTEX_INITIALIZER;

struct Key
{
long long high;
long long low;
};

struct KeyComp
{
inline bool operator()(const Key& lhs, const Key& rhs)
{
return lhs.high < rhs.high || (lhs.high == rhs.high && lhs.low < rhs.low);
}
};

static set<Key, KeyComp> keySet;
static int keyCount;

void* threadFailed()
{
return reinterpret_cast<void*>(-1);
}

extern "C"
void* readRandom(void* d)
{
int threadId = reinterpret_cast<int>(d);

for(int i = 0; i < keyCount; ++i)
{
int fd = open("/dev/urandom", O_RDONLY);

if (fd == -1)

{
    cerr << "could not open /dev/urandom" << endl;
    return threadFailed();
}

int reads = 0;
size_t index = 0;
char buffer[16];

while(reads <= 20 && index != sizeof(Key))

{
    ssize_t bytesRead = read(fd, buffer + index, sizeof(Key) - index);

    if(bytesRead == -1)
    {
 if(errno != EINTR)
 {
     int err = errno;
     cerr << "Reading /dev/urandom returned " << strerror(err) << endl;
     close(fd);
     return threadFailed();
 }
    }
    else
    {
 index += bytesRead;
 reads++;
    }
}

if(index != sizeof(buffer))

{
    close(fd);
    cerr << "Giving up after 20 reads!" << endl;
    return threadFailed();
}

close(fd);

int err = pthread_mutex_lock(&staticMutex);
if(err != 0)

{
    cerr << "pthread_mutex_lock failed" << endl;
    return threadFailed();
}

Key& key = reinterpret_cast<Key&>(buffer);

pair<set<Key, KeyComp>::iterator, bool> result = keySet.insert(key); if(!result.second)

{
    cerr << "******** Found duplicate!! **********" << endl;
    struct AsInts
    {
 unsigned int x1;
 unsigned int x2;
 unsigned int x3;
 unsigned int x4;
    };

    AsInts& ints = reinterpret_cast<AsInts&>(buffer);
    cerr << hex << ints.x1 << "-" << ints.x2 << "-" << ints.x3 << "-" << 

ints.x4 << endl;

    pthread_mutex_unlock(&staticMutex);
    return threadFailed();
}

if(i > 0 && (i % 100000 == 0))

{
    cout << "Thread " << threadId << ": read " << i << " keys" << endl;
}

err = pthread_mutex_unlock(&staticMutex);
if(err != 0)

{
    cerr << "pthread_mutex_unlock failed" << endl;
    return threadFailed();
}

}

return 0;
}

int main(int argc, char* argv[])
{
if(argc != 3)
{
cerr << "Usage: " << argv[0] << " [number of keys to read] [number of threads]" << endl; return -1;
}

   int howMany = atoi(argv[1]);
   int threadCount = atoi(argv[2]);
   keyCount = howMany / threadCount;

   pthread_t* threads = new pthread_t[threadCount];

for(int i = 0; i < threadCount; ++i)
{
int err = pthread_create(&threads[i], 0, readRandom, reinterpret_cast<void*>(i)); if(err != 0)

{
    cerr << "pthread_create failed" << endl;
    return -1;
}

}

for(int i = 0; i < threadCount; ++i)
{
void* threadStatus;
int err = pthread_join(threads[i], &threadStatus); if(err != 0)

{
    cerr << "pthread_join failed" << endl;
    return -1;
}
if(threadStatus != 0)
{
    cerr << "Thread " << i << " failed" << endl;
    return -1;
}

}

delete[] threads;
return 0;
}

// build with g++ -D_REENTRANT -o utest utest.cpp -lpthread

#1 lore raw
Quoted 2 lines

As long as I serialize access to /dev/urandom, I get different values. However, with concurrent access to /dev/urandom, I quickly get duplicate

How do you concurrently read from urandom? That's only possible with 2 or more CPUs, and even then, I hope that the urandom chardev has some spinlock.

Quoted 2 lines

#include <pthread.h>
[...]

Rule of thumb: Post the smallest possible code that shows the problem.

Jan Engelhardt

Signature · 2 lines
Gesellschaft für Wissenschaftliche Datenverarbeitung
Am Fassberg, 37077 Göttingen, www.gwdg.de
#2 lore raw
Quoted 6 lines
Quoted 2 lines

As long as I serialize access to /dev/urandom, I get different values. However, with concurrent access to /dev/urandom, I quickly get duplicate

How do you concurrently read from urandom? That's only possible with 2 or more CPUs, and even then, I hope that the urandom chardev has some spinlock.

As shown in the code included in my first e-mail, each thread simply open("/dev/urandom", O_RDONLY), use read(2) to read 16 bytes, and then close the file descriptor.
Duplicates appear quickly on: single CPU with HT, dual CPU without HT, and dual CPU with HT (all with smp kernels)
But not on a lower end single CPU without HT (2.6.8-1.521 non-smp).

Quoted 4 lines
Quoted 2 lines

#include <pthread.h>
[...]

Rule of thumb: Post the smallest possible code that shows the problem.

Will do next time!

Bernard

#3 lore raw
Quoted 6 lines

As shown in the code included in my first e-mail, each thread simply open("/dev/urandom", O_RDONLY), use read(2) to read 16 bytes, and then close the file descriptor.
Duplicates appear quickly on: single CPU with HT, dual CPU without HT, and dual CPU with HT (all with smp kernels)
But not on a lower end single CPU without HT (2.6.8-1.521 non-smp).

Ok, so it is a case of two "kernel-side" CPUs.

Quoted 2 lines
Quoted 1 line

Rule of thumb: Post the smallest possible code that shows the problem.

Will do next time!

That would be great, because it could show that urandom is missing a lock somewhere.

Jan Engelhardt

Signature · 2 lines
Gesellschaft für Wissenschaftliche Datenverarbeitung
Am Fassberg, 37077 Göttingen, www.gwdg.de
#4 lore raw
Quoted 5 lines
Quoted 2 lines
Quoted 1 line

Rule of thumb: Post the smallest possible code that shows the problem.

Will do next time!

That would be great, because it could show that urandom is missing a lock somewhere.

Here is a smaller version (102 lines vs 173 before). It's difficult to get something very very small since I need to start a few threads.

Bernard

#include <pthread.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <assert.h>
#include <errno.h>

#include <set>
#include <iostream>
using namespace std;

// Each thread will generate keyCount keys
static int threadCount = 3;
static int keyCount = 1000000 / threadCount;

// When not defined, all threads read /dev/urandom concurrently // #define SERIALIZE_READS 1

struct Key
{
long long high;
long long low;

bool operator<(const Key& rhs) const

   {
       return high < rhs.high || (high == rhs.high && low < rhs.low);

}
};

static set<Key> keySet;
static pthread_mutex_t keySetMutex = PTHREAD_MUTEX_INITIALIZER;

extern "C" void* readRandom(void*)
{
for(int i = 0; i < keyCount; ++i)

   {
       int fd = open("/dev/urandom", O_RDONLY);
       assert(fd != -1);
#ifdef SERIALIZE_READS
       int err = pthread_mutex_lock(&keySetMutex);
       assert(err == 0);
#endif
       size_t index = 0;
       char buffer[sizeof(Key)];

       while(index != sizeof(Key))
       {
           ssize_t bytesRead = read(fd, buffer + index, sizeof(Key) - 

index);

           if(bytesRead == -1)
           {
               if(errno != EINTR)
               {
                   close(fd);
                   return reinterpret_cast<void*>(-1);
               }
           }
           else
           {
               index += bytesRead;
           }
       }

       close(fd);
#ifndef SERIALIZE_READS
       int err = pthread_mutex_lock(&keySetMutex);
       assert(err == 0);
#endif
       pair<set<Key>::iterator, bool> result = 
keySet.insert(reinterpret_cast<Key&>(buffer));
       if(!result.second)
       {
           cerr << "Found duplicate!" << endl;
       }
       err = pthread_mutex_unlock(&keySetMutex);
       assert(err == 0);

}

return 0;
}

int main(int argc, char* argv[])
{
pthread_t* threads = new pthread_t[threadCount]; for(int i = 0; i < threadCount; ++i)

   {
       int err = pthread_create(&threads[i], 0, readRandom, 0);
       assert(err == 0);
   }
   for(int i = 0; i < threadCount; ++i)
   {
       void* threadStatus;
       int err = pthread_join(threads[i], &threadStatus);
       assert(err == 0);
       assert(threadStatus == 0);

}

delete[] threads;
return 0;
}

// build with g++ -D_REENTRANT -o utest utest.cpp -lpthread

#5 lore raw

Reading concurrently /proc/sys/kernel/random/uuid also returns duplicates quite quickly ... which definitely looks like a bug. I included a small python test-case below. Can anybody suggest a work-around, for example a simple way to serialize access to /dev/urandom from multiple threads/processes on the same box?

Thanks,
Bernard

#!/usr/bin/env python
import threading
from threading import Thread, Lock

map = {}
lock = Lock()

class MyThread(Thread):

def __init__(self):

       Thread.__init__(self)

def run(self):

       for i in range(500000):
           f = open("/proc/sys/kernel/random/uuid")
           k = f.readline().strip()
           lock.acquire()
           if map.has_key(k):
               print "Error: duplicate key " + k
           else:
               map[k] = 1
           lock.release()
           f.close()

thread = {}

for i in range(4):
thread[i] = MyThread()
thread[i].start()

for i in range(4):
thread[i].join()

----- Original Message ----- From: "Bernard Normier" <[email protected]>
To: "Jan Engelhardt" <[email protected]>
Cc: <[email protected]>
Sent: Sunday, November 28, 2004 3:58 PM
Subject: Re: Concurrent access to /dev/urandom

Quoted 124 lines
Quoted 5 lines
Quoted 2 lines
Quoted 1 line

Rule of thumb: Post the smallest possible code that shows the problem.

Will do next time!

That would be great, because it could show that urandom is missing a lock somewhere.

Here is a smaller version (102 lines vs 173 before). It's difficult to get something very very small since I need to start a few threads.

Bernard

#include <pthread.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <assert.h>
#include <errno.h>

#include <set>
#include <iostream>
using namespace std;

// Each thread will generate keyCount keys
static int threadCount = 3;
static int keyCount = 1000000 / threadCount;

// When not defined, all threads read /dev/urandom concurrently // #define SERIALIZE_READS 1

struct Key

{
   long long high;
   long long low;

   bool operator<(const Key& rhs) const
   {
       return high < rhs.high || (high == rhs.high && low < rhs.low);
   }
};

static set<Key> keySet;
static pthread_mutex_t keySetMutex = PTHREAD_MUTEX_INITIALIZER;

extern "C" void* readRandom(void*)

{
   for(int i = 0; i < keyCount; ++i)
   {
       int fd = open("/dev/urandom", O_RDONLY);
       assert(fd != -1);
#ifdef SERIALIZE_READS
       int err = pthread_mutex_lock(&keySetMutex);
       assert(err == 0);
#endif
       size_t index = 0;
       char buffer[sizeof(Key)];

       while(index != sizeof(Key))
       {
           ssize_t bytesRead = read(fd, buffer + index, sizeof(Key) - 

index);

           if(bytesRead == -1)
           {
               if(errno != EINTR)
               {
                   close(fd);
                   return reinterpret_cast<void*>(-1);
               }
           }
           else
           {
               index += bytesRead;
           }
       }

       close(fd);
#ifndef SERIALIZE_READS
       int err = pthread_mutex_lock(&keySetMutex);
       assert(err == 0);
#endif
       pair<set<Key>::iterator, bool> result = 
keySet.insert(reinterpret_cast<Key&>(buffer));
       if(!result.second)
       {
           cerr << "Found duplicate!" << endl;
       }
       err = pthread_mutex_unlock(&keySetMutex);
       assert(err == 0);

}

   return 0;
}

int main(int argc, char* argv[])

{
   pthread_t* threads = new pthread_t[threadCount];
   for(int i = 0; i < threadCount; ++i)
   {
       int err = pthread_create(&threads[i], 0, readRandom, 0);
       assert(err == 0);
   }
   for(int i = 0; i < threadCount; ++i)
   {
       void* threadStatus;
       int err = pthread_join(threads[i], &threadStatus);
       assert(err == 0);
       assert(threadStatus == 0);
   }

   delete[] threads;
   return 0;
}

// build with g++ -D_REENTRANT -o utest utest.cpp -lpthread

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

maintainer
#6 lore raw
Quoted 5 lines · Bernard Normier

Reading concurrently /proc/sys/kernel/random/uuid also returns duplicates quite quickly ... which definitely looks like a bug. I included a small python test-case below.
Can anybody suggest a work-around, for example a simple way to serialize access to /dev/urandom from multiple threads/processes on the same box?

This has been fixed in 2.6, but not yet in 2.4. Really, this should be fixed in the kernel, but if you need to worry about this from the perspective of user-level programs that might be running on unfixed distribution kernels, the best way to deal with the problem is to use /dev/urandom to seed a cryptographic random number generator, and then mix in your pid and time/date into the CRNG.

For example (in Pseudo code):

char key[16];
int counter;

seed_random_number_generator()

{
	key <- SHA(20 bytes from /dev/random || pid || time(0));
	counter = 0;
}

get_random_bytes()

{
	return SHA(counter++ || key);
}

This by the way is a generally a good thing to do in all cases; /dev/urandom is designed to be used to seed a cryptographic random generator. If you need a large number of cryptographic random numbers, it's much faster to do it in user space than to try to do it in the kernel.

- Ted

#7 lore raw

In which version of 2.6 did this bug get fixed? I am seeing these duplicates with 2.6.9-1.667smp (FC3)? I am just trying to generate UUIDs (without duplicates, obviously).

Thanks,
Bernard

Quoted 42 lines · Bernard Normier
Quoted 5 lines

Reading concurrently /proc/sys/kernel/random/uuid also returns duplicates quite quickly ... which definitely looks like a bug. I included a small python test-case below.
Can anybody suggest a work-around, for example a simple way to serialize access to /dev/urandom from multiple threads/processes on the same box?

This has been fixed in 2.6, but not yet in 2.4. Really, this should be fixed in the kernel, but if you need to worry about this from the perspective of user-level programs that might be running on unfixed distribution kernels, the best way to deal with the problem is to use /dev/urandom to seed a cryptographic random number generator, and then mix in your pid and time/date into the CRNG.

For example (in Pseudo code):

char key[16];
int counter;

seed_random_number_generator()
{
key <- SHA(20 bytes from /dev/random || pid || time(0)); counter = 0;
}

get_random_bytes()
{
return SHA(counter++ || key);
}

This by the way is a generally a good thing to do in all cases; /dev/urandom is designed to be used to seed a cryptographic random generator. If you need a large number of cryptographic random numbers, it's much faster to do it in user space than to try to do it in the kernel.

- Ted
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

maintainer
#8 lore raw
Quoted 2 lines · Bernard Normier

In which version of 2.6 did this bug get fixed? I am seeing these duplicates with 2.6.9-1.667smp (FC3)?

SMP locking was added before 2.6.0 shipped (between 2.6.0-test7 and -test8). But I see what happened; the problem is that the locking was added around add_entropy_words(), and not in the extract_entropy loop. Yes, extract_entropy() does call add_entropy_words() (which makes the fix more than just a two-line patch), but if two processors enter extract_entropy() at the same time, the locking turns out not to be sufficient.

I'm currently travelling so I can't easily test this patch, not having easy access to an SMP machine. Could you give it a spin and let me know if this fixes things?

Quoted 1 line

I am just trying to generate UUIDs (without duplicates, obviously).

That's funny. I had put in a workaround into libuuid as of e2fsprogs 1.35 that mixed in the pid and first time uuid_generate() was called into the randomness, as a temporary workaround. So this should have prevented duplicate uuid's from being generated. The only way this could have happened would be if /dev/urandom and /dev/random failed to open, and so the time-based uuid was used, or if the generate_uuid is being called from a threaded program, where the uuid's internal random number generator was only getting initialized once (and where we don't have any thread-specific locking in the uuid library).

What version of the uuid library are you using, and what's the application that requires so many UUID's in the first place. I wrote the uuid library with the assumption that it wasn't the sort of thing where applications would be calling them in tight loops on threaded applications on SMP machines. If my assumptions are wrong, then clearly I need to do some work to make the uuid library robust against this (mis-?)use.

- Ted

Patch explanation:

This patch solves a problem where simultaneous reads to /dev/urandom can cause two processes on different processors to get the same value. We're not using a spinlock around the random generation loop because this will be a huge hit to preempt latency. So instead we just use a mutex around random_read and urandom_read. Yeah, it's not as efficient in the case of contention, if an application is calling /dev/urandom a huge amount, it's there's something really misdesigned with it, and we don't want to optimize for stupid applications.

There is also a kludge where the CPU # permutes the starting value of the hash in order to make sure that even if extract_entropy is called in parallel, the two CPU's will not get the same value. This is a belt-and-suspenders thing, mainly to handle the case where the kernel calls get_random_bytes --- which happens only but rarely, so this is mainly for paranoia's sake.

===== drivers/char/random.c 1.60 vs edited =====

drivers/char/random.c +13 -3
@@ -404,6 +404,7 @@ static struct entropy_store *sec_random_
 static struct entropy_store *urandom_state; /* For urandom */
 static DECLARE_WAIT_QUEUE_HEAD(random_read_wait);
 static DECLARE_WAIT_QUEUE_HEAD(random_write_wait);
+static DECLARE_MUTEX(random_read_sem);
 
 /*
  * Forward procedure declarations
@@ -1345,7 +1346,7 @@ static ssize_t extract_entropy(struct en
 	__u32 tmp[TMP_BUF_SIZE];
 	__u32 x;
 	unsigned long cpuflags;
-
+	unsigned int cpu;
 
 	/* Redundant, but just in case... */
 	if (r->entropy_count > r->poolinfo.POOLBITS)
@@ -1380,6 +1381,7 @@ static ssize_t extract_entropy(struct en
 	spin_unlock_irqrestore(&r->lock, cpuflags);
 
 	ret = 0;
+	cpu = get_cpu();
 	while (nbytes) {
 		/*
 		 * Check if we need to break out or reschedule....
@@ -1403,7 +1405,7 @@ static ssize_t extract_entropy(struct en
 		}
 
 		/* Hash the pool to get the output */
-		tmp[0] = 0x67452301;
+		tmp[0] = 0x67452301 ^ cpu;
 		tmp[1] = 0xefcdab89;
 		tmp[2] = 0x98badcfe;
 		tmp[3] = 0x10325476;
@@ -1449,6 +1451,7 @@ static ssize_t extract_entropy(struct en
 		buf += i;
 		ret += i;
 	}
+	put_cpu();
 
 	/* Wipe data just returned from memory */
 	memset(tmp, 0, sizeof(tmp));
@@ -1605,10 +1608,12 @@ random_read(struct file * file, char __u
 			  n*8, random_state->entropy_count,
 			  sec_random_state->entropy_count);
 
+		down(&random_read_sem);
 		n = extract_entropy(sec_random_state, buf, n,
 				    EXTRACT_ENTROPY_USER |
 				    EXTRACT_ENTROPY_LIMIT |
 				    EXTRACT_ENTROPY_SECONDARY);
+		up(&random_read_sem);
 
 		DEBUG_ENT("%04d %04d : read got %d bits (%d still needed)\n",
 			  random_state->entropy_count,
@@ -1669,6 +1674,7 @@ static ssize_t
 urandom_read(struct file * file, char __user * buf,
 		      size_t nbytes, loff_t *ppos)
 {
+	ssize_t n;
 	int flags = EXTRACT_ENTROPY_USER;
 	unsigned long cpuflags;
 
@@ -1677,7 +1683,11 @@ urandom_read(struct file * file, char __
 		flags |= EXTRACT_ENTROPY_SECONDARY;
 	spin_unlock_irqrestore(&random_state->lock, cpuflags);
 
-	return extract_entropy(urandom_state, buf, nbytes, flags);
+	down(&random_read_sem);
+	n = extract_entropy(urandom_state, buf, nbytes, flags);
+	up(&random_read_sem);
+	return (n);
+	
 }
 
 static unsigned int
#9 lore raw

I am not using libuuid: I wrote my own "version-4" UUID generator that reads /dev/urandom and assumes it's not "out to lunch". When I started to test this generator more thoroughly (with multiple threads), I quickly got these duplicates. This test does not represent the typical usage of my UUID generator; however, I get duplicates so quickly that I am very concerned about real applications also getting duplicates. BTW a single processor with hyper-threading is enough to get these duplicates.

For now, I've worked around this issue by replacing the last 15 bits of each UUID by the last 15 bits of the process id, and in each process my UUID generator serializes access to /dev/urandom.

I will also try your patch.

Thanks,
Bernard

Quoted 142 lines · Bernard Normier
Quoted 2 lines

In which version of 2.6 did this bug get fixed? I am seeing these duplicates with 2.6.9-1.667smp (FC3)?

SMP locking was added before 2.6.0 shipped (between 2.6.0-test7 and -test8). But I see what happened; the problem is that the locking was added around add_entropy_words(), and not in the extract_entropy loop. Yes, extract_entropy() does call add_entropy_words() (which makes the fix more than just a two-line patch), but if two processors enter extract_entropy() at the same time, the locking turns out not to be sufficient.

I'm currently travelling so I can't easily test this patch, not having easy access to an SMP machine. Could you give it a spin and let me know if this fixes things?

Quoted 1 line

I am just trying to generate UUIDs (without duplicates, obviously).

That's funny. I had put in a workaround into libuuid as of e2fsprogs 1.35 that mixed in the pid and first time uuid_generate() was called into the randomness, as a temporary workaround. So this should have prevented duplicate uuid's from being generated. The only way this could have happened would be if /dev/urandom and /dev/random failed to open, and so the time-based uuid was used, or if the generate_uuid is being called from a threaded program, where the uuid's internal random number generator was only getting initialized once (and where we don't have any thread-specific locking in the uuid library).

What version of the uuid library are you using, and what's the application that requires so many UUID's in the first place. I wrote the uuid library with the assumption that it wasn't the sort of thing where applications would be calling them in tight loops on threaded applications on SMP machines. If my assumptions are wrong, then clearly I need to do some work to make the uuid library robust against this (mis-?)use.

- Ted

Patch explanation:

This patch solves a problem where simultaneous reads to /dev/urandom can cause two processes on different processors to get the same value. We're not using a spinlock around the random generation loop because this will be a huge hit to preempt latency. So instead we just use a mutex around random_read and urandom_read. Yeah, it's not as efficient in the case of contention, if an application is calling /dev/urandom a huge amount, it's there's something really misdesigned with it, and we don't want to optimize for stupid applications.

There is also a kludge where the CPU # permutes the starting value of the hash in order to make sure that even if extract_entropy is called in parallel, the two CPU's will not get the same value. This is a belt-and-suspenders thing, mainly to handle the case where the kernel calls get_random_bytes --- which happens only but rarely, so this is mainly for paranoia's sake.

===== drivers/char/random.c 1.60 vs edited =====

drivers/char/random.c 2004-12-08 13:31:05 -05:00 renamed from drivers/char/random.c 2004-11-18 17:23:14 -05:00 +0 -0
@@ -404,6 +404,7 @@ static struct entropy_store *sec_random_

static struct entropy_store *urandom_state; /* For urandom */ static DECLARE_WAIT_QUEUE_HEAD(random_read_wait); static DECLARE_WAIT_QUEUE_HEAD(random_write_wait); +static DECLARE_MUTEX(random_read_sem);

/*
* Forward procedure declarations

drivers/char/random.c 2004-12-08 13:31:05 -05:00 renamed from drivers/char/random.c 2004-11-18 17:23:14 -05:00 +12 -3
@@ -1345,7 +1346,7 @@ static ssize_t extract_entropy(struct en
 __u32 tmp[TMP_BUF_SIZE];
 __u32 x;
 unsigned long cpuflags;
-
+ unsigned int cpu;
 
 /* Redundant, but just in case... */
 if (r->entropy_count > r->poolinfo.POOLBITS)
@@ -1380,6 +1381,7 @@ static ssize_t extract_entropy(struct en
 spin_unlock_irqrestore(&r->lock, cpuflags);
 
 ret = 0;
+ cpu = get_cpu();
 while (nbytes) {
 /*
 * Check if we need to break out or reschedule....
@@ -1403,7 +1405,7 @@ static ssize_t extract_entropy(struct en
 }
 
 /* Hash the pool to get the output */
- tmp[0] = 0x67452301;
+ tmp[0] = 0x67452301 ^ cpu;
 tmp[1] = 0xefcdab89;
 tmp[2] = 0x98badcfe;
 tmp[3] = 0x10325476;
@@ -1449,6 +1451,7 @@ static ssize_t extract_entropy(struct en
 buf += i;
 ret += i;
 }
+ put_cpu();
 
 /* Wipe data just returned from memory */
 memset(tmp, 0, sizeof(tmp));
@@ -1605,10 +1608,12 @@ random_read(struct file * file, char __u
   n*8, random_state->entropy_count,
   sec_random_state->entropy_count);
 
+ down(&random_read_sem);
 n = extract_entropy(sec_random_state, buf, n,
     EXTRACT_ENTROPY_USER |
     EXTRACT_ENTROPY_LIMIT |
     EXTRACT_ENTROPY_SECONDARY);
+ up(&random_read_sem);
 
 DEBUG_ENT("%04d %04d : read got %d bits (%d still needed)\n",
   random_state->entropy_count,
@@ -1669,6 +1674,7 @@ static ssize_t
 urandom_read(struct file * file, char __user * buf,
       size_t nbytes, loff_t *ppos)
 {
+ ssize_t n;
 int flags = EXTRACT_ENTROPY_USER;
 unsigned long cpuflags;
 
@@ -1677,7 +1683,11 @@ urandom_read(struct file * file, char __
 flags |= EXTRACT_ENTROPY_SECONDARY;
 spin_unlock_irqrestore(&random_state->lock, cpuflags);
 
- return extract_entropy(urandom_state, buf, nbytes, flags);
+ down(&random_read_sem);
+ n = extract_entropy(urandom_state, buf, nbytes, flags);
+ up(&random_read_sem);
+ return (n);
+
 }
 

static unsigned int
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

#10 lore raw
In reply to Theodore Ts'o
Quoted 11 lines · Theodore Ts'o
Quoted 2 lines · Bernard Normier

In which version of 2.6 did this bug get fixed? I am seeing these duplicates with 2.6.9-1.667smp (FC3)?

SMP locking was added before 2.6.0 shipped (between 2.6.0-test7 and -test8). But I see what happened; the problem is that the locking was added around add_entropy_words(), and not in the extract_entropy loop. Yes, extract_entropy() does call add_entropy_words() (which makes the fix more than just a two-line patch), but if two processors enter extract_entropy() at the same time, the locking turns out not to be sufficient.

Oh, duh. Thought I'd looked at that race. Because of the locking in add_entropy_words, each CPU is mixing "tmp" into r in a serialized fashion. However, before grabbing the pool lock, they can be grabbing the same tmp from the pool and then sending that off to userspace.

So the requirement is this: we have to extract data from the pool AND change the pool state sufficiently to avoid identical extraction in one atomic step. We can do either an entire pool mix atomically (which is ideal, but expensive), or we can avoid using the same bits of the pool for mixing/extraction with a mixing pointer. We don't care if the mixing pointer wraps around because when that happens, we've done a full mix.

Ted, I think this is a bit more straightforward than your patch, and safer as it protects get_random_bytes() and internal extract_entropy() users. And I'd be leery of your get_cpu() trick due to preempt issues.

drivers/char/random.c +24 -9
Index: linux/drivers/char/random.c
===================================================================
@@ -498,7 +498,7 @@
 
 	/* read-write data: */
 	spinlock_t lock ____cacheline_aligned_in_smp;
-	unsigned	add_ptr;
+	unsigned	add_ptr, mix_ptr;
 	int		entropy_count;
 	int		input_rotate;
 };
@@ -550,6 +550,7 @@
 static void clear_entropy_store(struct entropy_store *r)
 {
 	r->add_ptr = 0;
+	r->mix_ptr = 0;
 	r->entropy_count = 0;
 	r->input_rotate = 0;
 	memset(r->pool, 0, r->poolinfo.POOLBYTES);
@@ -572,7 +573,7 @@
  * it's cheap to do so and helps slightly in the expected case where
  * the entropy is concentrated in the low-order bits.
  */
-static void add_entropy_words(struct entropy_store *r, const __u32 *in,
+static void __add_entropy_words(struct entropy_store *r, const __u32 *in,
 			      int nwords)
 {
 	static __u32 const twist_table[8] = {
@@ -582,9 +583,7 @@
 	int new_rotate, input_rotate;
 	int wordmask = r->poolinfo.poolwords - 1;
 	__u32 w, next_w;
-	unsigned long flags;
 
-	/* Taps are constant, so we can load them without holding r->lock.  */
 	tap1 = r->poolinfo.tap1;
 	tap2 = r->poolinfo.tap2;
 	tap3 = r->poolinfo.tap3;
@@ -592,7 +591,6 @@
 	tap5 = r->poolinfo.tap5;
 	next_w = *in++;
 
-	spin_lock_irqsave(&r->lock, flags);
 	prefetch_range(r->pool, wordmask);
 	input_rotate = r->input_rotate;
 	add_ptr = r->add_ptr;
@@ -625,7 +623,14 @@
 
 	r->input_rotate = input_rotate;
 	r->add_ptr = add_ptr;
+}
 
+static void add_entropy_words(struct entropy_store *r, const __u32 *in,
+			      int nwords)
+{
+	unsigned long flags;
+	spin_lock_irqsave(&r->lock, flags);
+	__add_entropy_words(r, in, nwords);
 	spin_unlock_irqrestore(&r->lock, flags);
 }
 
@@ -1425,12 +1430,22 @@
 		 * the state of the pool plus the current outputs, and
 		 * attempts to find previous ouputs), unless the hash
 		 * function can be inverted.
+		 *
+		 * We must hash and mix as an atomic operation to
+		 * avoid threads grabbing the same hash. The mix_ptr
+		 * lets us mix less than the whole pool and still pull
+		 * unique hashes.
 		 */
-		for (i = 0, x = 0; i < r->poolinfo.poolwords; i += 16, x+=2) {
-			HASH_TRANSFORM(tmp, r->pool+i);
-			add_entropy_words(r, &tmp[x%HASH_BUFFER_SIZE], 1);
+		for (i = 0; i < r->poolinfo.poolwords/16; i++) {
+			spin_lock_irqsave(&r->lock, flags);
+			HASH_TRANSFORM(tmp, r->pool+r->mix_ptr);
+			r->mix_ptr = (r->mix_ptr + 16) &
+				(r->poolinfo.poolwords - 1);
+			__add_entropy_words(r,
+					    &tmp[(i*2)%HASH_BUFFER_SIZE], 1);
+			spin_unlock_irqrestore(&r->lock, flags);
 		}
-		
+
 		/*
 		 * In case the hash function has some recognizable
 		 * output pattern, we fold it in half.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
maintainer
#11 lore raw
Quoted 6 lines · Matt Mackall

Ted, I think this is a bit more straightforward than your patch, and safer as it protects get_random_bytes() and internal extract_entropy() users. And I'd be leery of your get_cpu() trick due to preempt issues.

I'm concerned that turning off interrupts during even a single SHA-1 transform will put us above the radar with respect to the preempt latency statistics again. We could use a separate spinlock that only pretects the mix_ptr and mixing access to the pool, so we're at least not disabling interrupts, but we still are holding a spinlock across a cryptographic operation.

So I've come up with another trick which I think avoids needing to add additional locking altogether. What we do is we diddle the initial HASH input values with the following values: initial the processor ID, the current task pointer, and preempt_count(). On an UP system with preemption, it won't matter if we get preempted, since on a UP system access to the pool is by definition serialized :-). On a SMP system with preemption, while we could theoretically get preempted away and then scheduled on another CPU, just in time for another process to call extract_entropy(), the task identifier is enough to guarantee a unique starting point. The reason for adding preempt_count() is so we can deal with the case where a process gets interrupted, and the bottom half handler calls get_random_bytes(), and at the same time said process gets preempted away to another CPU(). I think this covers all of the cases.....

Yeah, it would be simper to reason about things if we were to just put it under the spinlock, but everyone seems tp be on a reduce latency at all costs kick as of late. :-)

Comments?

- Ted

===== drivers/char/random.c 1.60 vs edited =====

drivers/char/random.c +13 -4
@@ -1402,10 +1402,19 @@ static ssize_t extract_entropy(struct en
 				  sec_random_state->entropy_count);
 		}
 
-		/* Hash the pool to get the output */
-		tmp[0] = 0x67452301;
-		tmp[1] = 0xefcdab89;
-		tmp[2] = 0x98badcfe;
+		/* 
+		 * Hash the pool to get the output.
+		 *
+		 * We diddle the initial inputs so that if two
+		 * processors are executing extract_entropy
+		 * concurrently, they will get different results.
+		 * Even if we get preempted and moved to another CPU,
+		 * the combination of initial CPU, task pointer, and
+		 * preempt count is good enough to avoid duplication.
+		 */
+		tmp[0] = 0x67452301 ^ smp_processor_id();
+		tmp[1] = 0xefcdab89 ^ (__u32) current;
+		tmp[2] = 0x98badcfe ^ preempt_count();
 		tmp[3] = 0x10325476;
 #ifdef USE_SHA
 		tmp[4] = 0xc3d2e1f0;
#12 lore raw

hi Ted

i think this is better than use the spin lock.
but i think maybe there should put an #ifdef SMP :)
just like

#ifdef CONFIG_SMP
               tmp[0] = 0x67452301 ^ smp_processor_id();
               tmp[1] = 0xefcdab89 ^ (__u32) current;
               tmp[2] = 0x98badcfe ^ preempt_count();

#endif

is it needed?

Quoted 75 lines · Theodore Ts'o
Quoted 6 lines · Matt Mackall

Ted, I think this is a bit more straightforward than your patch, and safer as it protects get_random_bytes() and internal extract_entropy() users. And I'd be leery of your get_cpu() trick due to preempt issues.

I'm concerned that turning off interrupts during even a single SHA-1 transform will put us above the radar with respect to the preempt latency statistics again. We could use a separate spinlock that only pretects the mix_ptr and mixing access to the pool, so we're at least not disabling interrupts, but we still are holding a spinlock across a cryptographic operation.

So I've come up with another trick which I think avoids needing to add additional locking altogether. What we do is we diddle the initial HASH input values with the following values: initial the processor ID, the current task pointer, and preempt_count(). On an UP system with preemption, it won't matter if we get preempted, since on a UP system access to the pool is by definition serialized :-). On a SMP system with preemption, while we could theoretically get preempted away and then scheduled on another CPU, just in time for another process to call extract_entropy(), the task identifier is enough to guarantee a unique starting point. The reason for adding preempt_count() is so we can deal with the case where a process gets interrupted, and the bottom half handler calls get_random_bytes(), and at the same time said process gets preempted away to another CPU(). I think this covers all of the cases.....

Yeah, it would be simper to reason about things if we were to just put it under the spinlock, but everyone seems tp be on a reduce latency at all costs kick as of late. :-)

Comments?

- Ted

===== drivers/char/random.c 1.60 vs edited =====

drivers/char/random.c 2004-12-08 20:51:18 -05:00 renamed from drivers/char/random.c 2004-11-18 17:23:14 -05:00 +13 -5
@@ -1402,10 +1402,19 @@ static ssize_t extract_entropy(struct en
                                 sec_random_state->entropy_count);
               }
 
-               /* Hash the pool to get the output */
-               tmp[0] = 0x67452301;
-               tmp[1] = 0xefcdab89;
-               tmp[2] = 0x98badcfe;
+               /*
+                * Hash the pool to get the output.
+                *
+                * We diddle the initial inputs so that if two
+                * processors are executing extract_entropy
+                * concurrently, they will get different results.
+                * Even if we get preempted and moved to another CPU,
+                * the combination of initial CPU, task pointer, and
+                * preempt count is good enough to avoid duplication.
+                */
+               tmp[0] = 0x67452301 ^ smp_processor_id();
+               tmp[1] = 0xefcdab89 ^ (__u32) current;
+               tmp[2] = 0x98badcfe ^ preempt_count();
               tmp[3] = 0x10325476;
 #ifdef USE_SHA
               tmp[4] = 0xc3d2e1f0;
 
 
-

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Signature · 1 line
Yours andyliu
#13 lore raw
Quoted 6 lines · andyliu

hi Ted

i think this is better than use the spin lock.
but i think maybe there should put an #ifdef SMP :)
just like

Quoted 7 lines
#ifdef CONFIG_SMP
               tmp[0] = 0x67452301 ^ smp_processor_id();
               tmp[1] = 0xefcdab89 ^ (__u32) current;
               tmp[2] = 0x98badcfe ^ preempt_count();

#endif

is it needed?

The race can be hit with get_random_bytes on UP if we get interrupted/preempted between hashing and mixing. Which is why preempt_count is useful..

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
#14 lore raw
In reply to Theodore Ts'o
Quoted 7 lines · Theodore Ts'o
Quoted 5 lines · Matt Mackall

Ted, I think this is a bit more straightforward than your patch, and safer as it protects get_random_bytes() and internal extract_entropy() users. And I'd be leery of your get_cpu() trick due to preempt issues.

Quoted 6 lines

I'm concerned that turning off interrupts during even a single SHA-1 transform will put us above the radar with respect to the preempt latency statistics again. We could use a separate spinlock that only pretects the mix_ptr and mixing access to the pool, so we're at least not disabling interrupts, but we still are holding a spinlock across a cryptographic operation.

A big mixlock was my first thought, but it'd still have to be _irqsave as we can reach extract_entropy from irq handlers.

Quoted 15 lines

So I've come up with another trick which I think avoids needing to add additional locking altogether. What we do is we diddle the initial HASH input values with the following values: initial the processor ID, the current task pointer, and preempt_count(). On an UP system with preemption, it won't matter if we get preempted, since on a UP system access to the pool is by definition serialized :-). On a SMP system with preemption, while we could theoretically get preempted away and then scheduled on another CPU, just in time for another process to call extract_entropy(), the task identifier is enough to guarantee a unique starting point. The reason for adding preempt_count() is so we can deal with the case where a process gets interrupted, and the bottom half handler calls get_random_bytes(), and at the same time said process gets preempted away to another CPU(). I think this covers all of the cases.....

Quoted 3 lines

Yeah, it would be simper to reason about things if we were to just put it under the spinlock, but everyone seems tp be on a reduce latency at all costs kick as of late. :-)

I'd like to combine this with my approach of fiddling with the mixing offset in a similar manner. In the duplicate case, we were basically returning SHA(x[y]) twice and now we're returning SHA(x[y]^knowns). This makes me a bit uneasy. I'd rather do SHA(x[knowns%sizeof(x)]^knowns2), then we've at least got some different _unknowns_ in the hash from the attacker's perspective, yes?

Something like:

drivers/char/random.c +27 -6
Index: random/drivers/char/random.c
===================================================================
@@ -1343,7 +1343,7 @@
 {
 	ssize_t ret, i;
 	__u32 tmp[TMP_BUF_SIZE];
-	__u32 x;
+	__u32 x, offset, wrap;
 	unsigned long cpuflags;
 
 
@@ -1402,14 +1402,35 @@
 				  sec_random_state->entropy_count);
 		}
 
-		/* Hash the pool to get the output */
-		tmp[0] = 0x67452301;
+		/*
+		 * Hash the pool to get the output.
+		 *
+		 * We diddle the initial inputs so that if two
+		 * processors are executing extract_entropy
+		 * concurrently, they will get different results. Even
+		 * if we get preempted and moved to another CPU, the
+		 * combination of initial CPU, task pointer, and
+		 * preempt count is good enough to avoid duplication.
+		 * We could instead use more locking here, but the
+		 * resulting latency is painful.
+		 */
+		tmp[0] = 0x67452301 ^ smp_processor_id();
 		tmp[1] = 0xefcdab89;
-		tmp[2] = 0x98badcfe;
+		tmp[2] = 0x98badcfe ^ preempt_count();
 		tmp[3] = 0x10325476;
 #ifdef USE_SHA
 		tmp[4] = 0xc3d2e1f0;
 #endif
+
+		/*
+		 * Generate an offset for mixing (multiple of 16) so
+		 * that we have different unknowns in the mix in the
+		 * concurrent case as well.
+		 */
+
+		wrap = r->poolinfo.poolwords;
+		offset = ((__u32)current * 8675309 % wrap) & ~15;
+
 		/*
 		 * As we hash the pool, we mix intermediate values of
 		 * the hash back into the pool.  This eliminates
@@ -1419,10 +1440,10 @@
 		 * function can be inverted.
 		 */
 		for (i = 0, x = 0; i < r->poolinfo.poolwords; i += 16, x+=2) {
-			HASH_TRANSFORM(tmp, r->pool+i);
+			HASH_TRANSFORM(tmp, r->pool + (i + offset) % wrap);
 			add_entropy_words(r, &tmp[x%HASH_BUFFER_SIZE], 1);
 		}
-		
+
 		/*
 		 * In case the hash function has some recognizable
 		 * output pattern, we fold it in half.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
#15 lore raw
In reply to Theodore Ts'o
Quoted 8 lines · Theodore Ts'o
Quoted 6 lines · Matt Mackall

Ted, I think this is a bit more straightforward than your patch, and safer as it protects get_random_bytes() and internal extract_entropy() users. And I'd be leery of your get_cpu() trick due to preempt issues.

Quoted 6 lines

I'm concerned that turning off interrupts during even a single SHA-1 transform will put us above the radar with respect to the preempt latency statistics again. We could use a separate spinlock that only pretects the mix_ptr and mixing access to the pool, so we're at least not disabling interrupts, but we still are holding a spinlock across a cryptographic operation.

It's been suggested to me that a sequence lock might be the right approach to this, which I'll try to take a look at this evening. Also, I'm going to time the lock hold time in my previous more conventional patch and see what kind of neighborhood we're in.

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
#16 lore raw
Quoted 16 lines · Matt Mackall
Quoted 8 lines · Theodore Ts'o
Quoted 6 lines · Matt Mackall

Ted, I think this is a bit more straightforward than your patch, and safer as it protects get_random_bytes() and internal extract_entropy() users. And I'd be leery of your get_cpu() trick due to preempt issues.

Quoted 6 lines

I'm concerned that turning off interrupts during even a single SHA-1 transform will put us above the radar with respect to the preempt latency statistics again. We could use a separate spinlock that only pretects the mix_ptr and mixing access to the pool, so we're at least not disabling interrupts, but we still are holding a spinlock across a cryptographic operation.

Quoted 4 lines

It's been suggested to me that a sequence lock might be the right approach to this, which I'll try to take a look at this evening. Also, I'm going to time the lock hold time in my previous more conventional patch and see what kind of neighborhood we're in.

Seqlock seems to not be a terribly good fit.

I benched SHATransform + add_entropy_works, and came up with ~2us on 1.8GHz P4M. I'm guessing this is under the latency radar.

But it turns out that we can do this without hashing under the lock after all. What's important is that we mix and extract atomically. Something like this should be quite reasonable:

drivers/char/random.c +28 -11
Index: random/drivers/char/random.c
===================================================================
@@ -573,7 +573,7 @@
  * the entropy is concentrated in the low-order bits.
  */
 static void add_entropy_words(struct entropy_store *r, const __u32 *in,
-			      int nwords)
+			      int nwords, __u32 out[16])
 {
 	static __u32 const twist_table[8] = {
 		         0, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
@@ -623,6 +623,13 @@
 		r->pool[i] = (w >> 3) ^ twist_table[w & 7];
 	}
 
+	if (out) {
+		for (i = 0; i < 16; i++) {
+			out[i] = r->pool[add_ptr];
+			add_ptr = (add_ptr - 1) & wordmask;
+		}
+	}
+
 	r->input_rotate = input_rotate;
 	r->add_ptr = add_ptr;
 
@@ -763,7 +770,7 @@
 							sec_random_state;
 			max_entropy = r->poolinfo.POOLBITS;
 		}
-		add_entropy_words(r, batch_entropy_copy[tail].data, 2);
+		add_entropy_words(r, batch_entropy_copy[tail].data, 2, NULL);
 		credit_entropy_store(r, batch_entropy_copy[tail].credit);
 		tail = (tail+1) & (batch_max-1);
 	}
@@ -1320,7 +1327,7 @@
 
 		bytes=extract_entropy(random_state, tmp, bytes,
 				      EXTRACT_ENTROPY_LIMIT);
-		add_entropy_words(r, tmp, bytes);
+		add_entropy_words(r, tmp, bytes, NULL);
 		credit_entropy_store(r, bytes*8);
 	}
 }
@@ -1342,7 +1349,7 @@
 			       size_t nbytes, int flags)
 {
 	ssize_t ret, i;
-	__u32 tmp[TMP_BUF_SIZE];
+	__u32 tmp[TMP_BUF_SIZE], data[16];
 	__u32 x;
 	unsigned long cpuflags;
 
@@ -1418,11 +1425,21 @@
 		 * attempts to find previous ouputs), unless the hash
 		 * function can be inverted.
 		 */
-		for (i = 0, x = 0; i < r->poolinfo.poolwords; i += 16, x+=2) {
+		for (i = 16, x = 2; i < r->poolinfo.poolwords; i += 16, x+=2) {
 			HASH_TRANSFORM(tmp, r->pool+i);
-			add_entropy_words(r, &tmp[x%HASH_BUFFER_SIZE], 1);
+			add_entropy_words(r, &tmp[x%HASH_BUFFER_SIZE],
+					  1, NULL);
 		}
-		
+
+		/*
+		 * To avoid duplicates, we hash the first block last,
+		 * atomically extract a portion of the pool while mixing,
+		 * and hash one final time.
+		 */
+		HASH_TRANSFORM(tmp, r->pool);
+		add_entropy_words(r, &tmp[0], 1, data);
+		HASH_TRANSFORM(tmp, data);
+
 		/*
 		 * In case the hash function has some recognizable
 		 * output pattern, we fold it in half.
@@ -1503,7 +1520,7 @@
 	do_gettimeofday(&tv);
 	words[0] = tv.tv_sec;
 	words[1] = tv.tv_usec;
-	add_entropy_words(r, words, 2);
+	add_entropy_words(r, words, 2, NULL);
 
 	/*
 	 *	This doesn't lock system.utsname. However, we are generating
@@ -1512,7 +1529,7 @@
 	p = (char *) &system_utsname;
 	for (i = sizeof(system_utsname) / sizeof(words); i; i--) {
 		memcpy(words, p, sizeof(words));
-		add_entropy_words(r, words, sizeof(words)/4);
+		add_entropy_words(r, words, sizeof(words)/4, NULL);
 		p += sizeof(words);
 	}
 }
@@ -1716,7 +1733,7 @@
 		c -= bytes;
 		p += bytes;
 
-		add_entropy_words(random_state, buf, (bytes + 3) / 4);
+		add_entropy_words(random_state, buf, (bytes + 3) / 4, NULL);
 	}
 	if (p == buffer) {
 		return (ssize_t)ret;
@@ -1855,7 +1872,7 @@
 		return ret;
 
 	add_entropy_words(new_store, random_state->pool,
-			  random_state->poolinfo.poolwords);
+			  random_state->poolinfo.poolwords, NULL);
 	credit_entropy_store(new_store, random_state->entropy_count);
 
 	sysctl_init_random(new_store);
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
maintainer
#17 lore raw
Quoted 4 lines · Matt Mackall

But it turns out that we can do this without hashing under the lock after all. What's important is that we mix and extract atomically. Something like this should be quite reasonable:

The core idea is good, but your patch has a bug in it; it bashes add_ptr before it gets saved into r->add_ptr. Also, it's a more complicated than it needed to be (which makes it harder to analyze it). Finally, it won't work if the pool doesn't get initialized with sufficient randomness in the init scripts, and there are too many constant zero's in the pool. But this is easily fixed by using a different initialization pattern.

How about this?

- Ted

This patch fixes a problem where /dev/urandom can return duplicate values when two processors read from it at the same time. It relies on the fact that we already are taking a lock in add_entropy_words(), and atomically hashes in some freshly mixed in data into the returned randomness.

drivers/char/random.c +30 -5
@@ -549,10 +549,13 @@ static int create_entropy_store(int size
 /* Clear the entropy pool and associated counters. */
 static void clear_entropy_store(struct entropy_store *r)
 {
+	int i;
+
 	r->add_ptr = 0;
 	r->entropy_count = 0;
 	r->input_rotate = 0;
-	memset(r->pool, 0, r->poolinfo.POOLBYTES);
+	for (i=0; i < r->poolinfo.poolwords; i++)
+		r->pool[i] = i;
 }
 #ifdef CONFIG_SYSCTL
 static void free_entropy_store(struct entropy_store *r)
@@ -572,8 +575,8 @@ static void free_entropy_store(struct en
  * it's cheap to do so and helps slightly in the expected case where
  * the entropy is concentrated in the low-order bits.
  */
-static void add_entropy_words(struct entropy_store *r, const __u32 *in,
-			      int nwords)
+static void __add_entropy_words(struct entropy_store *r, const __u32 *in,
+				int nwords, __u32 out[16])
 {
 	static __u32 const twist_table[8] = {
 		         0, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
@@ -626,9 +629,23 @@ static void add_entropy_words(struct ent
 	r->input_rotate = input_rotate;
 	r->add_ptr = add_ptr;
 
+	if (out) {
+		for (i = 0; i < 16; i++) {
+			out[i] = r->pool[add_ptr];
+			add_ptr = (add_ptr - 1) & wordmask;
+		}
+	}
+
 	spin_unlock_irqrestore(&r->lock, flags);
 }
 
+static inline void add_entropy_words(struct entropy_store *r, const __u32 *in,
+				     int nwords)
+{
+	__add_entropy_words(r, in, nwords, NULL);
+}
+
+
 /*
  * Credit (or debit) the entropy store with n bits of entropy
  */
@@ -1342,7 +1359,7 @@ static ssize_t extract_entropy(struct en
 			       size_t nbytes, int flags)
 {
 	ssize_t ret, i;
-	__u32 tmp[TMP_BUF_SIZE];
+	__u32 tmp[TMP_BUF_SIZE], data[16];
 	__u32 x;
 	unsigned long cpuflags;
 
@@ -1422,7 +1439,15 @@ static ssize_t extract_entropy(struct en
 			HASH_TRANSFORM(tmp, r->pool+i);
 			add_entropy_words(r, &tmp[x%HASH_BUFFER_SIZE], 1);
 		}
-		
+
+		/*
+		 * To avoid duplicates, we atomically extract a
+		 * portion of the pool while mixing, and hash one
+		 * final time.
+		 */
+		__add_entropy_words(r, &tmp[x%HASH_BUFFER_SIZE], 1, data);
+		HASH_TRANSFORM(tmp, data);
+
 		/*
 		 * In case the hash function has some recognizable
 		 * output pattern, we fold it in half.
#18 lore raw
Quoted 8 lines · Theodore Ts'o
Quoted 4 lines · Matt Mackall

But it turns out that we can do this without hashing under the lock after all. What's important is that we mix and extract atomically. Something like this should be quite reasonable:

The core idea is good, but your patch has a bug in it; it bashes add_ptr before it gets saved into r->add_ptr.

I seem to remember having a rationale for that, but I'm fine with your way.

Quoted 3 lines

Also, it's a more
complicated than it needed to be (which makes it harder to analyze it).

Fair enough. s/__add/mix/, please.

Quoted 4 lines

Finally, it won't work if the pool doesn't get initialized with sufficient randomness in the init scripts, and there are too many constant zero's in the pool. But this is easily fixed by using a different initialization pattern.

It won't work as in we'll still get duplicates? I don't see how that happens. The polynomial for the output pools is dense enough that even on the very next one word mix, we're getting 96 bits changed in the output and 32 new ones shifted in. And we're always doing at least three adds for each pull.

It's still suboptimal, perhaps, but I'd rather mix more in init_std_data. In fact, I was hoping to abolish the pool clearing function in favor of just init_std_data, as there's not much utility in going back to a known state here. Let's address this separately.

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
maintainer
#19 lore raw
Quoted 3 lines · Matt Mackall

Fair enough. s/__add/mix/, please.

Why? Fundamentally, it's all about adding entropy to the pool. I don't have an strong objection to calling it __mix_entropy_words, but if we're going to change it, we should change the non-__ variant for consistency's sake, and I'd much rather do that in a separate patch if we're going to do it all. I don't see the point of the rename, though.

Quoted 5 lines

It won't work as in we'll still get duplicates? I don't see how that happens. The polynomial for the output pools is dense enough that even on the very next one word mix, we're getting 96 bits changed in the output and 32 new ones shifted in. And we're always doing at least three adds for each pull.

You're right, it should be OK. I was concerned about the case where some percentage of the pool was still all zero's, and what might happen if two adjacent add_entropy_words() mixed in the same data (as could still happen). But one of the add_entropy_words() will be mixed in first, and even if the other add_entropy_words mixes in the exact same data, the data[] returned by first and second add_entropy_words() will be different, and we should be OK.

Still, I'd feel better if we did initialize more data via init_std_data(), and then cranked the LFSR some number of times so that we don't have to worry about analyzing the case where a good portion of the pool might contain consecutive zero values. But yeah, we can save that for another patch, as it's not absolutely essential.

Are we converging here?

- Ted

This patch fixes a problem where /dev/urandom can return duplicate values when two processors read from it at the same time. It relies on the fact that we already are taking a lock in add_entropy_words(), and atomically hashes in some freshly mixed in data into the returned randomness.

drivers/char/random.c +26 -4
@@ -572,8 +572,8 @@ static void free_entropy_store(struct en
  * it's cheap to do so and helps slightly in the expected case where
  * the entropy is concentrated in the low-order bits.
  */
-static void add_entropy_words(struct entropy_store *r, const __u32 *in,
-			      int nwords)
+static void __add_entropy_words(struct entropy_store *r, const __u32 *in,
+				int nwords, __u32 out[16])
 {
 	static __u32 const twist_table[8] = {
 		         0, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
@@ -626,9 +626,23 @@ static void add_entropy_words(struct ent
 	r->input_rotate = input_rotate;
 	r->add_ptr = add_ptr;
 
+	if (out) {
+		for (i = 0; i < 16; i++) {
+			out[i] = r->pool[add_ptr];
+			add_ptr = (add_ptr - 1) & wordmask;
+		}
+	}
+
 	spin_unlock_irqrestore(&r->lock, flags);
 }
 
+static inline void add_entropy_words(struct entropy_store *r, const __u32 *in,
+				     int nwords)
+{
+	__add_entropy_words(r, in, nwords, NULL);
+}
+
+
 /*
  * Credit (or debit) the entropy store with n bits of entropy
  */
@@ -1342,7 +1356,7 @@ static ssize_t extract_entropy(struct en
 			       size_t nbytes, int flags)
 {
 	ssize_t ret, i;
-	__u32 tmp[TMP_BUF_SIZE];
+	__u32 tmp[TMP_BUF_SIZE], data[16];
 	__u32 x;
 	unsigned long cpuflags;
 
@@ -1422,7 +1436,15 @@ static ssize_t extract_entropy(struct en
 			HASH_TRANSFORM(tmp, r->pool+i);
 			add_entropy_words(r, &tmp[x%HASH_BUFFER_SIZE], 1);
 		}
-		
+
+		/*
+		 * To avoid duplicates, we atomically extract a
+		 * portion of the pool while mixing, and hash one
+		 * final time.
+		 */
+		__add_entropy_words(r, &tmp[x%HASH_BUFFER_SIZE], 1, data);
+		HASH_TRANSFORM(tmp, data);
+
 		/*
 		 * In case the hash function has some recognizable
 		 * output pattern, we fold it in half.
#20 lore raw
Quoted 11 lines · Theodore Ts'o
Quoted 3 lines · Matt Mackall

Fair enough. s/__add/mix/, please.

Why? Fundamentally, it's all about adding entropy to the pool. I don't have an strong objection to calling it __mix_entropy_words, but if we're going to change it, we should change the non-__ variant for consistency's sake, and I'd much rather do that in a separate patch if we're going to do it all. I don't see the point of the rename, though.

I suppose I don't really care. The __add is no longer just add, and mix was the word that came to mind. But it doesn't really describe it well either.

Quoted 7 lines

Still, I'd feel better if we did initialize more data via init_std_data(), and then cranked the LFSR some number of times so that we don't have to worry about analyzing the case where a good portion of the pool might contain consecutive zero values. But yeah, we can save that for another patch, as it's not absolutely essential.

Are we converging here?

I'm gonna call this last iteration done. Repasted below for akpm's benefit. Urgency: medium-ish.

---

This patch fixes a problem where /dev/urandom can return duplicate values when two processors read from it at the same time. It relies on the fact that we already are taking a lock in add_entropy_words(), and atomically hashes in some freshly mixed in data into the returned randomness.

drivers/char/random.c +26 -4
@@ -572,8 +572,8 @@ static void free_entropy_store(struct en
  * it's cheap to do so and helps slightly in the expected case where
  * the entropy is concentrated in the low-order bits.
  */
-static void add_entropy_words(struct entropy_store *r, const __u32 *in,
-			      int nwords)
+static void __add_entropy_words(struct entropy_store *r, const __u32 *in,
+				int nwords, __u32 out[16])
 {
 	static __u32 const twist_table[8] = {
 		         0, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
@@ -626,9 +626,23 @@ static void add_entropy_words(struct ent
 	r->input_rotate = input_rotate;
 	r->add_ptr = add_ptr;
 
+	if (out) {
+		for (i = 0; i < 16; i++) {
+			out[i] = r->pool[add_ptr];
+			add_ptr = (add_ptr - 1) & wordmask;
+		}
+	}
+
 	spin_unlock_irqrestore(&r->lock, flags);
 }
 
+static inline void add_entropy_words(struct entropy_store *r, const __u32 *in,
+				     int nwords)
+{
+	__add_entropy_words(r, in, nwords, NULL);
+}
+
+
 /*
  * Credit (or debit) the entropy store with n bits of entropy
  */
@@ -1342,7 +1356,7 @@ static ssize_t extract_entropy(struct en
 			       size_t nbytes, int flags)
 {
 	ssize_t ret, i;
-	__u32 tmp[TMP_BUF_SIZE];
+	__u32 tmp[TMP_BUF_SIZE], data[16];
 	__u32 x;
 	unsigned long cpuflags;
 
@@ -1422,7 +1436,15 @@ static ssize_t extract_entropy(struct en
 			HASH_TRANSFORM(tmp, r->pool+i);
 			add_entropy_words(r, &tmp[x%HASH_BUFFER_SIZE], 1);
 		}
-		
+
+		/*
+		 * To avoid duplicates, we atomically extract a
+		 * portion of the pool while mixing, and hash one
+		 * final time.
+		 */
+		__add_entropy_words(r, &tmp[x%HASH_BUFFER_SIZE], 1, data);
+		HASH_TRANSFORM(tmp, data);
+
 		/*
 		 * In case the hash function has some recognizable
 		 * output pattern, we fold it in half.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
#21 lore raw
Quoted 23 lines · Matt Mackall
Quoted 11 lines · Theodore Ts'o
Quoted 3 lines · Matt Mackall

Fair enough. s/__add/mix/, please.

Why? Fundamentally, it's all about adding entropy to the pool. I don't have an strong objection to calling it __mix_entropy_words, but if we're going to change it, we should change the non-__ variant for consistency's sake, and I'd much rather do that in a separate patch if we're going to do it all. I don't see the point of the rename, though.

I suppose I don't really care. The __add is no longer just add, and mix was the word that came to mind. But it doesn't really describe it well either.

Quoted 6 lines

Still, I'd feel better if we did initialize more data via init_std_data(), and then cranked the LFSR some number of times so that we don't have to worry about analyzing the case where a good portion of the pool might contain consecutive zero values. But yeah, we can save that for another patch, as it's not absolutely essential.

Quoted 4 lines
Quoted 1 line

Are we converging here?

I'm gonna call this last iteration done. Repasted below for akpm's benefit. Urgency: medium-ish.

Actually, I think this is a security issue. Since any plain old program can read from /dev/urandom at any time, an attacker could attempt to read from that device at the same moment some other program is doing so, and thereby gain some knowledge as to the other program's state.

#22 lore raw
Quoted 27 lines · Adam Heath
Quoted 25 lines · Matt Mackall
Quoted 11 lines · Theodore Ts'o
Quoted 3 lines · Matt Mackall

Fair enough. s/__add/mix/, please.

Why? Fundamentally, it's all about adding entropy to the pool. I don't have an strong objection to calling it __mix_entropy_words, but if we're going to change it, we should change the non-__ variant for consistency's sake, and I'd much rather do that in a separate patch if we're going to do it all. I don't see the point of the rename, though.

I suppose I don't really care. The __add is no longer just add, and mix was the word that came to mind. But it doesn't really describe it well either.

Quoted 7 lines

Still, I'd feel better if we did initialize more data via init_std_data(), and then cranked the LFSR some number of times so that we don't have to worry about analyzing the case where a good portion of the pool might contain consecutive zero values. But yeah, we can save that for another patch, as it's not absolutely essential.

Are we converging here?

Quoted 7 lines
Quoted 2 lines

I'm gonna call this last iteration done. Repasted below for akpm's benefit. Urgency: medium-ish.

Actually, I think this is a security issue. Since any plain old program can read from /dev/urandom at any time, an attacker could attempt to read from that device at the same moment some other program is doing so, and thereby gain some knowledge as to the other program's state.

It is indeed a security issue. Some interesting non-tin-foil remote attacks may even be possible, but they're still at the handwaving stage. It should be fixed and soon, but I'm also aware that 2.6.10 is imminent.

Unfortunately, the 2.6 development methodology is not well suited to timely security fixes, unless we get serious about this 2.6.x.y strategy.

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
maintainer
#23 lore raw
In reply to Adam Heath
Quoted 5 lines · Adam Heath

Actually, I think this is a security issue. Since any plain old program can read from /dev/urandom at any time, an attacker could attempt to read from that device at the same moment some other program is doing so, and thereby gain some knowledge as to the other program's state.

It could be a potential exploit, but....

(a) it only applies on SMP machines
(b) it's not a remote exploit; the attacker needs to have the ability to run arbitrary programs on the local machine
(c) the attacker won't get all of other programs' reads of /dev/urandom, and
(d) the attacker would have to have a program continuously reading from /dev/urandom, which would take up enough CPU time that it would be rather hard to hide.

That's not to say that we shouldn't fix it at our earliest convenience, and I'd urge Andrew to push this to Linus for 2.6.10 --- but I don't think we need to move heaven and earth to try to accelerate the 2.6.10 release process, either.

- Ted

#24 lore raw
Quoted 19 lines · Theodore Ts'o
Quoted 5 lines · Adam Heath

Actually, I think this is a security issue. Since any plain old program can read from /dev/urandom at any time, an attacker could attempt to read from that device at the same moment some other program is doing so, and thereby gain some knowledge as to the other program's state.

It could be a potential exploit, but....

(a) it only applies on SMP machines
(b) it's not a remote exploit; the attacker needs to have the ability to run arbitrary programs on the local machine
(c) the attacker won't get all of other programs' reads of /dev/urandom, and
(d) the attacker would have to have a program continuously reading from /dev/urandom, which would take up enough CPU time that it would be rather hard to hide.

Quoted 4 lines

That's not to say that we shouldn't fix it at our earliest convenience, and I'd urge Andrew to push this to Linus for 2.6.10 --- but I don't think we need to move heaven and earth to try to accelerate the 2.6.10 release process, either.

Is it a problem for other kernel versions? 2.4? Shouldn't this patch be pushed out separately to distributions?

#25 lore raw
Quoted 21 lines · Adam Heath
Quoted 19 lines · Theodore Ts'o
Quoted 5 lines · Adam Heath

Actually, I think this is a security issue. Since any plain old program can read from /dev/urandom at any time, an attacker could attempt to read from that device at the same moment some other program is doing so, and thereby gain some knowledge as to the other program's state.

It could be a potential exploit, but....

(a) it only applies on SMP machines
(b) it's not a remote exploit; the attacker needs to have the ability to run arbitrary programs on the local machine
(c) the attacker won't get all of other programs' reads of /dev/urandom, and
(d) the attacker would have to have a program continuously reading from /dev/urandom, which would take up enough CPU time that it would be rather hard to hide.

Quoted 7 lines
Quoted 4 lines

That's not to say that we shouldn't fix it at our earliest convenience, and I'd urge Andrew to push this to Linus for 2.6.10 --- but I don't think we need to move heaven and earth to try to accelerate the 2.6.10 release process, either.

Is it a problem for other kernel versions? 2.4? Shouldn't this patch be pushed out separately to distributions?

It's a problem for all kernels back to 1.3.57 (when SMP was added) and perhaps earlier for kernel-internal get_random_bytes users. Fixing pre-2.6 means backporting the whole driver but not the changes in the network area.

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
#26 lore raw
In reply to Theodore Ts'o

Hi!

Quoted 17 lines
Quoted 4 lines

Actually, I think this is a security issue. Since any plain old program can read from /dev/urandom at any time, an attacker could attempt to read from that device at the same moment some other program is doing so, and thereby gain some knowledge as to the other program's state.

It could be a potential exploit, but....

(a) it only applies on SMP machines
(b) it's not a remote exploit; the attacker needs to have the ability to run arbitrary programs on the local machine
(c) the attacker won't get all of other programs' reads of /dev/urandom, and
(d) the attacker would have to have a program continuously reading from /dev/urandom, which would take up enough CPU time that it would be rather hard to hide.

Quoted 4 lines

That's not to say that we shouldn't fix it at our earliest convenience, and I'd urge Andrew to push this to Linus for 2.6.10 --- but I don't think we need to move heaven and earth to try to accelerate the 2.6.10 release process, either.

"Johanka, you really need to generate your own gpg key"

(Starts monitoring johanka by ps -aux, and when time is right, attempts to read /dev/urandom to get same random seed Johanka got.

And BTW it could be made remote expoit if some application sends data from urandom to the net. I'd not be surprised if some authentication program generated challenges from /dev/urandom.
Pavel

Signature · 2 lines
People were complaining that M$ turns users into beta-testers...
...jr ghea gurz vagb qrirybcref, naq gurl frrz gb yvxr vg gung jnl!
#27 lore raw
In reply to Theodore Ts'o

Is this problem a security issue? On SMP, couldn't an attacker read from /dev/urandom, then know what other programs have read, and use that to do some kind of subversion?

#28 lore raw
In reply to Bernard Normier
Quoted 2 lines · Bernard Normier

I am just trying to generate UUIDs (without duplicates, obviously).

pulling data from /dev/random or /dev/urandom will not ensure that you don't have duplicates.

the key factor in a random number generator is that the next number to coem out must be (sufficiantly) unpredictable. this says nothing about it being unique, in fact it says that if you pull the number 1234 the first time you should have the exact same odds of pulling 1234 the second time as you have in pulling 4321 (or any other number)

no much of the time you can get away with useing a random number generator like this, but if you pull enough numbers you will get collisions.

remember the birthday paradox. it says that if you get a group of 26 people in a room you have about a 50% chance that two of these people have the same birthday.

now that's only with numbers in the range of 1-365 if you pull 16 bit numbers (1-65536) you will need a much larger group to see the problem, but if you pull enough you WILL see the problem eventually.

David Lang

Signature · 2 lines
There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies.
 -- C.A.R. Hoare
#29 lore raw
Quoted 7 lines · David Lang
Quoted 2 lines · Bernard Normier

I am just trying to generate UUIDs (without duplicates, obviously).

pulling data from /dev/random or /dev/urandom will not ensure that you don't have duplicates.

No, but this problem can generate duplicates as large as an SHA hash with relative ease when it should be essentially impossible. In other words, it works exactly wrong for UUIDs, which needs fixing.

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
maintainer
#30 lore raw
In reply to David Lang
Quoted 11 lines · David Lang

pulling data from /dev/random or /dev/urandom will not ensure that you don't have duplicates.

remember the birthday paradox. it says that if you get a group of 26 people in a room you have about a 50% chance that two of these people have the same birthday.

now that's only with numbers in the range of 1-365 if you pull 16 bit numbers (1-65536) you will need a much larger group to see the problem, but if you pull enough you WILL see the problem eventually.

Yes, but a UUID is 128 bits. So the chance of a collision is 1 in 2**62. (There are 4 version/type bits, so there are 122 bits of randomness in a type-4, randomly generated UUID). Assuming a correctly working random number generator, yes, it's possible that you could get a duplicate. It's also possible that all of the oxygen molecules could suddenly randomly end up in the other part of the room, and you would suffocate. But it's not very likely. 2**62 is a rather large number....

- Ted

#31 lore raw
In reply to Bernard Normier
Quoted 2 lines · Bernard Normier

I use /dev/urandom to generate UUIDs by reading 16 random bytes from /dev/urandom (very much like e2fsprogs' libuuid).

Why not use /dev/random for such data instead?

/dev/urandom suffers from a poor level of entropy if you keep reading from it over and over again whereas the alternative can block until it has more randomness available.

Cheers,

Jon.

#32 lore raw
Quoted 4 lines
Quoted 2 lines

I use /dev/urandom to generate UUIDs by reading 16 random bytes from /dev/urandom (very much like e2fsprogs' libuuid).

Why not use /dev/random for such data instead?

A UUID generator that blocks from time to time waiting for entropy would not be usable.

Cheers,
Bernard

#33 lore raw
Quoted 6 lines · Bernard Normier
Quoted 4 lines
Quoted 2 lines

I use /dev/urandom to generate UUIDs by reading 16 random bytes from /dev/urandom (very much like e2fsprogs' libuuid).

Why not use /dev/random for such data instead?

A UUID generator that blocks from time to time waiting for entropy would not be usable.

Especially when used on a box without any effective entropy source - like praktically most cheap servers stashed away into some rack.

c'ya
sven

Signature · 2 lines
The Internet treats censorship as a routing problem, and routes around it.
(John Gilmore on http://www.cygnus.com/~gnu/)
#34 lore raw
Quoted 6 lines · Bernard Normier
Quoted 4 lines
Quoted 4 lines
Quoted 3 lines

I use /dev/urandom to generate UUIDs by reading 16 random bytes from /dev/urandom (very much like e2fsprogs' libuuid).

Quoted 8 lines
Quoted 3 lines
Quoted 1 line

Why not use /dev/random for such data instead?

A UUID generator that blocks from time to time waiting for

entropy would not

Quoted 1 line

be usable.

Especially when used on a box without any effective entropy source - like praktically most cheap servers stashed away into some rack.

Assuming most of your cheap servers are running some version of the Intel
Pentium or comparable, they have wonderful entropy sources. Nobody can predict the oscillator offset between the crystals in the network cards on both ends and the TSC. This entropy source is mined by the kernel.

DS

#35 lore raw
Quoted 7 lines · David Schwartz
Quoted 2 lines

Especially when used on a box without any effective entropy source - like praktically most cheap servers stashed away into some rack.

Assuming most of your cheap servers are running some version of the
Intel
Pentium or comparable, they have wonderful entropy sources. Nobody can predict the oscillator offset between the crystals in the network cards on both ends and the TSC. This entropy source is mined by the kernel.

Even timer interrupts are incredibly unpredictable. Instructions can take variable times to complete, and all instructions plus some indeterminate cache operations and queue flushing must occur before the CPU can even begin to service an interrupt. Also of note, there are small critical sections with interrupts disabled scattered all over the kernel and scheduler, in addition to varying memory latencies, etc. (NOTE: I am not an arch expert so this is all just a very general overview of the way most kinds of CPUs handle interrupts). In general these unpredictable instabilities have a randomization effect on the low bits of the TSC at each timer interrupt, (or arch equivalent). The same thing goes for most other such events. I suspect that the computational power necessary to provide a useful model of such a system would be so tremendous you would have an easier job just trying all the possible cryptographic keys. :-D

Cheers,
Kyle Moffett

-----BEGIN GEEK CODE BLOCK-----
Version: 3.12
GCM/CS/IT/U d- s++: a17 C++++>$ UB/L/X/*++++(+)>$ P+++(++++)>$ L++++(+++) E W++(+) N+++(++) o? K? w--- O? M++ V? PS+() PE+(-) Y+ PGP+++ t+(+++) 5 X R? tv-(--) b++++(++) DI+ D+ G e->++++$ h!*()>++$ r !y?(-) ------END GEEK CODE BLOCK------

#36 lore raw
Quoted 5 lines

Even timer interrupts are incredibly unpredictable. Instructions can take
variable times to complete, and all instructions plus some indeterminate cache operations and queue flushing must occur before the CPU can even begin to service an interrupt.

Well, don't timer interrupts happen every 1/1000 s (unless, of course, cli() is in effect)?

Quoted 6 lines

Also of note, there are small
critical
sections with interrupts disabled scattered all over the kernel and scheduler,
in addition to varying memory latencies, etc. (NOTE: I am not an arch expert

In case you mean the RDTSC, it is of course better than the I8042, for random-aphy.

Jan Engelhardt

Signature · 2 lines
Gesellschaft für Wissenschaftliche Datenverarbeitung
Am Fassberg, 37077 Göttingen, www.gwdg.de
#37 lore raw
Quoted 10 lines
Quoted 6 lines

Even timer interrupts are incredibly unpredictable. Instructions can take
variable times to complete, and all instructions plus some indeterminate cache operations and queue flushing must occur before the CPU can even begin to service an interrupt.

Well, don't timer interrupts happen every 1/1000 s (unless, of course, cli() is
in effect)?

Roughly. If you store the TSC on every timer interrupt, there is nobody in the world that can accurately predict what TSC value you will get. Or, to put it in more precise terms, if you log 100 such TSC values and run an MD5 on all of them together, nobody can predict with better than 50% accuracy the value of any bit of that MD5 output.

Quoted 9 lines
Quoted 6 lines

Also of note, there are small
critical
sections with interrupts disabled scattered all over the kernel and scheduler,
in addition to varying memory latencies, etc. (NOTE: I am not an arch expert

In case you mean the RDTSC, it is of course better than the I8042, for random-aphy.

To mine the entropy in the unpredictability of instruction scheduling, cache effectiveness, and slew between the various oscillators in a computer, you need a timing source with the accuracy of the TSC.

You can mine entropy from any two independent oscillators. However, the rate at which you can mine them varies largely upon the frequency of the slowest oscillator. This is why network cards are such good sources of entropy on Pentium machines. You have the network card's oscillator, the oscillator on the network card sending the data to you, and the TSC. All are fast and totally independent.

The timer interrupt may be generated by a clock that ultimately comes from the same source as the TSC clock. This varies from motherboard to motherboard. However, they're generally produced by a PLL that has lots of jitter and slew. So there should be some entropy in there, even without considering unpredictable cache and disk delays.

DS

#38 lore raw
In reply to Jon Masters
Quoted 5 lines · Jon Masters
Quoted 2 lines · Bernard Normier

I use /dev/urandom to generate UUIDs by reading 16 random bytes from /dev/urandom (very much like e2fsprogs' libuuid).

Why not use /dev/random for such data instead?

Because /dev/urandom is the right thing to use, and /dev/random is not.

Quoted 3 lines

/dev/urandom suffers from a poor level of entropy if you keep reading from it over and over again whereas the alternative can block until it has more randomness available.

That's not accurate. Once it has been properly seeded, /dev/urandom should be fine for this purpose (assuming no root compromise). Because /dev/urandom uses a cryptographically secure PRNG, once it has been securely seeded with (say) 128 bits of secure entropy, you can generate as much pseudorandom output as you like without worries (unless someone breaks the crypto, which is usually considered unlikely). If the crypto is secure and /dev/urandom is properly seeded, then its pseudorandom output is indistinguishable from true random bits; this is true even if you extract millions of pseudorandom bits. "Entropy" is often a misleading notion, when you are dealing with cryptographic PRNGs and computationally bounded adversaries.