5 ms·

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 13y 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 13y 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 13y 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 13y 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 13y 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.
        raverbashing 13y ago
        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
        mikeash 13y ago
        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 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.
        tptacek 13y ago
        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").
        raverbashing 13y ago
        True, unfortunately /dev/random blocking "soon" in Linux helps to propagate this myth. I stand corrected.
  - zatkin 13y ago
    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.
    - mmckeen 13y ago
      If there is only one process, then no spinlock contention, so no problem. The problem comes with multiple processes competing for the lock.
    - ef47d35620c1 13y ago
      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.
bodyfour 13y 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 13y 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 13y 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).

drsnyder 13y 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 13y 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 13y 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 13y 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 13y 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.
      - raverbashing 13y ago
        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
        mikeash 13y ago
        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 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.
        tptacek 13y ago
        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").
        raverbashing 13y ago
        True, unfortunately /dev/random blocking "soon" in Linux helps to propagate this myth. I stand corrected.
- zatkin 13y ago
  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.
  - mmckeen 13y ago
    If there is only one process, then no spinlock contention, so no problem. The problem comes with multiple processes competing for the lock.
  - ef47d35620c1 13y ago
    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.

bodyfour 13y 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 13y 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 13y 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).