9 ms·

Random number generator updates for Linux 5.17

103 points by zx2c4 5y ago

CiPHPerCoder 5y ago
I am stoked for updating all my systems to use Linux 5.17 now.
zx2c4 5y ago
Commits of note in this pull: - https://git.kernel.org/pub/scm/linux/kernel/git/crng/random.git/commit/?id=9f9eff85a008b095eafc5f4ecbaf5aca689271c1 https://git.kernel.org/pub/scm/linux/kernel/git/crng/random.... - https://git.kernel.org/pub/scm/linux/kernel/git/crng/random.git/commit/?id=2ee25b6968b1b3c66ffa408de23d023c1bce81cf https://git.kernel.org/pub/scm/linux/kernel/git/crng/random.... - https://git.kernel.org/pub/scm/linux/kernel/git/crng/random.git/commit/?id=f7e67b8e803185d0aabe7f29d25a35c8be724a78 https://git.kernel.org/pub/scm/linux/kernel/git/crng/random....
- loeg 5y ago
  Do you have further plans / ideas for Linux random infrastructure enhancements? I’d love to hear about them.
  - zx2c4 5y ago
    The general idea is to clean things up piecemeal and gradually, until we've got a coherent design that's easy to reason about and enables us to then start working on proofs and formal verification, discussions with the academic cryptography community, and even test vectors. This initial pull request is mostly getting feet wet with fixes and low hanging fruits, but long term I'm interested in more comprehensive improvements. The thing is, with Linux development, these things tend to work their way in _gradually_, rather than totally radical rewrites. (If you recall, I tried the radical rewrite thing with my Zinc replacement [1] for the crypto API, which wasn't too well received.) So I'm definitely not looking to cause a ruckus, but I do really want to get this into good shape. Provably secure constructions and slow-but-steady work will hopefully be key in doing that. So, that may not the concrete answer perhaps you were hoping for, but that's a snapshot of my general approach. [1] https://www.youtube.com/watch?v=a9A80i6noLw https://www.youtube.com/watch?v=a9A80i6noLw
    - Genbox 5y ago
      Thank you for the contribution and for thinking about the issue as a fundamental one that has to be proven correct rather than hacking on it until it seems to work. The use of RDRAND was especially overzealous. The problem is always finding the line between retaining entropy and performance - in this case (without having done the statistics) I believe you have done the right thing. If I wanted to contribute an entropy mixer not based on CRC32 (as the current one is) that is much faster, includes test vectors and entropy analysis - where would be a good place to start?
1over137 5y ago
Headline seems overly generic: 5.17 of what?
- 0xJRS 5y ago
  I think they assumed that the reader would know 5.17 and (kernel.org) next to it would mean the Linux kernel
  - nicce 5y ago
    Yeah, Linux is the name of the kernel, not some distribution.
  - dr_zoidberg 5y ago
    Well it's the subject of the email sans the "[GIT PULL]" at the start. Maybe they just went with it for the title? It's been changed to "...for Linux 5.17" so it's clear now for those just reading the headlines.
tptacek 5y ago
Also discussed here: https://news.ycombinator.com/item?id=29742977 https://news.ycombinator.com/item?id=29742977
throw0101a 5y ago
For comparison: A random device appeared in FreeBSD 2.2. The implementation was changed to the Yarrow algorithm in FreeBSD 5.0. In FreeBSD 11.0, the Fortuna al- gorithm was introduced as the default. In FreeBSD 12.0, Yarrow was re- moved entirely. * https://www.freebsd.org/cgi/man.cgi?query=random&sektion=4 https://www.freebsd.org/cgi/man.cgi?query=random&sektion=4 * https://www.schneier.com/academic/fortuna/ https://www.schneier.com/academic/fortuna/ Also a video presentation "A Deep Dive into FreeBSD's Kernel RNG" from vBSD 2017: * https://papers.freebsd.org/2017/vbsdcon/gurney-a_deep_dive_into_freebsds_kernel_rng/ https://papers.freebsd.org/2017/vbsdcon/gurney-a_deep_dive_i...
- throwawaylinux 5y ago
  Do you have any idea about what Linux uses now, and how it differs from Fortuna? I must say (and I say this very much as a rabid Linux fanboy) that it bothered me a bit how Linux's random number generator for a long time did not appear to be developed to a particular published and reviewed specification, but rather it seemed to be a somewhat ad hoc affair. This might be completely mischaracterizing it unfairly, but that's just how it comes across. Does Linux's latest RNG design (which people say is finally good) conform to any mature and well analyzed and characterized published standard? I'm not asking if it uses standardized ciphers in particular stages, but whether the entire RNG follows a standard.
  - loeg 5y ago
    There are good reasons not to use Fortuna-as-written nowadays, so I don't fault Linux that. But it would be nice if someone familiar with the design published something like the Fortuna whitepaper, or Microsoft's Windows 10 RNG whitepaper[1]. (Why not use Fortuna as-written? The main reason is that it is not designed to scale. It's a reasonable design for the single core machines of the era when it was written, but it does not worry about contention at all. You could also swap out AES for Chacha as PRF, because: Chacha is faster to seed, faster to generate on machines without AES-NI, and doesn't have some of the theoretical problems -- discussed in the Fortuna chapter -- that AES has with its relatively small 128-bit blocks.) [1]: https://aka.ms/win10rng https://aka.ms/win10rng
stefanpie 5y ago
As a novice Linux (Ubuntu) user, I am curious as to how these new changes for rand will speed up a Linux distro overall or if there is even a way to measure this. It seems that, in addition to an overdue replacement SHA-1, the new code is a significant increase in performance. I would think that there are a lot of places where random used in the OS and this update would translate into performance improves in those other places. I'm not an expert and would love to head any thoughts on this.
- loeg 5y ago
  > As a novice Linux (Ubuntu) user, I am curious as to how these new changes for rand will speed up a Linux distro overall Totally negligible. It speeds up benchmarks of getrandom() and /dev/urandom, which is a good thing, but if you were spending any significant CPU there, it was due to an architectural problem that this doesn't solve. > It seems that, in addition to an overdue replacement SHA-1, the new code is a significant increase in performance. No, the big improvement is removing RDRAND (arch_get_random_long) from the hot path, which only existed on relatively fast x86 hardware. (The only other arch with a non-empty arch_get_random_long implementation was s390, a mainframe.) SHA1 to Blake is only used periodically (~0.003 Hz) and probably not noticeable.
  - Genbox 5y ago
    Encrypted file systems wants to have a word with you. :) I don't think it is hard to imagine an increase in throughput for disk encryption due to less time spent in the RNG.
    - loeg 5y ago
      I don’t believe this will make any appreciable difference for encrypted filesystems. AFAIK the popular scheme (XTS) does not heavily use the RNG.

103 points by zx2c4 5y ago

I am stoked for updating all my systems to use Linux 5.17 now.

Commits of note in this pull: - https://git.kernel.org/pub/scm/linux/kernel/git/crng/random.git/commit/?id=9f9eff85a008b095eafc5f4ecbaf5aca689271c1 https://git.kernel.org/pub/scm/linux/kernel/git/crng/random.... - https://git.kernel.org/pub/scm/linux/kernel/git/crng/random.git/commit/?id=2ee25b6968b1b3c66ffa408de23d023c1bce81cf https://git.kernel.org/pub/scm/linux/kernel/git/crng/random.... - https://git.kernel.org/pub/scm/linux/kernel/git/crng/random.git/commit/?id=f7e67b8e803185d0aabe7f29d25a35c8be724a78 https://git.kernel.org/pub/scm/linux/kernel/git/crng/random....

loeg 5y ago
Do you have further plans / ideas for Linux random infrastructure enhancements? I’d love to hear about them.
- zx2c4 5y ago
  The general idea is to clean things up piecemeal and gradually, until we've got a coherent design that's easy to reason about and enables us to then start working on proofs and formal verification, discussions with the academic cryptography community, and even test vectors. This initial pull request is mostly getting feet wet with fixes and low hanging fruits, but long term I'm interested in more comprehensive improvements. The thing is, with Linux development, these things tend to work their way in _gradually_, rather than totally radical rewrites. (If you recall, I tried the radical rewrite thing with my Zinc replacement [1] for the crypto API, which wasn't too well received.) So I'm definitely not looking to cause a ruckus, but I do really want to get this into good shape. Provably secure constructions and slow-but-steady work will hopefully be key in doing that. So, that may not the concrete answer perhaps you were hoping for, but that's a snapshot of my general approach. [1] https://www.youtube.com/watch?v=a9A80i6noLw https://www.youtube.com/watch?v=a9A80i6noLw
  - Genbox 5y ago
    Thank you for the contribution and for thinking about the issue as a fundamental one that has to be proven correct rather than hacking on it until it seems to work. The use of RDRAND was especially overzealous. The problem is always finding the line between retaining entropy and performance - in this case (without having done the statistics) I believe you have done the right thing. If I wanted to contribute an entropy mixer not based on CRC32 (as the current one is) that is much faster, includes test vectors and entropy analysis - where would be a good place to start?

