Post · bonfire.cafe

@hipsterelectron@circumstances.run 8 hours ago

big huge actually important breakthrough https://circumstances.run/@hipsterelectron/116961115914825897 the page cache that POSIX demands is deeply analogous to the single global address space in the C abstract machine model. but C is a language, and we can achieve safety through the frontend. the POSIX page cache requires your computer hardware to maintain globally-addressable memory across all processes and threads. that is not solvable in the frontend. that is a backdoor at the hardware level, which is maintained by the OS.

@rysiek i'm sure you recall copy dot fail. i have written what i consider low-level i/o code for years, and that vuln was the first time i had ever heard about the linux page cache. it's not well-known (because the POSIX spec actively obfuscates it), but one of the very few hard requirements that POSIX demands is the immediate global visibility of any write() call (along with an "atomic" ordering which is literally not specified). POSIX describes this in terms of torn writes (which is a userspace i/o semantic), but it then imposes this global (cross-process!!!!) mutable data store in the kernel. this is completely fucked.

65 Replies

·

0 Boosts

@hipsterelectron@circumstances.run 8 hours ago

and on top of all that, the page cache is the reason filesystem i/o through POSIX is slow and extremely difficult to buffer, because it maps the entire filesystem into volatile memory and requires each write to pay the toll before proceeding

@tris@chaos.social 3 hours ago

@hipsterelectron I'm not sure all of this, just mere existence of https://github.com/bytecodealliance/rustix even boils some people's blood xD

GitHub - bytecodealliance/rustix: Safe Rust bindings to POSIX-ish APIs

Safe Rust bindings to POSIX-ish APIs. Contribute to bytecodealliance/rustix development by creating an account on GitHub.

@hipsterelectron@circumstances.run 8 hours ago

this is also the only infrastructural reason we can't add transactional semantics without breaking POSIX compat. it's literally the single non-portable part of POSIX i/o

@hipsterelectron@circumstances.run 8 hours ago

this isn't defeatist btw. in the linked thread i'm very specific in saying:

hard fork POSIX to make it actually portable
we do not fork linux, we make an OS without a page cache
we introduce POSIX transactional i/o semantics as an extension—it will be possible to emulate on linux/BSD, if you can separate write()s from the page cache.
we completely rearchitect and indeed reimagine the concept of a filesystem given the very minimal additional user input from the POSIX transactional i/o extensions

@hipsterelectron@circumstances.run 8 hours ago

(5) this immediately sees use in HPC environments who have precise and extensive demands on i/o and already distinguish write() from sync()

(6) this immediately sees use in embedded environments who can interface with a structured filesystem abstraction without an MMU that ensures transactional semantics for data persistence while imposing very few requirements upon the format of non-volatile memory

~59 more replies

@hipsterelectron@circumstances.run 8 hours ago

oooooooo ok yeah i uh really like thinking about this as an extension of the MMU. unfortunately the MMU is emphatically not about moving data but about dividing up and indirecting the address space. the more modern and not exactly standardized IOMMU does the same kind of redirection but for interrupts and i/o ports. the AMD IOMMU actually has a pretty well-designed explicit command buffer interface (RING BUFFER GANG!!!!) but its role is very precise and (this is good) wholly orthogonal from the concepts of isolation and locality we introduce that achieve abstract semantic guarantees for (🤡🤡🤡) memery safety and (👀👀👀) data persistence in user code

@hipsterelectron@circumstances.run 8 hours ago

if any chip designer were to provide an accelerator within the motherboard (or i mean ideally within the CPU itself) that enabled rings 0-2 to queue up memcpy/memmove operations across absolute addresses in main memory independently of the CPU and then get a notification when a batch has completed (i would actually like this to be an interrupt and not another ring buffer, where the CPU invalidates its caches for those addresses before calling my registered interrupt handler), that would be pretty fucking innovative. i would gladly write hardware-specific code for such a platform

@hipsterelectron@circumstances.run 7 hours ago

