Correct. As long as you have Turing Complete machines you made theoretical hack possible. This was nicely illustrated by the problem that Ethereum had a while ago while it would not be possible on Turing incomplete-Bitcoin.
If you have time, read up on the basics: http://www.erights.org/talks/promises/paper/tgc05-submitted....
This is false theoretically.
For example, a while loop code in a Turing Machine is unhackable; the state repeats forever.
Suppose you have a Turing complete machine, with network connection, programmed to respond to 1 particular message with a particular message, and ignore all other messages. It seems clear that this should be possible to make secure against attackers who cannot do physical attacks?
I am not sure what you mean.
Just because it is Turing complete does not imply that it uses a stack.
Consider:
look_for := "some string"; n := len(look_for); send_out := "other string"; i := 0; while(true){ c=getInputChar(); if(c==None){ i=0; continue; } if(c==look_for[i]) { i+=1; continue; } if(i==n){ output(send_out); i=0; continue; } //else i=0; continue; }
(Pseudo code. No specific language intended.)
I see no reason that the above would require a stack (provided that the input and output features are hardware built ins rather than function calls. Just reading or writing from/to a pair of registers.)
I see no way that such a program could be exploited (short of flaws in the machine).
Causing the stack to dump wouldn't work, as it has no stack. It just cycles through a small number of states based on input.
Now, some other program which is much more complicated could be written for the same machine, as the machine is Turing complete, but this particular program would not be vulnerable.
So, there's a bug and now a maintainer has to go in and patch the bug, which may introduce a security flaw (either in the coding or the release deployment process).
You also have the exposure of whatever getInputChar() and output() do internally.
I'm not arguing there is an exploit just because of using Turing complete system, but observing that even simple systems tend to have bugs and get maintenance over time.
Also, you are right that I made a mistake, in that I forgot to check if a wrong next character was a correct first character and similar problems.
Oops!
Ok.
What I was trying to argue was that it is possible for a program in a Turing complete system to have no exploits, not that it is easy to write a program like that.
I thought it was being claimed that it is completely impossible to write a program with no exploits for a Turing complete machine, and I was trying to argue against that.
I took the thread to a slight diversion given the premise that it's easy to write bugs in even short, simple code snippets, and that those bugs then introduce the requirement for maintenance, which brings in further opportunities for exploits to be introduced.
Of course, that isn't actually necessary for the argument. It doesn't matter whether the program is running on hardware directly or through some OS, so long as the thing running it is not broken.
When one talks about a Turing machine running a program, one generally does not model the machine as occasionally not working as specified.
Similarly here, the assumption is that the implementing thing, whether it be an OS or a circuit, works according to the spec that the program for it is based around.
This sounds like an attempt to combine intuitions about the pumping lemma with memory corruption vulnerabilities: that "any system" must have some inputs that are "too much" for it to interpret correctly (for many programs written in C, that could be a single input string that's "too long").
https://en.wikipedia.org/wiki/Pumping_lemma
https://en.wikipedia.org/wiki/Buffer_overflow
These intuitions are founded on good reasons because every computing system has different kinds of limitations, and some kinds of distinctions that it can't make correctly, and some kinds of failure modes if it's expected to make arbitrary distinctions.
But there are ways out:
* If we narrow the definition of the task that the system has to do, it may be possible for the system to do it perfectly, and it may even be possible to make a formal proof that the system performs that task perfectly, even though there are other more general tasks that it doesn't perform, or performs imperfectly.
* If we allow the system to "give up" or indicate that it refuses or fails to answer certain questions, then it doesn't have to be "wrong" or exhibit wrong or unpredictable behavior. It can just say "sorry, not sure", which may be annoying but isn't a mistake and isn't necessarily a security vulnerability. (Maybe this is akin to those movie robots saying "does not compute" all the time.)
Within these frameworks, a kind of perfection, or at least a kind of correctness, is possible for many computing tasks -- including some that involve Turing-completeness, either as a property of the environment they're implemented in or as a property of the machine they implement.