Random number generator enhancements for Linux 5.17 and 5.18

https://www.zx2c4.com/projects/linux-rng-5.17-5.18/

by CyberRabbi • 4 years ago

242 83 4 years ago

With these kind of changes I always wonder if they make the product more secure or less secure.

Cthulhu_• 4 years ago

It's why I'm thankful it's both open source and highly scrutinized by the community, both volunteers, independent security researchers, and big companies like Google that deploy billions of instances of Linux (servers, google cloud, android, chromeOS, etc).

blcknight• 4 years ago

The backdoored elliptical curves were vetted too…

bspammer• 4 years ago

As Jason mentions, the most important contribution here is to make the code more readable and improve documentation.

But there are also some fairly unambiguous improvements - switching from SHA1 to BLAKE2 for extracting the random bytes for example.

mkesper• 4 years ago

Yes, I think there's some points we can generalize for all software there:

- Readability counts. If you can't read the code, who could test or improve it?

- Documentation needs to be cared for near the code, only then you have a chance it's not outdated

- It's possible to improve correctness and efficiency at the same time (if your code is understandable)

- Use the literature available

- Code once holding high standards will need to be checked constantly too so it doesn't rot.

ape4• 4 years ago

With this and Wireguard Jason is hitting it out of the park. I wonder what's next.

tptacek3• 4 years ago

In this case, more.

OscarCunningham3• 4 years ago

I know it's an HN cliche to talk about the website instead of the content, but I really like the LaTeX look and I want to know how it was done.

m4lvin• 4 years ago

I first assumed it was a PDF and when I got to the video thought "Wait, browsers do video-in-pdf now?"

XCSme• 4 years ago

Same, I thought it was a PDF.

This is actually an interesting approach, make the website look like a text document but enrich it with web functionalities (videos, interactions). It looks very clean/minimal and distraction-free, excellent to read/learn content like this.

Someone• 4 years ago

If they support a somewhat recent version of PDF, they’ll have to; PDF itself can contain video. https://helpx.adobe.com/acrobat/using/rich-media.html:

“Adding video, sound, and interactive content transforms PDFs into multidimensional communication tools that increase interest and engagement in your documents.

All multimedia that are H.264 compliant can be played back in Adobe Reader 9 and later. (H.264, also known as MPEG-4 part 10, is a video compression standard that provides high-quality video without substantially increasing file size.) Video files of varying formats and filename extensions can be H.264 compliant.

Media files in other formats can be played back in earlier versions of Adobe Reader. However, users must install the appropriate application (such as QuickTime or Windows Media Player) to play the multimedia.

Another way to add multimedia is by entering a URL that refers to a video file or streaming media. Three types of URLs can be used: RTMP, HTTP, and HTTPS. On HTTP and HTTPS servers, H.264-compliant MOV and MP4 files are supported.“

imhoguy• 4 years ago

It is very compact CSS and embedded web fonts e.g. "LM Roman", just check the source of page html>head>style tag. Pure minimalism art - I love it too.

pahae• 4 years ago

I've been using something similar: https://github.com/vincentdoerig/latex-css Seems like it could easily be adapted to match the style.

Archelaos• 4 years ago

The author's Web-site includes a repository of everything, including documentation, at https://git.zx2c4.com/linux-rng/tree/ -- Start with the README at https://git.zx2c4.com/linux-rng/tree/README

throw0101a• 4 years ago

[…] but I really like the LaTeX look and I want to know how it was done.

Except that it's fully justified and the spacing between words is horrendous. Seems that no one can get Knuth & Plass right (at least online); maybe because there's no hyphenation / word breaking.

Probably best to just stick with left justified / ragged right.

OscarCunningham3• 4 years ago

There is word breaking though. At my screen width, 'overhauled' is broken in the second paragraph.

derbOac2• 4 years ago

Lol. I was going to comment when there were only two or so others that I really dislike the font used on the website.

I loathe the old school Latex look. I appreciate Latex as a markup language, but the computer modern fonts always drove me nuts.

To each their own though. It's interesting to me that someone else had the opposite reaction.

OscarCunningham3• 4 years ago

I'm a mathematician, so it might be that it's calmingly familiar rather than any typographical excellence.

vngzs• 4 years ago

If you haven't, check it out from a high DPI printer. The font is much more tolerable there.

I used uBlock customization to block the font from loading to read the article.

majewsky• 4 years ago

Computer Modern fonts are very much designed for printing. On a screen, the really narrow parts of each letter are usually close to unbearable.

salmo• 4 years ago

Tangentially, I do use a LaTeX inspired Hugo theme[1].

It’s not perfect, but I like it. I worked on math textbooks and LaTeX as a side gig in college and it’s very comfortable for me.

Probably off putting to a non nerd audience, but it’s a self indulgent site, so whatever.

A LaTeX static site generator could be cool itself. I markdown so much these days it might be refreshing to revisit my past. One day I’ll Google that, I guess. :)

[1] https://github.com/queensferryme/hugo-theme-texify

dataflow• 4 years ago

In case anyone's interested in how Windows behaves for the sake of comparison, see: https://aka.ms/win10rng

zinekeller4• 4 years ago

