Ken Thompson의 Reflections On Trusting Trust

들어가기

“Reflections On Trusting Trust”은 Ken Thompson의 논문 내용으로 총 3 Stage로 구성되어 있다. 내용은 백도어에 대한 것으로 특히 C 컴파일러에 대해서 다룬 글이다. 개인적으로 제목을 “신뢰를 신뢰하는 것에 대한 고찰”이라고 직역할 수 있을 듯 하네요. 다르게 하면 “신뢰에 대한 재고찰” 정도가 될까요? 그리고 샘플 코드가 C 언어로 되어 있습니다.

작성자: ospace114@empal.com, http://ospace.tistory.com/

Stage 1

Self-reproducing program은 콰인(quine)으로 소스코드가 자신 복제하는 프로그램이다. 결국 프로그램이 다른 프로그램에 의해 쉽게 작성될 수 있다. 아래 메인 프로그램이 의해 생성되는 프로그램 크기보다 초과된 코드이다. 이를 응용하면 코드에 포함되지 않은 여분의 코드를 더 추가할 수 있게 된다.

char s[] = {
  '\t',
  '0',
  '\n',
  // 중략
  0
};
main() {
    int i;
    printf("char\ts[]={\n");
    for(i=0;s[i];i++) printf("\t%d,\n",s[i]);
    printf("%s", s);
}

Stage 2

C 컴파일러는 C에 의해서 작성되었다. 이는 아마도 “닭과 달걀” 문제와 비슷한다. 특수 문자 출력하는 경우를 살펴보자. 예를 들어 “Hello world\n” 문자열을 출력해야 하는데 “\n” 문자는 개행 문자이다. 다음 처럼 처리할 수 있다.

c = next();
if(c != '\\') return (c);
c = next();
if(c == '\\') return ('\\');
if(c == 'n') return ('\n');

새로운 특수 문자 추가도 추가해보자. vertical tab(‘\v’)으로 수직탭 문자이다. 이것도 아래 처럼 처리할 수 있다.

c = next();
if(c != '\\') return (c);
c = next();
if(c == '\\') return ('\\');
if(c == 'n') return ('\n');
if(c == 'v') return ('\v');

에러가 발생했다. 문제는 아직 컴파일러가 “\v”를 지원하지 않는다. 이식 가능한 코드 작성 필요하다. 수직 탭은 아스키값 11을 알고 있기에 다음 처럼 수정할 수 있다.

c = next();
if(c != '\\') return (c);
c = next();
if(c == '\\') return ('\\');
if(c == 'n') return ('\n');
if(c == 'v') return (11);

이후로부터는 ‘\v’를 사용 가능하다. 어떻게 보면 “학습” 프로그램과 비슷하다.

Stage 3

compile 루틴으로 소스 다음 라인을 컴파일한다.

compile(char *s)
char *s;
{
    //...
}

간단한 수정을 해보자. 중간에 패턴매칭이 추가되었다. 의도되지 않은 코드이면 버그이거나 의도적인 “트로이목마”라고 할 수 있다.

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

Ken Thompson는 “login” 유닉스 명령에 일치하는 코드에 대해 컴파일과정에서 버그를 심었다고 했다. 대체코드는 로그인을 잘못 컴파일해서 정상적인 패스워드 또는 미리 알려진 패스워드를 허용하게 만들어졌다. 이 코드가 바이너리로 만들어져서 설치되면 로그인 명령을 컴파일할 때 사용되어진다. 그러나 이런 노골적인 코드는 언젠가는 들키게 된다.

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

이번은 단순히 두 번째 트로이목마 코드를 추가했다. 두 번째 패턴의 대상은 C 컴파일러이고 대체 코드는 두 트로이 목마를 생성하는 Stage 1의 self-reproducing program으로 컴파일러에 추가된다.
이를 위해 Stage 2에서 처럼 학습 과정이 필요하다. 먼저 수정된 코드를 일반 컴파일러로 버그 바이너리 생성하게 한다. 이 바이너리를 공식적인 C로 설치한다. 그리고 컴파일 소스에서 이 버그를 제거한다. 이제 새로운 바이너리는 컴파일 할 때마다 버그를 추가하게 된다. 로그인 명령에는 소스 코드 어디에도 추적 불가한 버그 존재하게 된다.

결론

이 논문의 결론은 전부 직접 만든 코드가 아니면 100% 신뢰할 수 없다라는 말이다. 여기서는 C 컴파일러를 선택했지만 임의 대상을 선택할 수 있다. 특히 로우 레벨로 갈수록 이런 버그는 더욱 발견하기 어려워진다고 한다.
이 논문에서도 아이들에 대해서도 언급하고 있다. 아이들은 자신들에 행동이 어떤 의미인지 잘 모른다. 만약 컴퓨터 사용에 대해 제대로 가르치지 않을 경우 잘못된 행위를 할 가능성이 매우 높다라고 말할 수 있다. 또는 자신들이 벌을 받지 않는다는 사실을 악용할 수도 있다.

그렇기 때문에 컴퓨터 시스템에 대한 무단 접근은 매우 심각한 범죄로 다뤄야 한다. 컴퓨터 시스템 침입은 남의 집을 무단침입과 동일하다는 인식을 갖게해야 한다. 이부분은 한국에서는 무단 침입이 중요하게 받아들이지 않아서 심각하다고 인식하지 못하지만 미국에서는 무단침입한 사람을 죽여도 “캐슬독트릭”으로 어느정도 보호를 받는다. 즉, 무단침입은 매우 심각한 문제로 받아들인다는 뜻이다.

부족한 글이지만 여러분에게 참고가 되었으면 하네요. ^^ ospace.

참고

[1] Ken Thompson, Reflections on Trusting Trust, https://www.win.tue.nl/~aeb/linux/hh/thompson/trust.html
[2] https://ko.wikipedia.org/wiki/콰인_(전산학)