In March 2024, an engineer named Andres Freund noticed that logging in to his Linux machines over SSH had become slow. Even a login for a user that does not exist, which is refused anyway, took 0.807 seconds instead of 0.299. He chased that extra half second and found a backdoor, a hidden way in, planted in xz, a compression library that the SSH server loads. On 29 March he posted to the oss-security mailing list: "The upstream xz repository and the xz tarballs have been backdoored."
The code was open for anyone to read. So how did a backdoor end up in the program that actually ran? About forty years earlier, in his Turing Award lecture of October 1983, Ken Thompson had described a deeper version of the same problem: a backdoor with no trace in any source at all. The printed lecture is three pages long.
This paper is hosted by its original publisher.
Read on dl.acm.orgThe Lecture and Its Question
Ken Thompson built Unix with Dennis Ritchie at Bell Labs. In 1983 the two of them shared the ACM Turing Award, and Thompson gave his lecture that October. It was printed in Communications of the ACM in August 1984 (volume 27, number 8, pages 761 to 763). Early on he says he is not going to talk about Unix. Instead: "I would like to present to you the cutest program I ever wrote." He builds it in three stages.
Right under the title sits the question:
To what extent should one trust a statement that a program is free of Trojan horses? Perhaps it is more important to trust the people who wrote the software. (p. 761)
A Trojan horse, in Thompson's own terms, is a bug planted on purpose: "If this were not deliberate, it would be called a compiler 'bug.' Since it is deliberate, it should be called a 'Trojan horse.'"
