how i stopped fuzzing and learned to love the halting problem

for most of my life, my entire professional vocabulary was BYPASS. bypass the EDR, bypass the sanitizer, defeat the sandbox, chain the primitive. i said "muh detections" with a straight face. i was, in the clinical sense, trash. a vendorspeak-shaped void that mistook a list of techniques for an understanding. and the tragedy of it is i was GOOD at it, which is the worst possible thing to be, because being good at the wrong abstraction is how you stay there.

with time, i ended up realizing that most of my work, most of everything i've ever said was either wrong, imprecise or provably incorrect. it hurt. a lot. coming to the realization that my entire worldview was wrong, that i've been prescribing medicine to treat the symptoms, and not the treatment to treat the disease.

the good thing is that the evolution happened quicker than i ever thought it would. i've never really been "married" to my beliefs in the security world, since everything either changes twice a week, or something new comes out and breaks something nobody thought was breakable.

let's begin.

act one: the offsec dood

edr user. siem enjoyer. i fuzzed the world and found IDORs like candy and felt like a wizard. mostly i was memorizing, pattern matching. every engagement was a fresh deck of tricks and i shuffled it and dealt it and if it worked i put that shit on the report.

act two: the DICOM months

then medical imaging ate me alive. orthanc, dcm4chee, gdcm, dcmtk, every PACS and every image viewer that ever swore it read the standard. i loved it. i hacked the whole zoo. i'd get a malformed object to land in one archive and bounce off another and i thought that difference was just, you know, TRIVIA. a quirk. vendor being vendor.

DICOM was the beginning of all of this change, all of this mindset replacement. even though i despise it, i do have to thank it for fucking my brain.

act three: the small dumb realization

here's the thing i was actually doing and could not see: differential testing. at a smaller, dumber scale, with no method. i would sometimes take a payload that broke implementation A and try it on implementation B, and sometimes it did something spicy, and i never did it CONSISTENTLY because i had no theory of why it would. i was standing on the finding every single day and calling it a coincidence. i kept re-discovering the same idea and forgetting it by lunch.

so: the basis of my work on DICOM was a bastardized version of what differential testing is supposed to be. nevertheless, i had already captured a lot of knowledge about the sins of DICOM and what implementers (usually) got wrong on their systems and, eventually, on what they read off of the standard itself.

act four: langsec touches my door

and then i found out there was a NAME for it. a whole lineage of people doing exactly what i was doing, except they were smart about it and i was a raccoon. language-theoretic security. the moment reorganized my brain like someone reached in and defragged it.

because suddenly the pipeline had a shape. a message doesn't just travel, it MUTATES at every hop:

1
2
3
4

M            the thing you meant to say
E(TCP(M))    encoded, framed, shoved onto the wire
D(E(TCP(M))) the receiver decodes what it THINKS you said
C(D(...))    and then some poor recognizer has to decide what it means

every one of those arrows is a place where two machines can disagree about what language they're even speaking. i started seeing recognizers where i used to see functions, shit grammars where i used to see "the parser," interoperability as a MAP of who accepts what. i couldn't turn it off. still can't. it's the best drug i've ever done and i've done several.

and most importantly, and i say it outright because its simpler than to deduce it off of what i've just said: where two consumers of the same format admit different strings and the difference crosses a trust boundary, no memory bug is required for it to be a vulnerability. the differential itself is the vulnerability.

act five: the toolkit

not necessarily trying to build a toolkit, i built DICOMKILLA, or DCMK. it was merely a tool to reproduce the same, byte exact payload on several implementations of the same given thing (DICOM, in this case). it was quite limited in scope, but general enough for me to expand on it later on.

it wasn't really that good. i mean, payloads reproduced nicely, no problem there; but grading was... not necessarily the best, to be honest.

but it was the beginning of the top-to-bottom effort of pwning standards first, to apply the pwnage to the implementations later. breaking prose is usually easier than going after an implementation of a standard one doesn't really know nothing about.

act six: the paper

and after a while and a lot of work on DCMK, it was mature enough for me to depend on it to actually be able to generate useful data for the DICOM paper i'm working on. spec-anchored payloads, each attempting to break a given ambiguity in the DICOM standard. many things appeared, many CVEs were requested, and so the tool proved itself to me as more than good enough. it became a product of the paper, an actual artifact that was producing good results.

thus, DCMK was renamed, and was newly called the Differential Conformance Matrix Kraftwerk.

act seven: evolution

spec-anchoring became a reflex. every wrong-on-purpose payload had to cite the exact clause it was stressing or i wouldn't ship it. the axe you swing at a standard written by committee to find the places the committee couldn't agree with ITSELF. i still didn't fully get what i was holding. one rarely does.

