10 ms·
Random number generator enhancements for Linux 5.17 and 5.18
- oofbey 5y agoI 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.
- corvettez0606 5y agoWith these kind of changes I always wonder if they make the product more secure or less secure.
- Cthulhu_ 5y agoIt'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).
- stbenjam 5y agoThe backdoored elliptical curves were vetted too…
- ObscureScience 5y agoI've not been in the loop, what was this?
- spiorf 5y agohttps://en.wikipedia.org/wiki/Dual_EC_DRBG https://en.wikipedia.org/wiki/Dual_EC_DRBG
- tovej 5y agohttps://en.wikipedia.org/wiki/RSA_Security#NSA_Dual_EC_DRBG_backdoor https://en.wikipedia.org/wiki/RSA_Security#NSA_Dual_EC_DRBG_...
- aaronmdjones 5y agoCompromised approved (subsequently retracted) elliptic curve random number generator [1] Potentially-compromised elliptic curves used for Diffie-Hellman-Merkle key agreement and digital signatures [2][3][4] [1] https://en.wikipedia.org/wiki/Dual_EC_DRBG https://en.wikipedia.org/wiki/Dual_EC_DRBG [2] https://safecurves.cr.yp.to/rigid.html https://safecurves.cr.yp.to/rigid.html [3] https://www.hyperelliptic.org/tanja/vortraege/20130531.pdf https://www.hyperelliptic.org/tanja/vortraege/20130531.pdf [4] https://blog.cr.yp.to/20140323-ecdsa.html https://blog.cr.yp.to/20140323-ecdsa.html
- deleted 5y ago[deleted]
- zahllos 5y agoDual EC DRBG is the known backdoored curve. You have the links to the high level story in a sibling comment. I would also like to add, however, that the possibility of a backdoor was patented by Scott Vanstone I think, and raised in NIST standardization process (and I suspect standardized under pressure from the NSA more than anything). Other negative facts that were raised include the fact that it sucks badly, i.e. compared to just about any other RNG, it performs very poorly. So the process isn't as bad as it looks. DualEC was a backdoor, but not a very good one. People noticed the possibility and it sucks compared to literally anything else. The only people who used it appear to be customers of RSA Inc. I would also like to add that Elliptic (not Elliptical, these are not the equations of ellipses) Curves, even the NIST ones, are not known to be backdoored and there's no evidence they contain any weaknesses at present. There are plenty of non-American cryptographers who are unlikely to keep any analysis a secret if they found such evidence, and I would say quite a few American ones who would also publish.
- spiorf 5y agoAnd we know about it. The backdoor methods have been generalized and now researchers can check for that too. For example bitcoin's elliptic curve secp256k1 was choosen because its constants were chosen in a predictable way and that reduces the possibility of a backdoor.
- bspammer 5y agoAs 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 5y agoYes, 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 5y agoWith this and Wireguard Jason is hitting it out of the park. I wonder what's next.
- tptacek 5y agoIn this case, more.
- OscarCunningham 5y agoI 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 5y agoI first assumed it was a PDF and when I got to the video thought "Wait, browsers do video-in-pdf now?"
- XCSme 5y agoSame, 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 5y agoIf 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 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 5y agoIt 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.
- dataflow 5y agoIn case anyone's interested in how Windows behaves for the sake of comparison, see: https://aka.ms/win10rng https://aka.ms/win10rng
- zinekeller 5y agoNote 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.
- mkj 5y agoAnd the author of this MS paper is who first publicised the potential Dual_EC_DRBG backdoor years before it was outed by Snowden.
- e40 5y agoOuted in what way?
- zinekeller 5y agoOn the Possibility of a Back Door in the NIST SP800-90 Dual EC-PRNG (2007, Shumow and Ferguson, https://rump2007.cr.yp.to/15-shumow.pdf https://rump2007.cr.yp.to/15-shumow.pdf)
- mkj 5y agoOuted by the memos he leaked: > Classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency. The N.S.A. wrote the standard and aggressively pushed it on the international group, privately calling the effort “a challenge in finesse.” From https://www.propublica.org/article/the-nsas-secret-campaign-to-crack-undermine-internet-encryption https://www.propublica.org/article/the-nsas-secret-campaign-... Or for some other discussion https://blog.cryptographyengineering.com/2015/01/14/hopefully-last-post-ill-ever-write-on/ https://blog.cryptographyengineering.com/2015/01/14/hopefull...
- gillesjacobs 5y agoGreat 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!
- creatonez 5y 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 5y ago> The "Jiggle your mouse to generate encryption key" ridiculousness is now a thing of the past is it really ridiculous?
- creatonez 5y agoYes. 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/ 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.
- loeg 5y agoThe mouse-jiggling might remain valid for initial seeding / unblocking in an environment without other random sources (including Torvalds' version of jitterentropy), but it's hard to imagine those are anything but theoretical.
- Xarodon 5y ago> https://www.2uo.de/myths-about-urandom/ https://www.2uo.de/myths-about-urandom/ Needs an update now, it contains numerous facts that are no longer true.
- pulse7 5y ago
- creatonez 5y ago> The past has shown that often the USA government/NSA sponsored or developed encryption algorithms used in many popular devices This sort of unfounded conspiratorial thinking is absurd. The past has shown the opposite, that whenever government tries to shove broken algorithms down people's throats, cryptographers ignore it and go for something they can prove is correct. BLAKE2 and ChaCha20 are algorithms designed by cryptographers that hate the government.
- nsajko 5y ago> This sort of unfounded conspiratorial thinking is absurd. GP's baseless accusations indeed are distasteful. > cryptographers ignore it and go for something they can prove is correct. BLAKE2 and ChaCha20 are algorithms designed by cryptographers BLAKE2 is based on ARX, so proofs regarding some of its properties are very difficult or infeasible, as far as I understand. It is my understanding that other designs are much more popular among cryptographers because they are mathematically and financially easier to analyze, implying better security (because nation-state-level resources aren't necessary for finding vulnerabilities). See, e.g.: https://keccak.team/2017/not_arx.html https://keccak.team/2017/not_arx.html
- api 5y agoWild-ass speculation alert! Please don't turn into FUD. NSA floated a cipher a while back called Speck. https://en.wikipedia.org/wiki/Speck_(cipher) https://en.wikipedia.org/wiki/Speck_(cipher) After the dual-EC debacle it's understandable that people would be skeptical of a cipher from the NSA. People assumed Speck might be intentionally weak or backdoored. Thing is... it's a stupid simple ARX cipher. Dual-EC was obviously suspect for multiple reasons, but Speck is so simple it doesn't really have room for any "magic" constants that could have been optimized to introduce a back door or vulnerability. That means there are two possibilities: (1) Speck is fine. (2) The NSA knows something about ARX ciphers that we don't. Option #1 is orders of magnitude more likely than option #2, but if we are entertaining wild speculation there's some for you.
- deleted 5y ago[deleted]
- exfil 5y agoWhat 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.
- Zamicol 5y agoFantastic article. You're a great writer and I learned a lot. Thank you.
- lizardactivist 5y agoLooking 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 5y agofont on the page is awful
- mcpherrinm 5y agoThe 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 5y agoRight, 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 5y 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.
- er4hn 5y agoAny comments about how related the Linus Jitter Dance (btw, glad to see that djb isn't the only one making new dance moves..) is to JitterRNG: https://www.chronox.de/jent.html https://www.chronox.de/jent.html ? The PDF linked to on the page goes into more detail but that is measured across a number of CPUs and has good performance in both amount and entropy quality produced. You do need to measure it per CPU, but it does comply with SP 800-90B which is what the US Gov considers the standards for randomness.
- chocological 5y agoThe "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/ 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 5y agoJason, I'm very happy to see you contributing excellent work to the Linux kernel. Keep up the good work!
- loeg 5y agoIt'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.