[CS][Paper Review] Reflections on Trusting Trust

이 글은 Ken Thompson이 튜링상을 수상하며 한 강연을 논문으로 만든 Reflections on trusting trust를 리뷰한 글입니다.
원 논문은 ACM Digital Library에서 확인할 수 있습니다. 논문에서 예시로 제시한 코드 중 일부는 이해가 더 쉽도록 수정했습니다.

이 논문은 공급망 공격의 개념을 최초로 제시한 논문으로, 프로그래머가 아무리 안전한 소프트웨어를 만들어도 그 소프트웨어를 빌드하는 툴체인에 백도어가 존재한다면 빌드된 소프트웨어도 신뢰할 수 없다는 것을 지적한 논문이다.

제목을 직역하면, “신뢰를 신뢰하는 것에 대한 고찰”정도쯤으로 해석할 수 있을 것 같다. 제목만 봐서는 무슨 말인지 잘 모르겠는데, abstract도 짧고 알쏭달쏭해서 사실상 본문을 읽기 전까지는 무슨 내용인지 감을 못 잡았다. 톰슨은 이 논문의 주제를 전달하기 위해 몇 가지로 단계를 나눠 C 컴파일러에 벡도어를 심는 과정을 제시한다.

Stage I.

C 컴파일러는 C로 짜여 있다. C로 짜인 잘 만들어진 C 컴파일러가, "Hello, world!\n" 이라는 문장에서 \n을 어떻게 해석하는지 생각해보자. C 컴파일러는 C로 짜였기 때문에, \n이 LF라는 것을 안다. 따라서 다음과 같은 처리가 가능하다.

c = next();
if (c != '\\') {
    // 이스케이프가 아닌 경우 그대로 리턴
    return c;
}

// 이스케이프인 경우
c = next();
if (c == '\\') return '\\';
if (c == 'n') return '\n';
// ...

이제 vertical tab을 나타내는 \v라는 새로운 이스케이프 문자를 넣는다고 가정하자. C 컴파일러는 \v를 알고 있지 않기 때문에, 위에서처럼 단순히 \n을 리턴할 수 없게 된다. 대신, 다음과 같이 vertical tab을 나타내는 아스키코드인 11을 리턴할 수 있을 것이다.

c = next();
if (c != '\\') {
    // 이스케이프가 아닌 경우 그대로 리턴
    return c;
}

// 이스케이프인 경우
c = next();
if (c == '\\') return '\\';
if (c == 'n') return '\n';
if (c == 'v') return 11;  // <- 새로 추가된 부분
// ...

이렇게 컴파일된 컴파일러는, 이제 \v가 나타내는 것이 뭔지 잘 알고 있다. 따라서 위 소스를 다음과 같이 바꾼 후 다시 컴파일하면 \n을 처리하는 것과 같은 방식으로 처리가 가능해진다.

c = next();
if (c != '\\') {
    // 이스케이프가 아닌 경우 그대로 리턴
    return c;
}

// 이스케이프인 경우
c = next();
if (c == '\\') return '\\';
if (c == 'n') return '\n';
if (c == 'v') return '\v';  // <- 바뀐 부분
// ...

이 과정은 마치 컴파일러가 새로운 문자를 학습하는 것처럼 보인다.

Stage II.

이제, 다음과 같이 특정 코드 패턴이 보일 때 임의 코드를 삽입하는 로직을 컴파일러에 삽입한다고 가정해 보자. 여기서는 이해를 위해, 리눅스의 login 바이너리를 컴파일할 때 임의의 사용자로 로그인이 가능하도록 하는 백도어를 삽입한다고 가정했다.

void compile(char *s) {
    ...
    if match(s, "login") {
        compile("backdoor");
        return;
    }
    ...
}

만약 이렇게 컴파일된 컴파일러가 배포되고, 이 컴파일러를 통해 login 유틸리티가 빌드된다면 공격자는 심어 둔 백도어를 통해 로그인이 가능해질 것이다. 그러나 이렇게 컴파일된 C 컴파일러는 소스가 공개되어 있기 때문에 얼마 안 가 들통나게 될 것이다. 그렇다면 다음과 같이 컴파일러 자체에 백도어를 심는 로직을 컴파일러에 삽입하면 어떻게 될까?

void compile(char *s) {
    ...
    if match(s, "login") {
        compile("backdoor");
        return;
    }
    if match(s, "compiler") {
        compile("compiler_code_with_login_backdoor");
        return;
    }
    ...
}

이제 이렇게 컴파일된 컴파일러는, 위에서 본 \v를 학습한 것과 같이 “컴파일러 코드가 들어올 때는 백도어를 심는 것”을 학습하게 되었다. 이제 백도어 코드를 전부 삭제하고, 빌드된 컴파일러로 정상 컴파일러 빌드하듯 컴파일러를 새로 빌드하면 새로 빌드된 컴파일러에는 소스 변형 없이 백도어를 삽입하는 것이 가능해진다.

이렇게 빌드된 컴파일러가 한 번 배포되면, 누가 컴파일러를 빌드하든 소스 자체에는 이상이 없지만 login 유틸리티를 빌드할 때와 컴파일러 자체를 빌드할 때 백도어를 심는 공격이 가능해지게 된다. 만약 공격자가 더 치밀하게 디버거와 objdump, xxd등 바이너리 유틸리티에 만들어 둔 백도어를 숨기는 백도어를 삽입한다면, 공격자는 자신이 심은 모든 백도어를 완전히 숨길 수 있게 된다.

일반적으로 사람들은 보안이라고 하면 프로그래머가 보안적으로 완벽한 코드를 짜는 것을 생각한다. 그러나 이 논문은 아무리 완벽한 코드일지라도 그 코드를 컴파일하는 툴체인 자체가 오염된 경우, 즉 공급망이 공격당한 경우 취약점이 발생할 수 있다는 사실을 보여주었다. 이로 인해 신뢰할 수 있는 공급망을 구축하려는 노력이 진행되어 왔고, 대표적으로 GlobalPlatform 재단에서 PSA Certificate와 같은 프로그램을 운영하게 되었다.