Linux /dev/urandom and concurrency | Hacker News Reader

urandom and concurrency

drsnyder.us

90 pointsdrsnyder78 comments

If your program needs to read 4K from /dev/urandom multiple times per second, you're doing it wrong. There is little benefit in reading anything over 32 bytes at a time.

According to the man page for /dev/random and /dev/urandom:

> no cryptographic primitive available today can hope to promise more than 256 bits of security, so if any program reads more than 256 bits (32 bytes) from the kernel random pool per invocation, or per reasonable reseed interval (not less than one minute), that should be taken as a sign that its cryptography is not skillfully implemented.

So why is there a lock for reads from urandom? I suppose if there weren't a lock concurrent reads would all get the same random values?

Good question. The only reference to it that I could find was here http://lkml.iu.edu//hypermail/linux/kernel/0412.1/0181.html but he doesn't explain why it's necessary.

From the mail:

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

I guess that means all go applications that use crypto/rand are considered misdesigned then[1].

[1]: http://golang.org/src/pkg/crypto/rand/rand_unix.go#L30

If you're using crypto/rand to yank a whole bunch of random numbers out for the purpose of deciding which DNS record to use when multiple DNS records were returned, yes, the Go application is misdesigned. Such applications should be using math/rand. Seeding your math/rand from crypto/rand isn't a bad idea, but you don't need to be hammering on /dev/urandom in such code.

You don't need to be, but why not? It should be plenty fast and work well. If it's turning out to be too slow due to too much locking, that should be fixed.

1 - Rand is faster

2 - You don't need the crypto qualities of it and you're emptying the entropy pool for nothing

3 - You're doing much more work, especially if you're reading one byte at a time from /dev/urandom (doing a syscall, etc), while rand is just a calculation

1 and 3 are the same thing. I think the best way to address these, if performance is a problem (don't optimize what doesn't need it) is buffering to reduce syscalls, and optimizing the kernel implementation to fix the sort of internal performance problems like the link describes.

For 2, entropy pool depletion is a fictitious problem if you're worried about security. Some discussion here:

https://news.ycombinator.com/item?id=7361694

If you're worried about blocking apps that use /dev/random, the answer there is to fix them to use /dev/urandom so they don't block.

There is in practice no such thing as "entropy depletion". The retail side of a CSPRNG is very similar to a stream cipher. The idea behind "entropy depletion" is structurally the same as the idea of a stream cipher "depleting its key". You can run AES-CTR as a stream cipher for several exbibytes before the output starts becoming distinguishable (which is not the same thing as "reveals the key").

True, unfortunately /dev/random blocking "soon" in Linux helps to propagate this myth. I stand corrected.

Yes, it should be fixed. Yes, it's still a "misdesign" to use the cryptographic random number generator when you just want "a" psuedo-random number, right now. For choosing which of the several DNS answers you use, you could pretty much get away with keeping a counter and returning that counter modulo the number of choices. It's technically wrong for several reasons, but you could get away with it. That's how low-impact this random number usage is. Using a cryptographically secure random number generator for that is always going to be overkill for such a task.

There are lots of applications that require a cryptographically secure random number generator, which math/rand doesn't claim to be.

This is not one of them.

And while that's interesting from the perspective of fetching web content via curl (and kudos to the author tracing it down to that), that doesn't mean the fundamental issue shouldn't be fixed.

In the current security environment, from heartbleed to the NSA, it's becoming clear that security issues need to be systematically dealt with from an industry perspective or people will start to lose faith in secure Internet communication, which would undermine too much of what's valuable about the Internet.

What we need is great APIs/frameworks/design patterns to simplify cryptography so that a newbie ruby on rails programmer CAN create actually secure applications and not even realize that it was complicated in the first place.

In cryptography you make one misstep and the entire chain is broken. It's thus important for things like the linux kernel to provide great implementations so that people don't think twice about using it and never want their own PRNG.

Are you also suggesting that the kernel provide a "great implementation" of SHA? Of SSL? Of https? Where do you draw the line?

