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
>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, http://www.gwdg.de
> >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
>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, http://www.gwdg.de
>>> 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
On Sat, 27 Nov 2004 15:45:49 -0500, Bernard Normier <[email protected]> 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.
>> 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
Jon Masters wrote:
>On Sat, 27 Nov 2004 15:45:49 -0500, Bernard Normier <[email protected]> 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.
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/)
> 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
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------
>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, http://www.gwdg.de
> >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