obviously this has implications for memory-mapped i/o. personally i think memory-mapped i/o was an interesting experiment, but it is directly responsible for the unreliability of data persistence mechanisms, which cannot be constructed on top of them, therefore making it a poor choice of semantics for a primitive operation in a general computing device (which by definition has a large range of requirements).

@hipsterelectron@circumstances.run 7 hours ago

this is kind of a general category of design fallacy in the hardware industry, where the concept of the requirements for "general computing" is interpreted to mean "provide more complex and abstract functionality in hardware interfaces". see this AMD chiplet marketing copy from dec. 9 2024:

Accelerator Chiplets: These specialized chiplets offload specific tasks from the main processing cores, improving overall SoC performance. Examples include:
Custom Arithmetic Engines: Tailor-made computations designed to accelerate arithmetic-heavy algorithms. These can include specialized cryptographic calculations or financial computations.
Compression/encoding engines: Hardware-assisted compression and decompression of data for efficient storage and transmission.
Networking engines: Optimized chiplets for handling network traffic and communication protocols.

@hipsterelectron@circumstances.run 7 hours ago

let's set aside for a moment the obvious corporate financial motivation for monopolistic control that justifies these, because i want to discuss their technical characteristics in order to ground my proposed alternatives. but it's very important to recall that underlying the following discussion are political incentives for the status quo which are very public (e.g. described in investor calls) and largely uncontroversial to state as a given.

@hipsterelectron@circumstances.run 7 hours ago

so the idea that in TYOOL 2024 (note: one month after trump re-election) a major CPU developer proposes specialized cryptographic support for their future high-end general-purpose laptops and servers, but only to "accelerate" cryptographic computations, with NOT A FUCKING WORD ABOUT TIMING ATTACKS, is why i emphatically distrust and have no time for daniel jackoff bernstein telling me to write slower and more obfuscated CRYPTOGRAPHIC IMPLEMENTATIONS, in order to (supposedly) frustrate LITERAL KNOWN-PLAINTEXT ATTACKS IN STANDARD CRYPTOGRAPHIC PROTOCOLS

@hipsterelectron@circumstances.run 7 hours ago

but i literally don't even care about that here because that's a matter of protocol design to be fixed elsewhere. it is not the CPU's job to dictate what discrete mathematics you can execute on it, and the CPU provably cannot secure a broken protocol. the vast majority if not literally all timing attacks are trivially translateable to cryptographic proofs of the failure to uphold indifferentiability, the gold standard information-theoretic framework for cryptographic security (Maurer et al 2012 is what everyone always cites)

@hipsterelectron@circumstances.run 7 hours ago

if your cryptographic protocol is indeed indifferentiable over data but not over timing, then you need to add data-dependent timing feedback into the mathematical model of information that can be extracted by an attacker querying the system. but most of these "timing attacks" are active diversions from very basic key extraction techniques of the sort that were used in ww2 to crack the enigme. if the attacker can request a signature from your private key for data they specify, your problem is not how long you take to return their call. if you're using a static (no IV/nonce) signature like EdDSA, you are leaking info about your private key.

@hipsterelectron@circumstances.run 6 hours ago

this is, by the way, explicitly stated in the paper https://ed25519.cr.yp.to/ed25519-20110926.pdf

Standard PRF hypotheses imply that this pseudorandom session key r is indistinguishable from a truly random string generated independently for each M, so there is no loss of security.

this sentence is actively a lie. see the next sentence:

Well-known length-extension properties prevent secret-prefix SHA-512 from being a PRF, but also do not threaten the security of Ed25519-SHA-512, since r is not visible to the attacker.

"r is not visible to the attacker" is a circular argument that would also apply to ECDSA, the standard elliptic-curve signature a algorithm which does use an IV/nonce. the argument against that is that the attacker may be able to control the output of randomness generation, so EdDSA avoids any per-message calls to the RNG. instead, the RNG can be performed securely in a separate location, and then your publicly-exposed interface has no reliance upon new randomness.

@hipsterelectron@circumstances.run 6 hours ago