There's no reason for the kernel to provide standard library functions. In fact, I'd argue that syscalls should be reserved for only actions that cannot be done wholly in userspace (futex is a good example of this). The current model of "hardware randomness to seed a PRNG" makes sense. It is up to the userspace libraries to provide good implementations.

I would draw the line somewhere between SHA and SSL. Next question? ;)

Exactly. I thought it was pretty clear that I was talking about the kernel providing great crypto (read: random) by default for the things it already provides.

Similarly there's a need for great "APIs/frameworks/design patterns" for what the kernel doesn't provide. I predict over the next 5 years this will become a far bigger priority in how people develop software and thus use libraries.

Why does kernel have to be "fixed" if anything in the current "APIs/frameworks/deseign patterns" is not doing its own homework?

It seems the author admits in the comments: "All the application needs to do is open a socket and generate a GET request." So why complaining about the kernel?

If there's problem with urandom, demonstrate it on the reasonable use case example, don't try to impress anybody by showing how much different libraries, modules and programs you combine for one key-value query.

This "some random data is more important then other random data" musical chair dance going on with /dev/random vs /dev/urandom vs userland [CS]PRNGs (often gathering from extremely poor sources, or using broken algos) has been nothing short of an unmitigated security and useability disaster.

We have the abillity to make the /dev/urandom CSPRNG secure enough and fast enough for (almost) any randomness purpose. We need to cut all the rest of this insane crap.

People choose the wrong RNGs and get burned, or wont use the right ones because of speed or imaginary entropy exhaustion issues. This matters.

Yes. Exactly this.

It's impossible (or just not worth the trade-off) to make one piece of software (this time, kernel) fast for any use case imaginable. In this case, kernel behaved correctly but with the speed degradation for extreme cases. That the author's Rube Goldberg machine then runs slow I don't consider kernel to be guilty.

The guy uses PHP and instead of built-in HTTPRequest he uses curl to make a request to "a bucketed key-value store built on PostgreSQL that speaks HTTP which uses Clojure and the Compojure web framework to provide a REST interface over HTTP." A bit of shooting the flies with cannons on every side?

On another side, if it can be proved that urandom has serious problems in reasonable use cases it should be checked what can be changed and how.

Slightly off topic, but I wanted to clear this up:

> The guy uses PHP and instead of built-in HTTPRequest he uses curl to make a request

HTTPRequest is not built-in to PHP. It is a PECL extension that is usually installed separately from PHP.

Curl is more built-in to PHP - it's a PHP compile-time flag, and it is distributed with PHP source.

So the best approach for the given problem (just send the request, fetch the response, without too much overhead) seems to be using something a bit lower level:

http://at2.php.net/stream_socket_client

> It's impossible (or just not worth the trade-off) to make one piece of software (this time, kernel) fast for any use case imaginable.

We're not nearly at the theoretical limit of what /dev/urandom can provide.

Exactly. Most developers are about as good at picking RNGs as end-users are at picking passwords. We need to stop asking them to make that choice.

So, would a possible solution be to check how many people are using the random generator at once? If only one process is currently accessing /dev/urandom, then avoid the spinlock and problem solved. Or, I am completely wrong.

If there is only one process, then no spinlock contention, so no problem.

The problem comes with multiple processes competing for the lock.

Would a possible solution be to check how many people are using the random generator...?

One preson may have multiple processes reading from /dev/urandom.

Yeah basically. That could be a disaster for, say, nonce generation.

The solution would be to have multiple independent entropy pools and either bind them to cores(/sets of cores) or pick a non-busy one in a contention case.

Yes, if there is no a urandom generator per core, it would be convenient for some extreme cases to introduce such. The question is if it's worth the effort and the resulted "bloat" of the kernel code and memory usage. Linux runs on some very small devices too and even there decent user-space programmers can easily do their own per-thread generation in their programs. Normal uses of crypto are such: you initialize your own crypto once, then produce a lot of data in your own space.

If urandom is really "one for all cores" somebody should be able to demonstrate the speed drop by just writing some bash script? Volunteers?

