Accidentially Turing Complete

In the (German) Podcast "INNOQ Security Podcast", Episode "Parsen statt Validieren" I discovered a funny concept: "Accidentally Turing complete Software". 

This means that a piece of Software, often a parser, by chance provides everything a computer provides (or in other words, allows to calculate everything that can be calculated).

In other words, if you control the input to this parser (for example a JPEG Parser), you can basically write arbitrary programs that the parser will then happily execute. Depending on the privileges the parsers process has, this can have annoying to devastating effects.

That is one of the reasons why the principle of least privilege is so important: never give a part of your system higher privileges than required.

Matt Rickhard has compiled a small list of accidentially Turing complete Software.

Andreas Zwinkau compiled an even larger list.

The probably most impressive abuse of this was the specially created PDF that NSO used to inject Pegasus into iPhones (although it is debatable of this accidental or intended Turing completeness).

Funny enough, this story is related to this excellent talk by David Kriesel: "Lies, damned lies and scans" where David has shown that Xerox printers used to optimize PDFs just a little too much.