Compsci boffin publishes proof-of-concept code for 54-year-old zero-day in Universal Turing Machine

Patch your devi... oh, hang on a sec


A computer science professor from Sweden has discovered an arbitrary code execution vuln in the Universal Turing Machine, one of the earliest computer designs in history – though he admits it has "no real-world implications".

In a paper published on academic repository ArXiv, Pontus Johnson, a professor at the KTH Royal Institute of Technology in Stockholm, Sweden, cheerfully explained that his findings wouldn't be exploitable in a real-world scenario because it pertained specifically to the 1967 implementation [PDF] of the simulated Universal Turing Machine (UTM) designed by the late Marvin Minsky, who co-founded the academic discipline of artificial intelligence.

Yet what the amusing little caper really brings to the world is a philosophical point: if one of the simplest concepts of a computer is vulnerable to user meddling, where in the design process should we start trying to implement security features?

"The universal Turing machine is generally considered to be the simplest, most abstract model of a computer," wrote Johnson in his paper. Through exploiting the Minsky-spec UTM's lack of input validation, he was able to trick it into running a program he had put together.

The Minsky specification describes a tape-based machine that reads and executes very simple programs from a simulated tape. Instructions on the tape move the simulated tape reader head left or right across the "tape" itself, which is represented as a one-line alphanumeric string. While users can make inputs at the start of the tape, in the UTM model they're not supposed to alter the program that follows.

"Regardless of the historical aspect of it, the fact [is] that the most simple [computer] we can describe seems to have had this propensity for vulnerability," Johnson told The Register.

Security (if you could call it that) for UTM consists of a single digit that tells the machine "user input ends here, everything after this point is executable with the parameters you've just read."

Johnson's exploit was as simple as writing that "input ends here" character in the user input field and then writing his own program after it. The UTM executes that and skips past the intended program.

Parallels with modern vulnerabilities are obvious: scale it up a bit in complexity and this has all the hallmarks of a SQL injection vuln, for example – or any other unsanitised or unescaped user input field.

Johnson told The Register today: "In this case, as in many cases, the vulnerability is based on confusing the machine… in academia, we scientists like to start with the basic principle: demonstrate something for a small system, then maybe it's true for a larger system. It seems to me that for the very smallest system, there is this intrinsic vulnerability, this propensity to be vulnerable."

The compsci prof continued: "Obviously Marvin Minsky didn't have the intention to [create] either a secure or a vulnerable system. Nevertheless, what happened was [it] was vulnerable."

Philosophically, Johnson's vuln (which has been assigned as CVE-2021-32471) raises deeper questions for hardware and firmware designers alike to think upon, he told us: "Some people say that security needs to be built in from the start; you can't add it later. But in this case, all the mitigations of this that I could think of, they need to be add-ons, you can't build it into this machine.

"And if this is the mother of all computers, then it seems to me that you cannot build security in from the start."

Professor Alan Woodward of the University of Surrey opined to El Reg: "It's an interesting and provocative thought as to whether or not there is some fundamental cause for the number of specific attacks we see. I don't think we need to panic that there is some fundamental flaw in modern computer architecture, more it's a reminder that complexity brings its own threats."

Looking specifically at Johnson's vuln, he commented: "Interestingly, it seems to point more to issues with interpretations/implementations of the Turing machine. It seems to support the adage that nothing is totally secure once it's actually implemented." ®

Similar topics


Other stories you might like

Biting the hand that feeds IT © 1998–2021