It seems to work in part. For /dev/urandom, I see always roughly the same throughput:

  $ time dd if=/dev/urandom of=/dev/null bs=1 count=10000000
  real	0m10.640s
  user	0m0.696s
  sys	0m9.940s

  $ time (for i in $(seq 1 50); do dd if=/dev/urandom of=/dev/null bs=1 count=200000 2>/dev/null & done; wait)
  real	0m11.199s
  user	0m1.232s
  sys	0m42.828s

  $ time (for i in $(seq 1 500); do dd if=/dev/urandom of=/dev/null bs=1 count=20000 2>/dev/null & done; wait)
  real	0m11.234s
  user	0m1.252s
  sys	0m42.536s

whereas for /dev/zero:

  $ time dd if=/dev/zero of=/dev/null bs=1 count=10000000
  real	0m3.268s
  user	0m0.660s
  sys	0m2.604s

  $ time (for i in $(seq 1 50); do dd if=/dev/zero of=/dev/null bs=1 count=200000 2>/dev/null & done; wait)
  real	0m2.550s
  user	0m1.192s
  sys	0m8.760s

  $ time (for i in $(seq 1 500); do dd if=/dev/zero of=/dev/null bs=1 count=20000 2>/dev/null & done; wait)
  real	0m2.612s
  user	0m1.228s
  sys	0m8.112s

Of course, the bash for-loop here together with the forking has some considerable overhead, so these values should likely be interpreted carefully (Linux 3.14-rc7, Core i5 520M).

As a user of libcares (which is awesome for bulk DNS lookups btw) I'll add that I've only ever needed one ares_channel per process. Having one ares_channel for every CURL-handle seems a bit excessive. This is probably the main problem here, not the kernel spinlock.

Edit: Come to think about it, why isn't the CURL-handle reused? Sounds like a new CURL-handle is inited for every request, which I don't recall being necessary.

The curl handle should be re-used if possible so that's also part of the problem.

A more important question would be "Why does asynchronous DNS resolution require random data in the first place?"

So you can randomise the ID in the request packet to help protect against cache poisoning. And also so you can apply 0x20 bit (x) encoding to the qname for further protection.

(x) http://courses.isi.jhu.edu/netsec/papers/increased_dns_resis...

Hard to say w/o seeing the data in question, but based on that, perhaps nscd or re-using curl handles could mitigate their frustration w/ runtime.

the c-ares init (which reads /dev/urandom) inside curl init happens even when DNS isn't used at all (even when making a request to 127.0.0.1), so it's pretty hard to avoid as long as curl is built with c-ares. The only way to mitigate is to remove c-ares or limit calls to curl init.

Ah... I've worked a lot w/ libcurl, and a bit w/ c-ares, but don't fully know how c-ares works w/i curl. Thanks for the rundown.

Re: "limit calls to curl init" -- do you mean curl_easy_init() ? In that case, reusing handles (eg:

  CURL  *handle

) would mitigate that, no?

Edit: This doesn't make sense. c-ares relationship must be in curl_easy_perform(). Now I'm curious:

  1) Am I correct re: c-ares / curl_easy_perform()
  2) Can one reuse CURL *handle and not invoke c-ares and /dev/urandom if one reuses the same domain name (but not necessarily the same URL) within a handle.

Isn't the solution exactly what is described here:

http://curl.haxx.se/libcurl/c/curl_easy_init.html

"If you did not already call curl_global_init(3), curl_easy_init(3) does it automatically. This may be lethal in multi-threaded cases, since curl_global_init(3) is not thread-safe, and it may result in resource problems because there is no corresponding cleanup."

I can imagine that only curl_global_init reads from urandom? Your application should do curl_global_init only once, then do other fetches each time using just curl_easy_init and cleanup.

We're using libcurl via PHP (I know, I know) which doesn't expose curl_global_init at all.

