8 ms·

urandom and concurrency

90 points by drsnyder 12y ago

rafekett 12y ago
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_generator http://en.wikipedia.org/wiki/Hardware_random_number_generato... exist
- kevingadd 12y ago
  A hardware RNG isn't going to do anything to address the scalability problems inherent in having a single shared lock around /dev/urandom.
- claudius 12y ago
  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.
- deleted 12y ago
  [deleted]
- jerf 12y ago
  /dev/urandom is not /dev/random.
Glyptodon 12y ago
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?
- drsnyder 12y ago
  Good question. The only reference to it that I could find was here http://lkml.iu.edu//hypermail/linux/kernel/0412.1/0181.html http://lkml.iu.edu//hypermail/linux/kernel/0412.1/0181.html but he doesn't explain why it's necessary.
  - gizmo686 12y ago
    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.
    - helper 12y ago
      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 http://golang.org/src/pkg/crypto/rand/rand_unix.go#L30
      - jerf 12y ago
        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.
        mikeash 12y ago
        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.
- bodyfour 12y ago
  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.
  - acqq 12y ago
    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?
    - claudius 12y ago
      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).
ape4 12y ago
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.
- frankfarmer 12y ago
  Simply initializing a curl handle causes the /dev/urandom read -- so a large number of parallel curl requests easily triggers this issue.
  - ape4 12y ago
    Thanks for the reply.
Mister_Snuggles 12y ago
A more important question would be "Why does asynchronous DNS resolution require random data in the first place?"
- mike-cardwell 12y ago
  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_resistance.pdf http://courses.isi.jhu.edu/netsec/papers/increased_dns_resis...
  - bch 12y ago
    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.
    - frankfarmer 12y ago
      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.
      - bch 12y ago
        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.
      - acqq 12y ago
aidenn0 12y ago
Seed a secure userspace PRNG from urandom, perhaps?
- hosay123 12y ago
  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
  - mcpherrinm 12y ago
    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.
    - raverbashing 12y ago
      Of course. But there are a lot of needs for random numbers that don't need the random numbers to be secure.
      - azinman2 12y ago
        In which case rand and the like really should be renamed unsecure_random to prevent confusion.
        raverbashing 12y ago
        Fine by me
      - 12y ago
sebcat 12y ago
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.
- drsnyder 12y ago
  The curl handle should be re-used if possible so that's also part of the problem.
mike-cardwell 12y ago
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);
- en4bz 12y ago
  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.
- aidenn0 12y ago
  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.
  - mike-cardwell 12y ago
    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.
    - ekimekim 12y ago
      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).
bcl 12y ago
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.git/tree/drivers/char/random.c?id=refs/tags/v3.15-rc1#n1365 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.
rcoh 12y ago
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 http://unixhelp.ed.ac.uk/CGI/man-cgi?rand+3
- ekimekim 12y ago
  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).
X-Istence 12y ago
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()...
- clarry 12y ago
  arc4random_buf() operates in userspace (in this case; it also exists in the kernel). It is seeded from the kernel, using a sysctl.
kijin 12y ago
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.

90 points by drsnyder 12y ago

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_generator http://en.wikipedia.org/wiki/Hardware_random_number_generato... exist

kevingadd 12y ago
A hardware RNG isn't going to do anything to address the scalability problems inherent in having a single shared lock around /dev/urandom.
claudius 12y ago
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.
deleted 12y ago
[deleted]
jerf 12y ago
/dev/urandom is not /dev/random.

Glyptodon 12y ago

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?

drsnyder 12y ago
Good question. The only reference to it that I could find was here http://lkml.iu.edu//hypermail/linux/kernel/0412.1/0181.html http://lkml.iu.edu//hypermail/linux/kernel/0412.1/0181.html but he doesn't explain why it's necessary.
- gizmo686 12y ago
  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.
  - helper 12y ago
    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 http://golang.org/src/pkg/crypto/rand/rand_unix.go#L30
    - jerf 12y ago
      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.
      - mikeash 12y ago
        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.
bodyfour 12y ago
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.
- acqq 12y ago
  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?
  - claudius 12y ago
    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).

ape4 12y ago

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.

frankfarmer 12y ago
Simply initializing a curl handle causes the /dev/urandom read -- so a large number of parallel curl requests easily triggers this issue.
- ape4 12y ago
  Thanks for the reply.

Mister_Snuggles 12y ago

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

mike-cardwell 12y ago
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_resistance.pdf http://courses.isi.jhu.edu/netsec/papers/increased_dns_resis...
- bch 12y ago
  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.
  - frankfarmer 12y ago
    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.
    - bch 12y ago
      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.
    - acqq 12y ago

aidenn0 12y ago

Seed a secure userspace PRNG from urandom, perhaps?

hosay123 12y ago
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
- mcpherrinm 12y ago
  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.
  - raverbashing 12y ago
    Of course. But there are a lot of needs for random numbers that don't need the random numbers to be secure.
    - azinman2 12y ago
      In which case rand and the like really should be renamed unsecure_random to prevent confusion.
      - raverbashing 12y ago
        Fine by me
    - 12y ago

sebcat 12y ago

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.

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

mike-cardwell 12y ago

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

en4bz 12y ago
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.
aidenn0 12y ago
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.
- mike-cardwell 12y ago
  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.
  - ekimekim 12y ago
    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).

bcl 12y ago

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.git/tree/drivers/char/random.c?id=refs/tags/v3.15-rc1#n1365 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.

rcoh 12y ago

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 http://unixhelp.ed.ac.uk/CGI/man-cgi?rand+3

ekimekim 12y ago
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).

X-Istence 12y ago

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

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

kijin 12y ago

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.