第二篇 密码技术

第七章 密钥长度

7.1 对称密钥长度

    对称密码体制的安全性是算法强度和密钥长度的函数：前者更加重要而后者则更容易描述。

    假设算法具有足够的强度，实际上这点极难做到，不过本例却很容易。这里我所指的足够是：除了用穷举攻击的方式试探所有的密钥外没有更好的方法破译该密码系统。

    为了发动对密码系统的攻击，密码分析者需要少量的密文和对应的明文，穷举攻击是一种已知明文的攻击。对分组密码来说，密码分析者需要密文分组和对应的明文分组：通常是64比特。获得明文和密文比你想象的要容易，密码分析者可通过一些手段获取明文消息的副本而后去截取相应的密文。他们可能知道有关密文格式的一些信息：如，它是一个WordPerfect文件，它有一个标准的电子邮件消息头，它是一个UNIX目录文件，一幅TIFF图像，或用户数据库中的一个标准记录。而所有这些格式都有一些予定义字节。密码分析者不需要太多的明文来发起这种攻击。

    很容易计算一次穷举攻击的复杂程度：如果密钥长度为8比特，那么有2⁸=256种可能的密钥，因而找出正确的密钥将需要256次尝试，在128次尝试后找到正确密钥的概率是百分之五十。假如密钥长度为56比特，会有2⁵⁶种可能密钥。设想有一台每秒能检验一百万个密钥的超级计算机，也需要2285年时间才能找出正确的密钥。如果密钥长度为64比特，则将需要585,000年才能在2⁶⁴种可能的密钥中找出正确的密钥；如果密钥长128比特，则需要10²⁵年的时间。宇宙也只有10¹⁰年的历史，相对而言10²⁵年太长了。对于一个长为2048比特的密钥，用每秒尝试百万个密钥的百万个计算机并行工作要10⁵⁹⁷年才能完成。到那时宇宙或许早已爆炸或膨胀得无影无踪了。

    在你急着去发明一个8K字节密钥的密码体制之前，请记住其强度问题的另一面：加密算法必须非常安全，以致于除穷举攻击外没有其它更好的方法来破译它。这并不像看上去那样容易。密码学是一门奇妙的艺术，看上去完美的密码系统往往是非常脆弱的。很强的密码系统，哪怕是一点点的改变就会使它变得非常脆弱。对业余密码设计人员的忠告是要对任意新的算法进行健康的、执着的怀疑，最好去信任那些专业密码人员分析了多年而未能攻破的算法，以及去怀疑那些设计者宣称其安全性是如何好的算法。

    回忆一下1.1 节里的一个重要点：密码体制的安全性应依赖于密钥，而不是依赖于算法的细节。假设密码分析者已经获得了你的算法的所有细节；假设他们能够得到发起唯密文攻击的足够多的密文；假设他们能得到所需要的尽可能多的数据发起明文攻击；甚至假设他们能进行选择明文攻击。在这些情况下，如果你的密码体制仍然是安全的，那么它就达到所需要的安全性要求了。

    忠告归忠告，在密码学领域业余密码人员还是有许多事是可以做的。其实，这里讨论的安全性在许多情况下并非必须，大多数敌手并不具备这方面的知识，也不具有一个强大国家所拥有的计算资源，甚至他们连破译密码的兴趣都没有。要是你正密谋推翻一个强大的政府，就得依靠本书后面讲的那些可靠而正确的算法。剩下的，就是玩得开心了。

    穷举攻击所需时间和代价估计

    要记住，穷举攻击是一种典型的已知明文攻击,它需要少量的密文及相应的明文。如果你假设穷举攻击是对算法最有效的攻击的话——一个大的假设——密钥必须足够长以致使攻击不可行，那么密钥要多长呢？

    有两个参数决定穷举攻击的速度：需测试的密钥量及每个测试的速度。大多数对称密码算法接受一个固定比特长度模式作为密钥，DES有56比特的密钥；共2⁵⁶个可能密钥。本书讨论的算法一些有64比特的密钥，也就是说有2⁶⁴个可能密钥，另外一些有128比特密钥。

    每一个可能密钥的测试速度也是一个因素，但重要性次之。为了分析的目的，我们将假定每种不同算法的测试时间是相同的。实际上测试一种算法的速度可能比另一种算法的速度快两、三倍，甚至十倍。但由于我们正在寻找的密钥长度比破译密码的难度大百万倍之多，这个密钥长度是可行的，所以测试速度小小的差异是可以忽略的。

    在保密通信中关于穷举攻击效率的多数讨论都集中在DES算法上。1977年Whitfield Diffie和Martin Hellman[497]假设了一种专用破译DES的机器。这台机器由一百万个芯片组成，每秒能测试一百万个密钥。这样它可在20个小时内测试2⁵⁶个密钥，如果制造出来用于破译64比特密钥的算法，它可在214天内尝试所有的密钥。

    穷举攻击必须有并行处理器的存在。每个处理器测试密钥空间中的一个子集，它们之间不需要什么通信，要说通信那就是报道成功的消息，并且它们没有共享的内存。设计这样一台具有一百万个并行处理器的机器，并让它们彼此独立地工作是很容易的。

    最近，Micheal Wiener 决定设计一台穷举攻击机器[1597，1598]。（这台机器是为攻击DES设计的，但对任何算法都适用。）他设计了专门的芯片、主板、支架，并且估算了其价格。他发现只要给定一百万美元就能制造出一台这样的机器使其在平均3.5小时（最多不超过7小时）里能破译密钥长为56比特的DES算法。他还发现机器的价格和破译速度之比是呈线性的，表7.1列出了各种密钥长度的对应数据。记住Moore定律：大约每经18个月计算机的计算能力就翻一番。这意味着每5年价格就会下降到原来的百分之十，所以在1995年所需要的一百万美元到了2000年就只用花十万美元。流水线计算机能够做得更好[724]。

