8 ms·

CVE-2021-32471 – Input validation in Marvin Minsky 1967 Turing Machine

139 points by wsces 5y ago

avibhu 5y ago
> NOTE: the discoverer states "this vulnerability has no real-world implications." Not sure if declaring this is standard practice, but I had a good laugh.
yabones 5y ago
> NOTE: the discoverer states "this vulnerability has no real-world implications." At least they're honest about it with this CVE...
- stevekemp 5y ago
  Issues like this, in obsolete code, are a lot of fun. Even if they are essentially meaningless. I reported CVE-2014-3423 back in the day, relating to GNU Emacs using a predictable filename when talking to the Mosiac browser. No choice, as that was what the browser required, something that wouldn't exist these days.
- buitreVirtual 5y ago
  I'm not so sure. Some banks and airlines might still be running those machines.
segfaultbuserr 5y ago
A better link is the research paper: https://arxiv.org/abs/2105.02124 https://arxiv.org/abs/2105.02124 > The universal Turing machine is generally considered to be the simplest, most abstract model of a computer. This paper reports on the discovery of an accidental arbitrary code execution vulnerability in Marvin Minsky's 1967 implementation of the universal Turing machine. By submitting crafted data, the machine may be coerced into executing user-provided code. The article presents the discovered vulnerability in detail and discusses its potential implications. To the best of our knowledge, an arbitrary code execution vulnerability has not previously been reported for such a simple system. > A common strategy for understanding a problem is to reduce it to its minimal form. In the field of computer security,we may ask the question: "What is the simplest system exploitable to arbitrary code execution?" In this article, we pro-pose an answer to that question by reporting on the discovery that a well-established implementation of the universal Turing machine is vulnerable to a both unintentional and non-trivial form of arbitrary code execution.
- Igorvelky 5y ago
  LIES > A common strategy for understanding a problem is to reduce it to its minimal form. In the field of computer security,we may ask the question: "What is the simplest system exploitable to arbitrary code execution?" means that i will remove all security abstractions which were generated in past 40 years and i find that it is more vulnerable this is not research, this is plain and simple trolling, BS feeding
- OskarS 5y ago
  Haven't looked into this paper deeply, but this reads very strange to me: > This paper reports on the discovery of an accidental arbitrary code execution vulnerability in Marvin Minsky's 1967 implementation of the universal Turing machine. By submitting crafted data, the machine may be coerced into executing user-provided code. It's a universal Turing machine. Its whole purpose is running "user-provided code". That's what a Universal Turing machine does, it runs arbitrary Turing machines. This is a little bit like saying "we found a weakness in the Python interpreter whereby you can feed it specially crafted input that allows you to run arbitrary Python programs". Like... yeah... that's what it's supposed to do.
  - qsort 5y ago
    Yes, that's the joke.
    - mycall 5y ago
      Wait until they try unicode, then the joke will be on them.
      - AreYouSirius 5y ago
        reddit is saying that macos is build on turing complete emojis ! we should investigate XD
      - jradd 5y ago
        I cannot fathom how complicated arbitrary code execution could get with multi byte characters that could use shift registers, null bytes and byte order marks with determinism in a NOP slide on a heap spray. Filtering only printable user input helps but even bit map images can expose a heap to a sensitive registers that will execute some target specific generated shell code. https://en.m.wikipedia.org/wiki/NOP_slide https://en.m.wikipedia.org/wiki/NOP_slide. https://en.m.wikipedia.org/wiki/Heap_spraying https://en.m.wikipedia.org/wiki/Heap_spraying
Igorvelky 5y ago
in my opinion this is recipe for DDoS attack on mitre infrastructructure
zitterbewegung 5y ago
Sure this CVE sounds like a joke but if you create a programming language that is non Turing complete it is much easier to secure than a Turing complete language. Making a language that have the expressive power of finite state machines could be an example.
- qsort 5y ago
  We are doing this already. - Configuration languages (JSON, YAML, XML) are pure combinatorial logic. - Regular expressions are... mostly not actually regular, but you get the idea. - Some templating languages are deliberately less powerful than Turing machines, e.g. ST4 is context-free. - Prepared SQL statements are a similar idea on a different axis. The real question is whether a non-TC language could be useful for general purpose programming. Such a language might come with very strong guarantees (termination, time complexity, even correctness or a limited form of correctness), but they might be extra-cumbersome for 'normal' workloads.
  - ludamad 5y ago
    A non-TC language can be achieved just by forcing proofs. Oh, you want that program to run? Just prove that it is bounded memory and can't halt, etc
    - qsort 5y ago
      Yeah, but that's the 'cumbersome' part. Could we imagine a non-TC language with simple syntax that's suitable for at least some of the task you'd use a TC language for?
      - magmastonealex 5y ago
        C compiled down to eBPF (as implemented with the Linux kernel) is not turing-complete. eBPF has a wide variety of uses from network filtering to hooking into certain syscalls. The bytecode is theoretically turing-complete, but the verifier present in the kernel ensures that the code contains no loops and accesses no out-of-bounds memory. With `clang`, you can compile C down to eBPF bytecode. It's a subset of C, with a lot of restrictions, but it is familiar and capable of some remarkable things past just simple packet parsing & filtering.
