7 ms·

Reflections on Trusting Trust (Ken Thompson's Turing Award speech)

147 points by dlo 15y ago

mycroftiv 15y ago
I never get tired of re-reading this. It goes right to the heart of what is magical and wonderful and also scary about computer programming, the sheer power of abstraction available and the unintuitive consequences that are a result of those possibilities. It also makes me wonder how much we can rely on things generally held to be secure. I certainly have never tried to guarantee that the compilers I get from the distros I use are fully honest, much less disassemble my BIOS, and of course the tools I would try to use even if I did achieve that level of paranoia might not be reliable and I would need other tools to test the tools, and the next thing you know I'm out in the woods sawing at trees to get lumber to carve because only a hand-built analytical engine is a reliable and trustworthy platform in any provable way.
- stcredzero 15y ago
  The world needs an opt-in trusted execution environment. If it is mandated from above, then people will rebel against it. At the same time, it must not put compliant programs at a disadvantage to noncompliant malware, as most sandboxing schemes do so today.
  - jleader 15y ago
    Did you read the article? Who will you trust to build your "trusted execution environment"? What tools will they use to build it?
    - deleted 15y ago
      [deleted]
jleader 15y ago
I think of this essay whenever someone talks about making something "100% secure".
- aidenn0 15y ago
  At least some types of safety critical software require binary analysis, which is expensive, but addresses both this, and the more banal compiler bugs.
  - rxin 15y ago
    The binary file reader could have been compromised.
    - stcredzero 15y ago
      Write it yourself?
      - _delirium 15y ago
        ...on an operating system you wrote yourself (or fully understand), on a chip you fabricated from a design you thoroughly understand
        killerswan 15y ago
        But who trusts you or me, anyways?
        stcredzero 15y ago
        NAND to Tetris http://www.cs.huji.ac.il/course/2006/nand2tet/ http://www.cs.huji.ac.il/course/2006/nand2tet/
        silentbicycle 15y ago
        Better link: http://www1.idc.ac.il/tecs/ http://www1.idc.ac.il/tecs/ But yes, awesome book. :)
      - rxin 15y ago
        The compiler could've been compromised too, as said by Ken Thompson.
sdfgewhger 15y ago
ONLINE STORE : ====( http://www.etradinglife.com http://www.etradinglife.com )===== The website wholesale for many kinds of fashion shoes, like the nike,jordan,prada,, also including the jeans,shirts,bags,hat and the decorations. All the products are free shipping, and the the price is competitive, and also can accept the paypal payment.,after the payment, can ship within short time. free shipping competitive price any size available accept the paypal jordan shoes $32 nike shox $32 Christan Audigier bikini $23 Ed Hardy Bikini $23 Smful short_t-shirt_woman $15 ed hardy short_tank_woman $16 Sandal $32 christian louboutin $80 Sunglass $15 COACH_Necklace $27 handbag $33 AF tank woman $17 puma slipper woman $30 ====( http://www.etradinglife.com http://www.etradinglife.com )=====
ChuckMcM 15y ago
I love this essay too. When I was looking at security issues that were going to arise by creating 'executable content' with Java it reminded me of the sheer magnitude of the problem. In re-reading it I was struck by this comment: The moral is obvious. You can't trust code that you did not totally create yourself. (Especially code from companies that employ people like me.) Ken was one of the people Google hired who didn't have to get 'slotted' (for obvious reasons) and Bill Coughran held him up as the "the kind of engineer Google wants to hire." The juxtaposition is delicious.
- tzs 15y ago
  What does it mean to get 'slotted' at Google?
  - ChuckMcM 15y ago
    Sorry, nominally when Google hires engineers they offer a job at 'x' level of engineer but you're not actually hired at that level. What they do instead is wait 6 months and then a committee evaluates your performance relative to other engineers in the company and then tells you what level you are at Google. The point of the exercise is to avoid hiring people as 'Senior Staff Engineer' (even if they had that title at a previous company) and then finding they only put out 'Staff engineer' or less in the Google equivalent. They don't change your salary if they effectively demote you down a slot or two but the pay ranges are different. If the committee decides you are more than a couple of levels below what you were hired at they fire you. If you do 'down slot' it means that if you do get a promotion later you probably won't get a pay raise. Its supposed to keep things evened out. Generally it means they don't successfully hire senior people from outside the company. It was entirely unclear to me how they handled acquisitions of talent.
- gnosis 15y ago
  Whenever there's a mention of someone of Thompson's caliber working for Google I'm reminded of what Jeff Hammerbacher said: The best minds of my generation are thinking about how to make people click ads. That sucks.
kevinburke 15y ago
My compilers professor gave this to our class on the first day. Love this article.
SamReidHughes 15y ago
One of the awesomest moments in science fiction is in Accelerando when one of the characters reveals that it's bootstrapped itself up from an alarm clock controller to escape this attack.
swolchok 15y ago
There's a practical (for some value of practical) defense against this attack: "Countering Trusting Trust through Diverse Double Compiling." It's fairly clever. http://arxiv.org/pdf/1004.5548 http://arxiv.org/pdf/1004.5548 If I recall correctly, here it is in short: 1) Invent a new virtual machine ISA. 2) Write a trusted compiler that targets that ISA. It is totally OK if this compiler is crap as long as it is correct. 3) Build the original compiler with the new compiler. The result is a cross compiler, running on your new VM-ISA and targeting your host architecture (e.g., x86). 4) Build the original compiler again with the output of step 3. The result is an x86-hosted compiler targeting x86. The abstract seems to imply the last step: 5) Diff the output of step 4 with the untrusted compiler. The author, David A. Wheeler, apparently expanded on this paper for his 2009 dissertation: http://www.dwheeler.com/trusting-trust/ http://www.dwheeler.com/trusting-trust/
- runningdogx 15y ago
  What about trusted hardware? Without that, your somewhat trusted compiler cannot be trusted, even if it's something like tcc whose code you might realistically be able to formally verify by yourself. There are at least two approaches, but neither are really satisfactory... first, using an electron microscope and validating the finished design gate by gate. That won't work if the software and hardware toolchain used to generate the gate design is compromised. So you'd have to validate the gates without the help of the software toolchain used for design and layout. I suppose you could also attempt to validate silicon (sans microcode) by attaching a clever external apparatus and external clock source and current meter (which you trust?), and timing every single instruction that hits the processor, validating the time it takes for the instruction to return results and the power consumed, and comparing that against the design specs. That suffers from the same general problem though: unless you're deriving timing and power consumption from basic principles, the tools used to generate expected timings and power consumption could have been compromised. For processors with few gates, though, it could work. The worst situations are where the malware is so subtle -- one changed gate or instruction for instance, with a specific application in mind that can be subverted through that change -- or where from an external POV the malware is non-deterministic, for instance if a processor randomly and rarely injects malware into a running system, using a hardware rng for randomness, on average once every million years of cpu time. Would chip makers be able to detect those sorts of attacks if they tried?
bitsai 15y ago
I had the pleasure of reading this paper during a computer security course. To complement the paper, the prof gave us the task of writing a 2-level polyglot quine (a program in language X that outputs a program in language Y, which outputs the original program). It was my first exposure to quines, let alone polyglot quines, so you can imagine how much I struggled. This paper will always remind me of the frustrations I experienced, and the brilliance of the moment when the "trick" finally clicked for me.
Groxx 15y ago
Someone correct me if I'm wrong, but isn't there a relatively-easy solution to this? Store everything in a versioned, secure-hashed repository. Git is too complex, just checksum everything and store it along with the code (this repository is created by the rest of this paragraph). Hand-build a minimal, trivially-human-readable (thus trustable by those who are interested) compiler to compile the first commit. Compile SHA. Get a secure hash of the binary. Store it. Read the next commit. Verify there is no "compile('bug 1')" in that step. Compile it with v1, and store the hash. Continue. You now have a chain of trust established, starting with something you can read easily, and building minimally at each step (just read the diffs). And you've got the signature of the trusted compiler at any stage. Now check the signature of the downloaded compiler against your known-trusted signature. Compile, secure in the knowledge you have no infected compiler - an infected one wouldn't match the signature of the compiler you could create from your most-recent trusted result. This is extendable with digital signatures, the algorithms of which can be understood with a little number theory, and the code shortly thereafter. Choose who you trust, and spread the work out, just like every other trust-based system. Or trust nobody, and do it yourself (edit: yes, this implies you must build your own computer from tools you develop independently). We've now arrived at the problems around trusting other humans, which are unsolvable. The fact of which must be accepted to varying degrees, or rejected entirely, which requires you to live in isolation. Since you're reading this, you're not in isolation, so you accept some level of human trust, so the previously-established chain of trust would solve the issue for you if the ones you trusted had approved the chain you're using. In this setup, all you'd need to trust is others who fill the gaps you don't directly approve yourself (note that this includes the security / validity of the hash algorithm). Which is the best you can do without omniscience, which would solve the trust issue on its own anyway.
- gaius 15y ago
  You are wrong, because you make a huge leap of faith here: Choose who you trust No-one deliberately chooses to use software written by people who are known to be untrustworthy! And never has! Yet we find ourselves in a less than perfect world...
  - 15y ago

147 points by dlo 15y ago

I never get tired of re-reading this. It goes right to the heart of what is magical and wonderful and also scary about computer programming, the sheer power of abstraction available and the unintuitive consequences that are a result of those possibilities. It also makes me wonder how much we can rely on things generally held to be secure. I certainly have never tried to guarantee that the compilers I get from the distros I use are fully honest, much less disassemble my BIOS, and of course the tools I would try to use even if I did achieve that level of paranoia might not be reliable and I would need other tools to test the tools, and the next thing you know I'm out in the woods sawing at trees to get lumber to carve because only a hand-built analytical engine is a reliable and trustworthy platform in any provable way.

stcredzero 15y ago
The world needs an opt-in trusted execution environment. If it is mandated from above, then people will rebel against it. At the same time, it must not put compliant programs at a disadvantage to noncompliant malware, as most sandboxing schemes do so today.
- jleader 15y ago
  Did you read the article? Who will you trust to build your "trusted execution environment"? What tools will they use to build it?
  - deleted 15y ago
    [deleted]

jleader 15y ago

I think of this essay whenever someone talks about making something "100% secure".

aidenn0 15y ago
At least some types of safety critical software require binary analysis, which is expensive, but addresses both this, and the more banal compiler bugs.
- rxin 15y ago
  The binary file reader could have been compromised.
  - stcredzero 15y ago
    Write it yourself?
    - _delirium 15y ago
      ...on an operating system you wrote yourself (or fully understand), on a chip you fabricated from a design you thoroughly understand
      - killerswan 15y ago
        But who trusts you or me, anyways?
      - stcredzero 15y ago
        NAND to Tetris http://www.cs.huji.ac.il/course/2006/nand2tet/ http://www.cs.huji.ac.il/course/2006/nand2tet/
        silentbicycle 15y ago
        Better link: http://www1.idc.ac.il/tecs/ http://www1.idc.ac.il/tecs/ But yes, awesome book. :)
    - rxin 15y ago
      The compiler could've been compromised too, as said by Ken Thompson.

sdfgewhger 15y ago

ONLINE STORE : ====( http://www.etradinglife.com http://www.etradinglife.com )===== The website wholesale for many kinds of fashion shoes, like the nike,jordan,prada,, also including the jeans,shirts,bags,hat and the decorations. All the products are free shipping, and the the price is competitive, and also can accept the paypal payment.,after the payment, can ship within short time. free shipping competitive price any size available accept the paypal jordan shoes $32 nike shox $32 Christan Audigier bikini $23 Ed Hardy Bikini $23 Smful short_t-shirt_woman $15 ed hardy short_tank_woman $16 Sandal $32 christian louboutin $80 Sunglass $15 COACH_Necklace $27 handbag $33 AF tank woman $17 puma slipper woman $30 ====( http://www.etradinglife.com http://www.etradinglife.com )=====

ChuckMcM 15y ago

I love this essay too. When I was looking at security issues that were going to arise by creating 'executable content' with Java it reminded me of the sheer magnitude of the problem. In re-reading it I was struck by this comment: The moral is obvious. You can't trust code that you did not totally create yourself. (Especially code from companies that employ people like me.) Ken was one of the people Google hired who didn't have to get 'slotted' (for obvious reasons) and Bill Coughran held him up as the "the kind of engineer Google wants to hire." The juxtaposition is delicious.

tzs 15y ago
What does it mean to get 'slotted' at Google?
- ChuckMcM 15y ago
  Sorry, nominally when Google hires engineers they offer a job at 'x' level of engineer but you're not actually hired at that level. What they do instead is wait 6 months and then a committee evaluates your performance relative to other engineers in the company and then tells you what level you are at Google. The point of the exercise is to avoid hiring people as 'Senior Staff Engineer' (even if they had that title at a previous company) and then finding they only put out 'Staff engineer' or less in the Google equivalent. They don't change your salary if they effectively demote you down a slot or two but the pay ranges are different. If the committee decides you are more than a couple of levels below what you were hired at they fire you. If you do 'down slot' it means that if you do get a promotion later you probably won't get a pay raise. Its supposed to keep things evened out. Generally it means they don't successfully hire senior people from outside the company. It was entirely unclear to me how they handled acquisitions of talent.
gnosis 15y ago
Whenever there's a mention of someone of Thompson's caliber working for Google I'm reminded of what Jeff Hammerbacher said: The best minds of my generation are thinking about how to make people click ads. That sucks.

kevinburke 15y ago

My compilers professor gave this to our class on the first day. Love this article.

SamReidHughes 15y ago

One of the awesomest moments in science fiction is in Accelerando when one of the characters reveals that it's bootstrapped itself up from an alarm clock controller to escape this attack.

swolchok 15y ago

There's a practical (for some value of practical) defense against this attack: "Countering Trusting Trust through Diverse Double Compiling." It's fairly clever. http://arxiv.org/pdf/1004.5548 http://arxiv.org/pdf/1004.5548 If I recall correctly, here it is in short: 1) Invent a new virtual machine ISA. 2) Write a trusted compiler that targets that ISA. It is totally OK if this compiler is crap as long as it is correct. 3) Build the original compiler with the new compiler. The result is a cross compiler, running on your new VM-ISA and targeting your host architecture (e.g., x86). 4) Build the original compiler again with the output of step 3. The result is an x86-hosted compiler targeting x86. The abstract seems to imply the last step: 5) Diff the output of step 4 with the untrusted compiler. The author, David A. Wheeler, apparently expanded on this paper for his 2009 dissertation: http://www.dwheeler.com/trusting-trust/ http://www.dwheeler.com/trusting-trust/

runningdogx 15y ago
What about trusted hardware? Without that, your somewhat trusted compiler cannot be trusted, even if it's something like tcc whose code you might realistically be able to formally verify by yourself. There are at least two approaches, but neither are really satisfactory... first, using an electron microscope and validating the finished design gate by gate. That won't work if the software and hardware toolchain used to generate the gate design is compromised. So you'd have to validate the gates without the help of the software toolchain used for design and layout. I suppose you could also attempt to validate silicon (sans microcode) by attaching a clever external apparatus and external clock source and current meter (which you trust?), and timing every single instruction that hits the processor, validating the time it takes for the instruction to return results and the power consumed, and comparing that against the design specs. That suffers from the same general problem though: unless you're deriving timing and power consumption from basic principles, the tools used to generate expected timings and power consumption could have been compromised. For processors with few gates, though, it could work. The worst situations are where the malware is so subtle -- one changed gate or instruction for instance, with a specific application in mind that can be subverted through that change -- or where from an external POV the malware is non-deterministic, for instance if a processor randomly and rarely injects malware into a running system, using a hardware rng for randomness, on average once every million years of cpu time. Would chip makers be able to detect those sorts of attacks if they tried?

bitsai 15y ago

I had the pleasure of reading this paper during a computer security course. To complement the paper, the prof gave us the task of writing a 2-level polyglot quine (a program in language X that outputs a program in language Y, which outputs the original program). It was my first exposure to quines, let alone polyglot quines, so you can imagine how much I struggled. This paper will always remind me of the frustrations I experienced, and the brilliance of the moment when the "trick" finally clicked for me.

Groxx 15y ago

Someone correct me if I'm wrong, but isn't there a relatively-easy solution to this? Store everything in a versioned, secure-hashed repository. Git is too complex, just checksum everything and store it along with the code (this repository is created by the rest of this paragraph). Hand-build a minimal, trivially-human-readable (thus trustable by those who are interested) compiler to compile the first commit. Compile SHA. Get a secure hash of the binary. Store it. Read the next commit. Verify there is no "compile('bug 1')" in that step. Compile it with v1, and store the hash. Continue. You now have a chain of trust established, starting with something you can read easily, and building minimally at each step (just read the diffs). And you've got the signature of the trusted compiler at any stage. Now check the signature of the downloaded compiler against your known-trusted signature. Compile, secure in the knowledge you have no infected compiler - an infected one wouldn't match the signature of the compiler you could create from your most-recent trusted result. This is extendable with digital signatures, the algorithms of which can be understood with a little number theory, and the code shortly thereafter. Choose who you trust, and spread the work out, just like every other trust-based system. Or trust nobody, and do it yourself (edit: yes, this implies you must build your own computer from tools you develop independently). We've now arrived at the problems around trusting other humans, which are unsolvable. The fact of which must be accepted to varying degrees, or rejected entirely, which requires you to live in isolation. Since you're reading this, you're not in isolation, so you accept some level of human trust, so the previously-established chain of trust would solve the issue for you if the ones you trusted had approved the chain you're using. In this setup, all you'd need to trust is others who fill the gaps you don't directly approve yourself (note that this includes the security / validity of the hash algorithm). Which is the best you can do without omniscience, which would solve the trust issue on its own anyway.

gaius 15y ago
You are wrong, because you make a huge leap of faith here: Choose who you trust No-one deliberately chooses to use software written by people who are known to be untrustworthy! And never has! Yet we find ourselves in a less than perfect world...
- 15y ago