Note that while CTR_DRBG is totally different from the similar-sounding Dual_EC_DRBG (which is widely suspected of being backdoored), CTR_DRBG has some flaws (being a counter-based design) that allows insecure or secure-but-lower-than-expected-randomness depending on the symmetric cipher used. It seems that it uses AES-256, but depending on whether it takes 224 or 256 bytes of output per round is not discussed on the document (counterintuitively, taking only 224 bytes is slightly more secure than taking the whole 256 bytes).

Edit: re-reading the document, it seems to imply (considering the buffer size) that the output they are using is 128 bytes.

mkj2• 4 years ago

And the author of this MS paper is who first publicised the potential Dual_EC_DRBG backdoor years before it was outed by Snowden.

Aardwolf• 4 years ago

How is secure-but-lower-than-expected-randomness actually possible? I thought being indistinguishable from true random is one of the requirements of a CSPRNG

loeg5• 4 years ago

They use a buffer of 128 bytes for small requests. Larger requests come directly from AES_CTR_DRBG:

There is a small buffer (currently 128 bytes). If a request for random bytes is 128 bytes or larger, it is generated directly from AES_CTR_DRGB. If it is smaller than 128 bytes it is taken from the buffer.

At least, that's my read of it.

tptacek3• 4 years ago

I'm not sure if any of these concerns are really practical. NIST does a great job of making CTR_DRBG sound complicated, but it's pretty close to the simplest possible CSPRNG: it's just a block cipher in CTR mode, which is pretty close to the theoretical simplest secure CSPRNG.

It's true that if you use DES-EDE or something with CTR_DRBG, you have all the problems that come from use a short block with CTR mode --- but if you can reason about how to use CTR mode, you can I think reason about the limitations you'll run into with CTR_DRBG.

You're not getting insecure randomness from AES CTR_DRBG.

purkka• 4 years ago

AES always has a 128 bit (16 byte) block size; AES-256, AES-192 and AES-128 only change the key size.

(Also, the 128-byte buffer therefore contains 8 blocks; I believe the size is chosen more for performance than security reasons.)

belter• 4 years ago

I know Microsoft claims to have corrected many of the issues raised here but do they have a formal response to it? Do we even care?

Cryptanalysis of the Random Number Generator of the Windows Operating System https://eprint.iacr.org/2007/419.pdf

Cryptanalysis of the Windows Random Number Generator https://www.cs.huji.ac.il/~dolev/pubs/thesis/msc-thesis-leo....

zinekeller4• 4 years ago

