9 ms·
Reflections on Rusting Trust
- zitterbewegung 10y agoA way to migtate this attack is here http://www.acsa-admin.org/countering-trusting-trust-through-diverse-double-compiling/ http://www.acsa-admin.org/countering-trusting-trust-through-... .
- Manishearth 10y agoYes, I mention it in the post :)
- akkartik 10y agoWorth linking "diverse double-compiling" there or to some other resource, if I may make the suggestion. For other interested readers: a) html version of David Wheeler's dissertation: http://www.dwheeler.com/trusting-trust/dissertation/html/wheeler-trusting-trust-ddc.html http://www.dwheeler.com/trusting-trust/dissertation/html/whe.... I read it over a week last month, and it made a big impression on me. b) the HN discussion for the Wheeler dissertation: https://news.ycombinator.com/item?id=12666923 https://news.ycombinator.com/item?id=12666923
- Manishearth 10y agoGood point, linked!
- tcoppi 10y agoWell it looks like this answers the question I posited above. Very interesting work, surprised I hadn't seen it.
- nickpsecurity 10y agoAs I said there, Wheeler was exemplary for handling most of this right ahead of time. He gave credit to Karger for inventing the compiler subversion attack. He wrote the reference page on high-assurance FLOSS (for compiler verification) and high-assurance SCM (for repo security, esp distribution). He also wrote a cheat I gripe about in reproducible builds to give us something to work with if high-assurance methods get ignored. Any of his stuff on this subject is worth reading. Here's his high-assurance and SCM pages: http://www.dwheeler.com/essays/high-assurance-floss.html http://www.dwheeler.com/essays/high-assurance-floss.html http://www.dwheeler.com/essays/scm-security.html http://www.dwheeler.com/essays/scm-security.html
- drvdevd 10y agoGreat writeup! And actually a fun idea for an intro to rust compiler internals. I'll be stepping through this in detail later. It would be extra cool if you had a series and did this with Go as well :)
- Manishearth 10y agoThanks! It shouldn't be hard, and I've played with the Go AST before. I ... could :) This was sort of a bucket list thing though, doing it a second time is less fun :p And I don't have that much time. Why don't you try? The technique explained in the blog post is pretty universal. Go has an AST too, and while the Folder abstraction doesn't exist in its codebase (as far as I know), you can still tweak the AST. In the case of Go it would be easier to do the injection during parsing. https://github.com/golang/go/blob/5c9035acc1e1540a564ea660000f4f64e783d5ac/src/go/parser/parser.go#L2369 https://github.com/golang/go/blob/5c9035acc1e1540a564ea66000... would be a good entry point. https://golang.org/pkg/go/ast/ https://golang.org/pkg/go/ast/ should help. (I am not a Go compiler dev so there may be better entry points)
- kibwen 10y ago> It shouldn't be hard, and I've played with the Go AST > before. I ... could :) Do it! :) Sadly the title is destined to be less fabulous than this one, but given Thompson's association with Go the motivating angle is obvious.
- drvdevd 10y agoAh yes - I forgot to mention: great title!
- drvdevd 10y agoI think I might as well :) Time is also an issue for me though, but it's not a complete impossibility. I appreciate the tips on starting points. Very interesting. If I do end up doing something like this I will give credit where it's due.
- deleted 10y ago[deleted]
- vog 10y agoFrom that article: > Simply recompile the purported source code twice: once with a second (trusted) compiler, and again using the result of the first compilation. If the result is bit-for-bit identical with the untrusted binary, then the source code accurately represents the binary This sounds very familar to me. If I remember correctly, this is exactly what happens when you build GCC. GCC's 3-stage bootstrap process is well-known for a long time, as well as the decussion about whether this makes sense or is just paranoid. It's nice to have this written down and analyzed throughly in a scientific paper, though.
- preordained 10y agoI'll dig into the article, but out front there is something I don't understand. What is this second, trusted compiler? How did we get that? Why not just use that and its results, rather than vetting foreign compilers...? EDIT: Reading, but I think I'm having more questions, not less. The compiler source could introduces optimizations into the compiler binary's output that could be used to recompile the source again and get a _better_ binary right? The article speaks of compiling the source once with the the foreign compiler and then again with its results; but, on the trusted side it seems to be saying you just do one compilation and you don't compile the source again with the result of that compilation. Seems like you'd have to use the same measures on both sides before comparing binaries?
- floatboth 10y ago> a second (trusted) compiler but… can we assume that any compiler is trusted?
- nickpsecurity 10y agoWe can't. It's why we need verifiable builds. C0, CompCert, KCC, and Simpl all have strong evidence of their ability to produce correct code from good C or specs of it. Checking that on local tooling plus an assembly build of it would be a start. It can build other things. Or you can use the incremental approach I describe elsewhere in this thread.
- tcoppi 10y agoAn interesting experiment would be to see if a modern, easy(relatively) to audit compiler like tcc can still be used to bootstrap a more full-featured compiler like gcc or llvm. That would provide at least some protection against this, in that it is unlikely a backdoor in your binary version of gcc will have a trusting trust backdoor for tcc, which can then compile a clean gcc. I know this was possible in the past, but I'm not sure if tcc can still compile a relatively new gcc.
- Gankro 10y agoThis particular attack is done entirely in the rustc frontend, so adding another way to build the backend shouldn't matter? One requires a new implementation of the frontend to apply diversity mitigations.
- kibwen 10y agoWhich makes me wonder if Miri ( https://github.com/solson/miri https://github.com/solson/miri ) counts as an alternate implementation of the frontend. Combined with, say, Cretonne ( https://internals.rust-lang.org/t/possible-alternative-compiler-backend-cretonne/4275 https://internals.rust-lang.org/t/possible-alternative-compi... ) I wonder if we couldn't cobble together an alternate frankencompiler for mitigating RoTT.
- Manishearth 10y agoYou need to generate the MIR though (to feed to miri); this only fixes attacks that happen in the pipeline after MIR. Doing path and type resolution is the tough part and so far we only have one implementation of that. https://github.com/thepowersgang/mrustc https://github.com/thepowersgang/mrustc exists, anyway. I don't think it can compile rustc yet.
- deleted 10y ago[deleted]
- nickpsecurity 10y agoBetter off making it close to but not C language so it's easy to compile. A language easy to compile + easy to write a compiler in. Scheme and ML are probably ideal for the compiler + verification part given I've seen it done already down to machine code in relatively few pages of text. Not C-like, though. Best method I can think of is assembly writes a macro assembler that writes compiler for simple, high-level language which is used for the first, C compiler. That compiles the complicated, optimizing one. HLA, a P-code variant, and Hansen's Edison are all potential contenders for low-level language. An Oberon-like language with something closer to C syntax & Wirth-style compiler might do for initial, high-level language. tcc or QBE backend have potential for simple, initial, C compiler. I'd do both LLVM and GCC for last step as good projects rely on each. If one wanted to spend money, then license CompCert, extract it to ML, compile with CakeML, verify each function against assembly, and equivalence check everything with testing. CompCert verifies C to ASM with its outputed ML verified by CakeML assuming their specs are correct. Easiest cheat. Use CompCert to compile first C compiler, the main C compilers, or anything else you can.
- foota 10y agoSeems to be like the best way to mitigate this would be to write a rust interpreter in assembly and use that to compile the compiler.
- kibwen 10y agoIt doesn't need to be in assembly, you could write a compiler/interpreter in any non-Rust language and use that to verify the compiler binary from source (unless you think that someone has already inserted a backdoor into your X-lang compiler with the specific intent of inserting backdoors into the Rust compiler, which is a bit of a stretch (especially if you use a compiler that completely predates Rust, e.g. a version of GCC from 2005)). And even writing your compiler in assembler doesn't provide assurance that your CPU itself hasn't been compromised. :P
- Gankro 10y agoI still believe in the dream of the mythical Graydon Backdoor in OCaml. No one could even be mad, it would be so good.
- kibwen 10y agoEventually it will be revealed that he even bothered to politely document the backdoor in the Rust reference manual, confident that nobody would ever, ever believe anything found in the reference manual.
- steveklabnik 10y agoIIRC, last time he was asked about this, he said something like "I consider it a great compliment that someone thinks I'm smart enough to have done this, I assure you I am not."
- foota 10y agoTil the google results for "Graydon Backdoor" are... interesting.
- qwertyuiop924 10y ago
- scythe 10y agoI suppose the true counter is to write a verified scheme (or forth) interpreter in assembly language, and then write a simple rust compiler in that scheme, which you use to compile the real compiler, and then you can use that to make an optimized build of the compiler. >So you have a string containing the contents of the module, except for itself I assume interesting versions of TT would have to avoid this trick, since someone running "strings" on the binary would notice something very suspicious, unless something strange is done to string literals.
- Manishearth 10y agoUnless your assembler, loader, OS, or microprocessor is also backdoored :) The original article was really about this -- at the end of the day, you have to trust _someone_. Of course, we more easily trust microprocessors and assemblers over binary blobs, so > I assume interesting versions of TT would have to avoid this trick Pretty easy to encode the string literal into some binary format. Alternatively, serialize and later deserialize the AST with a stable binary serialization mechanism. A really good version of TT operating on the AST would have to backdoor not only the part where it creates the AST, but also the parts where intermediate state is displayed by the compiler (e.g. where it can dump AST/MIR output). There are things you can do. As a proof of concept, I didn't bother to do them. My current POC is toothless and I like it that way! It's cleaner to instead operate at the end of the pipeline; on llvm ir or the generated binary (but it's also harder to write). And if you can insert a trusting trust attack in llvm itself, well, that would be something :)
- dwheeler 10y ago> Unless your assembler, loader, OS, or microprocessor is also backdoored :) True... but it has to be backdoored for that particular system. There are many ways you can make it very unlikely that the other compiler/system is backdoored for the same target. For more information, see my work: http://www.dwheeler.com/trusting-trust/ http://www.dwheeler.com/trusting-trust/
- Manishearth 10y ago
- mrob 10y agoHow about writing a minimal pseudo-Rust compiler that treats all invalid Rust code as undefined behavior? This would be a lot easier than reimplementing the real Rust compiler, because a lot of the complexity is in the compile time error checking (eg. the borrow checker) and the detailed error messages. The original Rust compiler could be used to check the code is valid first. Would this be any use for diverse double compiling style countermeasures? You might be able to write a backdoor that both circumvents the error checking in the real Rust compiler and exploits undefined behavior in the pseudo-Rust compiler, but this must be more difficult than a traditional trusting trust attack.
- Manishearth 10y agoI think that borrow checking is only a minor part of the complexity. You still need to do most of type checking for type and method resolution. So it would be easier, but not much easier. But yes, such a compiler can be used.
- comex 10y agoSomeone has tried to do something along those lines: https://github.com/thepowersgang/mrustc/blob/master/README.md https://github.com/thepowersgang/mrustc/blob/master/README.m... > Thankfully, (from what I have seen), the borrow checker is not needed to compile rust code (just to ensure that it's valid) It's not finished, though, and honestly I'm pretty sure that borrow checking isn't even that hard compared to all the other stuff a Rust compiler has to do, like generic/trait resolurion. But we'll see.
- naasking 10y ago> It's not finished, though, and honestly I'm pretty sure that borrow checking isn't even that hard compared to all the other stuff a Rust compiler has to do, like generic/trait resolurion. You can implement basic trait resolution via name mangling and a global map. I did this as an experiment a number of years ago to implement type class-like overloading in C. I'm not sure how far you could take that technique though. I don't think it would work for higher-kinded types, but Rust doesn't have those.
- qwertyuiop924 10y agoThis is pretty cool, and a neat demo. For the minority of you that haven't read the original Reflections on Trusting Trust, you should do so now. It goes more in depth on this attack category, and its implications. Personally, I would say it's one of the few papers that should be required reading for programmers (along with In The Beginning Was The Command Line, and The Lambda Papers).
- nwah1 10y agoSo, technically, it is possible that there's an undetected backdoor that has lingered around since GCC 1.0
- smegger001 10y agoTechnically it would have been in the original C complier written for the original unix by Ken Thompson and Dennis Ritchie, and been compiled in every complier and login utility since the 70s. At this point try finding a complier that doesn't trace is compiling lineage at some point reach back to a complier compiled by a complier that doens't eventually reach back to it may be pretty hard.
- nwah1 10y agoTrue, but that compiler wasn't open source. The real head-scratcher here seems to be that you can have a self-replicating security vulnerability in a completely open source stack including the compiler
- nickpsecurity 10y agoIf you really find that attack interesting, you might also find it interesting to read the paper Thompson ripped it off of. Paul Karger co-invented INFOSEC and more attacks/defenses than about anyone in the field if you're counting foundational stuff. He wrote during his landmark pentest of MULTICS that the PL/I compiler could be subverted with a trap door. Added you could even do a compiler/compiler trap. The trap doors were their favorite technique. Thompson was working on MULTICS and received that evaluation. His initial citation for his idea was "an unknown, Air Force document." They made him change it later by giving him another copy. Everyone still credits Thompson despite Karger inventing it and the original mitigations. Those became part of Orange Book class A1 requirements for security certification with all those products coming with defenses against subversion by malicious developers. The misattribution and forcing a correction by Thompson is in 3.2.4 of their lessons learned paper: http://hack.org/mc/texts/classic-multics.pdf http://hack.org/mc/texts/classic-multics.pdf Here's the original paper where the so-called Thompson attack is described on page 17. https://www.acsac.org/2002/papers/classic-multics-orig.pdf https://www.acsac.org/2002/papers/classic-multics-orig.pdf Also note they were inventing both hacking techniques and INFOSEC while doing this evaluation. It was part of forerunner work happening among small number of people with little to draw on. It's why you see me say "the legendary Paul Karger" when describing the results they got. Due credit might be "Paul Karger's compiler attack popularized & further explored by Ken Thompson's paper, Trusting Trust." I keep mentioning it until more give it. Back on topic. These days we have verified and certifying compilers, too. Even typed assembly language with correctness proofs. Lots of stuff to base it off of that's close to what most developers can understand. Basic refinement from Rust compiler code with no optimizations to macro assembly or local scripting languages is what I've been recommending outside verified compilers since any developer can do it without special tooling. I even proposed bash one time although as a compile target more than what I'd try code it in lol. I see using local scripting is in your suggestions, too. That different people are thinking on same lines here more often might mean it's worth exploring further.
- yazaddaruvala 10y agoSay a trusting trust attack is discovered. Whats the resolution? Do you manually edit the binary? Do you rewrite a compiler in a language with a verified compiler? Would something like randomizing memory layouts, or reversing stack direction be an easy mitigation or solve an attack like this?
- rusbus 10y agoRandomizing memory layouts and modifying the stack will have no impact since this attack isn't exploiting anything in the language, you've created a compiler that intentionally miscompiles source code. And not only does it miscompile source code, it miscompiles itself so that it preserves the exploit. One potential way to try to remove attacks like this is to run the source code of the compiler through something that randomizes the structure and text without changing how it actually functions. That way, you may be able to defeat the code that is trying to match on code that looks like the part of the compiler it's trying to hijack.
- logicallee 10y agoyou use an old compiler binary that didn't have the attack yet to compile the latest source code that it is able to compile, then use that compile the latest it can compile, and so forth. what I mean is that I wouldn't expect a the 2012 rust prerelease to be able to compile the 2016 rust source code, but it can probably do 2013, use that to compile 2014, use that to compile 2015 use that to compile 2016. As long as you have a single binary from any point before the attack was introduced it shouldn't be an issue. The whole point is that at no point does the source code contain the trust backdoor, so you can just work forward from any binary that doesn't have it yet. if the very first version of rust binary already had it as an issue, as well as was written in rust, you could conceivably have a problem though. then you would need an alternative compiler, however sub-optimal it might be... or you could simply patch and remove the backdoor from the binary and then have it compile itself without inserting the backdoor.
- Manishearth 10y ago> but it can probably do 2013, use that to compile 2014, use that to compile 2015 use that to compile 2016. Clearly you aren't aware of Rust's history :) proto-Rust has been under so many rapid changes that each compiler usually only compiles with a specific hash. Now stuff works with a numbered Rust release, but that's a relatively new phenomenon. This process will likely need to go through hundreds of compilation steps. Doable, but not as simple as a year-by-year process.
- adamcharnock 10y agoI believe this attack featured early on in the Nexus trilogy of books by Ramez Naam. I remember being impressed at the time. An excellent read covering many topics often featured on HN. Edit: typo
- tomerv 10y ago> "The local variable is called krate because crate is a keyword" This is an interesting solution to a problem I often face (whenever I write a tool to in environment X to process something for environment X) . Is this a common way to handle this problem? I don't think I've seen this before.
- steveklabnik 10y agoYes. In Ruby, 'class' is a keyword, so most people use 'klass', for example. The other one that comes up in Rust is 'type', people tend to use 'ty'.
- wink 10y agoThe Java version used to be 'klass' and 'clazz' - haven't seen it in a few years though.
- Manishearth 10y agoI've seen it crop up quite often in JNI code (also code that uses reflection)