表7.1  1995年硬件穷举攻击的平均时间估计

    对一个56比特密钥，穷举攻击所需金额对很多大公司和一些犯罪组织来说还是可以承受的。对于64比特密钥，则只有一些发达国家的军事预算才能承受。而破译80比特密钥现在仍然不行，但是如果按目前的形势继续发展下去的话，这种情况将会在30年内发生改变。

    当然，估计未来35年计算机的计算能力是很可笑的，一些科幻小说里出现的技术突破可能会觉得上述预测很可笑。相反，目前一些未知的物理限制又使人们产生不切实际的乐观。在密码学中悲观一点是很明智的。用80-比特密钥的加密算法是一种目光非常短浅的行为，还是坚持用至少112-比特的密钥吧。

    如果攻击者想要不择手段地破译一个密钥，他们必须要做的全部事情就是花费钱。所以，试图估计一下密钥的最小“价值”似乎是明智的：在试图破译一个有经济价值的密钥之前，要确信它到底有多大价值呢？举个极端的例子，如果一个加密了的消息值1.39 美元，一台价值1000万美元的破译机来寻找密钥在经济上就毫无意义了。另一方面，如果明文消息值1亿美元，那么造一台破译机破译此信息是值得的，何况有些信息的价值会随时间迅速减少。

