6 ms·
Random number generator enhancements for Linux 5.17 and 5.18
- 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.
- nullc 5y agoSpeck supports configurations with keys small enough to be brute forcable. There is a nice attack pattern where you standardize something with some insecure modes, then you use targeted attacks to get your targets to use those insecure modes. I'm not aware of any non-NSA ciphers from the last decade that supports a 64-bit key...
- api 5y agoThis is a good point. They claim this is to support tiny devices but that would have to be a really tiny device for trimming 64 bits off a key to matter. The 128-bit and 256-bit key versions of Speck are probably fine, but...
- tptacek 5y agoThere's a cool paper that proposes embedding a NOBUS susceptibility to linear cryptanalysis in constants for ARX ciphers like SPECK (like SPECK, not SPECK), I should dig it up. Reliably demonstrating that capability would be an advancement in the state of the art of cryptography, though, as I understand it.
- whatshisface 5y ago(3) Speck is fine, but NSA wants to weaken the precedent of not trusting the cyphers it releases, to slip a bad one in later.
- Dylan16807 5y agoWanting a better reputation is an obvious motivator for 1. This isn't a separate option.
- saagarjha 5y ago> This is their MAIN WEAPON against massively used, fully E2E encryption. I’d say their main weapon is people continuing to not design their products around end-to-end encryption.
- creatonez 5y agoYup. Much of the Snowden and wikileaks reports revealed that the government is a lot more interested in getting your data before it's encrypted.
- matheusmoreira 5y agoI assume the cryptography community is also aware of these changes. I trust they would have voiced concerns if there were problems.
- deleted 5y ago[deleted]
- Zamicol 5y agoFantastic article. You're a great writer and I learned a lot. Thank you.
- 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?
- 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_...
- spiorf 5y agohttps://en.wikipedia.org/wiki/Dual_EC_DRBG https://en.wikipedia.org/wiki/Dual_EC_DRBG
- deleted 5y ago[deleted]
- 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
- 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.
- Archelaos 5y agoThe author's Web-site includes a repository of everything, including documentation, at https://git.zx2c4.com/linux-rng/tree/ https://git.zx2c4.com/linux-rng/tree/ -- Start with the README at https://git.zx2c4.com/linux-rng/tree/README https://git.zx2c4.com/linux-rng/tree/README
- 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.“
- 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.
- purkka 4y agoAES 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.)
- 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)
- 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?
- Dylan16807 5y agoYes because it already collected plenty of data from the mouse since boot.
- 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.
- 5y ago
- 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.
- 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.
- metadat 5y agoInterestingly, it seems the Jitter Dance has previously been discussed on HN quite a bit: https://hn.algolia.com/?dateRange=all&page=0&prefix=false&query=Jitter%20dance&sort=byPopularity&type=story https://hn.algolia.com/?dateRange=all&page=0&prefix=false&qu... Though this is the first time I recall hearing about it.
- 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.
- 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.
- 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.