量子哈希
最近，一条引起程序员圈热议的消息是Unix之父Ken Thompson的旧密码被破解了！这一消息由德国慕尼黑的程序员Leah Neukirchen发布，在她的博客中称，她花了四年多的时间无法破解Ken Thompson的密码，但在本月初被Nigel Williams成功破解。这一消息立即在技术论坛上引起了狂欢和好奇。那么到底发生了什么呢？
早在2014年，Leah在BSD 3源码树的文件转储中发现了一个/etc/passwd文件，其中包含了一些计算机领域传奇工程师的旧密码，包括Dennis Ritchie、Ken Thompson、Brian Kernighan、Steve Bourne和Bill Joy等Unix开发大师。Leah对他们使用的密码非常感兴趣，决定尝试破解这些密码。她成功破解了大部分密码，但有5个密码一直困扰着她，其中最令她头疼的是Ken Thompson的密码。
这是否意味着计算机大师使用的密码都很脆弱？作为Unix的原始版本之一，BSD是一个古老的操作系统。因此，以今天的标准来衡量，它使用的安全措施可能看起来奇怪甚至荒谬，这并不令人惊讶。首先，保护密码的哈希函数虽然在40年前是最先进的技术，但现在要破解它并不难。更奇怪的是，一些BSD创建者的密码散列包含在公开的源代码中。
Leah报告说她找到了大约1980年BSD 3的源码树，并成功地破解了许多早期计算机先驱的密码。她发现大多数情况下，她的成功是因为用户的密码太容易被猜到。比如，BSD的共同发明者Dennis Ritchie使用了”dmac”作为密码（他的中间名是MacAlistair）；Stephen R. Bourne是Bourne shell命令行解释器的创建者，他的密码是”Bourne”；Eric Schmidt是Unix软件的早期开发者，现在是谷歌母公司Alphabet的执行董事长，他的密码是妻子的名字”wendy!!!”；Unix自动化工具make的作者、同时也是第一个Fortran编译器的作者Stuart Feldman，他使用的密码是”axolotl”（一种墨西哥蝾螈的名字）。其中最弱的是Unix贡献者Brian W. Kernighan的密码：” /.,/., “，表示一个三个字符的字符串，重复敲两次QWERTY键盘上的相邻键得到。
然而，至少有五个纯文本密码仍然无法破解。包括土耳其计算机科学家Ozalp Babaoğlu，Unix软件开发人员Howard Katseff，Unix的重要贡献者Tom London和Bob Fabry。但是，最令Leah费解、花费最长时间的是Unix之父Ken Thompson使用的密码。
Leah对无法破解Ken的密码感到沮丧，她在Unix Heritage Society的邮件列表中表示：“我一直没有办法用散列ZghOT0eRm4U9s破解Ken的密码，我列举了所有8个小写字母+特殊符号键空间。任何帮助都行，欢迎大家给我指点。”
那么为什么Ken的密码如此难以破解呢？我们已经知道答案，但我们将在稍后公布。在此之前，让我们先讨论一下BSD 3操作系统的默认哈希算法Descrypt。
Descrypt在1979年首次亮相时代表了密码函数的最前沿。它是第一个使用加密salt的哈希函数，salt是一个随机选择的附加到密码中的文本字符串，旨在防止相同的纯文本输入具有相同的哈希字符串。它也是第一个将纯文本输入置于多个哈希迭代的算法。通过25次迭代的密钥拉伸过程，大大增加了攻击者破解哈希所需的时间和计算量。
然而，随着破解工具的不断发展，Descrypt在20多年前就被弃用了，因为出现了更强大的函数。从今天的标准来看，Descrypt远远不够强大（尽管有时仍在使用，但对最终用户的损害很大）。Descrypt将密码限制在8个字符以内，这使得最终用户几乎不可能选择真正强大的安全凭证。Descrypt使用的salt只提供了12位的熵，相当于两个可打印字符。这个小小的salt空间使得大型数据库可能包含数千个哈希字符串，攻击者可以同时破解它们，因为哈希字符串使用相同的salt。
这些弱点意味着Leah发布的其余未破解的哈希密码最终都将被破解。但由于大多数论坛成员都不是经验丰富的黑客，他们似乎都使用了效率较低的技术。在Leah发布求助的第六天，论坛成员Nigel Williams成功破解了Thompson的明文密码：”p/q2-q4!”。
这个密码的破解让人想起了Ken Thompson的国际象棋爱好。”p/q2-q4!”实际上是国际象棋中一种常见的开局走法的符号。乍一看，它像是一个数学公式，但实际上它是一种古老的符号，代表国际象棋中棋子的走位。具体来说，它表示”皇后前面的兵（Pawn）向前移动2个方格”。其中，q代表Queen（皇后），p代表Pawn（兵），这种走棋记法属于国际象棋的代数记谱法。
这个密码的破解与Ken Thompson的国际象棋爱好息息相关。他曾是1980年第3届全球计算机国际象棋锦标赛的冠军，并开发了一个专用于下国际象棋的计算机程序”Belle”。因此，这个密码的选择与他的兴趣和才能相吻合。
密码被破解后，Ken Thompson通过邮件向Nigel Williams表示赞赏，并回复道：”恭喜！”
Ken Thompson是硅谷传奇的计算机科学家和工程师，黑客文化圈通常称他为”ken”。他在1960年就读于加州大学伯克利分校，主修电气工程，并于1966年获得电子工程硕士学位。他的导师是美国数学家和计算机科学家埃尔温・伯利坎普。
1966年，Ken Thompson加入了贝尔实验室。在贝尔实验室工作期间，他参与了Multics操作系统项目，并开发了一款名为《星际旅行》的游戏，这是一款飞行模拟游戏。玩家需要控制太空飞船在黑色背景和白色线条组成的太阳系中飞行，并在不同行星和卫星之间着陆，没有特定的目标。
后来，贝尔实验室退出了Multics项目。为了继续玩游戏，Ken Thompson不得不找到一台老式的PDP-7机器，并重新编写了游戏代码。但他发现游戏在新机器上运行非常慢，于是他借鉴了丹尼斯・里奇和Rudd Cassaway在开发Multics文件系统时的经验，设计了自己的文件系统。随着扩展，这个文件系统发展成了一个完整的操作系统，并于1970年被命名为Unix。
在完成Unix系统的基本开发工作后，Ken Thompson认为Unix系统需要一种系统级的编程语言，于是他创造了B语言。后来，丹尼斯・里奇在B语言的基础上创造了C语言。
在60年代，Ken Thompson还参与了正则表达式的设计，并开发了QED的兼容分时系统版本，其中引入了对正则表达式的支持。QED和后来由Ken Thompson编写的ed编辑器对正则表达式的流行做出了重要贡献。现在，几乎所有使用正则表达式的程序都使用了某种来自Ken Thompson的记号的变体。
Ken Thompson还是一位国际象棋爱好者，他曾制作了专门用于下国际象棋的计算机程序”Belle”，并创建了残局数据库。
2000年下半年，Ken Thompson离开了贝尔实验室，加入了美国的Entrisphere公司工作。2006年，他加入了Google公司。之后，他与Rob Pike和Robert Griesemer共同设计了Go语言。由于对C++的厌恶，三人共同讨论了语言的每个特性，因此Go语言最终没有任何”无用的垃圾”。
Ken Thompson和丹尼斯・里奇一起获得了1983年的图灵奖。
参考链接：arstechnica.com/information-technology/2019/10/forum-cracks-the-vintage-passwords-of-ken-thompson-and-other-unixpioneers zh.wikipedia.org/wiki/肯・汤普逊
