Hacker News new | past | comments | ask | show | jobs | submit login

GNU's printf specifier language is Turing complete, I believe.



Theres a great example of what you can do with this, submitted and discussed on HN here: https://news.ycombinator.com/item?id=25690319


>Format specifiers can take extra “arguments”. - "%hhn": store the number of bytes written mod 256 to the char pointer ...

Oh boy. I'll put that down for my "thing I don't think I wanted to know" of the day.


There is some innocent beauty in the twistedness of printf - especially with GNU extensions.


So I can port doom to gnu printf?


GNU's printf specifier language is Turing complete, I believe.


GNU's printf is Turing complete[0]... so "yes."

[0] Mentioned (but not directly linked) by TFA:

https://www.usenix.org/conference/usenixsecurity15/technical...


GNU's printf specifier language is Turing complete, I believe.


What is up with this thread? These comments are duplicated from the top thread...


Is it possible that it's a joke based on the material of the OP? Maybe we're trapped in some sort of International Obfuscated Internet Thread Contest...

Edit: ok, I'm guessing it's a joke about Turing completeness. Loops, you know.


It’s a joke about the recursion introduced here: https://news.ycombinator.com/item?id=25691615.


Well executed jokes on HN. 2021 already is a crazy year.


Ohhhh... Now I get it.


(The usernames are different)


Presumably it needs a loop around it, so it's not Turing-complete by itself?


No need to use a loop around it, printf can take care of that pesky detail for you! To quote [0] (my emphasis):

> To achieve full Turing-complete computation, we need a way to loop a format string. This is possible by overwriting the pointer inside printf() that tracks which character in the format string is currently being executed. The attacker is unlucky in that at the time the “%n” format specifier is used, this value is saved in a register on our 64-bit system. However, we identify one point in time in which the attacker can always mount the attack. The printf() function makes calls to puts() for the static components of the string. When this function call is made, all registers are saved to the stack. It turns out that an attacker can overwrite this pointer from within the puts() function. By doing this, the format string can be looped.

> An attacker can cause puts() to overwrite the desired pointer. Prior to printf() calling puts(), the attacker uses “%n” format specifiers to overwrite the stdout FILE object so that the temporary buffer is placed directly on top of the stack where the index pointer will be saved. Then, we print the eight bytes corresponding to the new value we want the pointer to have. Finally, we use more “%n” format specifiers to move the buffer back to some other location so that more unintended data will not be overwritten.

[0] https://www.usenix.org/system/files/conference/usenixsecurit..., Appendix B "Printf is Turing-complete".


Or, you know, you can just use printf to overwrite the return address and ROP your way to a shell.


Herein lies madness


Not portable, but if you can get the address of the stack you can force printf to overwrite the return address, obviating the loop.


It does not need the loop. It might be easier to understand by looking at something like this. [0] That printf allows for this kind of Turing complete control flow is well known [1].

[0] https://github.com/HexHive/printbf

[1] http://nebelwelt.net/publications/files/15SEC.pdf



The implementation is accidentalyl turing-complete because you can exploit it to get arbitrary memory writes. But the language as specified is not Turing-complete.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: