Concurrent access to /dev/urandom

Concurrent access to /dev/urandom

[Bernard Normier]

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

Re: Concurrent access to /dev/urandom

[Jan Engelhardt]

>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.

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

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


Jan Engelhardt
-- 
Gesellschaft für Wissenschaftliche Datenverarbeitung
Am Fassberg, 37077 Göttingen, www.gwdg.de

Re: Concurrent access to /dev/urandom

[Bernard Normier]

> >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).

>>#include <pthread.h>
>>[...]
>
> Rule of thumb: Post the smallest possible code that shows the problem.
Will do next time!

Bernard

Re: Concurrent access to /dev/urandom

[Jan Engelhardt]

>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.

>> 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
-- 
Gesellschaft für Wissenschaftliche Datenverarbeitung
Am Fassberg, 37077 Göttingen, www.gwdg.de

Re: Concurrent access to /dev/urandom

[Bernard Normier]

>>> 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

Re: Concurrent access to /dev/urandom

[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?

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" <bernard@zeroc.com>
To: "Jan Engelhardt" <jengelh@linux01.gwdg.de>
Cc: <linux-kernel@vger.kernel.org>
Sent: Sunday, November 28, 2004 3:58 PM
Subject: Re: Concurrent access to /dev/urandom


>>>> 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 majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/ 

Re: Concurrent access to /dev/urandom

[Theodore Ts'o]

On Tue, Dec 07, 2004 at 06:41:12PM -0500, Bernard Normier wrote:
> 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

Re: Concurrent access to /dev/urandom

[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)?
I am just trying to generate UUIDs (without duplicates, obviously).

Thanks,
Bernard

> On Tue, Dec 07, 2004 at 06:41:12PM -0500, Bernard Normier wrote:
>> 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 majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/ 

Re: Concurrent access to /dev/urandom

[Theodore Ts'o]

On Tue, Dec 07, 2004 at 08:56:17PM -0500, Bernard Normier wrote:
> 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?

> 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.

Signed-off-by: Theodore Ts'o <tytso@mit.edu>

===== drivers/char/random.c 1.60 vs edited =====
--- 1.60/drivers/char/random.c	2004-11-18 17:23:14 -05:00
+++ edited/drivers/char/random.c	2004-12-08 13:31:05 -05:00
@@ -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

Re: Concurrent access to /dev/urandom

[Bernard Normier]

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

> On Tue, Dec 07, 2004 at 08:56:17PM -0500, Bernard Normier wrote:
>> 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?
>
>> 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.
>
> Signed-off-by: Theodore Ts'o <tytso@mit.edu>
>
> ===== drivers/char/random.c 1.60 vs edited =====
> --- 1.60/drivers/char/random.c 2004-11-18 17:23:14 -05:00
> +++ edited/drivers/char/random.c 2004-12-08 13:31:05 -05:00
> @@ -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
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/ 

Re: Concurrent access to /dev/urandom

[Matt Mackall]

On Wed, Dec 08, 2004 at 02:21:27PM -0500, Theodore Ts'o wrote:
> On Tue, Dec 07, 2004 at 08:56:17PM -0500, Bernard Normier wrote:
> > 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.

Index: linux/drivers/char/random.c
===================================================================
--- linux.orig/drivers/char/random.c	2004-10-18 14:53:11.000000000 -0700
+++ linux/drivers/char/random.c	2004-12-08 13:52:42.729730568 -0800
@@ -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.


-- 
Mathematics is the supreme nostalgia of our time.

Re: Concurrent access to /dev/urandom

[Theodore Ts'o]

On Wed, Dec 08, 2004 at 01:56:14PM -0800, Matt Mackall wrote:
> 
> 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

Signed-off-by: Theodore Ts'o <tytso@mit.edu>

===== drivers/char/random.c 1.60 vs edited =====
--- 1.60/drivers/char/random.c	2004-11-18 17:23:14 -05:00
+++ edited/drivers/char/random.c	2004-12-08 20:51:18 -05:00
@@ -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;

Re: Concurrent access to /dev/urandom

[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

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

is it needed? 



On Wed, 8 Dec 2004 20:57:05 -0500, Theodore Ts'o <tytso@mit.edu> wrote:
> On Wed, Dec 08, 2004 at 01:56:14PM -0800, Matt Mackall wrote:
> >
> > 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
> 
> Signed-off-by: Theodore Ts'o <tytso@mit.edu>
> 
> ===== drivers/char/random.c 1.60 vs edited =====
> --- 1.60/drivers/char/random.c  2004-11-18 17:23:14 -05:00
> +++ edited/drivers/char/random.c        2004-12-08 20:51:18 -05:00
> @@ -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 majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
> 


-- 
Yours andyliu

Re: Concurrent access to /dev/urandom

[Matt Mackall]

On Thu, Dec 09, 2004 at 10:46:30AM +0800, andyliu wrote:
> 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? 

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..

-- 
Mathematics is the supreme nostalgia of our time.

Re: Concurrent access to /dev/urandom

[Matt Mackall]

On Wed, Dec 08, 2004 at 08:57:05PM -0500, Theodore Ts'o wrote:
> On Wed, Dec 08, 2004 at 01:56:14PM -0800, Matt Mackall wrote:
> > 
> > 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.

A big mixlock was my first thought, but it'd still have to be _irqsave
as we can reach extract_entropy from irq handlers.
 
> 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.  :-)

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:

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: random/drivers/char/random.c
===================================================================
--- random.orig/drivers/char/random.c	2004-12-08 18:17:21.000000000 -0800
+++ random/drivers/char/random.c	2004-12-08 18:47:17.914493794 -0800
@@ -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.


-- 
Mathematics is the supreme nostalgia of our time.

Re: Concurrent access to /dev/urandom

[Matt Mackall]

On Wed, Dec 08, 2004 at 08:57:05PM -0500, Theodore Ts'o wrote:
> On Wed, Dec 08, 2004 at 01:56:14PM -0800, Matt Mackall wrote:
> > 
> > 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.

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.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Concurrent access to /dev/urandom

[Matt Mackall]

On Thu, Dec 09, 2004 at 01:29:36PM -0800, Matt Mackall wrote:
> On Wed, Dec 08, 2004 at 08:57:05PM -0500, Theodore Ts'o wrote:
> > On Wed, Dec 08, 2004 at 01:56:14PM -0800, Matt Mackall wrote:
> > > 
> > > 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.
> 
> 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:

Index: random/drivers/char/random.c
===================================================================
--- random.orig/drivers/char/random.c	2004-12-08 18:17:21.000000000 -0800
+++ random/drivers/char/random.c	2004-12-10 02:43:10.280668659 -0800
@@ -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);



-- 
Mathematics is the supreme nostalgia of our time.

Re: Concurrent access to /dev/urandom

[Theodore Ts'o]

On Thu, Dec 09, 2004 at 08:47:59PM -0800, Matt Mackall wrote:
> 
> 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.

Signed-off-by: Matt Mackall <mpm@selenic.com>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>

--- 1.60/drivers/char/random.c	2004-11-18 17:23:14 -05:00
+++ edited/drivers/char/random.c	2004-12-10 11:23:55 -05:00
@@ -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.

Re: Concurrent access to /dev/urandom

[Matt Mackall]

On Fri, Dec 10, 2004 at 11:35:58AM -0500, Theodore Ts'o wrote:
> On Thu, Dec 09, 2004 at 08:47:59PM -0800, Matt Mackall wrote:
> > 
> > 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.

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

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

> 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.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Concurrent access to /dev/urandom

[Theodore Ts'o]

On Fri, Dec 10, 2004 at 10:28:04AM -0800, Matt Mackall wrote:
> 
> 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.

> 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.

Signed-off-by: Matt Mackall <mpm@selenic.com>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>

--- 1.60/drivers/char/random.c	2004-11-18 17:23:14 -05:00
+++ edited/drivers/char/random.c	2004-12-10 16:26:51 -05:00
@@ -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.

Re: Concurrent access to /dev/urandom

[Matt Mackall]

On Fri, Dec 10, 2004 at 04:28:15PM -0500, Theodore Ts'o wrote:
> On Fri, Dec 10, 2004 at 10:28:04AM -0800, Matt Mackall wrote:
> > 
> > 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.

> 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.

Signed-off-by: Matt Mackall <mpm@selenic.com>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>

--- 1.60/drivers/char/random.c	2004-11-18 17:23:14 -05:00
+++ edited/drivers/char/random.c	2004-12-10 16:26:51 -05:00
@@ -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.


-- 
Mathematics is the supreme nostalgia of our time.

Re: Concurrent access to /dev/urandom

[Adam Heath]

On Fri, 10 Dec 2004, Matt Mackall wrote:

> On Fri, Dec 10, 2004 at 04:28:15PM -0500, Theodore Ts'o wrote:
> > On Fri, Dec 10, 2004 at 10:28:04AM -0800, Matt Mackall wrote:
> > >
> > > 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.
>
> > 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.

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.

Re: Concurrent access to /dev/urandom

[Matt Mackall]

On Fri, Dec 10, 2004 at 06:22:37PM -0600, Adam Heath wrote:
> On Fri, 10 Dec 2004, Matt Mackall wrote:
> 
> > On Fri, Dec 10, 2004 at 04:28:15PM -0500, Theodore Ts'o wrote:
> > > On Fri, Dec 10, 2004 at 10:28:04AM -0800, Matt Mackall wrote:
> > > >
> > > > 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.
> >
> > > 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.
> 
> 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.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Concurrent access to /dev/urandom

[Theodore Ts'o]

On Fri, Dec 10, 2004 at 06:22:37PM -0600, Adam Heath wrote:
> 
> 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

Re: Concurrent access to /dev/urandom

[Adam Heath]

On Sat, 11 Dec 2004, Theodore Ts'o wrote:

> On Fri, Dec 10, 2004 at 06:22:37PM -0600, Adam Heath wrote:
> >
> > 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.

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

Re: Concurrent access to /dev/urandom

[Matt Mackall]

On Sat, Dec 11, 2004 at 01:58:45PM -0600, Adam Heath wrote:
> On Sat, 11 Dec 2004, Theodore Ts'o wrote:
> 
> > On Fri, Dec 10, 2004 at 06:22:37PM -0600, Adam Heath wrote:
> > >
> > > 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.
> 
> 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.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Concurrent access to /dev/urandom

[Pavel Machek]

Hi!

> > 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.


"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
-- 
People were complaining that M$ turns users into beta-testers...
...jr ghea gurz vagb qrirybcref, naq gurl frrz gb yvxr vg gung jnl!

Re: Concurrent access to /dev/urandom

[Adam Heath]

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?

Re: Concurrent access to /dev/urandom

[David Lang]

On Tue, 7 Dec 2004, Bernard Normier wrote:

> 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

-- 
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

Re: Concurrent access to /dev/urandom

[Matt Mackall]

On Wed, Dec 08, 2004 at 07:10:16PM -0800, David Lang wrote:
> On Tue, 7 Dec 2004, Bernard Normier wrote:
> 
> >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.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Concurrent access to /dev/urandom

[Theodore Ts'o]

On Wed, Dec 08, 2004 at 07:10:16PM -0800, David Lang wrote:
> 
> 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

Re: Concurrent access to /dev/urandom

[Jon Masters]

On Sat, 27 Nov 2004 15:45:49 -0500, Bernard Normier <bernard@zeroc.com> wrote:

> 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.

Re: Concurrent access to /dev/urandom

[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?

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

Cheers,
Bernard

Re: Concurrent access to /dev/urandom

[Sven-Haegar Koch]

On Mon, 29 Nov 2004, Bernard Normier wrote:

>>> 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

-- 

The Internet treats censorship as a routing problem, and routes around it.
(John Gilmore on http://www.cygnus.com/~gnu/)

RE: Concurrent access to /dev/urandom

[David Schwartz]

> On Mon, 29 Nov 2004, Bernard Normier wrote:
>
> >>> 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.

	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

Re: Concurrent access to /dev/urandom

[Kyle Moffett]

On Nov 29, 2004, at 21:31, David Schwartz wrote:
>> 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------

Re: Concurrent access to /dev/urandom

[Jan Engelhardt]

>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)?

>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
-- 
Gesellschaft für Wissenschaftliche Datenverarbeitung
Am Fassberg, 37077 Göttingen, www.gwdg.de

RE: Concurrent access to /dev/urandom

[David Schwartz]

> >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.
 
> >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

Re: Concurrent access to /dev/urandom

[David Wagner]

Jon Masters  wrote:
>On Sat, 27 Nov 2004 15:45:49 -0500, Bernard Normier <bernard@zeroc.com> wrote:
>> 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.

>/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.