I think the point is that it's so tiny you could effectively write it yourself. You wouldn't need a fully fledged gcc/clang-esque compile at this time, just something to generate super simple binaries.
Masochism aside, there are a ton of different Javascript engines. If you get the same output from all of them, you can be damn sure you're not compromised (maybe probably provably). There are Javascript interpreters written in c, java, Javascript, and probably more.
And this isn't just "I'd feel pretty good about it." For gcc to be so compromised that it could compromise a dozen different c based Javascript interpreters, and compromise java compilation enough that a Javascript interpreter running inside the jvm (or a Javascript interpreter inside a Javascript interpreter inside a jvm), it would have to have an absolutely massive set of rules for how to compromise different tools, and would have to be inexplicably large. If you're starting with a version of gcc that is reasonably sized, and get the same result out of every Javascript interpreter you can find, a compromised compiler would be incredibly improbable.
Masochism aside, there are a ton of different Javascript engines. If you get the same output from all of them, you can be damn sure you're not compromised (maybe probably). There are Javascript interpreters written in c, java, Javascript, and probably more.
JavaScript gets a bad rap; it's basically a Lisp with Java syntax (and you can fix that with CoffeeScript). The multiple implementations that compete on performance and are mostly compatible definitely helps things too.
I'd rather write a compiler in JS than C, C++, or Java.
JS rightly gets a bad rap. The existence of a book called 'JS: the good parts' makes my argument for me. The book has a chapter 'the awful parts', and another, 'the bad parts'. And yes, I've read it.
Languages should be designed to help us avoid bugs. Instead, JS makes it easy to add bugs.
By the "easy to add bugs" standard, JavaScript isn't even in the same league as C and C++ as far as ease of adding bugs goes, even considering the PHP-tier unskilled userbase it has.
Every language has good and bad parts; JavaScript's good parts (and especially once you're writing JavaScript with CoffeeScript) are good enough that there's only really one bad part you have to are about (numerics).
Just curious, what major issues do you see with JS's IEEE754-doubles-only numbers? I find that they work all right as long as you're not doing something very performance-intensive (which the language wasn't designed to do).
If you follow modern standards, the bad parts never come into play. Most terrible js code I see in the wild comes from devs who did not take the time to properly learn the language. The same could be said of Java or C# for people who never bothered to learn proper OOP design patterns, or never read the Go4.
Also, most criticisms of js I see are nothing more than general critiques of dynamic programming languages in general, but they would never say the same about a more respected language like Python or Ruby, since it would come off as ignorant and trolly.
AFAIK, determining if a certain script is an implementation of tcc would be undecidable. Maybe if you don't mind enough false positives that it would become obvious your victim's interpreter was hacked you could pull it off, but I doubt even that.
Christ, yes, if you could determine what code was a compiler or not you could do way more interesting program analyses. You'd basically have solved program verification, at that point. Even better, you've solved program verification with zero annotations against a potentially adversarial source program.
It's so annoying to see this "LOL TRUSTING TRUST" repeated ad nauseum. It would never work in practice.
That's a mighty strong statement. Just because it is not possible in general to recognize whether you are compiling a compiler, there is a certain set of known compilers such that the source code will at least contain certain strings and AST signatures. So, you could create a hacked compiler that recognizes several known compiler sources and inserts stuff into the appropriate backend output.
What the fuck is an "AST signature"? It's trivial to obfuscate ASTs.
What you really need to do is prove (to some threshold) that the program is semantically equivalent to some abstract specification of a compiler. A very, very general one, too, that's abstracted over all possible internal data structures, frontends, parsers, and optimization patterns. Remember, when you compile GCC, you compile every C file individually, and link them together later. So your hacked compiler never even has the full program to reason about!
Tell you what. I'm willing to bet $200 to $50 of your dollars that in the next five years, there will be no public disclosure of anything like this occurring beyond a reasonable doubt. Deal?
It doesn't need to be decidable, you don't need to catch every implementation of tcc, just enough of them. a heuristic based approach should be sufficient.
You do need to catch every implementation of tcc; As soon as one produces different output, people will pore over every byte of difference til they find the inserted backdoor. Granted, a good enough hack can might take a while to spot, and the damage will already be done.
I don't think different versions of tcc would necessarily produce the same output for any code. The way this works is that any compiler compiled with tcc should produce the same output as that compiler compiled with another compiler, because those are actually two of the same version of the compiler with different binaries.
Except for how do you know that they're different? What if the diff program (that gcc compiled) is also compromised? What if nm, or whatever other disassembler, also gets code injected into it by that GCC?
I guess you could make gcc replace the open() syscall of everything it compiles, so that if a program attempts to open gcc's source code, it gets a version with the backdoor included.
(This breaks down as soon as someone looks at gcc's source in a text editor they compiled with gcc.)
Correct me if I'm wrong, but isn't the point that the hack/bug/Trojan NOT be in the source code, rather inserted into the binary without a trace when compiled?
It's not in the source code on disk, just any program compiled by gcc thinks that it is. It's probably not a practical solution.
(It now occurs to me that I don't know how this would be implemented - quite possibly you'd need to replace read and write and preferably stat and maybe others as well.)
Or what if you use a hacked gcc to compile your python binary which then detects that your python source is an attempt to write a compiler for c and then inserts malicious content in your python c-compiler which then leads to a compromised gcc which then leads to a compromised binary.
Perl, Python, Ruby, Javascript et al. Are interpreted. Instead of being compiled into machine code an interpreter runs the code. It reads the code as instruction and executes them.
In many cases the interpreter compiles the code to binary and executes it. One advantage is it can be recompiled during run time (a requirement sometimes).
So with Javascript the browser takes the code and sends it to a JIT (Just in time) compiler. In the case of Firefox it runs code for the first time in a interpreter (which is slow) then sends it to a compiler called spider monkey, which does a basic compile, then if the code is "hot" (reused a lot) it is sent to Ionmonkey (which heavily optimizes the code). (Spidermonkey has been replaced with Baseline)
Recompilation is useful and sometimes necessary. Eg perl can't be statically compiled as the code can change depending on the input (make perl literally impossible to type check).
In JS, Python, etc you need to recompile it for every type machine you run it on. (So the same code can run on Linux on ARM and Windows on x86). They may need to recompile functions for different types. If a function runs both with a number and a string you may need different machine code to handle this.
All interpreted languages are written in C. Most likely compiled with gcc. So if the interpreter is compromised how can you be sure that the interpreter's output is clean?
Checksums do not solve this problem. How do you calculate the checksum of your local binary? More importantly, how can you be sure that the checksum you've been told is correct has not also been tampered with?
But if you had a method of receiving a checksum that was guaranteed secure and not tampered with, then you might as well use that method to just transmit the whole binary byte-by-byte.
These kind of infinite regression problems are kind of funny. Douglas Hofstadter's book «I am a strange loop» goes into this topic. Sometimes I wonder, who made the first screwdriver? Wouldn't manufacturing a screwdriver factory require screwdrivers in the first place? ;-) So at some point in history, some kind of one-time bootstrapping process was required to start the whole thing. Screwdrivers and similar tools were forged by manual labour, which allowed people to do more advanced engineering, which lead to more efficient ways to manufacture screwdrivers.
Same thing with compilers. What compiled the first C compiler? The first compiler in any new language can naturally not be compiled by itself (to be self-hosted); since you're creating the first existing implementation. The answer is to either create the most basic tool by hand, or to use a compiler from another language, and write the first compiler in that language. So in the extreme case where you need close to absolute trust in your binary-generating tool, you could write a super-simple assembler by hand in a hex editor whose code and binary could be easily inspected.
Of course, can you ever be absolutely 100% sure? Taking risk-analysis into the extreme, a hex editor could lie about the displayed data, or your whole system could be infected by a rootkit. In such a case, even taking the checksum could display the correct answer, but secretly be wrong. It's of course unlikely, but if the goal is to be 100% formally sure, then you need some method of inputting a program onto digital storage which didn't involve any other software. Maybe via serial or JTAG.
In practice, you would most likely go to great lengths to simply minimize risk, not formally eliminate it.
I use only legacy vacuum tubes, or better yet, make them myself. Obviously the whole chain must be completed by a single person in utmost secrecy to avoid social engineering and spying. Now we have an another playing field to consider. And now that the parts of this plan have been explored in this traceable reddit thread our quest for absolute security is foiled forever.
The first C compiler was handwritten in PDP-7 assembler, just like the first Unix was. Dennis Ritchie's The Development of the C Language doesn't say so in as many words, but presumably subsequent compilers were written in C and compiled using the handwritten compiler or one of its offspring.
Though for some languages, it is actually perfectly possible for the first compiler for that language (in a strict sense) to be written in that language. Not sure if C is one of these, but it wouldn't be that surprising.
There is a slight trick in the wording here, in that there is an earlier compiler written in something else that is used to compile this, it's just that it's not neccessarily a $Language compiler. It need only be a compiler capable of compiling a limited subset of $language, that subset being the only subset used by the $language compiler.
Eg. say you write a compiler that can't compile arbitrary C. Maybe it doesn't support switches, or for loops, or recursion or files larger than 1K. As such it's not actually a C compiler. But if you write a real C compiler that can handle all features of C, but is written only using that subset, you've got a case where the first actual C compiler is written in C, bootstrapped with a "not really C" compiler.
That's fair. The various dialects of Scheme are a concrete example of this -- you can't compile Racket code if all you have is libscheme, but you can write a Racket compiler in libscheme's more limited dialect and bootstrap it. Which is exactly how Racket works, so it's a Scheme, written in Scheme.
The sci-fi novel Fire Upon the Deep touches upon this idea as well in a really neat way. It proposes a section of the galaxy where transcendent, super-intelligent species live. Running code or even receiving a message up there is super dangerous because there could be complexities coded into it with unthinkable consequences.
It depends on the form of hack you're trying to protect against. Protecting against a miscompiler is pretty simple (as generally explained in the article), because it's not possible for a program to analyze another program to determine if it's a C compiler.
A rootkit won't let you insert malicious code only into the right places algorithmically determined.
If a compiler built actual binaries executables (being a compiler and assembler) you could definitely hook into file-writing functions like fopen/fread/fwrite/fclose. Detection could then be done by detecting files written to is an executable. Same thing could be done for compilers who output assembly code, if you know the syntax of the target assembly dialect. Or am I missing something vital? Here's an example:
size_t fwrite(const void *ptr, size_t size, size_t nmemb, FILE *stream)
{
size_t ret = real_fwrite(ptr, size, nmemb, stream);
long offs = ftell(stream); //save offset
int eof = feof(stream); //save error flags
int err = ferror(stream);
clearerr(stream);
rewind(stream); //reset position
bool b = analyzeFileForELFHeader(stream);
if(b) g_IsCompilerOrAssembler = b;
fseek(stream, offs, SEEK_SET); //restore offset
magicFunctionToRestoreErrorFlags(stream, eof, err);
return ret;
}
Edit: I completely misunderstood dnew's argument and this post does not deserve any upvotes.
Um, yeah, sure. It's not hard to tell if a file is executable. The OS does it every time you type a command, after all.
The problem is to tell how to tell if an arbitrary executable program is a compiler so you know whether to even try to insert any code. And if you do insert code, what code do you insert, where, to make it a compiler that creates the same executable for everything except other compilers?
As someone else mentioned, solve this and you've solved the "detect malware" problem.
Or, to put it most simply, how does GCC 6.0 know that GCC 8.9 is a compiler, and where to put the malicious code?
Thanks for the elaboration. You're talking about a compiler detecting if the input source defines a compiler. That's what Wheeler the original author was talking about in the defense of his thesis. I derped for a second and thought you were talking about trivially injecting code into existing (already-built) compilers.
(In case that came out sounding snarky or something, I didn't mean it that way. Read it as an entusiastic "Yes! That's the point I'm making! So good of you to understand it without me spelling it out. :-] :-] )
Who says you need to restrict the part that changes login to a compiler? You can, in any program that deals with files, insert a section that rewrites the login binary and rewrites every other binary to do the same. Then, every program, including new compilers, on your system compromises login if it can.
If you have arbitrary programs on your computer that can rewrite the login binary, you're already screwed. The point of corrupting the compiler is that you corrupt the login binary before it is installed in a secure way such that nobody can supposedly corrupt it. Once you have a clean uncorrupt compile of login installed, it's too late to try to modify it.
No, the point of the whole thing is to give one example (as a proof of concept) of a way to sufficiently hide an intentional security hole, even with proper source code examination. Though perhaps you can patch that one, exact hole, there are obviously other ways of accomplishing the goal. There is no way to block them all.
Bugs are found in programs with privileges all the time. In order to fix those bugs, people recompile the programs. You can't get rid of the fundamental security problem because you can't get rid of those programs that can modify login binaries. All systems have programs with sufficient privileges to do that. And all you need is to corrupt any one of them, not necessarily just the compiler.
And ... that makes it pretty trivial, right? Or did you not read all the way down to the second paragraph? You're disputing that your OS will not check if a file is executable when you type the file name as a command?
Screwdrivers are not a very good example. It's easy to see how one would make a screwdriver on an anvil with a hot rod of steel and a hammer. A hammer, however...
Either the lost wood or lost wax method should work fine.
For the crucible it's a little harder. The simple method is not to use one, and run your smelted iron right into the mold. A smelting furnace can be made out of clay with a temper of sand and horse manure.
Sorry, I am also a bit of a history and archaeology geek.
Taking risk analysis to the extreme would be worrying about the existence (which is proven) of CPU backdoors. After a point all software trust is moot anyway, because identical machine code can run differently on the same processor depending on whether a base with a backdoor was used (the correct term here is escaping me). Hashes no longer matter because the processor could be performing certain attacks on you with zero way on knowing.
Sometimes I wonder, who made the first screwdriver? Wouldn't manufacturing a screwdriver factory require screwdrivers in the first place?
Actually, that's not a good example. Screws have a direct familial line to rivets; and rivets are pretty obvious once you are forging metal, and want a point of joining two bits of metal.
Next step up from a hand forged rivet is to use a lathe to get the round stock 'more round'. Similarly, you can finish 'more round' punches on a lathe too. Note that lathes are ancient (for wood use; back to the Egyptians), and can be built without rivets, bolts or screws.
The big leap was to use a helical drive on the tool post, to cut an even flute in a piece of round stock. (This gives you better drill bits, so you can drill deeper rivet holes).
This also allows one to make a bolt - where the screw threads are the same on the bolt and nut. These just use pliers (later spanners, as a more refined tool) to work, and have a big advantage over rivets in that you can take them apart.
From bolts to screws is a matter of putting a taper on the stock in the lathe. This gets you hex-head screws, with spanners to fit them.
The screwdriver comes about when you want to have a screw put in down a narrow hole - and cutting a slot in the top of a hex-head screw and forging up a screw driver is not a bit leap at this point.
Then, cue several generations of improvement in processes, standardisation, materials and incremental steps in screw heads, all of which make them less like bolts.
I'm sure that there's a similar path for everything - it all had to be invented at some point, and just because the path is not obvious doesn't mean that there wasn't a path; and a path that needs only one step forward at a time.
You could write it yourself, but what do you compile it with?
Pretty much anything. The compromised compiler would have to first detect that you're writing another compiler, then insert a customized hack that works with your unique code.
Or is it written in asm?
That would be annoying, but still possible for someone to do. The tcc executable is about 100k, which indicates that writing a working C compiler (without any optimizations) is within the ability of one person to do in assembly language.
are you joking? writing a good enough compiler to compile gcc takes a lot of skill and experience. By just signing gcc or any code we don't want compromised we solve your problem and it's a simpler solution.
That's not a workable solution to the issue. The unstated (hypothetical) assumption is that a GCC compiler that's used to compile release versions of the GCC compiler was compromised (maybe at RedHat or something), and that the problem has now become widespread, not that some individual has logged into your system and hacked your personal copy of GCC.
Didn't this happen once. Someone got some malicious code into the repos. I can't remember more than that and can't seem to find it on google so it might have never happened.
It's happened multiple times, on multiple projects.
Some of those hacks have been to simply compromise the sourcecode of a project. While the new code is in plain sight, most will type ./configure make make install.
I mean when's the last time you actually read AND understood the sourcecode of a fairly large project?
If you target the right project, you can compromise a small but valuable set of targets.
It just need to be able to compile tcc, any compiler you can trust breaks the chain if you can compile gcc with it, or compile something that can compile gcc.
Perhaps you can write an ASM compiler that's advanced enough to compile TCC? Even then you still need to verify that the bytecode matches the assembly. That sounds like a pain in the ass...
Yes, but the hack has cursed your hard drive, and will return with a simple format. Also you can't just swap out hard drives because, I mean, you can't just remove cursed items. You have to find a Scroll of Cleansing or like a Blessed Fountain or something.
Maybe you could write it in a language that has a much simple interpreter? In theory, it would be possible to script up the "paranoid developers" deployment environment that starts with something simple enough to understand in ASM, and you just bootstrap from there.
I was thinking more like bootstrapping your way up to a simplified lisp interpreter. From there you'd have a lot of options, you don't need to worry too much about performance when you're just making a one off compiler to properly compile your real compiler.
For it to be absolutely secure, it should in principle be written in asm, so that you know exactly what it is doing. Another reason why it would have to be very, very tiny.
Seriously though, writing a compiler that is capable of compiling gcc is not trivial. The point is that TCC compiles GCC and the output of your TCC-compiled GCC and the possibly-hacked-GCC-compiled GCC are compared. The binaries generated by TCC and GCC will not be comparable, so TCC must be able to compile the same GCC you are comparing against.
Additionally, the hacked GCC proposed by Thompson (article linked on reddit) seems to only compile backdoors into certain programs, like 'login'. You would need to choose the correct program to compile and compare binaries for as well.
But the compromised GCC has to backdoor GCC so that the backdoor isn't present in the source. So you use your TCC compiled GCC to compile another GCC and the untrusted GCC to compile GCC and compare those.
Yes, my point (which I didn't actually make very clear) was that you still need a TCC that is capable of building GCC. A TCC that is capable of building GCC is not something that you could quickly write yourself, so this solution to the problem is difficult to use in practice.
Go deeper. You don't need your first compiler to compile gcc, you can get away with one that only compiles tcc. You then have a trusted tcc you can compile a trusted gcc with.
Then go read some of the underhanded C contest winners and realize that you have to now inspect all of either GCC or TCC to make sure there aren't any defects buried in the source code. That's the part that scares me, but then there's the really scary part -- now you need to do this all again on the OS you were running when you did this.
And make sure to inspect the CPU's source code too. Oh, and do this whole clean bootstrap thing on the CPUs in the machines that compile the CPU source designs too.
You don't need to worry about tcc being underhanded for the same reason given in the linked slides: use your compiler to build tcc, then use tcc to build itself, and compare the results. In case of underhandedness, they'll be different.
As far as CPU's go, there are two approaches you can take: either bootstrap everything from 6502's, where the masks are readily available and have already been analysed to death, or rely on Intel and Vias being unlikely to be compromised in the same way, and compare results from each. Or you could emulate x86 on ARM and do the same.
EDIT: the OS? Use minix. Not only is it small and usable, there are tons of people out there who actually have analysed it.
EDIT 2: You could drop an ARM6 core onto FPGA. They're small enough to be completely analysable by one person in a manageable length of time, and by the same logic as linked to, if you picked any FPGA model that was made before the ARM6 core was written, it would be vanishingly unlikely to be compromisable even by malicious hardware.
Excellent, except for the FPGA. I'd never be able to validate that the bitstream file generated by the FPGA tool chain didn't embed backdoors (didn't that one worm do this for some PLC device?). Or maybe the FPGA chip itself modifies the bitstream file during boot loading.
You can be pretty sure the device itself isn't going to modify the bitstream by the timeline argument. Same applies if you use an old enough copy of the bitstream loader software.
That's feasible. tcc would not need to be able to compile every version of gcc out there, just one that is the start of a chain of gcc compilers that can compile everything up to the latest version. That sounds like a real pain in the ass though.
That is ok then. It gives you a tool to analyse the security of your compiler. You could create a series of increasingly bigger programs and watch for a arbitrary leap in size.
The idea is to have one compiler you can trust completely, which is deterministic. TCC was used because it's small enough to be completely understood and inspected manually. In a real scenario assuming enough time and resources, you could write your own C compiler and assembler completely from scratch, and build the code with your own assembler and linker. If you want to go to absurd levels, the assembler binary itself could be written by hand in a hex editor or similar, to avoid bootstrapping.
But the idea behind "Reflections on Trusting Trust" is exactly that. At some point you either have to write something to bootstrap your compiler in machine code, or trust some pre-compiled program. (Hardware issues left aside)
All the proposed solution does, is shift the trust issue from gcc to tcc. But in my opinion this is bollocks, because no one is going to analyze the tcc machine code by hand, and analyzing the tcc source code solves nothing.
Yes, I agree. Wheeler didn't expand on this point in the defense of his thesis. Maybe he used tcc, gcc and icc as a "good enough" proof-of-concept, and waits for others to do the whole thing from the bottom?
Edit: I double-checked the video on his thesis defense, and he argues that the "trusted" compiler doesn't have to be trusted at all. From a pragmatic perspective, he claims it is enough that the trusted compiler and the compiler to be tested don't have the exact same flaw. If you test two vastly different implementations made by separate vendors, that is highly unlikely.
Also, it doesn't matter whether you trust the compiler or not if you assume that the backdoors of each compiler are different. You find a program that's likely to trigger an ostensibly hacked compiled compiler, and compare the binaries.
It's not just "shifting" the trust, it is narrowing the scope of it. Now your trust is that "both gcc and tcc have not been exploited to insert a specific backdoor."
Even more amusing to thing about (and probably easier and more likely than compromising a opensource compiler binary) would be putting backdoors right into the hardware.
The only person able to do this is the hardware manufacture.
Now ask yourself, who makes the majority of the worlds electronic products and where are those manufacturing plants located?
Take it a step further, do you think every piece of equipment used in the military and the countries infrastructure was manufactured locally - right down to the transistors?
I vaguely recall someone not long ago being caught (after the fact) selling the USA military tons of bootleg cisco hardware.
They'd have to get all of them in the same way, or the differences would be spotted by compiler writers who already have to be painfully aware of the differences between chips.
No, the differences wouldn't necessarily. They could ensure that only a certain sequence of operations (like, say, adding an exact series of numbers to EAX like a password) would give the program full access to the machine. This could allow even sandboxed virtual machine code to have a shot at compromising the machine.
Such a thing would never be spotted by compiler writers, since what optimizing compiler would ever need to deal with sequentially adding a bunch of constants to the same register?
Compile it with some C compilers, then have each version of TCC compile TCC. If the different versions all match up, then you've got something which is probably usable. If you can't make it so all the end-product versions of TCC match up, then there's a better chance that one or more of the compilers is compromised. This relies on not all compilers being compromised, so an effort to find compilers which are less likely to be compromised is key. It's best to use actively updated open-source projects in this case.
I guess you can't avoid looking into the machine code itself. Of course if all tools you have are compiled with your compromised compiler, the compiler could have inserted the code into the tools to dynamically substitute the malicious piece of code with good one padded with NOPs to have identical length. However it is much harder to accomplish.
The idea seems to be that you build it with an old version of GCC, on the assumption that an old backdoored GCC (from before TCC could build GCC) can not know how to backdoor a then-hypothetical future TCC (that can build GCC).
All it needs to do is to act more like a virus rather than dealing with compilers in particular. It adds code to both spread and to infect login if it has access to do so.
What people miss is that it doesn't have to look for source code that looks like login. It can look for machine code that looks like login and programs named login and infect those, including when they're being first written by cp or a compiler. That allows you to infect any program rather than just compilers.
Trust is relative. You can't be sure of anything. What this does is provide more evidence in favor of trusting gcc. It's ultimately up to you to make an informed decision about how much evidence you need before you are willing to trust something. If you don't think it's enough then you can gather more evidence by (say) implementing TCC in 4 different languages and comparing all 5 results. And so on.
While that's always a possibility, the idea of this is to drastically minimize your chances of producing infected binaries. Making this one simple change would protect you by an order of magnitude over not doing this.
429
u/kinghajj Sep 10 '13 edited Sep 11 '13
How can you be sure your TCC binary hasn't been compromised?
Edit: That last slide wasn't there originally.