Random number generator enhancements for Linux 5.17 and 5.18
zx2c4.com
zx2c4.com
Edit: re-reading the document, it seems to imply (considering the buffer size) that the output they are using is 128 bytes.
> 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-...
Or for some other discussion https://blog.cryptographyengineering.com/2015/01/14/hopefull...
It's still secure in a way that, for example a cipher that in theory gives you a security guarantee or margin of 160 bits (which means assuming no further reseeding you need around 2^160 bits before losing security guarantees) is reduced to around 128 bits (which means assuming no further reseeding you now only need around 2^128 bits before losing security guarantees). It shouldn't happen in practice (constant reseeding) but some symmetric ciphers paired with CTR_DRBG (Triple DES) makes reading its state a lot easier, especially on systems where they don't frequently reseed (note that this algorithm was invented in the late '90s, so practices now seen as obvious security blunders aren't being avoided).
> 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.
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.
(Also, the 128-byte buffer therefore contains 8 blocks; I believe the size is chosen more for performance than security reasons.)
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....
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.
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.
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.
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.
“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.“
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.
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.
I can totally see how it would feel sort of comforting though. I hadn't thought about it before but it does remind me of old Springer texts, and I could see how that would feel "homey" or something. This conversation has me kind of "resetting" my perspective on it a bit.
I used uBlock customization to block the font from loading to read the article.
For those on Mozilla Firefox[note], please also give the reader view a try.
Reader view is also available on other browsers such as Safari on the iPhone.
[note] - (if you are not on it, please consider downloading and using it but that is a different conversation)
Also, Computer Modern on the same screen, but rendered by Okular or Evince, when viewing a LaTeX document, is also perfectly legible.
When it is rendered properly, I find it very pretty and legible.
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. :)
is it really ridiculous?
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.
Needs an update now, it contains numerous facts that are no longer true.
Alongside BLAKE2 algorithmic improvements, we also get safer infrastructure. Very cool!
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.
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".)
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.
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.
Can anyone provide a specific explanation for why some of platforms can extract entropy from scheduling jitter and others can’t?
https://hn.algolia.com/?dateRange=all&page=0&prefix=false&qu...
Though this is the first time I recall hearing about it.
I recall using Haveged to prevent RNG from blocking on machines without hwrng (i.e. VMs) on old kernels.
> 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.
Truly random data is incompressible. Any alogirithm should work.
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
[2] https://safecurves.cr.yp.to/rigid.html
[3] https://www.hyperelliptic.org/tanja/vortraege/20130531.pdf
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.
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.
But there are also some fairly unambiguous improvements - switching from SHA1 to BLAKE2 for extracting the random bytes for example.
- 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.