软件破译机

    没有功能特殊的硬件设备和大规模并行计算机，穷举攻击很难有效地工作。对密码系统的软件攻击比硬件攻击大约慢一千倍。

    基于软件穷举攻击的真正威胁：并非是它的确定性，而是它的“自由”性。装配一台微型计算机来测试可能的密钥，无论其是否在测试都不涉及到成本问题，如果找到正确的密钥——那太好了，如果没找到，也不会失去什么。建立整个这样的微机网络同样不涉及成本问题。最近一次对DES的试验，在一天内用了40个工作站的空闲时间对2³⁴个密钥进行了测试[603]。照这样的速度，将需要四百万天来测试所有密钥，但是如果足够多的人试图像这样破译的话，总有某个人会在某处交上好运。文献[603]中这样写到：

    软件威胁的关键是十足的坏运气。设想一个具有512个工作站的大学计算机网络全部联网，对某些校园来说这是一个中等规模的网络，它们甚至可以遍及世界，通过电子邮件来协调各自行动。假设每个工作站能以每秒加密15,000次的速率运行…考虑测试和更换密钥的时间，便得到…每台每秒测试8,192次。用这样的速度测试完[一个56]比特密钥空间将需要545年（假定网络每天工作24小时）。但是请注意，假设学生破译者进行同样的计算，他们在一天内破译出密钥的机会是1/200,000，在一周内破译出的机会增加到1/66,000，他们的设备越先进，或者使用的机器越多，成功的机会自然就越大。这种概率对靠赛马谋生来说机会太小了，但在某些情况下它还算好的，如，同政府的博彩中奖相比它要好得多，“一百万分之一？”“一千年能发生一次吗？”，要简单地说清这些事已不再可能了。这种不断发展的冒险能接受吗？

    用一个64比特密钥来替换56比特密钥的密码算法来说，其破译难度要大256倍。而对于40比特的密钥，情况就远比这简单得多。一个由400台，每台每秒能加密32,000次的计算机组成的网络，能够在短短一天内完成对40比特密钥的破译（1992年， 40比特密钥的RC2和RC4算法已经被成功破译了——见13.8节）。

    对128比特密钥来说，进行穷举攻击是十分荒唐的。工业专家估计：到1996年止，世界上将有二亿台计算机在运行，这种估计包括从巨大的Cray大型机到笔记本电脑在内的计算机。如果所有的这些计算机同时一起进行穷举攻击，并且每台以每秒一百万次的加密速度进行，破译这个128比特的密钥也得需要一百万倍宇宙年龄的时间才能成功。

    神经网络

    神经网络对密码分析来说并不是非常有用，这主要是其解空间的模式导致的，因为神经网络最擅于处理那些连续解的问题，这些解一些比另一些更好。这就允许神经网络去学习并在学习中得出越来越好的解。而破译密码算法并没有提供太多学习“机会”的方法：你要么找到密钥要么没有。（至少对稍微好的算法是这样。）神经网络适用于那些结构化环境，在那里一些东西必须要学习，而在信息熵很高，随机性非常强的密码学领域就不适用了。

    病毒

    让数以百万台计算机放在一起进行穷举攻击的所遇到的最大难题是说服这些计算机的拥有者同意他们的机器参与，你会有礼貌地请求，但那是浪费时间，因为他们会说“不”；你也可以试图侵占他们的机器，但那更是浪费时间，并且你还可能被捕；你还可以利用计算机病毒来散布攻击程序，以更加有效地覆盖到尽可能多的计算机上。

    这是在文献[1593]中首次提到的特别有趣的思想。攻击者写下并散布计算机病毒，这些病毒并不重新格式化硬盘驱动器和删除文件，它只是在受染计算机的空闲时间处理穷举攻击的密码分析问题。各种各样的研究已表明微型计算机70%至90%的时间是空闲的，于是病毒可以无任何阻碍地找到时间来完成它的任务。如果它是良性的，在它发作的时候甚至可能逃过人们的注意。

    最后，某个机器也会偶然碰到正确的密钥，此时会有两条路可以选择：其一，攻击病毒将引发另一个不同的病毒。它除了复制有关正确密钥的信息和删除攻击病毒留下的其它的信息外不做任何事情。然后，新的病毒通过计算机网络传播，直到它回到书写原始病毒的人的计算机上为止。

    其二，卑鄙的方法将是病毒在屏幕上显示以下信息：

        本机中有严重的病毒存在！

        请拨1-800-123-4567并且读入下面的64比特数字给操作人员：

        ××××  ××××  ××××  ××××

        对于第一个报告该病毒的人给予100美元的奖金。

    这种攻击的有效性有多大呢？假设典型的被感染了病毒的计算机可以每秒测试一千个密钥，远远低于计算机的最大潜力，因为我们不得不假设它会干其他事情，我们也假设典型的病毒感染了一千万台机器，这样这个病毒可以在83天里破译一个56比特密钥，在58年内破译一个64比特的密钥。你或许会收买抗病毒软件的制造者，但那是你们的问题，任何计算机速度或者病毒感染速度的增长必然会使这种攻击更加有效。

    中国式抽彩法

    中国式抽彩法是一种折衷的，但对于大规模并行密码分析机来说是一个可行的建议[1278]。设想一种用于穷举攻击的、每秒有百万次测试速度的破译芯片被安装在每台收音机与电视机中售出，每块芯片在通过广播收到一对明文/密文后便自动利用其中的程序检测不同的密钥。于是，每当想要破译密钥时，就广播这个数据，这时所有的收音机和电视机便开始嘎嚓嘎嚓地开动起来。最后，正确的密钥将会在某个地方被某人找到，这个人也因此得到抽彩所中的奖金，这样便确保了结果会有迅速而正确的报告，且也有助于带有破译芯片的收音机和电视机的销售。

    如果中国每个成年男人、妇女和小孩都拥有一台这样的收音机或电视机，那么56比特算法的正确密钥在61秒内可找到。如果仅仅十分之一的中国人拥有收音机或电视机——这更接近于现实——正确的密钥将在10分钟内找到。64比特算法的密钥将在4.3小时内找到。——如果百分之一的人拥有收音机或电视机的话要43小时。

    为了使得攻击能付诸实际，要求进行一些修改。首先，使每块芯片测试随机的密钥，而不是唯一的一组密钥将会更加容易，这样将使攻击减慢大约39%左右——从目前我们正处理的数字来看这并不算多。如果每一个人都在测试中，最后，有人就在其“发现密钥”的灯灭了时要打电话通报这个结果，然后读出出现在他们屏幕上的一串数字。

    表7.2显示了中国式抽彩对不同国家和不同长度密钥的有效性。中国显然是最有利于实施这种攻击的地方，但他们不得不使每一个人都拥有电视机或收音机。美国人数较少，但有多得多的设备。怀俄明州能够在不到一天之内破译一个56比特的密钥。