Here's the stacktrace for the /dev/urandom read -- it's happening in curl_easy_init.

   Catchpoint 1 (call to syscall 'ioctl'), 0x0000003a74ecc4ba in tcgetattr () from /lib64/libc.so.6
   (gdb) backtrace
   #0  0x0000003a74ecc4ba in tcgetattr () from /lib64/libc.so.6
   #1  0x0000003a74ec7a1c in isatty () from /lib64/libc.so.6
   #2  0x0000003a74e60d51 in _IO_file_doallocate_internal () from /lib64/libc.so.6
   #3  0x0000003a74e6d6dc in _IO_doallocbuf_internal () from /lib64/libc.so.6
   #4  0x0000003a74e6ba7c in _IO_file_xsgetn_internal () from /lib64/libc.so.6
   #5  0x0000003a74e61dd2 in fread () from /lib64/libc.so.6
   #6  0x0000003341606414 in ares_init_options () from /usr/lib64/libcares.so.2
   #7  0x0000003d3404f0c9 in ?? () from /usr/lib64/libcurl.so.4
   #8  0x0000003d340242a5 in ?? () from /usr/lib64/libcurl.so.4
   #9  0x0000003d3402f9a6 in curl_easy_init () from /usr/lib64/libcurl.so.4
   #10 0x00002b35e0304fb0 in ?? () from /usr/lib64/php/modules/curl.so
   #11 0x0000000000606da9 in ?? ()
   #12 0x00000000006456b8 in execute_ex ()
   #13 0x00000000005d2bba in zend_execute_scripts ()
   #14 0x00000000005769ee in php_execute_script ()
   #15 0x000000000067e44d in ?? ()
   #16 0x000000000067ede8 in ?? ()
   #17 0x0000003a74e1d994 in __libc_start_main () from /lib64/libc.so.6
   #18 0x0000000000422b09 in _start ()
   (gdb)

I just guess, but maybe the things missing in the stack trace (marked with ?? -- maybe you miss some debug symbols?) do what is described in the manual entry I've quoted (calling global init which calls ares?).

And why curl at all? PHP has built in HTTPRequest?

HTTPRequest isn't technically built in to PHP.

I agree that they aren't using the correct technology for their use case though.

Yes, being a C programmer I knew curl is overkill, but not what's the best lightwieght alternative, now I believe it's:

http://at2.php.net/stream_socket_client

curl_global_init() really ought to be called on module load, before any (eg) set handle = curl::new is presented to a module user. And ea. curl::new call out to curl_easy_init(), will bypass global init again w/ this first line of code:

   if(initialized++)
    return CURLE_OK;

Correct?

IDs of requests?

choosing random UDP source port

Seed a secure userspace PRNG from urandom, perhaps?

Adding to aidenn0's comment, if you trust /dev/urandom to produce 4kb of random data, it follows that you trust it to produce 128 bits.