1over137 5y ago

Headline seems overly generic: 5.17 of what?

0xJRS 5y ago
I think they assumed that the reader would know 5.17 and (kernel.org) next to it would mean the Linux kernel
- nicce 5y ago
  Yeah, Linux is the name of the kernel, not some distribution.
- dr_zoidberg 5y ago
  Well it's the subject of the email sans the "[GIT PULL]" at the start. Maybe they just went with it for the title? It's been changed to "...for Linux 5.17" so it's clear now for those just reading the headlines.

tptacek 5y ago

Also discussed here: https://news.ycombinator.com/item?id=29742977 https://news.ycombinator.com/item?id=29742977

throw0101a 5y ago

For comparison: A random device appeared in FreeBSD 2.2. The implementation was changed to the Yarrow algorithm in FreeBSD 5.0. In FreeBSD 11.0, the Fortuna al- gorithm was introduced as the default. In FreeBSD 12.0, Yarrow was re- moved entirely. * https://www.freebsd.org/cgi/man.cgi?query=random&sektion=4 https://www.freebsd.org/cgi/man.cgi?query=random&sektion=4 * https://www.schneier.com/academic/fortuna/ https://www.schneier.com/academic/fortuna/ Also a video presentation "A Deep Dive into FreeBSD's Kernel RNG" from vBSD 2017: * https://papers.freebsd.org/2017/vbsdcon/gurney-a_deep_dive_into_freebsds_kernel_rng/ https://papers.freebsd.org/2017/vbsdcon/gurney-a_deep_dive_i...

throwawaylinux 5y ago
Do you have any idea about what Linux uses now, and how it differs from Fortuna? I must say (and I say this very much as a rabid Linux fanboy) that it bothered me a bit how Linux's random number generator for a long time did not appear to be developed to a particular published and reviewed specification, but rather it seemed to be a somewhat ad hoc affair. This might be completely mischaracterizing it unfairly, but that's just how it comes across. Does Linux's latest RNG design (which people say is finally good) conform to any mature and well analyzed and characterized published standard? I'm not asking if it uses standardized ciphers in particular stages, but whether the entire RNG follows a standard.
- loeg 5y ago
  There are good reasons not to use Fortuna-as-written nowadays, so I don't fault Linux that. But it would be nice if someone familiar with the design published something like the Fortuna whitepaper, or Microsoft's Windows 10 RNG whitepaper[1]. (Why not use Fortuna as-written? The main reason is that it is not designed to scale. It's a reasonable design for the single core machines of the era when it was written, but it does not worry about contention at all. You could also swap out AES for Chacha as PRF, because: Chacha is faster to seed, faster to generate on machines without AES-NI, and doesn't have some of the theoretical problems -- discussed in the Fortuna chapter -- that AES has with its relatively small 128-bit blocks.) [1]: https://aka.ms/win10rng https://aka.ms/win10rng

stefanpie 5y ago

As a novice Linux (Ubuntu) user, I am curious as to how these new changes for rand will speed up a Linux distro overall or if there is even a way to measure this. It seems that, in addition to an overdue replacement SHA-1, the new code is a significant increase in performance. I would think that there are a lot of places where random used in the OS and this update would translate into performance improves in those other places. I'm not an expert and would love to head any thoughts on this.

loeg 5y ago
> As a novice Linux (Ubuntu) user, I am curious as to how these new changes for rand will speed up a Linux distro overall Totally negligible. It speeds up benchmarks of getrandom() and /dev/urandom, which is a good thing, but if you were spending any significant CPU there, it was due to an architectural problem that this doesn't solve. > It seems that, in addition to an overdue replacement SHA-1, the new code is a significant increase in performance. No, the big improvement is removing RDRAND (arch_get_random_long) from the hot path, which only existed on relatively fast x86 hardware. (The only other arch with a non-empty arch_get_random_long implementation was s390, a mainframe.) SHA1 to Blake is only used periodically (~0.003 Hz) and probably not noticeable.
- Genbox 5y ago
  Encrypted file systems wants to have a word with you. :) I don't think it is hard to imagine an increase in throughput for disk encryption due to less time spent in the RNG.
  - loeg 5y ago
    I don’t believe this will make any appreciable difference for encrypted filesystems. AFAIK the popular scheme (XTS) does not heavily use the RNG.