the ecosystem, of course, grew out of the DICOMKILLA world, and out of its dependency too. DICOM became merely a plugin in an otherwise easily expandable, extensible and very cute interface. MLLP was second, J2K is there but unexorcised (don't have money for the J2K standard lol) and eventually FHIR came to be, alongside HL7 CDA XML.

act eight: the mentor

then someone whose work founded this entire field answered an email from a chilean nobody. i'm not putting her name on my blog (and i wont ask her cuz she's busy with a beautiful project of hers) so you'll have to take my word that it carries weight. she said: "you're recovering the boundaries of competence that real implementations actually exhibit, and that's really powerful."

the axe is the cure. that one sentence flipped the whole tool over in my hands. i thought i'd built a thing that destroys standards. she saw that the same swing hands you the safe subset, the decidable little island every implementation actually agrees on. same matrix. you decide on the way in whether you came to break it or to heal it. my WORLD shook. i went for a walk and did not come back the same animal.

DCMK stopped being a mere harness that proved different language classes exist. it grew two edges. an empirical falsifier that refutes "one standard, one language" by counterexample, and a constructive prover that carves out a subset small enough to prove decidable. not merely attack and destroy, but mend and cure.

falsifiability goes both ways after all. one edge: prove that n implementations read the standard differently and thus carve it into distinct language classes. the other edge: restrict that wire language down to a safe subset small enough that RECOGNIZING it is decidable again, and then prove whether a real implementation actually stays inside it. or doesn't, of course. that's what makes it a falsifier and not a wish. the thing you're making decidable isn't "the problem," it's membership: is this input in the safe language, yes or no, provably, every time.

act nine: the pattern under the pattern

and this is where it stops being about DICOM at all.

sit with the halting problem for a second. can a Turing machine take another Turing machine as input and decide whether it finishes? no. proven no, 1936, forever no. undecidable.

now add one word. INTENT.

can a program take another program and decide whether it is MALICIOUS? that's the same problem wearing a hoodie. it's halting with a motive stapled on. and it is not my clever observation, it's Fred Cohen, 1987, who proved that perfect detection of a virus is undecidable by reducing it straight to halting. the maliciousness problem. every antivirus, every EDR, every sandbox, every one of the products i spent years lovingly evading, is a machine built to answer a question that MATH says has no answer. they're not bad at their job. their job is impossible. they're selling you a solved halting problem in a nice UI with a threat feed.

and let's take it a step forward: people say the "no computer program, website, service, server, etcetera, can be completely and 100% secure or unhackable". people SAY this. they RECITE it with such a certainty it makes me CRY.

but why?

act nine/2: the science of (in)security

because it's the same no, one layer down. "unhackable" is just "benign or malicious?" asked about an entire system instead of one program, and we already established that question has no answer.

the world wide web, the world we live on, is a net of message (input) composition (encoding) and decomposition (decoding), from HTTP messages, TCP packets, BGP...OSPF routing, TCP decomposition, HTTP accession, data checking. each and every one of these steps is a place where the differentials may live. not to mention the ginormous amount of different protocols, some inocuous (TCP/UDP!!!), some trash (DICOM!!!), with standards and specs so complex, so big and so ass, that the only possible answer to "is unhackability possible?" is NO and ALWAYS no.

act ten: this post

so here's what actually happened to me, all the way at the bottom. i used to think computational theory was some stuff a few tubercular geniuses did for fun in the 1930s while waiting for penicillin to be invented. abstract. useless. a hazing ritual in undergrad.

it's not. it's the GENERALIZATION. the halting problem is why detection can't win. Cohen's reduction is why the antivirus is a religion. the Chomsky hierarchy is why your parser is an accidental interpreter. Rice's theorem is quietly the reason your entire static-analysis vendor is grading a test with no answer key. every security problem i ever fought was a decidability problem in a hat, and i was out there arguing with the HAT!!!

i've spent years learning bypasses. the part where it all fell over and rebuilt itself into something true took about two months. that's the joke i can't get over. the wrong abstraction held for many years and the right one arrived over a winter, because the right one isn't a bigger pile of tricks, it's a single idea that eats all the tricks at once. once you see that perfect detection is UNDECIDABLE, you stop hoarding bypasses. the theory already settled whether they exist. yes. always. a detector that catches everything cannot be built, so evasion is guaranteed, not discovered. "do the bypasses exist?" was never the question. the only question left is "can i find them?"

REGARDLESS OF THE HARDWARE, SERVICE OR ENCODING, CONNECT IT TO THE INTERNET AND SOMEONE'S GONNA OWN IT!