They acknowledged that the Windows 2000 design was also used in XP (https://www.computerworld.com/article/2539986/microsoft-conf...), but Vista and above used NIST algorithms defaulting to CTR_DRBG, although the problematic Dual_EC_DRBG (which was flagged by their own cryptographers as problematic: https://rump2007.cr.yp.to/15-shumow.pdf) was present until the Snowden revelations.

Windows 10's (and 11 and probably above) implementation of CTR_DBRG is different from Vista-8 though, mainly in the entropy generation and the switch from AES-128 to AES-256.

loeg5• 4 years ago

The 2007 papers predate the Win10 design linked by the grandparent comment. I haven't read the 2007 criticisms recently, but have read the Win10 design many times. I don't think there's anything objectionable in the current design.

Edit: I guess the criticism about the generator running in user mode is still true, although I don't think it's the flaw the authors do. Also, I think the current design adds forward-secrecy / key erasure vs the criticism mentioned in the 2007 paper. I believe the O(2^23) attack described is gone now.

tptacek3• 4 years ago

It's a good paper, but note that this is an attack on the (old) per-process RC4-based WRNG, not on CTR_DRBG. The attack essentially observes that if you get RCE on a Windows process and capture the WRNG state, you can get all previous and future states bounded by when the per-process WRNG reseeds (the seeding process reads random bytes from KSecDD, a sort of Windows equivalent of /dev/random).

The Windows design is interesting in that it runs a userland CSPRNG for each process, rather than a single kernel RNG like Linux/Unix provides, but still binds those RNGs to the kernel RNG. This seems like a good idea at first, but turns out not to be: the attack wouldn't be possible if KSecDD was the entire CSPRNG interface for Windows.

gillesjacobs• 4 years ago

Great to see as much thought is put in infrastructure as in the improved cryptographic logic. They removed the /dev/urandom and the virtual machine cloned entropy that cause unsafe randomness.

Alongside BLAKE2 algorithmic improvements, we also get safer infrastructure. Very cool!

creatonez2• 4 years ago

/dev/urandom and /dev/random interfaces present the exact same interface -- The "Jiggle your mouse to generate encryption key" ridiculousness is now a thing of the past!

hansel_der• 4 years ago

The "Jiggle your mouse to generate encryption key" ridiculousness is now a thing of the past

is it really ridiculous?

creatonez2• 4 years ago

Yes. The /dev/random device would formerly refuse to continue giving data even when it had plenty of entropy backing it. The reality is, unless you are in early boot (now fixed by Torvald's RNG seeder) you have enough entropy to generate nearly unlimited quantities of pseudorandom numbers without revealing much of the PRNG's internal state. You only need 256 bits of initial seed entropy to be virtually unpredictable, as long as those 256 bits are strong.

See: Myths about /dev/urandom https://www.2uo.de/myths-about-urandom/

Jiggling the mouse may have made feel better about the security of the software they're using, but really should have been considered a bug (and the UI, a horrible workaround) this whole time.

Now that /dev/random no longer exists, and the kernel now has Torvalds' cache timings based seeder, any software that mistakenly uses it will generate a key instantly regardless of how much mouse jiggling you do.

throwawayninja• 4 years ago

I imagine the people most burned by that design run / remote into servers.

Dylan16807• 4 years ago

Yes because it already collected plenty of data from the mouse since boot.

exfil• 4 years ago

What would be best way to evaluate randomness quality? This is something I've been thinking a lot. Yes, there are 'ent' and others, but I am more after trend of randomness quality over weeks and months.

loeg5• 4 years ago

https://github.com/usnistgov/SP800-90B_EntropyAssessment

Xarodon3• 4 years ago

Compress it.

Truly random data is incompressible. Any alogirithm should work.

jwilk• 4 years ago

Random data is incompressible, but not everything incompressible (as far as practical compression algorithms are concerned) is random.

Zamicol• 4 years ago

Fantastic article. You're a great writer and I learned a lot. Thank you.

lizardactivist• 4 years ago

Looking through the code, and am surprised to see just how much it takes to provide a secure source of RNG in an operating system.

slk500• 4 years ago

font on the page is awful

mcpherrinm• 4 years ago

The jitter dance mentioned in here is pretty interesting. It doesn't seem obvious to me that a deterministic CPU running a deterministic scheduler is going to yield randomness.

But hopefully any modern system has some kind of hardware RNG and the "jitter dance" is just a last-resort type thing for strange systems.

mjw1007• 4 years ago

Right, I'm surprised to be reading justifications that amount to "it's been deployed for several years now, so we think it's OK", rather than "here's a report from a researcher who's tested how it behaves on a wide range of systems".

I don't know enough to count myself as a "skeptic", but if I try to apply the test "suppose in ten years time you're reading a news report describing how this feature failed to work as intended; is it easy to imagine the sort of things it could be saying?", the jitter dance doesn't do terribly well.

(I'm imagining something like the case where large numbers of consumer routers ended up generating the same secret on first boot, or perhaps large numbers of virtual machines. And there seem to be lots of ways to imagine a processor that had surprisingly little jitter: maybe an x86 emulator for Arm, or a "Big/Little/Tiny" processor, or "Spectre is really truly absolutely mitigated now we promise".)

zx2c4• 4 years ago

I'm surprised to be reading justifications that amount to "it's been deployed for several years now, so we think it's OK",

I'm not making any claims or justifications about it being good or not. Just a simple statement that Linus put it there, and there it is, and it's been that way for a while. I even referred to it as "voodoo". As I mentioned in the post, 5.18 didn't change anything about entropy sources and gathering. Certainly trying to see more rigorously whether or not the Linus Jitter Dance is defensible would make for a worthwhile research project.

CyberRabbi2• 4 years ago

I haven’t looked into it but from what I’ve read from various sources, not every platform can extract entropy from that process. I took that to mean that the CPUs on which the jitter dance is employed are not entirely “deterministic.” Well of course they are but they must be carrying black box state that affects execution that, so far, is impossible to extract without knowing the full execution trace up to that point.

Can anyone provide a specific explanation for why some of platforms can extract entropy from scheduling jitter and others can’t?

whatshisface5• 4 years ago

Imagine running a Linux kernel on a fully deterministic CPU emulator. The jitter would be the same on every boot.

metadat• 4 years ago

Interestingly, it seems the Jitter Dance has previously been discussed on HN quite a bit:

https://hn.algolia.com/?dateRange=all&page=0&prefix=false&qu...

Though this is the first time I recall hearing about it.

oofbey• 4 years ago

I love taking these deep tech dives to appreciate how much thought and complexity goes into something seemingly as simple as random numbers. I know they're critically important for security - which truly is high stakes - so I'm not surprised. But it's fun and impressive nonetheless.

chocological• 4 years ago

The "Linus Jitter Dance" mentioned in the article is similar to Havaged, you can read more about it here: http://www.irisa.fr/caps/projects/hipsor/

I recall using Haveged to prevent RNG from blocking on machines without hwrng (i.e. VMs) on old kernels.

samgranieri• 4 years ago

Jason, I'm very happy to see you contributing excellent work to the Linux kernel. Keep up the good work!

loeg5• 4 years ago

It's great to see Linux adopting VMgenid. RDSEED over RDRAND when available also makes sense.

In the per-cpu extension of that design, all entropy is extracted to a “base” crng. Then, each time a per-cpu crng is used, it makes sure that it is up to date with the latest entropy in the base crng. If it is, then it continues on doing fast key erasure with its own key. If it isn’t, then it does fast key erasure with the base crng’s key in order to derive its new one.

Beautiful. This is essentially the same thing the Windows 10 design does in the kernel.

Random number generator enhancements for Linux 5.17 and 5.18

Related Stories