first off, "the attacker may be able to control or influence the RNG" is a very specific threat model assumption that generally requires an attacker-controlled hardware or kernel vulnerability. does the same attacker you're worried about also also control the kernel you put on the device?

@hipsterelectron@circumstances.run 6 hours ago

if the attacker is the US state and your kernel is linux, the answer is yes, which is another reason i'm making a separate OS and not forking linus's steaming pile of shit. but if your attacker is instead someone who can remotely trigger you to generate EdDSA signatures over attacker-controlled inputs, congrats! you are leaking your private key regardless of how long you take to return their calls. djb has swindled you.

@hipsterelectron@circumstances.run 6 hours ago

do you see any discussion in any of djb's published works about data leakage from triggering signature generation over attacker-controlled input? he is an absolute magician of omission—from the EdDSA paper, he creates a farcical strawman:

The chance of the attacker randomly guessing a is far smaller than the chance of the attacker computing a by known discrete-logarithm algorithms

attackers do not "randomly guess", they compute by brute force. if he had said brute force, then it would have been immediately obvious that brute force is not the easiest way to compute the secret key, which is deterministically leaked in every signature.

@hipsterelectron@circumstances.run 6 hours ago

this next part (same page, next paragraph) is shockingly arrogant:

Malleability. We also see no relevance of “malleability” to the standard definition of signature security.

malleability is a concept defined directly in terms of challenge-response schemes, which generalizes information-theoretic measures defined for single-message encryption to systems in which keys are reused across messages. it is in fact very relevant to signature schemes, because (informally) the very concept of cryptographic identity refers to the reuse of asymmetric key material—this is integral to the standard conception of public and private keys (keypairs).

@hipsterelectron@circumstances.run 6 hours ago

mihir bellare has a wonderful paper on malleability at https://cseweb.ucsd.edu/~mihir/papers/nm.pdf which informally describes the threat model and the security goal:

The definitions involve considering some relation R between plaintexts, having an adversary output a distribution on some set of messages, and then setting up a challenge-response game. The adversary is given as input a ciphertext y of a plaintext x drawn from the message distribution, and must produce a vector of ciphertexts y, none of whose components is y. If x is the plaintext vector corresponding to y, security requires, roughly, that the adversary’s ability to make R(x, x) true in this game is not much more than her ability to make it true had she had to produce y without being given y at all, namely given no information about x other than its distribution.

this is the classic formulation, which incorporates the probabilistic distribution over the message space (an important consideration that codifies the implicit "chosen-plaintext" characteristic inescapable in the use of any language).

@hipsterelectron@circumstances.run 5 hours ago

the bellare paper introduces a new characterization which it shows to be equivalent. they use this (imho) completely backwards terminology (which is actually standard, because the crypto field is Just Like That) in which a "chosen-ciphertext" attack is paired with an oracle that reveals the plaintext for a given ciphertext—there's a good reason for this (it means the attacker doesn't need to control the plaintext, but merely to know it—for example, if a signature is computed over public data, like a tarball release). so i shouldn't even be saying "chosen-plaintext" above.

@hipsterelectron@circumstances.run 5 hours ago

but i like this bellare paper so much because it puts in so much effort to state and restate every formalism at multiple levels of abstraction. this is the key definition which links challenge-response to the threat model and security goal:

In more detail the game is that we take two equal-length messages m0, m1, give the adversary a ciphertext y of a random one of them, and now allow it a single parallel vector decryption oracle query, the only constraint on which is that the query not contain y in any component. The adversary wins if it can then say which of the two messages m0, m1 had been encrypted to produce the challenge y, with a probability significantly better than that of guessing.

@hipsterelectron@circumstances.run 5 hours ago

and you should be going 🚨🚨🚨🚨 (i.e. getting excited and a little scared) in your head to read "with a probability significantly better than that of guessing", because yes, that is in fact the kind of "guessing" that djb is talking about in the paragraph right before he says "malleability doesn't matter", as usual without citing a goddamn thing.

@hipsterelectron@circumstances.run 5 hours ago

