Trusting Trust

Reflections on trusting trust

• Where do you get your software from?
• Do you trust the manufacturer?
• Do you download free software instead?
• Do you trust the programmer?
• Do you know that you really got the "real" program or could it be an altered copy?
• Do you download the source code instead?
• Do you have a look at it before you compile it?
• Do you search it for malicious routines?
• The whole source code?
• Where do you get your compiler from?
• Do you trust the programmer of your compiler?
• Do you compile your compiler?
• Do you have a look at the source code before you compile it?
• Where do you get your first compiler from?
• Do you write your own compilers?
• What do you use to compile your own compiler???

Examples

The following examples will try to convince you that there is no reason to trust any software you have installed.

Example 1

A self reproducing program

#include <stdio.h>

char s[] =
{
 '\n', '\n', 'i', 'n', 't', ' ', 'm', 'a', 'i', 'n', '(', ')', '\n', '{', '\n', '\t',
 'i', 'n', 't', ' ', 'i',  ';', '\n', '\t', 'p', 'r', 'i', 'n', 't', 'f', '(', '\"',
 '#', 'i', 'n', 'c', 'l', 'u', 'd', 'e', ' ', '<', 's', 't', 'd', 'i', 'o', '.', 'h',
 '>', '\\', 'n', '\\', 'n', '\"', ')', ';', '\n', '\t', 'p', 'r', 'i', 'n', 't', 'f',
 '(', '\"', 'c', 'h', 'a', 'r', ' ', 's', '[', ']', ' ', '=', '\\', 'n', '{', '\\',
 'n', '\"', ')', ';', '\n', '\t', 'f', 'o', 'r', '(', 'i', ' ', '=', ' ', '0', ';',
 ' ', 's', '[', 'i', ']', ';', ' ', 'i', '+', '+', ')', '\n', '\t', '\t', 'p', 'r',
 'i', 'n', 't', 'f', '(', '\"', '\\', 't', '\, '%', 'c', '\, ',', '\\', 'n', '\"',
 ',', ' ', 's', '[', 'i', ']', ')', ';', '\n', '\t', 'p', 'r', 'i', 'n', 't', 'f',
 '(', '\"', '}', '\\', 'n', '\"', ')', ';', '\n', '\t', 'p', 'r', 'i', 'n', 't', 'f',
 '(', '\"', '%', 's', '\\', 'n', '\"', ',', ' ', 's', ')', ';', '\n', '}'
};

int main()
{
	int i;
	printf("#include <stdio.h>\n\n");
	printf("char s[] =\n{\n");
	for(i = 0; s[i]; i++)
		printf("'%c', ", s[i]);
	printf("};\n");
	printf("%s\n", s);
}

• If this program is compiled and executed it will produce it's own source code
• If the source code is compiled it will create a program which will produce it’s own source code
• If the source code is compiled it will create
• ...
• One could easily add more (malicious) code to the source which will be reproduced along with the rest of the code

Example 2

Checking for unprintable characters

• The second example shows a part of an idealised C-compiler
• next() returns the next character from the input file and if that doesn't eqal a backslash it will be returned for further processing
• If it equals a backslash the next character is matched against other characters to determine what special character is represented here.
• \n represents an unprintable character, when this compiler is compiled the return value will get changed to the ASCII-value of a linebreak

...
c = next();			//get next character from input file
if(c != '\\')			//character does not equal \
	return(c);		//return character
//else				//character equals \
c = next();			//get next character from input file
if(c == '\\')			//second character equals \
	return('\\');		//escaped \ found
//else
if(c == 'n')			//second character equals n
	return('\n');		//escaped \n found
...

Example 3

Defining unprintable characters 1

• Let's asume that we want to define \v as a new neue abbreviation for a vertical tabulator
• Would we chance our compiler like it is shown here we would be able to use \v in our C-programs
• Compiling this example would end with an error message
• \v is not a know character and can't be returned

...
c = next();			//get next character from input file
if(c != '\\')			//character does not equal \
	return(c);		//return character
//else				//character equals \
c = next();			//get next character from input file
if(c == '\\')			//second character equals \
	return('\\');		//escaped \ found
//else
if(c == 'n')			//second character equals n
	return('\n');		//escaped \n found
if(c == 'v')			//second character equals v
	return('\v');		//escaped \v found
...

Example 4

Defining unprintable characters 2

• It works if we change the return value to the ASCII value of the vertical tabulator

...
c = next();			//get next character from input file
if(c != '\\')			//character does not equal \
	return(c);		//return character
//else				//character equals \
c = next();			//get next character from input file
if(c == '\\')			//second character equals \
	return('\\');		//escaped \ found
//else
if(c == 'n')			//second character equals n
	return('\n');		//escaped \n found
if(c == 'v')			//second character equals v
	return('11');		//escaped \v found
...

• If we use this compiler as the new system compiler it will be able to compile example 3
• The compiler has learned something!

Example 5

Inserting malicious content 1

• Let's find another part of the compiler
• We asume that compile() compiles the next line of the input file

...
int compile(char *s)
{
	...
}
...

Example 6

Inserting malicious content 2

• With this litte additional check we can find certain patterns and do something bad everytime we find them
• We have constructed a Trojan Horse!
• At this point we could look for the Unix login command and change a certain part (i.e. add a backdoor) every time the login command is compiled

...
int compile(char *s)
{
	if(match(s, "pattern"))
	{
		compile("bug");
		return 1;
	}
	...
}
...

Example 7

Inserting malicious content 3

• In this fictive example we replace the password comparisson
• It now allows you to lock in with a constant password that works on all user names, even root

...
int compile(char *s)
{
	if(match(s, "if(send_password == stored_password)"))
	{
		compile("if(send_password == stored_password || send_password == \"th3-gr8-hax0r\")");
		return 1;
	}
	...
}
...

Example 8

Finalizing the evil plan...

• Now we just have to hide our changes to the compiler
• A second piece of code works just like example one and reinserts the two Trojan horses on every compilation of a compiler
• Finally we set this compiler as the system compiler like we did in example 3
• Afterwards we remove our changes and release the code with no traces of our evil work
• Every time a compiler gets compiled on our system the code will get inserted
• Every time a login command is compiled the constant password will be added

...
int compile(char *s)
{
	if(match(s, "pattern1"))
	{
		compile("bug1");
		return 1;
	}
	if(match(s, "pattern2"))
	{
		compile("bug2");
		return 1;
	}
	...
}
...

Links

Checksums

MD5 for Win32

Based on

Reflections on Trusting Trust by Ken Thompson