表7.2  使用中国式抽彩的穷举攻击估计

(所有数据摘自《1995 World Almanac and Book of Facts》)

    生物工程技术

    如果生物芯片是可能的，那么不用它作为分布式的穷举攻击密码分析工具将是愚蠢的，考虑一种假想的动物；很不幸地称它为“DESosaur”[1278]，它由能够检验可能密钥的生物细胞组成，这些生物细胞可以通过光学通道接收明文/密文对（细胞是透明的你可以看见）。而密钥解则通过生物体内的特殊细胞经由循环系统送到DESosaur的发音器官。

    典型的恐龙古生物具有10¹⁴个细胞（包括细菌），如果它们每秒能完成一百万次加密（应该承认，这是一个大的假设），破译一个56比特的密钥需要一万分之七秒，破译一个64比特的密钥少于十分之二秒的时间。但破译一个128比特的密钥仍需10¹¹年。

    另一种生物方法是利用遗传密码分析海藻，它能够完成对密码算法的穷举攻击[1278]。这些生物体使制造多处理器的分布式机器成为可能，因为他们能够覆盖很大的区域。每个明/密文对可通过卫星广播，如果一个生物体找到了结果，它附近的细胞将改变颜色并把结果传回卫星。

    假设典型的海藻细胞大小为10立方微米（这或许是一个大的估计），那么10¹⁵个可占据一立方米，把它们放入海洋，覆盖深一米的200平方英里（518平方公里）的海水（你可以考虑怎样做到这点——我只是出主意的人），这样将有10²³（超过一千亿加仑）个海藻飘浮在海洋中（超过了一千亿加仑的石油）。如果它们中的每一个每秒能够尝试一百万个密钥，那么它们得花超过100年的时间才能破译128比特的密钥（让海藻的处于繁荣期是一个问题），不管海藻处理速度、海藻直径、或者甚至能够在海洋中的扩散区域的大小，其中任何一个取得突破，都将有效地减少这些数字。

    请不要问我有关纳米工艺的问题。

    热力学的局限性

    热力学第二定律的结论是：信息的表达需要一定的能量。通过改变系统的状态，记录单独的1比特所需要的能量不少于kT，其中T表示系统的绝对温度，k是Boltzman常数。（依靠我，物理课程几乎就结束了。）

    假定k=1.38*10^-16erg/^。Kelvin，宇宙的环境温度为3.2K，那么在此温度下运行的计算机每设置或清除1比特将消耗4.4*10^-16erg的能量。在比宇宙辐射温度低的环境中运行一台计算机会需要附加的能量来运行热泵。

    目前，太阳每年辐射出的能量约为1.21*10⁴¹erg。这一能量足以使理想的计算机上的2.7*10⁵⁶个单独比特发生改变，也足使一个187比特计算器中的所有状态值发生改变。如果绕太阳建造一个Dyson球，并且让它一点也不少地吸收32年的能量，那么我们就能使一台计算机的能量增加到2¹⁹²。当然，它不会让能量剩余，以便计算器完成任何有用的计算。

    但是，这仅仅是一颗星体，所有星体中很渺小的一颗。一颗典型的超新星释放的能量可达10⁵¹erg。（约是能量以微中子形式释放的一百倍，还得现在就开始。）如果所有的这些能量被全部用以运算，那么一个219比特的计算器会循环其所有的状态值。

    这些数字与设备的技术性能无关，它只是热力学允许的最大值。所以，我们可以断言：对256-比特的密钥进行穷举攻击是绝对行不通的，除非在超空间里用超物质制造计算机。