a final switch back to djb:

but it would still not accomplish the attacker’s goal, namely to forge a signature on a new message under a target public key.

that is absolutely fucking NOT the goal of the attacker for djb's precious timing attacks—it is to reveal the fucking secret key. if you understand that signatures are (handwaving furiously) the encryption of a checksum, and you recall that EdDSA's per-message (i.e. per-signature) encryption key incorporates the static private key directly, then you don't even need djb to tell you outright that his construction is weak to length extension to see that There Is A Problem Here Bruh!!!!

@hipsterelectron@circumstances.run 5 hours ago

i spent all this time to call out djb here because it reveals the fundamental primitive isolation boundary that NOBODY FUCKING TALKS ABOUT AND EVERY OS IS VULNERABLE TO, which is adversarial control over scheduling operations—and i furthermore claim this is strongly analogous to the ability of an attacker to trigger generation of ciphertexts over specific plaintexts in cryptographic protocols like EdDSA signature generation.

@hipsterelectron@circumstances.run 5 hours ago

the request-response model is an ideal framework to link OS semantics to cryptographic guarantees. unfortunately, all modern general-purpose OSes have introduced functionality that actively frustrates or even obliterates the ability to describe userspace interactions in terms of a request-response model. maybe they're right, and i just need to git gud and produce a better mathematical model that translates across OS semantics and cryptographic guarantees. or maybe i'm right, and the OS needs to git gud and implement Literally Any Fucking Semantics At All For Once.

@hipsterelectron@circumstances.run 5 hours ago

in particular, memory mapping sucks shit because "globally visible mutable address space" is fucking impossible to buffer or optimize. the AMD architecture specification is clear that mapped memory doesn't work like normal memory (atomics can't be guaranteed) and that essentially all operations will have varying performance characteristics depending upon the device (which does its best to translates mapped memory operations into the semantics of the underlying storage mechanism).

@hipsterelectron@circumstances.run 5 hours ago

i.e. memory-mapped I/O lets the OS be lazy and shoves off complexity into the hardware. this is kind of absurd since the OS (as a form of software) can be updated and extended, while the hardware definitely is limited to the semantics of the physical universe. hardware constitutes a form of matter you can plug into a computer, and firmware updates do not in fact involve nuclear or even chemical reactions. and hardware costs fucking money, while software, like mathematics, can be obtained freely from others.

@hipsterelectron@circumstances.run 5 hours ago

the C compiler does so much work to translate the abstract machine to hardware instructions—the OS should present its own abstract machine, and should have an actual backend that translates to hardware like a compiler.

oh, you're saying that's hard? you're saying it's difficult to support every type of hardware? you're saying hardware semantics are complex and confusing? sorry, my professors told me in class that the OS is the interface to the hardware and i still believe them, so i'm gonna do that if you won't [glares at linus torvalds]>

@hipsterelectron@circumstances.run 5 hours ago

of course, hardware-specific code can lock you in to one vendor. that's why you have to be fucking merciless and extremely opinionated about which hardware semantics you accept. these constitute your choice of axioms, from which you can then construct a higher-order logical framework: that's your OS.

@hipsterelectron@circumstances.run 4 hours ago

this is why i think formal verification of OS semantics that's not paired with implementation work (and vice versa e.g. Literally All Of Linux) is kind of boring and often useless. like daniel micay and grapheneOS, i'm trying to neg hardware designers mercilessly until they give me what i want, and anyone who gives in gets exclusive access to the competitive advantage of My Fucking Software. motorola finally decided that it wanted to start winning again and got the exclusive grapheneos support guarantee.

@hipsterelectron@circumstances.run 4 hours ago

apple can keep on taking micay&team's ideas without credit, but fundamentally they're not driving the allocation of resources and capital in the hardware space anymore. they can try to EEE, and they have the advantage of trillions of dollars of capital, but bells and whistles on the motherboard are actually not terribly common because you need to establish a whole fucking chain of support for that shit that connects the hardware to actual application code.

