量子哈希
最近，一条引起程序员圈热议的消息传开了：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的源码树，并成功地破解了许多早期计算机先驱的密码。其中一些被破解的哈希码和密码的组合包括：gfVwhuAMF0Trw:dmac、Pb1AmSpsVPG0Y:uio、ymVglQZjbWYDE:/.,/.,、c8UdIntIZCUIA:bourne、AAZk9Aj5/Ue0E:foobar、E9i8fWghn1p/I:apr1744、IIVxQSvq1V9R2:axolotl、9EZLtSYjeEABE:network、P0CHBwE/mB51k:whatnot、Nc3IkFJyW2u7E:…hello、olqH1vDqH38aw:sacristy、9ULn5cWTc0b9E:sherril.、N33.MCNcTh5Qw:uucpuucp、FH83PFo4z55cU:wendy!!!、OVCPatZ8RFmFY:cowperso、X.ZNnZrciWauE:5%ghj、IL2bmGECQJgbk:pdq;dq、4BkcEieEtjWXI:jilland1、8PYh/dUBQT9Ss:theik!!!、lj1vXnxTAPnDc:sn74193n。
大多数情况下，她成功破解这些密码是因为用户的密码太容易被猜到。例如，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的密码如此难以破解呢？我们已经知道答案，但我们将在稍后公布。首先，让我们先讨论一下Descrypt，这是BSD 3操作系统的默认哈希算法。
Descrypt在1979年首次亮相时，代表了密码函数的最前沿。它引入了一项重要改进：作为第一个使用加密salt的哈希函数，它在密码中随机选择一个附加的文本字符串，旨在防止相同的纯文本输入具有相同的哈希字符串。此外，Descrypt还是第一个将纯文本输入置于多个哈希迭代的算法。通过进行25次迭代，这个所谓的密钥拉伸过程显著增加了攻击者破解哈希所需的时间和计算量。
然而，随着破解工具的不断发展，Descrypt在20多年前就被淘汰了，取而代之的是更强大的函数。从现代的标准来看，Descrypt远远不够强大（尽管有时仍在使用，但使用它对最终用户的危害很大）。Descrypt将密码限制在8个字符以内，这一限制使得最终用户几乎不可能选择真正强大的安全凭证。此外，Descrypt使用的salt只提供了12位的熵，相当于两个可打印字符。这个小小的salt空间使得大型数据库可能包含数千个哈希字符串，攻击者可以同时破解它们，因为哈希字符串使用相同的salt。
这些弱点意味着，Leah发布的其余未破解的哈希密码最终也将被破解。然而，由于大多数论坛成员并非经验丰富的黑客，他们似乎都使用了效率较低的技术。
就在Leah发布求助的第六天，论坛成员Nigel Williams成功破解了Thompson的明文密码：“p/q2-q4!”。Williams表示，他花了超过4天的时间，利用AMD Radeon Vega64以约930MH/s的速度运行hashcat这个密码破解程序。
在Williams发布这一消息几个小时后，论坛成员Arthur Krewat公布了其余四个未破解的哈希密码。它们分别是：Katseff: graduat、Babaoğlu: 12ucdort、Fabry: 561cml..、London:..pnn521。他们很快发现，汤普森的密码“p/q2-q4!”实际上是国际象棋中一种常见的开局走法的符号。乍一看，p/q2-q4!可能看起来像一个数学公式，但实际上它是一种古老的符号，表示国际象棋中棋子的走位，意思是“皇后前面的兵（Pawn）向前移动2个方格”。其中，q代表Queen（皇后），p代表Pawn（兵），这种走棋记法属于国际象棋的代数记谱法。
这个密码选择对于汤普森来说非常典型，因为他是一个国际象棋爱好者，曾经是1980年第3届全球计算机国际象棋锦标赛的冠军，并开发了一个专门用于下国际象棋的计算机程序“Belle”。
当汤普森得知密码被破解的消息后，他对Williams表示了赞赏，并回复道：“恭喜！”
肯·汤普森（Ken Thompson）是硅谷传奇的计算机科学家和工程师，黑客文化圈通常称他为“ken”。1960年，汤普森就读于加州大学伯克利分校，主修电气工程，并于1966年获得了电子工程硕士学位。他的导师是美国数学家、计算机科学家埃尔温·伯利坎普。
1966年，汤普森加入贝尔实验室。在贝尔实验室工作期间，他参与了Multics操作系统项目，并开发了一款名为《星际旅行》的飞行模拟游戏。这款游戏要求玩家控制太空飞船在黑色背景和白色线条组成的太阳系中飞行，并在不同的行星和卫星之间着陆，没有特定的目标。
然而，贝尔实验室后来退出了Multics项目。为了继续玩游戏，汤普森不得不找到一台老式的PDP-7机器，并重新编写了游戏代码。但他发现游戏在新机器上运行非常缓慢，于是他借鉴了丹尼斯·里奇（Dennis Ritchie）和Rudd Cassaway在开发Multics文件系统时的经验，设计了自己的文件系统。随着不断的扩展，这个文件系统逐渐发展成为一个完整的操作系统，并于1970年被命名为Unix。
在完成Unix系统的基本开发工作后，汤普森认为Unix系统需要一种系统级的编程语言，于是他创造了B语言。后来，里奇在B语言的基础上发展出了C语言。
在60年代，汤普森还参与了正则表达式的设计，并开发了QED的兼容分时系统版本，其中引入了对正则表达式的支持。QED和后来由汤普森编写的ed编辑器对正则表达式的流行做出了重要贡献。现在，几乎所有使用正则表达式的程序都使用了某种来自汤普森的记号的变体。
汤普森还是一位国际象棋爱好者，他曾开发了专门用于下国际象棋的计算机程序“Belle”，并创建了残局数据库。
在2000年下半年，汤普森离开了贝尔实验室，加入了美国的Entrisphere公司工作。2006年，他加入了Google公司。之后，他与Rob Pike和Robert Griesemer共同设计了Go语言。由于对C++的不满，三人共同讨论了语言的每个特性，因此Go语言最终没有任何“无用的垃圾”。
汤普森和丹尼斯·里奇一起获得了1983年的图灵奖，以表彰他们对计算机科学的贡献。
