Post by @hipsterelectron@circumstances.run

@hipsterelectron@circumstances.run 5 hr. ago

so becausse the 1978 pohlig-hellman paper mentioned that one of knuth's taocp books had the sunzi remainder theorem they used, i finally cracked and opened up the knuth 1998 sorting and searching text

15 Replies

4 Boosts

This comment is unavailable — it may have been deleted or is not visible to you.

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

this next part is a brilliant fucking idea, please get ready (cc @somebody):

if a supervisor process wants to expose a namespace to other processes, it can do it in two ways, by exposing either:
- just the public key, which strictly supports read-only views of resources in that namespace
- the whole keypair (public & private), which allows the recipient to request named resources in that namespace which can mutate data (and therefore can communicate with others who have access to that namespace)

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

@somebody i can't fucking believe how naturally that corresponds to the unambiguous trust relationships of public-key cryptography (or to be precise: it maps specifically to the subgroup of unambiguous trust relationships in PKC--not all PKC is unambiguous lol). cc @ireneista

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

finally, how would we use this to support structured communication? well, in order to mimic an FHS system, i would create an i/o sync domain (essentially a chroot) with standard [readonly] executables mapped to /usr/bin/* (i would probably use busybox since coreutils is not a safe dependency anymore sadly).

the first supervisor process is the init system itself! but i'm thinking i would probably try to build that minimal busybox FHS into the initramfs. maybe i wouldn't even share the private key for that with the actual init system, so even an evil PID 1 written by lennart poettering can't modify its contents with evil calls to dlopen()

Filesystem Hierarchy Standard

This standard consists of a set of requirements and guidelines for file and directory placement under UNIX-like operating systems. The guidelines are intended to support interoperability of applications, system administration tools, development tools, and scripts as well as greater uniformity of documentation for these systems.

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

oh and in fact i just changed my mind about several things at once:

all types of shared memory mapping capabilities should require providing the file descriptor to map--this should be mutually exclusive with the standard file i/o interface
any attempts to use write() or read() on the same descriptor after conversion to a shared memory mapping will fail with a specific implementation dependent error code (e.g. EIO or EPERM or whatever)
we don't need a separate feature for anonymous memory mappings if we already have a process-local i/o sync domain by default
- i.e. instead of doing an anonymous mapping, you can just create a new file that you own, and that produces an anonymous mapping since no data is shared outside of the process's **filesystem i/o virtual memory space**

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

this immediately achieves incredible benefits for shell script robustness. instead of e.g. relying upon autoconf's polyfill for mktemp, or having to create a miniature build system to calculate invalidation against file checksums, a shell script can just use the entire filesystem available to it as scratch space, and only produces output artifacts others can see by requesting a communication vector capability!

compare to e.g. m4_maketemp(): https://www.gnu.org/savannah-checkouts/gnu/autoconf/manual/autoconf-2.72/html_node/Redefined-M4-Macros.html#index-m4_005fmaketemp-1

Posix requires maketemp to replace the trailing ‘X’ characters in template with the process id, without regards to the existence of a file by that name, but this a security hole. When this was pointed out to the Posix folks, they agreed to invent a new macro mkstemp that always creates a uniquely named file, but not all versions of GNU M4 support the new macro. In M4sugar, m4_maketemp and m4_mkstemp are synonyms for each other, and both have the secure semantics regardless of which macro the underlying M4 provides.

that last line i bolded was from paul eggert, who fucking rox my sox

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

note that there is no need to request a capability or to allocate anything outside of the standard POSIX interface in order to read from stdin or write to stdout/stderr. that's because POSIX i/o streams are already both anonymous and linearizable: exactly the properties we need!

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

this approach would change some things about shell scripts. for example, under this model, providing a path to another file (e.g. as a command-line argument) would require:

explicitly constructing a new i/o sync domain (i.e. chroot) by cloning another one, then splicing the desired file into the desired path
invoking the subprocess with a modified form of posix_spawn() which accepts a named i/o sync domain to construct the process in

one way to make this more ergonomic is to simply propagate a CoW copy of the i/o sync domain of the parent process into the subprocess by default! this would actually be exactly right!

#!/bin/sh

# This modifies the shell interpreter's local i/o state:
echo 'hey' > wow.txt

# This forks off a CoW i/o sync domain first,
# before spawning a `wc` subprocess that
# automatically sees the file we just created! 
wc -c wow.txt
# => 4

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

finally, this raises the question: when does an i/o sync domain get "named"? because i think we have now just described a system of automatic anonymous i/o sync domains by CoWing from the parent process (this obviously sounds like fork(), but i absolutely do not believe it should be merged with fork() as a syscall)

i mean, i think we solved the "name" problem with asymmetric cryptographic keypairs previously????

as in:

since we no longer have named shm mappings,
and i have just realized that my idea of a "named resource" was incorrectly encoding secret knowledge (the name of the resource to summon)

so, i think we say:

a process can generate new i/o sync domains from scratch at any time
- these are just empty directories--no cryptography
- these can be merged with and mutated and spliced just like the process-global "implicit" i/o sync domain
a process can register an i/o sync domains it has a handle to--and this is where we should generate the cryptographic keypair

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

it is intentional that this cryptographic keypair can be transmitted completely out-of-band. its purpose is to codify a permissions system that can be serialized and transferred across a filesystem or network

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

this means the permissions calculus for my kernel has been narrowed down to exactly three points:

given a public key, validate that the caller indeed possesses it through a cryptographic challenge
- generate a read-only view
given a private key, again validate by challenge
- generate a "standard" (mutable) handle to the shared state of the i/o sync domain
enforcing read-only/immutable status

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

in fact, i think (3) will be reasonably difficult to do correctly, particularly in the case of a large number of concurrent read-only views and then one mutable view.

but this is where i/o transactions come in, which (blocking or nonblocking) require the process who explicitly initiated a non-local mutation operation to wait until the OS synchronizes all that state (and takes a global lock).

we lose absolutely zero amortized performance if we simply take that task off the CPU and put something else in its place while we (the kernel) perform the filesystem i/o state synchroniation transaction.

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

one other useful result we have with this permissions system is that we can unambiguously audit and validate a process's read-write permissions are valid--so if someone created a vuln that exposes a read- or write- handle from my kernel without actually cracking the cryptographic keypair, that particular failure mode can be unambiguously identified at runtime

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

in fact, it seems like it would be plausible for my kernel to generate a graph of:

(1) the entire recursive process tree

and in particular the decomposition into supervisor graphs.

(2) two mappings:
- process => public key relationships
- process => private key relationships

this is simple enough to describe our own little binary protocol specified in C header files and printed out in response to either a syscall or some sort of /proc file nonsense.

i would strongly prefer it to be a syscall interface like read(), where the user provides the location for my kernel to write the result into via a function argument, and we just exit with ENOSPC or something if we find we needed more space than the caller gave us . (unlike read(), we are not allowed to

a userspace application built against this stable communication protocol can remain stable across kernel versions. since it's an official API, there will always be a thorough security analysis of that endpoints

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

we don't need to invest so much effort into tools like perf either, for example, since we won't put the onus on the user to optimize their code to our fickle and confusing system

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

ok now it is time to implement