128 bits (32 bytes) is sufficient to initialize a PRNG into any one of 115792089237316195423570985008687907853269984665640564039457584007913129639936 states (that's 1 with 77 digits). Consequently, hitting the kernel constantly for so much data is utterly inefficient in the first instance, and totally unnecessary in the second.

Blog author could improve his design's efficiency >128x just by seeding a PRNG with a single 32 byte read at the start of the subprocess

Userland PRNGs are one of the easiest ways to introduce security vulnerabilities into your programs. I would recommend being very, VERY careful before trying to do this, like the traditional "Don't roll your own crypto" advice.

Of course. But there are a lot of needs for random numbers that don't need the random numbers to be secure.

In which case rand and the like really should be renamed unsecure_random to prevent confusion.

Fine by me

Most developers don't know how to make that distinction, and even savvy ones know better than to take the risk of being wrong.

It's 2014. There are well-funded governments and organized crime attacking our systems. If downstream developers still have to ask the question, "what kind of random numbers does this API provide?", then it's a bug in the platform.

Only in this case you aren't rolling your own crypto, but (hopefully) using a popular, field-tested CSPRNG available as a library for your language of choice. Unless you mistakenly pick a non-cryptographic PRNG, and assuming the implementation is correct (which is just as true of kernel code as it is of user code), I fail to see how you would introduce a vulnerability.

If you care about security, avoid this approach; it creates an additional single point of failure, which historically has also tended to be a very likely point of failure (see: Debian randomness, Android Java SecureRandom, &c).

Interestingly enough, I have actually been working on writing a DNS client library in C++ with Boost ASIO this very afternoon. I was going to get my source of random data using the following C++11 standard library code. I would really appreciate any comments from people here if there is anything wrong with what I'm doing:

  #include <random>
  std::uniform_int_distribution<uint32_t> dist;

  // Seed a Mersenne twister PRNG with random data:
  std::mt19937 eng;
  std::random_device rd;
  eng.seed(dist(rd));

  // Now to generate random numbers, simply:
  uint32_t random_number = dist(eng);

I don't know what DNS uses the randomness for, but if a malicious attacker can gain from guessing the randomness, don't use MT, as the state can be extracted from MT by observing a relatively small number of outputs.

Ah. You appear to be right. I'm glad I asked now.

[edit] I'm going to skip using the Mersenne twister engine and just use std::random_device for all random data, instead of as a seed. It seems on Linux at least that random_device is basically /dev/urandom. I assume the source will be sane on other OS's too.

Please don't do this. This exact approach is what caused the problems described in the article.

If you need secure random numbers, do what you had above (though in light of other comments, perhaps consider a different algo besides MT).

This is a recommendation that says that a developer should actually consider using the Mersenne Twister for secure random numbers to avoid a potential performance problem.

The C++ standard gives little guarantees for the quality of std::random_device. As I remember, MinGW on Windows uses the Mersenne Twister with a hardcoded seed for it.

boost::random_device, on the other hand, has better guarantees: it is only implemented where there's a decent entropy source.

Thanks for the info. Seeing as I'm already using boost, that sounds very useful.

I believe you would use it to determine a random outgoing port to use to contact the DNS server; this prevents spoofing. However, the port space is only 16-bits, so how you map the outputs of the MT into that space would have the biggest impact -- but you're right that's it's probably best to avoid it entirely.

You also use it for randomising the 16 bit ID in the request packet, and you can use it for randomly capitalizing letters in the qname (0x20 bit encoding). Both of these to help protect against spoofing.

    std::random_device rd;
    std::mt19937 rng(rd()); //Construct with random seed. 
    uint32_t random_number = dist(rng);

Since only the seed value comes from `rd` you should be fine if you suspected the results from the article would affect you. What was most likely happening in the article was constant use of `rd` without a prng.

The stdlib rand() function on unix has a global lock around it provided by many versions of Linux. As such, if rand() is called in performance critical parallel code, performance will tank as each thread or process attempts to acquire this lock. Even if this lock is not acquired, you will still have a race condition on the state of the random number generator and may produce bad (non-random) randomness.

Use rand_r(unsigned int *state) instead in parallel and concurrent applications.

Sources: man 3 rand [unix command] http://unixhelp.ed.ac.uk/CGI/man-cgi?rand+3

The problem you're describing is similar but not the same as the one in the article. What you describe is part of the libc implementation of rand(3), whereas the article is talking about reads from /dev/urandom, which has a lock inside the kernel code (for the same reasons as libc).

I love how Theodore Ts'o suggests using a user space PRNG that is seeded from /dev/urandom. OpenBSD are ripping out all of the user space PRNG stuff from OpenSSL in favour of arc4random_buf()...

arc4random_buf() operates in userspace (in this case; it also exists in the kernel). It is seeded from the kernel, using a sysctl.

Why does he need so much pseudorandomness. And why use /dev/urandom directly. Maybe using the random library from the programming environment would make more sense.

Simply initializing a curl handle causes the /dev/urandom read -- so a large number of parallel curl requests easily triggers this issue.

Thanks for the reply.

overreliance on /dev/urandom in the presence of little entropy is a well known performance problem on servers. that's why http://en.wikipedia.org/wiki/Hardware_random_number_generato... exist

A hardware RNG isn't going to do anything to address the scalability problems inherent in having a single shared lock around /dev/urandom.

If I understand that problem correctly, it has nothing to do with the amount of entropy available but is a simple synchronisation/locking issue. Were reads from, say, /dev/zero ‘protected’ by spinlocks in the same way, the same issue would arise. Conversely, I don’t see how adding a hardware RNG to the system could alleviate the locking issue.

/dev/urandom is not /dev/random.

The code he pointed to is for kernel 2.6.18 which at this point could be considered ancient history. If you look at current master - https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux....

it looks like it has been re-factored somewhat, although the lock is still in there.

Reply on news.ycombinator.com