AreYouSirius 5y ago
But why to make CVE out of that ? this paper, this CVE has nothing to do with ! USEFUL ! research, paper is essentially saying that by using simplest machine possible we prove it does not provide layers of security abstractions which were invented and deployed in last 40+ years to machines so thats like getting CVE for turning off ASLR, AppARMOR SElinux etc in linux kernel. this proof is so obvious that highschooler should have to know this. If research alone does not get credited or recognized why we need to award CVE's to make it more credible ? WHICH IS NOT EITHER WAY second thing do we as industry want VANITY CVE's ? do we really need CVEs stemming from such a absurd exmples as some old vacuum tube computer does not provide ASLR ? no sane person wants that and what if someone gets credited with 2 CVE's for heartbleed, does such a person want to work in industry which awards CVE to person exploiting bugs in 80' APPLE drives, IN 2021? which i know of atlest 50 bugs in them. do i go and request CVE's for that ?
userbinator 5y ago
I think this should be considered a satire of what the "security industry" has become: finding any little thing that they can claim is exploitable, regardless of actual significance, and all the while using paranoia to slowly destroy general-purpose computing and user freedom.
- chaganated 5y ago
  best comment, last comment
SilasX 5y ago
@dang, this one should be merged here or vice versa: https://news.ycombinator.com/item?id=27104125 https://news.ycombinator.com/item?id=27104125
al2o3cr 5y ago
Meh. The "exploit" seems to rely on passing input that contains cells with values that are valid for the universal machine's tape alphabet, but not the simulated machine's. It's as if you could pass a "null terminator" in a Unicode string that didn't match the "normal" null character.
mousepilot 5y ago
I'm going to forward this to our local windows server admins, with the caveat that that it only applies if the particular windows server version is turing complete.

139 points by wsces 5y ago

> NOTE: the discoverer states "this vulnerability has no real-world implications." Not sure if declaring this is standard practice, but I had a good laugh.

yabones 5y ago

> NOTE: the discoverer states "this vulnerability has no real-world implications." At least they're honest about it with this CVE...

stevekemp 5y ago
Issues like this, in obsolete code, are a lot of fun. Even if they are essentially meaningless. I reported CVE-2014-3423 back in the day, relating to GNU Emacs using a predictable filename when talking to the Mosiac browser. No choice, as that was what the browser required, something that wouldn't exist these days.
buitreVirtual 5y ago
I'm not so sure. Some banks and airlines might still be running those machines.

segfaultbuserr 5y ago

A better link is the research paper: https://arxiv.org/abs/2105.02124 https://arxiv.org/abs/2105.02124 > The universal Turing machine is generally considered to be the simplest, most abstract model of a computer. This paper reports on the discovery of an accidental arbitrary code execution vulnerability in Marvin Minsky's 1967 implementation of the universal Turing machine. By submitting crafted data, the machine may be coerced into executing user-provided code. The article presents the discovered vulnerability in detail and discusses its potential implications. To the best of our knowledge, an arbitrary code execution vulnerability has not previously been reported for such a simple system. > A common strategy for understanding a problem is to reduce it to its minimal form. In the field of computer security,we may ask the question: "What is the simplest system exploitable to arbitrary code execution?" In this article, we pro-pose an answer to that question by reporting on the discovery that a well-established implementation of the universal Turing machine is vulnerable to a both unintentional and non-trivial form of arbitrary code execution.

