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

I'm pretty sure that attack you describe is mentioned in literature as essentially undefeatable. I really wish I could remember exactly what the name of it was; the gist is, there has to be a first compiler somewhere. If at any point in the chain, the compiler is infected with a self-propagating virus that hides itself in the byte code of the binary, it can ensure that the exploit is in every future version of the compiler.

I may be remembering the details a bit wrong, but it was a good read.




You're looking for "Reflections on Trusting Trust" by Ken Thompson, one of the original co-authors of Unix:

https://dl.acm.org/citation.cfm?id=358210


There is a possible defense: https://www.dwheeler.com/trusting-trust/


... and the hope is that https://github.com/thepowersgang/mrustc will let us do this for Rust.


I think you are referring to “Reflections on Trusting Trust” by Ken Thompson.

https://www.ece.cmu.edu/~ganger/712.fall02/papers/p761-thomp...


It's not undefeatable. The guy who invented it in 1970's, Paul Karger, told people the concepts on how to defeat it right afterward. Their advice for building systems in a way to catch a lot of subversion was encoded in the first standards for information security. I included most of those methods in my security framework here:

https://pastebin.com/y3PufJ0V

https://en.wikipedia.org/wiki/Trusted_Computer_System_Evalua...

One compiler made to the highest standard in development assurance is CompCert.

http://compcert.inria.fr/

It has specs of everything it does, proofs it does it in tool with minimalist checker, extracts to ML that can be compared against those specs in various ways (eg visually), can optionally be compiled with a mini-ML compiler or Scheme you homebrew yourself, and passed exhaustive testing by third party with only a few bugs in specs (not code). There's another using formal specs called KCC which could be ported to something bootstrappable like META II or Scheme.

The other requirement from TCSEC was that source be supplied to customer to build with their onsite, trusted tools. I looked into even having compilers done in Perl since it's already widely deployed. David A. Wheeler made brilliant suggestion of either bash or awk. I have put tools for those and more on rain1's bootstrapping page. rain1 or someone there called the concept "Ubiquitous Implementations." Note we've focused on technical content, not presentation, on that one being busy folks. Looks rough. :)

http://bootstrapping.miraheze.org/

You also need repo security to protect that source with it either cryptographically sealed and/or sent over secure transport. Link below on repo security from David A. Wheeler. Quite a few forms of transport security now.

https://www.dwheeler.com/essays/scm-security.html

After Thompson wrote on Karger's attack in 1980's, it took a life of its own among people that continue to mostly ignore the prior solutions. It's a problem absolutely solved to death starting with the person who discovered it in MULTICS Security Evaluation. Far as state-of-the-art, the current path of research is exploring how to integrate solutions for many languages, models, or levels of detail in one picture of a system with no abstraction gap attacks with proof of that for all inputs. That's a bit more complex but just an imperative language to assembly delivered and bootstrapped? Straight-forward but tedious, time-consuming work the first time it's done. :) Also, expensive if you buy CompCert which is only free for GPL stuff. Two of us are eyeballed CakeML's lowest-level languages as a cheat around that for verified bootstrapping.

http://cakeml.org/

EDIT: Btw, all that is technical discussion and argument. For fun, you might enjoy the story "Coding Machines" which is about only coding-related story I started reading and couldn't put down. Probably took an hour to read. It covers discovery of a Karger-Thompson-style attack along with how people might respond mentally and in terms of solutions. Some other stuff in that one.

http://www.teamten.com/lawrence/writings/coding-machines/


You want the "trusting trust" keyword.


A talk by Ken Thompson, "trusting trust".


Technically, his Turing award lecture.




Consider applying for YC's W25 batch! Applications are open till Nov 12.

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

Search: