41–50 of 50 posts
From https://docs.microsoft.com/en-us/typography/opentype/spec/tt... looks to have 32-bit words, a dynamic heap, unrestricted JMP targets, a generous number of math functions, ...
> This matters because, if one is clever, it provides an escape hatch from system which is small, predictable, controllable, and secure, to one which could do anything . It’s hard enough to make a program do what it’s supposed to do without giving anyone in the world the ability to insert another program into your program, which can then interfere with or take over its host I take issue with the statement that TC mea…
> Turing completeness does not in itself give access to any additional resources; being TC does not magically allow something to talk to internet or write to disk or spawn new processes, or possibly not even allocate new memory. Computers do so much more than just compute; TC might be the first step towards being able to "do anything" but it certainly is not the final step. In many cases it is the final step. If you'…
That's where your thinking goes wrong. TC does not mean that the program can take over the host process control flow.
Earlier quoted context omitted.
> Turing completeness does not in itself give access to any additional resources; being TC does not magically allow something to talk to internet or write to disk or spawn new processes, or possibly not even allocate new memory. Computers do so much more than just compute; TC might be the first step towards being able to "do anything" but it certainly is not the final step. In many cases it is the final step. If you'…
> because as soon as the attacker can execute their own code, the process already had access to the sensitive data and to the internet. That's where your thinking goes wrong. TC does not mean that the program can take over the host process control flow.
Just because you can hit "Replace all" a bunch of times to run the TC "regex code", transforming some input to some output, doesn't in itself mean you can make Notepad++ do something weird.
A related idea that I’m interested in but find a bit hard to articulate is to describe “simple” Turing complete languages, where simplicity is defined more by ease of reasoning for a human than by any objective metric. Basically, if I wanted to provide someone with a Turing complete language, what’s the simplest/easiest thing I could provide, that would still be useful?
Earlier quoted context omitted.
Yeah, I'm not so sure. Security is about ensuring certain guarantees. If your configuration language is Turing complete, it's easy to get into a spot where you simply can't be certain of the final state of your system. That's not secure. Turing complete configuration language might be an instant red flag, like "perpetual motion" is to physicists. It's possible to ensure termination of Turing complete languages by rej…
I’m unsure of how you mean that in a technical sense. It’s straightforward to make those guarantees in your interpreter. And just to be clear, Dhall, the configuration language we’re talking about, is not TC, but powerful enough to compute the Ackermann function: https://gist.github.com/Gabriel439/77f715350ecc0443eed5fa613... Add “ackermann 10 10” to your configuration file and you have something that’s technically p…
Earlier quoted context omitted.
> Turing completeness does not in itself give access to any additional resources; being TC does not magically allow something to talk to internet or write to disk or spawn new processes, or possibly not even allocate new memory. Computers do so much more than just compute; TC might be the first step towards being able to "do anything" but it certainly is not the final step. In many cases it is the final step. If you'…
> because as soon as the attacker can execute their own code, the process already had access to the sensitive data and to the internet. That's where your thinking goes wrong. TC does not mean that the program can take over the host process control flow.
But that's commonly what happens in practice. Return into libc and similar do exactly that.
Not only that, compromising the host process control flow is not strictly required. You may be executing weird machine instructions and not machine code instructions, but the weird machine being inside the host process often means that it already has access to at least some of the host process address space. When it's the whole address space or even an interesting subset (e.g. read access to sensitive data, write access to anything that goes into an outgoing network buffer), achieving TC is already the end of the game.
Access to host process data need not even be so direct. Once you can execute weird machine code inside the host process, it enables timing attacks that may reveal more host process data -- especially when you're inside the host process control flow, even if you don't fully control it. Exporting data is likewise possible if you can bring about any externally-visible change in the host process behavior whatsoever, e.g. the timing of outgoing network packets.
There are cases where none of these things are true but the cases where they are true are common. And they're also not generally regarded as a vulnerabilities that could justify mitigating them with things like denying network access, even though maybe they should be.
Earlier quoted context omitted.
Complexity theorist here. In addition to your point, there's another commonly-overlooked problem: TC isn't quite the actual top! There are ways to make problems that, even with an oracle for solving Halting, are still hard [0]. It seems like folks are very quick to confuse the expressiveness of a machine with the expressiveness of analyzing programs for that machine; usually, a program is far harder to analyze than t…
I don't think this discussion thread is giving the writer's concern enough credit. Universality on its own obviously doesn't allow the instance to take over its host, but it can enable the bulk of the malicious payload to be encoded as legitimate instances of whatever P-hard optimization problem the cloud service solves, so that it need not be injected directly via the actual vulnerability that the malicious actor us…
And, if you thought that it was easy to be accidentally Turing-complete, wait until you see how easy it is to be accidentally NP [1]. The typical database query is in NP, because constraint satisfaction problems are in NP. So is the typical optimization problem.
[0] https://www.researchgate.net/publication/266217730_Pola_a_la...
[1] https://en.wikipedia.org/wiki/List_of_NP-complete_problems
If TrueType hinting is turing complete - are outputs observable from a Web Font context? Is it possible to write a WASM polyfill based on TrueType hinting? From https://docs.microsoft.com/en-us/typography/opentype/spec/tt... looks to have 32-bit words, a dynamic heap, unrestricted JMP targets, a generous number of math functions, ...
Earlier quoted context omitted.
The simplest you could give someone is probably the Turing machine itself, the Brainfuck language or the lambda calculus. Simplifying, to have a TC programming language you need two things: RAM and the ability to decide your next state based on the memory contents.
Right, so I think the suggestion of brainfuck illustrates the difficulty I’m having articulating what I want, because while it’s TC and trivial to implement, it is basically impossible to use as a language. I think I’m going for simultaneous ease-of-implementation and ease-of-use rather than any actually type of “minimalism”. I’m probably just looking for Lisp, really. It’s easy to implement and usable enough.
Brainfuck is useless because the operations are useless. But if you give the user a few more things, like addressing memory, basic arithmetic and a way to define variables and functions, then you have something way more useful very quickly.