Igorvelky 5y ago
LIES > A common strategy for understanding a problem is to reduce it to its minimal form. In the field of computer security,we may ask the question: "What is the simplest system exploitable to arbitrary code execution?" means that i will remove all security abstractions which were generated in past 40 years and i find that it is more vulnerable this is not research, this is plain and simple trolling, BS feeding
OskarS 5y ago
Haven't looked into this paper deeply, but this reads very strange to me: > This paper reports on the discovery of an accidental arbitrary code execution vulnerability in Marvin Minsky's 1967 implementation of the universal Turing machine. By submitting crafted data, the machine may be coerced into executing user-provided code. It's a universal Turing machine. Its whole purpose is running "user-provided code". That's what a Universal Turing machine does, it runs arbitrary Turing machines. This is a little bit like saying "we found a weakness in the Python interpreter whereby you can feed it specially crafted input that allows you to run arbitrary Python programs". Like... yeah... that's what it's supposed to do.
- qsort 5y ago
  Yes, that's the joke.
  - mycall 5y ago
    Wait until they try unicode, then the joke will be on them.
    - AreYouSirius 5y ago
      reddit is saying that macos is build on turing complete emojis ! we should investigate XD
    - jradd 5y ago
      I cannot fathom how complicated arbitrary code execution could get with multi byte characters that could use shift registers, null bytes and byte order marks with determinism in a NOP slide on a heap spray. Filtering only printable user input helps but even bit map images can expose a heap to a sensitive registers that will execute some target specific generated shell code. https://en.m.wikipedia.org/wiki/NOP_slide https://en.m.wikipedia.org/wiki/NOP_slide. https://en.m.wikipedia.org/wiki/Heap_spraying https://en.m.wikipedia.org/wiki/Heap_spraying

Igorvelky 5y ago

in my opinion this is recipe for DDoS attack on mitre infrastructructure

zitterbewegung 5y ago

Sure this CVE sounds like a joke but if you create a programming language that is non Turing complete it is much easier to secure than a Turing complete language. Making a language that have the expressive power of finite state machines could be an example.

qsort 5y ago
We are doing this already. - Configuration languages (JSON, YAML, XML) are pure combinatorial logic. - Regular expressions are... mostly not actually regular, but you get the idea. - Some templating languages are deliberately less powerful than Turing machines, e.g. ST4 is context-free. - Prepared SQL statements are a similar idea on a different axis. The real question is whether a non-TC language could be useful for general purpose programming. Such a language might come with very strong guarantees (termination, time complexity, even correctness or a limited form of correctness), but they might be extra-cumbersome for 'normal' workloads.
- ludamad 5y ago
  A non-TC language can be achieved just by forcing proofs. Oh, you want that program to run? Just prove that it is bounded memory and can't halt, etc
  - qsort 5y ago
    Yeah, but that's the 'cumbersome' part. Could we imagine a non-TC language with simple syntax that's suitable for at least some of the task you'd use a TC language for?
    - magmastonealex 5y ago
      C compiled down to eBPF (as implemented with the Linux kernel) is not turing-complete. eBPF has a wide variety of uses from network filtering to hooking into certain syscalls. The bytecode is theoretically turing-complete, but the verifier present in the kernel ensures that the code contains no loops and accesses no out-of-bounds memory. With `clang`, you can compile C down to eBPF bytecode. It's a subset of C, with a lot of restrictions, but it is familiar and capable of some remarkable things past just simple packet parsing & filtering.

AreYouSirius 5y ago

But why to make CVE out of that ? this paper, this CVE has nothing to do with ! USEFUL ! research, paper is essentially saying that by using simplest machine possible we prove it does not provide layers of security abstractions which were invented and deployed in last 40+ years to machines so thats like getting CVE for turning off ASLR, AppARMOR SElinux etc in linux kernel. this proof is so obvious that highschooler should have to know this. If research alone does not get credited or recognized why we need to award CVE's to make it more credible ? WHICH IS NOT EITHER WAY second thing do we as industry want VANITY CVE's ? do we really need CVEs stemming from such a absurd exmples as some old vacuum tube computer does not provide ASLR ? no sane person wants that and what if someone gets credited with 2 CVE's for heartbleed, does such a person want to work in industry which awards CVE to person exploiting bugs in 80' APPLE drives, IN 2021? which i know of atlest 50 bugs in them. do i go and request CVE's for that ?

userbinator 5y ago

I think this should be considered a satire of what the "security industry" has become: finding any little thing that they can claim is exploitable, regardless of actual significance, and all the while using paranoia to slowly destroy general-purpose computing and user freedom.

chaganated 5y ago
best comment, last comment

SilasX 5y ago

@dang, this one should be merged here or vice versa: https://news.ycombinator.com/item?id=27104125 https://news.ycombinator.com/item?id=27104125

al2o3cr 5y ago

Meh. The "exploit" seems to rely on passing input that contains cells with values that are valid for the universal machine's tape alphabet, but not the simulated machine's. It's as if you could pass a "null terminator" in a Unicode string that didn't match the "normal" null character.

mousepilot 5y ago

I'm going to forward this to our local windows server admins, with the caveat that that it only applies if the particular windows server version is turing complete.