[HN Gopher] Linux RNG RFC Patch: implement getrandom() in vDSO
___________________________________________________________________
Linux RNG RFC Patch: implement getrandom() in vDSO
Author : zx2c4
Score : 72 points
Date : 2022-07-29 16:32 UTC (6 hours ago)
(HTM) web link (lore.kernel.org)
(TXT) w3m dump (lore.kernel.org)
| 10000truths wrote:
| Why not just have the kernel map a page containing random bytes,
| that it rewrites with newly seeded random bytes when needed? Then
| userspace CSPRNGs could use that as a basis for their own
| reseeding.
| quesomaster9000 wrote:
| How often do you reseed?
|
| How frequently does the kernel populate these pages with new
| entropy (for every process, pre-emptively?)
|
| Does this avoid pagefaults or other process interrupts? Don't
| want process interrupting every time it accesses the 'magic
| page of random'.
|
| Surely these are all pain points that Intel's `RDRAND` is
| supposed to alleviate.
| mjb wrote:
| Making providing high-quality randomness without compromises a
| first-class OS feature seems like a great idea. Especially
| because it reduces the chances of using a bad/incorrectly
| seeded/inadequately seeded/cloned from snapshot userspace
| cryptographic PRNG, and of using a non-cryptographic PRNG for
| cryptographic stuff.
|
| I'm a kernel expert, so I don't know if VDSO is the right
| implementation, but the idea seems sound. Make it harder for
| people to make mistakes that break security!
| mjb wrote:
| To clarify, I am _not_ a kernel expert.
| marcodiego wrote:
| For those who need it: vDSO is almost a hack that allows
| implementation of syscalls without context switch.
| onmobile2022 wrote:
| Slightly more verbose: it is an ELF library that is mapped into
| every process containing kernel code that runs (due to app
| calls) in userspace. Most often it works (like in the case of
| gettimeofday) by reading values from another shared memory
| segment mapped between the kernel and user space. Getting time
| just involves carefully ordered reading from that shared mem
| colmmacc wrote:
| This change makes me sad, not because it isn't brilliant work -
| it is - but because this kind of brilliant work is unlikely to
| move the needle in the real-world. I can't use this RNG because
| it isn't FIPS validated. I can't sponsor getting it FIPS
| validated because the cryptography it uses isn't even FIPS
| compatible. It wouldn't make it past the cursory skim of a
| reviewer. That says more about FIPS than it does this work, but
| it still means that it's a non-starter for many libraries and
| applications that end up having US Federal Government users ...
| which is to say that basically everything important gets pushed
| away from benefiting from work like this.
|
| Seperately, I'm also a little sad that there are no distinct RNGs
| for secret and non-secret output. It is an indispensable layer of
| defense to have separately seeded RNGs for these use-cases. That
| way if there is an implementation flaw or bug in the RNG that
| leads to re-use or predictability, it is vastly harder for that
| flaw to be abused. s2n, BouncyCastle, OpenSSL, and more user-
| space libraries use separately seeded RNGs for this reason and I
| don't think I could justify removing that protection.
| fweimer wrote:
| I don't see why this couldn't be validated if an approved DRBG
| is used instead.
| staticassertion wrote:
| > That says more about FIPS than it does this work
|
| It would be nice to have companies collectively reject FIPS. I
| realize that that's a pipe dream, but we do it with patents.
| Lots of companies pool their patents to defend against trolls
| on the condition that none of those companies sue each other
| over patent violations.
|
| If a bunch of companies were like "We won't require you to be
| FIPS, and we won't get FIPS" or something that'd be cool.
| Unfortunately, that can't happen with FIPS specifically as it's
| government mandated, but idk, maybe SOC2 or something?
|
| I hate things so much
| yjftsjthsd-h wrote:
| That's not really a fault of Linux or the 'real world', that's
| government entities intentionally holding themselves back. I'm
| not even saying that's a terrible thing - gov't work is a good
| place to require audited security options! - but that's the
| tradeoff they've chosen.
| gerdesj wrote:
| "unlikely to move the needle in the real-world"
|
| FIPS does not impinge on me in any way whatsoever - that's my
| real world and that's the real world for a darn sight larger
| number of people than ... Americans.
|
| I note your secret/non secret discussion for RNGs and that
| seems to be a good idea - many non FIPS standards also have a
| dichotomy like that or something more complicated. However,
| separately seeded pools reduces the entropy available
| (IANACryptographer) that's a trade off of some sort that I'm
| not qualified to assess.
|
| This work is done by people I respect and I will evaluate it
| according to the standards I have to adhere to. None of those
| standards is FIPS. I'm not quite in a cargo cult state but I
| have to take a certain amount of things on trust when it comes
| to this stuff!
| tptacek wrote:
| On the other hand, there's the FIPS-accelerationist
| perspective, which suggests that as more and more modern
| cryptography is mainstreamed irrespective of FIPS silly
| requirements, FIPS will itself gradually become untenable,
| leaving us all better off.
| oittaa wrote:
| I'm not a cryptographer so disregard my opinions as you
| please, but I really like OpenSSH's approach. They just
| implement whatever the cryptographer community thinks is the
| best approach at the moment and disregard NIST and other
| authorities. For example they already have a post quantum key
| exchange as one of the default algorithms.
| hinkley wrote:
| For lower-stakes streams of random data, like such as
| unguessable patterns in video games (or perhaps in Monte Carlo
| simulations for a Chess or Go engine), CSPRNGs are a common
| solution here.
|
| You bite off a chunk of data from the RNG and use it as the
| seed for a sequence based on a cryptographic hash, relying on
| the non-repeating qualities of these algorithms to give you a
| convincing random data stream that is not necessarily suitable
| for generating cryptographic keys.
|
| The problem here, if there is one, is that if you implemented
| your RNG source as just reading from a file descriptor, the
| subsequent bite of that proverbial sandwich gets the entire
| tomato slice and most of the lettuce. If the language you
| picked already abstracts /dev/random, then it's just a couple
| lines of code difference for you. If not, well then welcome to
| the wide world of cryptography APIs, friend.
| cesarb wrote:
| > I can't use this RNG because it isn't FIPS validated. I can't
| sponsor getting it FIPS validated because the cryptography it
| uses isn't even FIPS compatible. It wouldn't make it past the
| cursory skim of a reviewer. [...] but it still means that it's
| a non-starter for many libraries and applications that end up
| having US Federal Government users
|
| But how do these user-space libraries get the entropy for their
| RNG? If they read it from /dev/random or /dev/urandom or call
| getrandom(), it's the _exact same algorithm_.
|
| To put it another way: even though this is running in user
| mode, it's not a user-space library; it's part of the Linux
| kernel, which happens to be running in user mode. If for some
| reason you need to make getrandom() use FIPS algorithms, you
| already have to patch the kernel, and when doing so you'd patch
| this code to match. Because this code _is_ the getrandom()
| system call, which like a couple of other "fast" system calls
| like gettimeofday(), is implemented partially in user mode and
| partially in kernel mode.
| thayne wrote:
| Possibly, it uses `/dev/random` or `/dev/urandom` to seed
| (and periodically re-seed) a userspace implementation of a
| FIPS validated PRNG.
| fweimer wrote:
| I expect that most vendors carry downstream kernel patches
| with an approved algorithm, so that the kernel can still be
| used as an entropy source.
| colmmacc wrote:
| Usually those libraries seed from a FIPS-validated hardware
| entropy source. AES-NI is a common one, it's validated on
| some chips, but other hardware vendors have others (we have a
| hardware RNG in the AWS Nitro System for example). FIPS
| specifies a handful of DRBG algorithms that can then be used.
| AES-CTR-DRBG is the most popular. That's definitely no the
| exact same algorithm as the ChaCha/Blake constructions in
| Jason's work. It's all rather carefully constructed and then
| checked as part of the validation process. This is probably
| the most common reason for userspace RNGs in cryptographic
| software.
| cipherboy wrote:
| Every major Linux distro ships FIPS crypto libraries that
| seed from the Linux kernel; the source is available.
| a-dub wrote:
| > hyperspeed card shuffling
|
| i think that's mostly scientific computing where you want the
| ability to control the RNG and even intentionally use
| deterministic seeds for reproducibility.
|
| i think if the kernel is going to provide secure random numbers
| (which seems like a good idea), it should be through a (new)
| specific system call that fails unless a hardware entropy
| facility is available. performance seems like a secondary goal,
| where the primary is ensuring that people are using the right
| thing to generate keys and such.
| secondcoming wrote:
| I think you need reproducible RNGs for financial modelling
| audits.
| comex wrote:
| On many operating systems, including macOS and Windows, the only
| ABI-stable interface is a userland-to-userland interface.
| Application code loads a shared library vended by the system and
| calls functions from that library like open() or CreateFileW(),
| in userland. These functions are in turn are usually thin
| wrappers around system calls with equivalent argument lists - but
| not always, and even when they are, it's only an implementation
| detail. Trying to call system calls directly without going
| through the wrappers risks incompatibility with future OS
| versions, e.g. [1].
|
| On Linux, traditionally, the userland-kernel interface itself is
| ABI-stable. The userland code can be fully custom and doesn't
| even need to support dynamic linking. Syscall numbers and
| arguments are fixed, and application code can perform its own
| syscall instructions. You can then layer something like glibc on
| top of that, which provides its own syscall wrapper functions
| with a corresponding stable (userland-to-userland) ABI, but
| that's separate.
|
| The vDSO has always been a step away from that. It's userland
| code, automatically mapped by the kernel, that provides its own
| system call wrappers. Applications are still allowed to make
| system calls manually, but they're encouraged to use the vDSO
| instead. Its original purpose was to allow certain functions such
| as gettimeofday() to be completed in userland rather than
| actually performing a syscall [2], but it's been used for a few
| other things. It's worked pretty well, but it does have the
| drawback that statically linked binaries no longer control all of
| the code in their address space. This, for instance, caused a
| problem with the Go runtime [3], which expected userland code to
| follow a certain stack discipline.
|
| Anyway, this patch seems to me like a significant further step.
| Not just putting an RNG into the vDSO, which is more complicated
| than anything the vDSO currently does, but also essentially
| saying that you _must_ use the vDSO 's RNG to be secure (to quote
| the RFC, "userspace rolling its own RNG from a getrandom() seed
| is fraught"), and explicitly choosing not to provide stable APIs
| for custom userland RNGs to access the same entropy information.
|
| I don't think that's necessarily a bad thing. It's not _that_
| complicated, and to me, macOS ' and Windows' approach always
| seemed more sensible in the first place. But it's a step worth
| noting.
|
| [1] https://github.com/jart/cosmopolitan/issues/426
|
| [2] https://man7.org/linux/man-pages/man7/vdso.7.html
|
| [3] https://marcan.st/2017/12/debugging-an-evil-go-runtime-bug/
| tptacek wrote:
| Just for the sake of clarity: the claim is that you must use
| getrandom, somehow, to be secure, or maybe more specifically
| "you are almost certainly not secure if you roll your own
| CSPRNG". Even before the vDSO, I think one would have made the
| same claim about getrandom.
| comex wrote:
| > Just for the sake of clarity: the claim is that you must
| use getrandom, somehow, to be secure, or maybe more
| specifically "you are almost certainly not secure if you roll
| your own CSPRNG".
|
| Right; more accurately stated, you must use the vDSO's RNG to
| securely get random numbers _quickly_.
|
| > Even before the vDSO, I think one would have made the same
| claim about getrandom.
|
| Because of VM forks. But an alternative would be to expose VM
| fork events more explicitly to userland, so custom RNGs can
| take them into account.
|
| And I'm not sure that fixing the RNG, without providing a
| generic way for userland code to take forks into account, is
| enough to avoid all vulnerabilities. After all, there will
| always be a window between generating random numbers and
| using them. As a dumb example, suppose a DSA implementation
| first picks a random nonce, then reads the data to be signed
| from some external source. If the VM forks in between those
| actions, and the two forks choose different data to be
| signed, you're in trouble no matter how good the RNG is.
|
| I said it's a dumb example because there's an obvious fix
| (picking the nonce after the data to be signed). But as a
| nonexpert, I'd be kind of surprised if there wasn't _some_
| cryptographic protocol where forking midway through operation
| is inherently insecure, and the only solution is to abort and
| retry. Heck, couldn 't that apply to TLS?
|
| Actually, I see that Jason submitted an earlier patch [1]
| that does provide explicit fork events. I don't know whether
| this vDSO patch is meant as a replacement or a complement.
|
| [1] https://www.spinics.net/lists/linux-crypto/msg63759.html
| mustache_kimono wrote:
| Nowhere near an expert, but this seems like a bad idea?
| [deleted]
| zx2c4 wrote:
| It's kind of wild, yea. I'd rather not do it. But if it's
| between unsafe userspace implementations and this thing, this
| thing is better. Maybe people will decide they don't care about
| hyperspeed card shuffling or whatever else. But if they do,
| this is an attempt to provide it safely.
| deathanatos wrote:
| > _hyperspeed card shuffling_
|
| The article mentions this case too. getrandom() on my system
| seems to return the required amount of random bits to perform
| a shuffle of a deck in less time than my clock seems to have
| precision for; ... that's ... too slow?
| AlotOfReading wrote:
| There are cases where you want tons of random numbers (e.g.
| monte carlo) and the line between "good enough" and
| "disastrously bad" is often unclear. Providing
| cryptographic random numbers is the only possible API
| that's both safe and generic.
|
| As the post says, it's worth entertaining the idea of
| having the kernel provide a blessed way for userspace to do
| that, though I admit I've never personally seen a scenario
| where RNG was truly the bottleneck. But it'd still be nice
| to kill all the custom RNGs out there.
| kzrdude wrote:
| Don't you always want a reproducible random sequence for
| such simulations? I.e you use getrandom for the initial
| seed only, record it, and do the rest of your RNG state
| in userspace code?
| nneonneo wrote:
| I guess my biggest concern here is the notion that vDSO is
| going to manage the state in user space, if I understand
| correctly. That seems like a big footgun.
|
| If I call the getrandom system call, and it succeeds, I am
| (pretty much) guaranteed that the results are properly random
| no matter what state my userspace program might be in.
|
| With vDSO, it seems we lose this critical guarantee. If a
| memory corruption occurs, or my process's memory contents can
| be disclosed somehow (easier to do against a userspace
| process than against the kernel!), I don't have truly random
| numbers anymore. Using a superficially similar API to the
| system call for this seems like a really bad idea.
| sophacles wrote:
| The vDSO page is mapped without write though, just r and x.
| saagarjha wrote:
| If you have memory corruption in your process, what makes
| you confident your program state will let you do something
| useful with the randomness you get back from getrandom()?
| nneonneo wrote:
| I guess my concern is with "silent" memory corruption,
| e.g. someone putting in a "bzero(state, ...)" by accident
| and winding up with deterministic randomness. Sure, they
| could also just as well do a "bzero(randombuf, ...)"
| before using it but that's much easier to detect (and in
| my head, somewhat harder to do by accident).
|
| Silly mistakes like the Debian randomness bug come to
| mind - a program can be totally well-behaved even in the
| face of a glaring entropy failure, in a way that's hard
| for developers to detect.
| saagarjha wrote:
| I guess? I mean, I see "something overflowed on the stack
| and into my randomness buffer" as being similarly common
| and about as undetectable. That's not to say we shouldn't
| invest in making APIs that are harder to misuse even if
| you hold them incorrectly, but I'm not sure the benefits
| are very compelling here.
| zx2c4 wrote:
| > If a memory corruption occurs, or my process's memory
| contents can be disclosed somehow (easier to do against a
| userspace process than against the kernel!), I don't have
| truly random numbers anymore.
|
| Yea, that's definitely a downside of sorts. Jeffrey Walton
| mentioned that in the glibc discussion a few days ago:
| https://lore.kernel.org/linux-
| crypto/CAH8yC8n2FM9uXimT71Ej0m...
|
| A mitigating factor might be that if your process memory
| leaks, then the secrets generated leak anyway, no matter
| what generated them, so maybe not as large of a difference.
| But of course a generator leaking means future secrets
| potentially leak too. I suppose frequent reseeds could
| mitigate this, just as they do for potential leaks in the
| kernel.
|
| But anyway, I agree that compromising application memory is
| somewhat more possible than compromising kernel memory,
| though both obviously happen.
| rogers18445 wrote:
| There is always the option to reseed userspace PRNG with with
| getrandom() regularly. This makes userspace PRNG safe and more
| versatile than getrandom().
| LukeShu wrote:
| The article specifically addresses why this is a bad idea.
| rogers18445 wrote:
| And it's wrong. If you initialize your own PRNG properly with
| multiple reseeds you saturate the entropy pool of your PRNG
| and subsequent reseeds are only relevant for ratcheting and
| state compromise proofing.
|
| This assumes you aren't starved for entropy on
| initialization. If you are, it would imply a constrained
| environment and you are better off using getrandom() then.
| tptacek wrote:
| There is no such thing as being "starved for entropy", once
| you've hit whatever threshold you require for considering
| your RNG to be seeded in the first place.
| rogers18445 wrote:
| If your PRNG state is is x bits, if you initialize it
| with less than x bits of entropy you are starved.
|
| Since you cannot know how many bits of entropy
| getrandom() would give you and when it itself is reseeded
| with fresh entropy, you usually have your userspace PRNG
| sample getrandom() for some amount of time, after which
| it is considered initialized.
| amluto wrote:
| > you usually have your userspace PRNG sample getrandom()
| for some amount of time, after which it is considered
| initialized.
|
| Who is "you"? Calling getrandom() extra times to get
| extra bits on the hope that the result is magically
| better is entirely useless.
| rogers18445 wrote:
| There is no magic. If entropy got injected in between
| getrandom() calls you get that entropy - it does not
| matter if the entropy is cryptographically scrambled and
| 'merged' into the kernel PRNG state.
|
| All you have to do is 'merge'/'absorb' multiple
| getrandom() results over some time t into your userspace
| PRNG, with t big enough to allow for multiple reseeding
| events by the kernel. You are in effect getting samples
| of the new entries into the kernel entropy pool
| indirectly by doing this, sampling too frequently is
| wasteful however as you are just going to be sampling the
| kernel CSRPNG with the same entropy in its state most of
| the time.
|
| Doing the above is actually the only way to properly seed
| your userspace CSPRNG if your userspace CSPRNG has a
| state larger than the kernel CSPRNG (kernel's is 512 bits
| I believe) otherwise you will be working with a 512 bits
| of entropy as an absolute maximum even if your CSPRNG is
| capable of holding more, at least until reseeding (both
| the kernel and the userspace PRNG).
| jepler wrote:
| It was the discussion of the situation with cloned virtual
| machines that convinced me, not this.
| fweimer wrote:
| This is what the patch does. It does not handle the case of VM
| resume yet. Fork safety is achieved through a generic mechanism
| that any userspace generator could use. The advantage the vDSO
| has is that it can assume that MADV_WIPEONFORK is implemented,
| but that's about it.
|
| The vDSO-based approach is certainly interesting because the
| kernel can know exactly where randomness caches are located and
| zap them as needed (on fork, periodically, after VM resume).
| But if entire pages of memory are dedicated to buffers anyway,
| MADV_WIPEONFORK is sufficient for now.
| fefe23 wrote:
| This looks like an excellent idea. I will implement support for
| it in my libc immediately when it's available in a release
| kernel.
|
| Currently userspace has incentive to roll their own RNG stuff.
| This removes that, which is good for everyone. The less incentive
| you give people to write code that has already been written by
| other, more experienced people, the better.
|
| I would go even further and export the kernel ciphers via vDSO.
| Then user space could rely on those ciphers being optimized for
| the host CPU and side channel free instead of everybody bringing
| their own crypto primitives. I don't think there is a good reason
| why gnupg and openssl would bring different crypto primitives.
| thadt wrote:
| Isn't there already userspace access to the kernel's crypto
| machinery?
|
| https://www.kernel.org/doc/html/latest/crypto/userspace-if.h...
___________________________________________________________________
(page generated 2022-07-29 23:00 UTC)