micay actually did that shit, because grapheneOS is on phones and users directly interact with the grapheneOS team's code. of course a corp could replicate it, but micay&team do this thing where they actually give a shit about users, which is completely outside the corporate realm of understanding and actively disincentivized by VCs.

@hipsterelectron@circumstances.run 4 hours ago

to buttress the bells and whistles claim, let's finally return to december 9th, 2024 and AMD's chiplets doc (see above):

we do have code for fucking "AI engines", for the same reasons GPUs exist: many small cores operating upon an application-provided shared memory region is a good and portable API.
- it also has request-response semantics. remember when apple released laptops with "unified cpu/gpu memory" and literally everyone who was told it would be faster found it was false? i do!

@hipsterelectron@circumstances.run 4 hours ago

we do not have compression/encoding engines, because hardware is actually fucking terrible at both of those things in general.
- these are the most serial computations you could possibly have chosen. hardware does parallel faster. that's why i told AMD here that i'm gonna implement BLAKE3 if they won't
- CPU-level support for memory decompression (analogous to AMD's existing support for automatic encryption of a memory region) is actually possible to do in a useful way, but you need to design the compression format for hardware, and literally nobody researches compression except phil katz and jarek duda.

@hipsterelectron@circumstances.run 4 hours ago

people literally talk about compression but i have never seen anyone actually fucking think about it. really fucking perplexes me.

@hipsterelectron@circumstances.run 4 hours ago

networking engines: this one gets a special call-out for being exceptionally half-assed, and furthermore for actually being solvable with my proposal from earlier: off-cpu onboard coprocessor for memcpy/memmove in main memory
- the reason this sounds good in marketing copy is because network switching is already done with specialized hardware (jane street always brags about their FPGAs). AMD wants to pretend that could be a new market.
- but network switches are so named because they don't fuck around with that data like a regular computer, they immediately forward it elsewhere. that's possible to do extremely quickly, because they don't report to a mainboard but instead are essentially always doing i/o in ways that are incompatible with the model that has a cpu and memory on the same board (i.e., AMD's whole deal)

@hipsterelectron@circumstances.run 3 hours ago

i claim there's just absolutely no fucking way to bolt on the megaparallelism (i.e. combinatorial logic) of network switching to an x86 cpu board, and that FPGAs are used for this because programming a network switch means programming hardware—literally what FPGAs are specifically made for.

@hipsterelectron@circumstances.run 3 hours ago

there is the use case of network filtering and "deep packet inspection", which is what hyperscan (bought by intel, the codebase is still open source, geoff langdale & team write fucking great papers) is created for. hyperscan has a huge amount of incredibly innovative code for text matching (rust regex is largely ripped off from there, andrew gallant credits them profusely), and you need really smart and motivated people to do that (i glazed it up so hard at https://docs.rs/vectorscan-async).

@hipsterelectron@circumstances.run 3 hours ago

a networking chiplet would have to handle mobo communication bandwidth constraints that hyperscan doesn't, because it runs on the CPU itself. i did mention hyperscan to AMD in my BLAKE3 post, but for different reasons of API design.

however, for the case of something like packet filtering, it would absolutely be useful to offload memory copies to a coprocessor. this is actually one of the infamous basic fucking limitations that have plagued OS design for several decades!

@hipsterelectron@circumstances.run 3 hours ago

the 1999 phd thesis by chuck cranor DESIGN AND IMPLEMENTATION OF THE UVM VIRTUAL MEMORY SYSTEM is incredibly accessible to read, and is also literally the freebsd memory manager (!!!)

it's a GREAT example of merging formal analysis and implementation work (as i advocated for earlier), and it begins by explaining how hardware semantics constrain OS capabilities (emphasis mine):

One major problem with traditional operating systems is that they
require unnecessary data copies. Data copies are expensive for a number of reasons.

AUSTRALOPITHECUS 🇺🇦🇨🇿

@lkundrak@metalhead.club 3 hours ago

@hipsterelectron lol named my cat buddy "chuck" because this was the paper i was reading when i got the kitten